Задан массив длины \(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\).
Обратите внимание, что запросы изменяют массив, т. е. после выполнения запроса массив не возвращается в изначальное состояние, и следующий запрос будет применен к измененному массиву.
Выходные данные
На каждый запрос выведите одно целое число — наибольшую сумму среди всех непрерывных подотрезков массива (включая пустой подотрезок) после обработки запроса.
Примечание
Преобразование массива в примере: \([-3, 5, -3, 2, 8, -20, 6, -1] \rightarrow [-3, 2, -3, 5, 6, -1, 8, -20] \rightarrow [2, -3, 5, -3, -1, 6, -20, 8] \rightarrow [5, -3, 2, -3, -20, 8, -1, 6]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1
|
18
8
13
|