「SWTR-8」美元巨大

小 A 有 $n$ 个 $2$ 的幂 $a_1, a_2, \cdots, a_n$。他要在这些数之间插入 $x$ 个异或运算符和 $y$ 个或运算符，组成一个表达式。保证 $x + y = n - 1$。 表达式越大，越有可能炸掉小 T 的博客。小 A 希望 **从左往右** 计算表达式时它的值最大。他想知道表达式最大可能的取值是多少，用二进制表示。他还希望你构造出这样的表达式，因为他懒得自己构造了。 若存在多组构造方案，输出任意一组。 多组测试数据。 ## Input 第一行一个整数 $S$，表示该测试点的编号。 第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如： - 第一行三个整数 $n, x, y$。 - 第二行 $n$ 个整数 $b_i$，表示 $a_i = 2 ^ {b_i}$。 ## Output 对于每组测试数据： - 第一行输出一个二进制数表示答案。**不允许有前导零**，除非答案为 $0$。 - 第二行输出一个长为 $n - 1$ 的由 `^` 和 `|` 组成的字符串，其中 $s_i = \texttt{\,\,\^{}\,\,}$ 表示 $a_i$ 与 $a_{i + 1}$ 之间的运算符为异或，$s_i = \texttt |$ 表示该运算符为或。你需要保证 `^` 的个数为 $x$，`|` 的个数为 $y$。 [samples] ## Background #### 输出不允许有前导零。 原题目名称为「美元巨大二的二的二的二的二」。 小 A 喜欢用形如 $$ \Huge 2 ^ {2 ^ {2 ^ {2 ^ {2}}}} $$ 的幂塔把小 T 的博客炸掉。 ## Note **「评分方式」** 对于每组测试数据： - 若你输出的第一行比标准答案劣，得 0 分。 - 若你输出的第一行比标准答案优，则 checker 将检查你的构造方案是否正确。若正确，则返回 `_fail`，表现为测试点 UKE；否则得 0 分。 - 否则，你输出的第一行和标准答案一样。若构造方案不正确，得 0.6 分；否则得 1 分。 每个测试点的得分为测试点内所有测试数据的得分的最小值乘以该测试点的分值。 注意，checker 能检测出你的答案比标准答案优的前提是输出完全符合格式。**一旦输出不符合格式，得 0 分**。格式限制包括但不限于： - 第一行不得输出除 `0` 和 `1` 以外的字符。 - 第二行不得输出除 `^` 和 `|` 以外的字符，且字符串长度恰为 $n - 1$。 - `^` 的个数恰为 $x$，`|` 的个数恰为 $y$。 **「数据范围与约定」** - 测试点 #1（10 points）：所有 $b_i$ 互不相等。 - 测试点 #2（20 points）：所有 $b_i$ 相等。 - 测试点 #3（30 points）：$n \leq 8$。 - 测试点 #4（25 points）：$n \leq 10 ^ 3$。 - 测试点 #5（15 points）：无特殊限制。 对于 $100\%$ 的数据： - $1\leq T\leq 20$。 - $1 \leq n \leq 2.5 \times 10 ^ 4$。 - $0 \leq x, y < n$，$x + y = n - 1$。 - $1\leq a_i < 2 ^ {2 ^ {2 ^ {2 ^ 2}}}$，即 $0\leq b_i < 65536$。 **「帮助与提示」** - 关于 [位运算](https://oi-wiki.org/math/bit/)。 - 请注意 IO 优化。 **「题目来源」** - [Sweet Round 8](https://www.luogu.com.cn/contest/73382) B - Idea & Solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。 - Tester：[chenxia25](https://www.luogu.com.cn/user/138400)。