给定一个大小恰好为 $2^h-1$ 的大根堆, 节点编号依次为 $1 \sim 2^h-1$。$i$ 号节点的父亲为 $\lfloor i/2 \rfloor$。$i$ 号结点的权值恰好为 $a_i$，保证 $a_i$ 为正数且互不相同。你可以对这个堆进行若干次操作，每一次操作会给定一个下标 $i(1 \le i < 2^h)$。你需要保证执行的该操作时候 $a_i$ 非 $0$。每一次操作具体内容如下：
- 执行 $a_i = 0$。
- 执行如下操作, 直到 $2i \ge 2^h$:
- 如果 $a_{2i} < a_{2i+1}$, 则交换 $a_i$ 和 $a_{2i+1}$ 的值, 之后执行 $i=2i+1$。
- 否则交换 $a_i$ 和 $a_{2i}$ 的值, 之后执行 $i=2i$。
- 换而言之，你可以理解为将堆中元素 $a_i$ 置为 $0$ 后, 从节点 $i$ 开始模拟的一次 SiftDown 过程, 使得其仍然满足大根堆性质。
给定一个集合 $S \subseteq \{1, 2, \cdots, 2^h-1\}$, 你需要执行上述操作若干次，使得经过上述操作后满足对于任意 $i \in S$, $a_i \neq 0$ 。在满足上述要求的前提下, 你希望最小化 $\sum\limits_{i=1}^{2^h-1} a_i$ 的值。你只需要输出最小值即可。
---- 题目来源：北京大学2023年秋季学期 《数据结构与算法A(实验班)》期末上机测试 Problem 4
小 Z 在复习期末考试题目的时候看到了这道题。作为熟练的竞赛选手小 Z 很快发现了这道题目的关键性质：在满足对于任意 $i \in S$, $a_i \neq 0$ 的前提下，最小化 $\sum\limits_{i=1}^{2^h-1} a_i$ 的值最终操作结果(也就是经过若干次操作的堆)唯一!，并迅速解决掉了这道题目。
在解决这道题目之后，小 Z 觉得这题还能够继续加强，于是给出了如下的修改版本：
给定集合 $S_1,S_2 \subseteq \{1, 2, \cdots, 2^h-1\}$, 初始 $S_1 = S_2 = \emptyset$。你需要支持如下询问：
- $1\ x\ y(y \in \{1, 2\}, 1 \le x < 2^h)$: $S_y = S_y \cup \{x\}$. 保证 $x \not \in S_y$，保证操作后 $S_1 \cap S_2 = \emptyset$。
- $2\ x\ y(y \in \{1, 2\}, 1 \le x < 2^h)$: $S_y = S_y - \{x\}$. 保证 $x \in S_y$，保证操作后 $S_1 \cap S_2 = \emptyset$。
- $3\ x\ z(1 \le x < 2^h, 1 \le z \le 10^6)$: 对于所有 $S_1 \subseteq S \subseteq (S_1 \cup S_2)$, 询问有多少个不同的 $S$，使得存在一种操作方案，满足如下性质:
- A. 经过上述操作后满足对于任意 $i \in S$, $a_i \neq 0$。
- B. 在满足条件 A 的情况下，$\sum\limits_{i=1}^{2^h-1} a_i$ 最小。这里我们不加证明的给出：在满足条件 A 的情况下，最小化 $\sum\limits_{i=1}^{2^h-1} a_i$ 的值的最终操作结果(也就是经过若干次操作的堆)唯一!
- C. 在满足条件 B 的情况下，经过上述操作后，满足 $a_x = z$。
输入格式
第一行一个正整数 $h$ 表示堆的大小。
第二行，一行 $2^h-1$ 个数字，第 $i$ 个数字表示 $a_i$。保证 $a_i$ 互不相同，且满足大根堆性质。
第三行一个正整数 $Q$ 表示询问次数。
接下来 $Q$ 行，一行三个正整数，表示一次询问。
输出格式
对于所有的询问 $3$，一行一个正整数表示答案。由于答案非常大，你只需要输出其对 $1,000,000,007(10^9+7)$ 取模后的结果即可。
样例数据
样例输入
2
3 2 1
11
1 1 2
1 2 2
1 3 2
3 1 3
3 1 2
3 1 1
2 1 2
1 1 1
3 1 3
3 1 2
3 1 1样例输出
4
2
1
2
1
1子任务
Subtask 1($10\%$): $h \le 2, Q \le 50$。
Subtask 2($10\%$): $h \le 4, Q \le 500$。
Subtask 3($20\%$): $h \le 9, Q \le 5000$, 保证对于操作 $1, 2$, $y = 1$。
Subtask 4($20\%$): $h \le 9, Q \le 5000$
Subtask 5($20\%$): 保证对于操作 $1, 2$, $y = 1$。
Subtask 6($20\%$): 无特殊性质。
对于所有测试数据，满足: $1 \le h \le 18, 1 \le Q \le 5 \times 10^5, 1 \le a_i \le 10^6$。