E. Swap and Maximum Blocktime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given an array of length 2^n. The elements of the array are numbered from 1 to 2^n.You have to process q queries to this array. In the i-th query, you will be given an integer k (0 \le k \le n-1). To process the query, you should do the following:  for every i \in [1, 2^n-2^k] in ascending order, do the following: if the i-th element was already swapped with some other element during this query, skip it; otherwise, swap a_i and a_{i+2^k};  after that, print the maximum sum over all contiguous subsegments of the array (including the empty subsegment). For example, if the array a is [-3, 5, -3, 2, 8, -20, 6, -1], and k = 1, the query is processed as follows:  the 1-st element wasn't swapped yet, so we swap it with the 3-rd element;  the 2-nd element wasn't swapped yet, so we swap it with the 4-th element;  the 3-rd element was swapped already;  the 4-th element was swapped already;  the 5-th element wasn't swapped yet, so we swap it with the 7-th element;  the 6-th element wasn't swapped yet, so we swap it with the 8-th element. So, the array becomes [-3, 2, -3, 5, 6, -1, 8, -20]. The subsegment with the maximum sum is [5, 6, -1, 8], and the answer to the query is 18.Note that the queries actually change the array, i. e. after a query is performed, the array does not return to its original state, and the next query will be applied to the modified array.InputThe first line contains one integer n (1 \le n \le 18).The second line contains 2^n integers a_1, a_2, \dots, a_{2^n} (-10^9 \le a_i \le 10^9).The third line contains one integer q (1 \le q \le 2 \cdot 10^5).Then q lines follow, the i-th of them contains one integer k (0 \le k \le n-1) describing the i-th query.OutputFor each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.ExampleInput
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1
Output
18
8
13
NoteTransformation of the array in the example: [-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].
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1

18 8 13 
['bitmasks', 'data structures', 'dfs and similar', 'divide and conquer', 'dp', '*2500']