#P18281. Knapsack
Knapsack
Knapsack
独立地从整数区间 中均匀随机生成 个整数 。
对于每个整数,你可以将它丢弃,或者将它放入集合 、、 中的一个。你需要使三个集合中的整数之和完全相等。
三个集合都必须至少包含一个整数。若存在多种方案,可以输出其中任意一种。保证所有测试数据均存在合法方案。
输入格式
第一行包含一个整数 ,表示整数的个数。,唯一的样例例外,其 。
第二行包含 个整数 ,满足 。
除样例外,所有测试的 都等于 ,且各个 按上述均匀分布独立生成。
输出格式
输出一个由 个字符组成的字符串,第 个字符说明第 个整数的去向:
.:丢弃;A、B或C:放入对应的集合。
每个整数只能作上述一种选择,三个集合均须非空,且三个整数和必须精确相等。
样例
6
4 3 8 1 5 4
ABC.BA
此方案的三个集合之和均为 。