#P18281. Knapsack

Knapsack

Knapsack

独立地从整数区间 [1,1012][1,10^{12}] 中均匀随机生成 n=104n=10^4 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

对于每个整数,你可以将它丢弃,或者将它放入集合 AA、BB、CC 中的一个。你需要使三个集合中的整数之和完全相等。

三个集合都必须至少包含一个整数。若存在多种方案,可以输出其中任意一种。保证所有测试数据均存在合法方案。

输入格式

第一行包含一个整数 nn,表示整数的个数。n=104n=10^4,唯一的样例例外,其 n=6n=6。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 1≤ai≤10121\le a_i\le10^{12}。

除样例外,所有测试的 nn 都等于 10410^4,且各个 aia_i 按上述均匀分布独立生成。

输出格式

输出一个由 nn 个字符组成的字符串,第 ii 个字符说明第 ii 个整数的去向:

  • .:丢弃;
  • A、B 或 C:放入对应的集合。

每个整数只能作上述一种选择,三个集合均须非空,且三个整数和必须精确相等。

样例

6
4 3 8 1 5 4
ABC.BA

此方案的三个集合之和均为 88。