Задан массив длины $$$2^n$$$. Элементы массива пронумерованы от $$$1$$$ до $$$2^n$$$.

Надо обработать $$$q$$$ запросов к массиву. В $$$i$$$-м запросе будет дано целое число $$$k$$$ ($$$0 \le k \le n-1$$$). Чтобы обработать запрос, надо сделать следующее:

• для каждого $$$i \in [1, 2^n-2^k]$$$ в возрастающем порядке сделайте следующее: если $$$i$$$-й элемент уже менялся местами с каким-либо другим элементов в текущем запросе, пропустите его; иначе поменяйте местами $$$a_i$$$ и $$$a_{i+2^k}$$$;
• после этого выведите наибольшую сумму среди всех непрерывных подотрезков массива (включая пустой подотрезок).

Например, если массив $$$a$$$ равен $$$[-3, 5, -3, 2, 8, -20, 6, -1]$$$, а $$$k = 1$$$, то запрос обрабатывается так:

• $$$1$$$-й элемент еще не менялся ни с кем местами, поэтому поменяем его местами с $$$3$$$-м элементом;
• $$$2$$$-й элемент еще не менялся ни с кем местами, поэтому поменяем его местами с $$$4$$$-м элементом;
• $$$3$$$-й элемент уже менялся местами;
• $$$4$$$-й элемент уже менялся местами;
• $$$5$$$-й элемент еще не менялся ни с кем местами, поэтому поменяем его местами с $$$7$$$-м элементом;
• $$$6$$$-й элемент еще не менялся ни с кем местами, поэтому поменяем его местами с $$$8$$$-м элементом.

Тогда массив становится равен $$$[-3, 2, -3, 5, 6, -1, 8, -20]$$$. Подотрезок с максимальной суммой — это $$$[5, 6, -1, 8]$$$, и ответ на запрос равен $$$18$$$.

Обратите внимание, что запросы изменяют массив, т. е. после выполнения запроса массив не возвращается в изначальное состояние, и следующий запрос будет применен к измененному массиву.