Дан массив $$$x_1, x_2, \ldots, x_{2^k}$$$ из попарно различных целых чисел. Построим над ним дерево отрезков: в листьях (слой $$$0$$$) записаны числа $$$x_1, x_2, \ldots, x_{2^k}$$$ в этом порядке, а слой $$$i$$$ ($$$1 \le i \le k$$$) состоит из $$$2^{k-i}$$$ вершин, $$$j$$$-я из которых — родитель вершин $$$2j-1$$$ и $$$2j$$$ слоя $$$i-1$$$.
Значения в вершинах слоёв $$$1, 2, \ldots, k$$$ задаются строкой $$$s = s_1 s_2 \ldots s_k$$$ из букв a и b: если $$$s_i = \texttt{a}$$$, то в каждой вершине $$$i$$$-го слоя записан минимум из значений двух её сыновей, а если $$$s_i = \texttt{b}$$$ — максимум. Таким образом, тип каждого слоя выбирается независимо, но все вершины одного слоя имеют один и тот же тип.
Скажем, что строка $$$s$$$ реализует значение $$$v$$$, если в корне (единственной вершине слоя $$$k$$$) построенного по строке $$$s$$$ дерева записано число $$$v$$$.
Поступают $$$q$$$ запросов. В $$$i$$$-м запросе значение $$$x_{p_i}$$$ заменяется на $$$y_i$$$, после чего требуется вывести строку $$$s$$$, которая реализует значение $$$y_i$$$ для текущего массива. Можно показать, что такая строка всегда существует.
Гарантируется, что в любой момент все числа массива $$$x$$$ попарно различны.
В первой строке задано целое число $$$k$$$ ($$$1 \le k \le 20$$$).
Во второй строке заданы $$$2^k$$$ попарно различных целых чисел $$$x_1, x_2, \ldots, x_{2^k}$$$ ($$$1 \le x_i \le 2 \cdot 10^6$$$).
В третьей строке задано целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.
В каждой из следующих $$$q$$$ строк заданы два целых числа $$$p_i$$$ и $$$y_i$$$ ($$$1 \le p_i \le 2^k$$$, $$$1 \le y_i \le 2 \cdot 10^6$$$). Гарантируется, что после замены $$$x_{p_i}$$$ на $$$y_i$$$ все числа массива по-прежнему попарно различны (в частности, $$$y_i$$$ может совпадать с прежним значением $$$x_{p_i}$$$).
Для каждого запроса выведите в отдельной строке строку длины $$$k$$$ из букв a и b, которая реализует значение $$$y_i$$$ после выполнения этого запроса.
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
На рисунке показано дерево из первого примера после первого запроса: массив равен $$$[9, 8, 2, 7, 3, 10, 6, 4]$$$, а строка bba задаёт слои $$$\max$$$, $$$\max$$$, $$$\min$$$. В корне оказывается число $$$9$$$.
Во втором примере после первого запроса массив равен $$$[5, 2, 7, 4]$$$. Для строки ba первый слой берёт максимумы: $$$\max(5, 2) = 5$$$, $$$\max(7, 4) = 7$$$, а второй слой — минимум: $$$\min(5, 7) = 5$$$. После второго запроса массив равен $$$[5, 2, 7, 3]$$$, и строка ab даёт $$$\max(\min(5, 2), \min(7, 3)) = \max(2, 3) = 3$$$. После третьего запроса массив равен $$$[5, 2, 1, 3]$$$, и строка aa даёт $$$\min(\min(5, 2), \min(1, 3)) = 1$$$.
| Название |
|---|


