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.
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}$$$).
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.
35 8 2 7 3 10 6 441 98 13 56 2
bba aaa aab aba
26 2 7 431 54 33 1
ba ab aa
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$$$.