Маомао и Джинши решили сыграть в игру. Ставки простые: ей нужны очередные экзотические яды для экспериментов, ему просто весело проводить с ней время. Разве что, чтобы не привлекать внимание эксцентричного стратега Лакана, они придумали свою игру, непохожую ни на го, ни на сёги.
Для игры у них есть массив длины $$$n$$$, состоящий из $$$x$$$-битных чисел $$$a_1, a_2, \ldots a_n$$$. Маомао и Джинши ходят по очереди, причём первой ходит Маомао.
За один ход игрок выбирает непустой подотрезок $$$[l, r]$$$ ($$$l \leq r$$$) массива $$$a$$$ и заменяет каждое число на этом подотрезке на его побитовую инверсию. Формально, для всех $$$l \leq i \leq r$$$ выполняется операция $$$$$$a_i \gets (2^x - 1) - a_i \text{.}$$$$$$
Красотой массива $$$a$$$ назовём сумму всех его элементов. Цели у игроков разные: Маомао хочет максимизировать красоту массива, а Джинши — минимизировать. Они договорились сделать ровно $$$k$$$ ходов суммарно, строго по очереди (таким образом, если $$$k$$$ нечетно, то последний ход будет за Маомао, а если четно, то за Джинши).
Определите, чему будет равна красота массива после завершения игры, если оба игрока действуют оптимально.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ — количество наборов входных данных ($$$1 \leq t \leq 5\,000$$$). Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержатся три целых числа $$$n$$$, $$$x$$$ и $$$k$$$ — длина массива, битность чисел и количество ходов в игре соответственно ($$$n \leq 50\,000$$$; $$$1 \leq x \leq 10$$$; $$$k \leq 10^{12}$$$).
Во второй строке перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы массива ($$$0 \leq a_i \lt 2^x$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$50\,000$$$.
Для каждого набора входных данных в отдельной строке выведите одно целое число — красоту массива в конце игры, если оба игрока играют оптимально.
Баллы за подзадачи начисляются только в случае, если все тесты соответствующей подзадачи и необходимых подзадач успешно пройдены.
Ниже за $$$N$$$ обозначена сумма $$$n$$$ по всем наборам входных данных в одном тесте.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке | |
| 0 | – | примеры из условия | полная | ||
| 1 | 5 | $$$t \leq 5$$$; $$$n \leq 5$$$; $$$k \leq 4$$$ | первая ошибка | ||
| 2 | 7 | $$$t \leq 5$$$; $$$n \leq 12$$$; $$$k \leq 10$$$ | 1 | первая ошибка | |
| 3 | 3 | $$$k \leq 2$$$; $$$N \leq 10$$$ | первая ошибка | ||
| 4 | 3 | $$$k \leq 2$$$; $$$N \leq 50$$$ | 3 | первая ошибка | |
| 5 | 4 | $$$k \leq 2$$$; $$$N \leq 300$$$ | 3, 4 | первая ошибка | |
| 6 | 8 | $$$k \leq 2$$$; $$$N \leq 5\,000$$$ | 3 – 5 | первая ошибка | |
| 7 | 2 | $$$k = 1$$$; $$$N \leq 100$$$ | первая ошибка | ||
| 8 | 3 | $$$k = 1$$$; $$$N \leq 2000$$$ | 7 | первая ошибка | |
| 9 | 5 | $$$k = 1$$$ | 7, 8 | первая ошибка | |
| 10 | 4 | все $$$a_i$$$ равны | первая ошибка | ||
| 11 | 5 | $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$; $$$N \leq 2000$$$ | первая ошибка | ||
| 12 | 5 | $$$a_{2i} + a_{2i+1} = 2^{x}-1$$$ для всех $$$i$$$; $$$a_i = a_{i+2}$$$ для всех $$$i$$$ | первая ошибка | ||
| 13 | 7 | число позиций $$$i$$$, для которых $$$a_i \neq a_{i+1}$$$, не превосходит $$$20$$$ | первая ошибка | ||
| 14 | 4 | $$$a_i | lt; 2^{x - 1}$$$ для всех $$$i$$$ | первая ошибка | |
| 15 | 13 | $$$N \leq 500$$$ | 0 – 5, 7 | первая ошибка | |
| 16 | 7 | $$$N \leq 3\,000$$$ | 0 – 5, 7, 8, 11, 15 | первая ошибка | |
| 17 | 6 | $$$N \leq 10\,000$$$ | 0 – 8, 11, 15, 16 | первая ошибка | |
| 18 | 9 | нет | 0 – 17 | первая ошибка |
65 3 10 7 1 6 36 3 17 7 0 0 7 75 3 10 0 0 0 05 3 22 5 1 6 05 3 20 7 1 6 36 4 320 15 0 15 0 15
244235141230
В первом наборе входных данных Маомао достаточно инвертировать подотрезок $$$[1, 1]$$$. Тогда массив $$$[0, 7, 1, 6, 3]$$$ превратится в $$$[7, 7, 1, 6, 3]$$$, и его красота станет равна $$$7 + 7 + 1 + 6 + 3 = 24$$$.
В четвёртом наборе входных данных оптимальная игра может выглядеть так: сначала Маомао инвертирует весь массив, то есть выбирает подотрезок $$$[1, 5]$$$. После этого массив $$$[2, 5, 1, 6, 0]$$$ станет равен $$$[5, 2, 6, 1, 7]$$$. Затем Джинши инвертирует подотрезок $$$[3, 5]$$$ и получает массив $$$[5, 2, 1, 6, 0]$$$, красота которого равна $$$5 + 2 + 1 + 6 + 0 = 14$$$. Большее значение Маомао гарантировать не может, поэтому ответ равен $$$14$$$.