E. Power или XOR?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Символ $$$\wedge$$$ довольно неоднозначный, особенно когда используется без контекста. Иногда используется для обозначения возведения в степень ($$$a\wedge b = a^b$$$), а иногда используется для обозначения операции побитового исключающего ИЛИ ($$$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$$$.

Вам дан массив $$$B$$$ длины $$$n$$$ и целое число $$$k$$$. Массив $$$A$$$ получается как $$$A_i=2^{B_i}$$$ и выражение $$$E$$$ получается как $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$. Вам нужно найти XOR значений всех возможных однозначных выражений $$$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$$$.

Примеры
Входные данные
3 2
3 1 2
Выходные данные
1110
Входные данные
3 1
3 1 2
Выходные данные
1010010
Входные данные
3 0
3 1 2
Выходные данные
1000000000000000001010010
Входные данные
2 1
1 1
Выходные данные
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$$$
XOR всех их значений равен $$$14\oplus 68\oplus 24 = 82 = (1010010)_2$$$.

Во третьем примере существуют четыре возможные подходящие однозначные выражения $$$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$$$
XOR всех их значений равен $$$14\oplus 68\oplus 24\oplus 16777216 = 16777298 = (1000000000000000001010010)_2$$$.

В четвёртом примере $$$A=\{2,2\}$$$ и $$$E=2\wedge 2$$$. Единственное возможное подходящее однозначное выражение $$$E' = 2\oplus 2 = 0 = (0)_2$$$.