{"raw_statement":[{"iden":"background","content":"小 S 共有 $n$ 只可爱的喵喵，第 $i$ 只喵喵有可爱度 $a_i$。小 S 想要把他的喵喵分成两组。考虑到小 S 的喵喵不像某些喵喵有九条命，他的喵喵只有一条，于是一只喵喵不能被同时分到两组内（请不要试图想象这个画面）。同时，如果一只喵喵没有被分到任意一组，他就会十分生气，很有可能导致小 S 失眠。\n\n当然，小 S 也希望两组的**组可爱度**相等。即存在一个正整数 $x$，使得其中一组的 $\\gcd(x, a_i)$ 之和等于另一组的 $\\gcd(x, a_i)$ 之和。请你判断是否可以使得小 S 可以将喵喵分成两组，并可以找出一个 $x$ 使得两组的**组可爱度**相等。"},{"iden":"statement","content":"给定正整数 $n$ 及长度为 $n$ 的正整数序列 $a$，请你将 $a$ 划分为两个集合 $B, C$ 并给出正整数 $x$，使得 $\\sum_{y\\in B}\\gcd(x,y) = \\sum_{y\\in C}\\gcd(x,y)$。如果无解，输出 $-1$。\n\n你需要保证 $1 \\leq x \\leq 10^9$，保证在本题的数据约束下若有解则总有 $x \\leq 10^9$ 的解。"},{"iden":"input","content":"第一行一个正整数 $n$。\n\n接下来一行为 $n$ 个正整数，其中第 $i$ 个表示 $a_i$。"},{"iden":"output","content":"如无解，仅输出一行一个整数 $-1$。否则：\n\n第一行输出一个正整数 $x$。\n\n第二行输出一个长度为 $n$ 的 $\\tt 01$ 串，第 $i$ 个数为 $\\tt 0$ 代表 $a_i$ 被划分到集合 $B$ 中，为 $\\tt 1$ 代表 $a_i$ 被划分到集合 $C$ 中。"},{"iden":"note","content":"**本题采用捆绑测试。**\n\n+ Subtask 0（2 pts）：$n$ 为偶数。\n+ Subtask 1（8 pts）：$a_i$ 均为奇数。\n+ Subtask 2（15 pts）：$n \\leq 50$，$a_i \\leq 50$。\n+ Subtask 3（25 pts）：$n \\leq 10^3$，$a_i \\leq 10^3$。\n+ Subtask 4（50 pts）：无特殊限制。\n\n对于所有数据，$1 \\leq n \\leq 10^5$，$1 \\leq a_i \\leq 10^6$。"}],"translated_statement":null,"sample_group":[["3\n1 1 1","-1"],["4\n4 1 2 3","3\n0001\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}