I. Минимакс
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$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$$$ после выполнения этого запроса.

Примеры
Входные данные
3
5 8 2 7 3 10 6 4
4
1 9
8 1
3 5
6 2
Выходные данные
bba
aaa
aab
aba
Входные данные
2
6 2 7 4
3
1 5
4 3
3 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$$$.