QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4984. 集合划分

Statistics

小 B、小 Y 和小 Z 是形影不离的好朋友,同时也是坚定的共产主义者。

这天,他们得到了 $n$ 块蛋糕,第 $i$ 块重量是 $a_i$. 蛋糕不能切开,只能整块地分给某一个人;蛋糕更不能浪费,即每块蛋糕都应归于三个人中的一个。

他们都具有大公无私的奉献精神,因此毫不在意自己分到的蛋糕重量比其他人小;但本着“主义高于友谊”的原则,他们必须保证任何两个人分到的蛋糕重量之和都严格大于第三个人,否则分到重量最小的两个人就会联合起来把旧世界打个落花流水。

由于生产力过度发达,蛋糕的数量和重量都已经远远超出他们的人脑计算能力,于是他们前来请教掌握计算机技术的你,希望你能为他们给出一组合理的分配方案,或确定该方案不存在。

输入格式

输入共包含两行

第一行输入一个正整数 $n$.

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n$.

输出格式

若不存在合法的分配方案,输出 Internationale!.

若存在,则输出一个长度为 $n$ 的字符串,每个字符均为 BYZ 中的一个,第 $i$ 个字符代表第 $i$ 块蛋糕的归属。

若有多组合法方案,给出任意一组即可。

样例数据

样例 1 输入

6
7 5 4 1 2 8

样例 1 输出

ZYBZYB

样例 2 输入

5
1 2 6 1 1

样例 2 输出

Internationale!

子任务

本题采用子任务评测。你必须通过一个子任务内的全部测试点,才能获得对应的分数。

对于全部数据,$3\le n\le 2\times 10^5,\ 1\le a_i\le 10^9$.

子任务 1($10$ 分):保证 $n=3$.

子任务 2($16$ 分):保证 $n\le 16$.

子任务 3($16$ 分):保证 $n\le 10^3,a_i\le n$.

子任务 4($28$ 分):保证存在合法解。

子任务 5($30$ 分):无特殊限制。