给定一个长度为 $$$2^n$$$ 的数组。数组的元素编号从 $$$1$$$ 到 $$$2^n$$$。
您必须处理对此数组的 $$$q$$$ 查询。在第 $$$i$$$ 查询中,您将获得一个整数 $$$k$$$ ($$$0 \le k \le n-1$$$)。要处理查询,您应该执行以下操作:
- 对于 [1, 2^n-2^k]$$$ 中的每个 $$$i \in 按升序排列,执行以下操作:如果在此查询期间第 $$$i$$$ 元素已与其他元素交换,则跳过它;否则,交换 $$$a_i$$$ 和 $$$a_{i+2^k}$$$;
- 之后,打印数组的所有连续子段(包括空子段)的最大总和。
例如,如果数组 $$$a$$$ 为 $$$[-3, 5, -3, 2, 8, -20, 6, -1]$$$,且 $$$k = 1$$$,则查询处理如下:
- $$$1$$$-st 元素尚未交换,因此我们将其与 $$$3$$$-rd 元素交换;
- $$$2$$$-nd 元素尚未交换,因此我们将其与 $$$4$$$-th 元素交换;
- $$$3$$$-rd 元素已被交换;
- 第 $$$4$$$ 个元素已被交换;
- 第 $$$5$$$ 个元素尚未交换,因此我们将其与第 $$$7$$$ 个元素交换;
- 第 $$$6$$$ 个元素尚未交换,因此我们将其与第 $$$8$$$ 个元素交换。
因此,数组变为 $$$[-3, 2, -3, 5, 6, -1, 8, -20]$$$。总和最大的子段是$$$[5, 6, -1, 8]$$$,查询的答案是$$$18$$$。
请注意,查询实际上更改了数组,即。 e.执行查询后,数组不会返回到其原始状态,下一次查询将应用于修改后的数组。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 18$$$)。
第二行包含 $$$2^n$$$ 整数 $$$a_1, a_2, \dots, a_{2^n}$$$ ($$$-10^9 \le a_i \le 10^9$$$)。
第三行包含一个整数$$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$)。
接下来是 $$$q$$$ 行,其中第 $$$i$$$ 行包含一个整数 $$$k$$$ ($$$0 \le k \le n-1$$$) 描述第 $$$i$$$ 查询。
输出
对于每个查询,打印一个整数 - 处理查询后数组的所有连续子段(包括空子段)的最大总和。
示例
输入 #1
3 -3 5 -3 2 8 -20 6 -1 3 1 0 1
输出 #1
18 8 13
注意
示例中数组的转换: $$$[-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]$$$。