Given a max-heap of size exactly $2^h-1$, with nodes numbered $1$ to $2^h-1$. The parent of node $i$ is $\lfloor i/2 \rfloor$. The value of node $i$ is $a_i$, where all $a_i$ are distinct positive integers.

You can perform several operations on this heap. Each operation is given by an index $i$ ($1 \le i < 2^h$). You must ensure that $a_i \neq 0$ when performing the operation. The operation is defined as follows:

• Set $a_i = 0$.
• Perform the following steps until $2i \ge 2^h$:
  • If $a_{2i} < a_{2i+1}$, swap $a_i$ and $a_{2i+1}$, then set $i = 2i+1$.
  • Otherwise, swap $a_i$ and $a_{2i}$, then set $i = 2i$.
• In other words, you can think of this as setting the element $a_i$ to $0$ and then simulating a SiftDown process starting from node $i$ to maintain the max-heap property.

Given a set $S \subseteq \{1, 2, \cdots, 2^h-1\}$, you need to perform the above operations several times such that after the operations, $a_i \neq 0$ for all $i \in S$. Under this requirement, you want to minimize the value of $\sum\limits_{i=1}^{2^h-1} a_i$. You only need to output the minimum value.

Xiao Z noticed a key property of this problem: Under the condition that $a_i \neq 0$ for all $i \in S$, the final state of the heap that minimizes $\sum\limits_{i=1}^{2^h-1} a_i$ is unique!

After solving this, Xiao Z proposed a modified version:

Given sets $S_1, S_2 \subseteq \{1, 2, \cdots, 2^h-1\}$, initially $S_1 = S_2 = \emptyset$. You need to support the following queries:

• $1\ x\ y$ ($y \in \{1, 2\}, 1 \le x < 2^h$): $S_y = S_y \cup \{x\}$. It is guaranteed that $x \notin S_y$ and that $S_1 \cap S_2 = \emptyset$ after the operation.
• $2\ x\ y$ ($y \in \{1, 2\}, 1 \le x < 2^h$): $S_y = S_y - \{x\}$. It is guaranteed that $x \in S_y$ and that $S_1 \cap S_2 = \emptyset$ after the operation.
• $3\ x\ z$ ($1 \le x < 2^h, 1 \le z \le 10^6$): For all $S$ such that $S_1 \subseteq S \subseteq (S_1 \cup S_2)$, count how many different sets $S$ exist such that there is an operation sequence satisfying:
  • A. After the operations, $a_i \neq 0$ for all $i \in S$.
  • B. Under condition A, $\sum\limits_{i=1}^{2^h-1} a_i$ is minimized. (The final heap state is unique).
  • C. Under condition B, after the operations, $a_x = z$.

Input

The first line contains a positive integer $h$ representing the size of the heap.

The second line contains $2^h-1$ integers, where the $i$-th integer is $a_i$. It is guaranteed that all $a_i$ are distinct and satisfy the max-heap property.

The third line contains a positive integer $Q$ representing the number of queries.

The next $Q$ lines each contain three positive integers representing a query.

Output

For each query of type $3$, output a single integer on a new line. Since the answer can be very large, output it modulo $1,000,000,007$ ($10^9+7$).

Examples

Input 1

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

Output 1

4
2
1
2
1
1

Subtasks

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$, guaranteed that for operations $1$ and $2$, $y = 1$.

Subtask 4 ($20\%$): $h \le 9, Q \le 5000$.

Subtask 5 ($20\%$): Guaranteed that for operations $1$ and $2$, $y = 1$.

Subtask 6 ($20\%$): No special properties.

For all test cases: $1 \le h \le 18, 1 \le Q \le 5 \times 10^5, 1 \le a_i \le 10^6$.