I. Min-max segment tree
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$x_1, x_2, \ldots, x_{2^k}$$$ of pairwise distinct integers. Build a segment tree over it: the leaves (layer $$$0$$$) hold $$$x_1, x_2, \ldots, x_{2^k}$$$ in this order, and layer $$$i$$$ ($$$1 \le i \le k$$$) consists of $$$2^{k-i}$$$ nodes, the $$$j$$$-th of which is the parent of nodes $$$2j-1$$$ and $$$2j$$$ of layer $$$i-1$$$.

The values in the nodes of layers $$$1, 2, \ldots, k$$$ are defined by a string $$$s = s_1 s_2 \ldots s_k$$$ of letters a and b: if $$$s_i = \texttt{a}$$$, every node of layer $$$i$$$ holds the minimum of the values of its two children, and if $$$s_i = \texttt{b}$$$, the maximum. So the type of each layer is chosen independently, but all nodes of one layer have the same type.

We say that a string $$$s$$$ yields a value $$$v$$$ if the root (the only node of layer $$$k$$$) of the tree built for $$$s$$$ holds $$$v$$$.

There are $$$q$$$ queries. In the $$$i$$$-th query the value $$$x_{p_i}$$$ is replaced by $$$y_i$$$, and after that you have to print a string $$$s$$$ that yields $$$y_i$$$ for the current array. It can be shown that such a string always exists.

It is guaranteed that at every moment all numbers of the array $$$x$$$ are pairwise distinct.

Input

The first line contains an integer $$$k$$$ ($$$1 \le k \le 20$$$).

The second line contains $$$2^k$$$ pairwise distinct integers $$$x_1, x_2, \ldots, x_{2^k}$$$ ($$$1 \le x_i \le 2 \cdot 10^6$$$).

The third line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$p_i$$$ and $$$y_i$$$ ($$$1 \le p_i \le 2^k$$$, $$$1 \le y_i \le 2 \cdot 10^6$$$). It is guaranteed that after replacing $$$x_{p_i}$$$ by $$$y_i$$$ all numbers of the array are still pairwise distinct (in particular, $$$y_i$$$ may be equal to the previous value of $$$x_{p_i}$$$).

Output

For each query print, on a separate line, a string of length $$$k$$$ consisting of letters a and b that yields $$$y_i$$$ after this query is applied.

Examples
Input
3
5 8 2 7 3 10 6 4
4
1 9
8 1
3 5
6 2
Output
bba
aaa
aab
aba
Input
2
6 2 7 4
3
1 5
4 3
3 1
Output
ba
ab
aa
Note

The picture shows the tree of the first example after the first query: the array is $$$[9, 8, 2, 7, 3, 10, 6, 4]$$$, and the string bba makes the layers $$$\max$$$, $$$\max$$$, $$$\min$$$. The root holds $$$9 = y_1$$$; the path of this value from the leaf $$$x_1$$$ to the root is highlighted.

In the second example, the array after the first query is $$$[5, 2, 7, 4]$$$. For the string ba, the first layer takes maximums: $$$\max(5, 2) = 5$$$, $$$\max(7, 4) = 7$$$, and the second layer takes the minimum: $$$\min(5, 7) = 5$$$. After the second query, the array is $$$[5, 2, 7, 3]$$$, and the string ab gives $$$\max(\min(5, 2), \min(7, 3)) = \max(2, 3) = 3$$$. After the third query, the array is $$$[5, 2, 1, 3]$$$, and the string aa gives $$$\min(\min(5, 2), \min(1, 3)) = 1$$$.