符号 $$$\wedge$$$ 非常不明确,特别是在没有上下文的情况下使用时。有时它用于表示幂 ($$$a\wedge b = a^b$$$),有时用于表示 XOR 运算 ($$$a\wedge b=a\oplus b$$$)。
您的表达式不明确 $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$。您可以将每个 $$$\wedge$$$ 符号替换为 $$$\texttt{Power}$$$ 运算或 $$$\texttt{XOR}$$$ 运算,以获得明确的表达式 $$$E'$$$。
该表达式 $$$E'$$$ 的值根据以下规则确定:
- 所有 $$$\texttt{Power}$$$ 操作均在任何 $$$\texttt{XOR}$$$ 操作之前执行。换句话说,$$$\texttt{Power}$$$ 运算优先于 $$$\texttt{XOR}$$$ 运算。例如,$$$4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32$$$。
- 连续幂从左到右计算。例如,$$$2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096$$$。
给定一个长度为 $$$n$$$ 的数组 $$$B$$$ 和一个整数 $$$k$$$。数组 $$$A$$$ 由 $$$A_i=2^{B_i}$$$ 给出,表达式 $$$E$$$ 由 $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$ 给出。您需要找到所有可能的明确表达式 $$$E'$$$ 的值的异或,这些表达式可以从 $$$E$$$ 获得,并且至少有 $$$k$$$ $$$\wedge$$$ 符号用作 $$$\texttt{XOR}$$$ 运算。由于答案可能非常大,因此您需要对 $$$2^{2^{20}}$$$ 求模。由于该数字也可能非常大,因此您需要打印其二进制表示形式,不带前导零。如果答案等于$$$0$$$,则打印$$$0$$$。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(1\leq n\leq 2^{20}, 0\leq k < n)$$$。
输入的第二行包含 $$$n$$$ 整数 $$$B_1,B_2,\ldots,B_n$$$ $$$(1\leq B_i < 2^{20})$$$。
输出
打印包含二进制字符串的单行,不带前导零来表示问题的答案。如果答案等于$$$0$$$,则打印$$$0$$$。
示例
输入 #1
3 2 3 1 2
输出 #1
1110
输入 #2
3 1 3 1 2
输出 #2
1010010
输入 #3
3 0 3 1 2
输出 #3
1000000000000000001010010
输入#4
2 1 1 1
输出#4
0
注意
对于每个测试用例 $$$1$$$ 到 $$$3$$$,$$$A = \{2^3,2^1,2^2\} = \{8,2,4\}$$$ 和 $$$E=8\wedge 2\wedge 4$$$。
对于第一个测试用例,只有一个可能的有效明确表达式 $$$E' = 8\oplus 2\oplus 4 = 14 = (1110)_2$$$。
对于第二个测试用例,存在三个可能的有效明确表达式 $$$E'$$$:
- $$$8\oplus 2\oplus 4 = 14$$$
- $$$8^2\oplus 4 = 64\oplus 4= 68$$$
- $$$8\oplus 2^4 = 8\oplus 16= 24$$$
对于第三个测试用例,有四个可能的有效明确表达式 $$$E'$$$:
- $$$8\oplus 2\oplus 4 = 14$$$
- $$$8^2\oplus 4 = 64\oplus 4= 68$$$
- $$$8\oplus 2^4 = 8\oplus 16= 24$$$
- $$$(8^2)^4 = 64^4 = 2^{24} = 16777216$$$
对于第四个测试用例,$$$A=\{2,2\}$$$ 和 $$$E=2\wedge 2$$$。唯一可能的有效明确表达式 $$$E' = 2\oplus 2 = 0 = (0)_2$$$。