考虑一个长度为 $2^n - 1$ 的整数序列 $b = (b_1, b_2, \dots, b_{2^n - 1})$。

设 $f(b)$ 为使以下条件成立所需的最少操作次数：

• 操作：选择一个整数 $i$ 满足 $1 \le i \le 2^n - 1$，并将 $b_i$ 增加或减少 $1$。
• 条件：对于所有满足 $1 \le i \le 2^{n-1} - 1$ 的 $i$，等式 $b_i = b_{2i} + b_{2i+1}$ 必须成立。

给你一个长度为 $2^n - 1$ 的序列 $a = (a_1, a_2, \dots, a_{2^n - 1})$。处理 $q$ 次询问。对于每次询问 $i$（其中 $1 \le i \le q$）：给定整数 $x_i$ 和 $v_i$，将 $a_{x_i}$ 修改为 $v_i$，然后输出 $f(a)$。

对序列的修改在询问之间是持续生效的。例如，第二次询问处理的是先经过 $a_{x_1} \leftarrow v_1$ 修改，再经过 $a_{x_2} \leftarrow v_2$ 修改后的序列。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 18$）。

第二行包含 $2^n - 1$ 个整数：序列 $a$（$-10^9 \le a_i \le 10^9$）。

第三行包含一个整数 $q$：询问的数量（$1 \le q \le 10^5$）。

接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $v_i$：第 $i$ 次询问的参数（$1 \le x_i \le 2^n - 1$，$-10^9 \le v_i \le 10^9$）。

输出格式

输出 $q$ 行。在第 $i$ 行中，输出第 $i$ 次询问的答案。

样例

样例输入 1

3
2 3 0 1 -5 2 1
5
3 1
5 3
6 -1
5 1
1 0

样例输出 1

9
5
3
2
4