题目描述 3s 512MB

实验室里有 $2^n$ 瓶药剂，从左到右排成一行，位置编号为 $1,2,\ldots,2^n$。第 $i$ 个位置上的药剂浓度值为 $a_i$，满足 $1\le a_i\le m$。

为了准备实验，小明需要用一台特殊的机器，将这些药剂整理成浓度值从小到大的顺序。整理时，药剂始终分别装在瓶子里，合并指的是将两列药剂瓶整理为一列，不会混合瓶内的液体，也不会改变浓度值。

机器按照下面的固定规则进行整理：

1. 如果当前这一列只有一瓶药剂，就不进行任何操作，也不产生热量。
2. 否则，从正中间将这一列分成长度相同的左半列和右半列，分别按照同样的规则整理这两半。
3. 将整理好的两半合并为一列。每次比较两半最前面尚未取出的药剂，取出浓度值较小的一瓶，放到新列的末尾；如果浓度值相同，优先取左半列中的药剂。一半取完后，依次取出另一半剩余的药剂。

在每一次合并中，取出的药剂从 $1$ 开始重新计数。如果第 $k$ 个取出的药剂浓度值为 $x$，这次取出就会产生 $x\times k$ 单位的热量。即使某一半已经取完，继续取出另一半的药剂时，仍按这个规则产生热量。

整个整理过程的总热量，就是所有合并、所有取出操作产生的热量之和。

上述规则保证：浓度值相同的药剂，在本次整理开始前位置靠前的，整理后仍然靠前。

现在有 $Q$ 次操作，每次给出两个位置 $u,v$，交换这两个位置上的药剂。交换累计生效。 每次交换后，请计算：如果对当前的整列药剂执行一次上述整理过程，总共会产生多少热量？

注意：这里只计算整理过程的热量，不会实际改变药剂的排列。 后续交换仍在前面所有交换完成后的序列上进行，而不是在整理后的有序序列上进行。

输入格式

从标准输入读入数据。

第一行输入三个正整数 $n,m,Q$，分别表示序列长度为 $2^n$、浓度值的上限为 $m$，以及交换次数为 $Q$。

第二行输入 $2^n$ 个整数 $a_1,a_2,\ldots,a_{2^n}$，表示初始排列中各瓶药剂的浓度值。数值允许重复，不要求 $1$ 至 $m$ 中的每个数值都出现。

接下来 $Q$ 行，每行输入两个整数 $u,v$，表示交换位置 $u$ 和位置 $v$ 上的药剂。允许 $u=v$，这种情况下序列不变。

输出格式

输出到标准输出。

对于每次交换，输出一行一个整数，表示交换后当前序列的整理总热量。无需输出初始序列的答案。

样例输入 #1

2 4 3
1 4 2 3
2 3
1 4
1 2

样例输出 #1

46
47
47

样例解释 #1

第一次交换后，序列为 $1,2,4,3$。

• 左半列 $1,2$ 合并时，产生 $1\times1+2\times2=5$ 单位热量。
• 右半列 $4,3$ 合并后为 $3,4$，产生 $3\times1+4\times2=11$ 单位热量。
• 最后将两半合并为 $1,2,3,4$，产生 $1\times1+2\times2+3\times3+4\times4=30$ 单位热量。

所以总热量为 $5+11+30=46$。

第二次交换是在序列 $1,2,4,3$ 上进行，而不是在 $1,2,3,4$ 上进行。交换后为 $3,2,4,1$，总热量为 $47$。

第三次交换后为 $2,3,4,1$，总热量仍为 $47$。

样例输入 #2

2 3 2
2 2 2 2
1 4
2 2

样例输出 #2

32
32

样例解释 #2

两个长度为 $2$ 的合并各产生 $2\times1+2\times2=6$ 单位热量，最后一次合并产生 $2\times(1+2+3+4)=20$ 单位热量，总热量为 $32$。

样例输入 #3

1 5 2
2 5
1 2
1 2

样例输出 #3

12
12

样例解释 #3

只有一次合并，无论交换前后，取出顺序都是浓度值为 $2$、$5$ 的药剂，总热量为 $2\times1+5\times2=12$。

另提供 sample 目录中的五组下发样例：data02、data04、data08、data15、data20，依次对应下表中的五档数据。题面中的三组小样例不另行下发。

数据范围

本题共 $20$ 个测试点，每个测试点 $5$ 分，共 $100$ 分。

测试点编号	$n$ 的范围	$Q\leq$	特殊性质
$1\sim2$	$n=2$	$100$	/
$3\sim4$	$1\le n\le6$
$5\sim8$	$1\le n\le10$	$1000$
$9\sim15$	$5\le n\le17$	$10^5$	A
$16\sim20$	$1\le n\le17$		/

特殊性质 A：将序列从左到右每 $32$ 个位置划为一个固定块，即 $[1,32],[33,64],[65,96],\ldots$。每次交换的两个位置都属于同一个固定块，不同次交换可以发生在不同的块中。

表格中的“/”表示没有额外限制。

对于 $100\%$ 的数据：

$$1\le n\le17，\qquad 1\le m\le20，\qquad 1\le Q\le10^5，$$$$1\le a_i\le m，\qquad 1\le u,v\le2^n。$$

附加样例

附加文件

附件包含题面所述的 sample 目录及下发样例，不参与计分。