Вадим обожает заполнять квадратные таблицы целыми числами. Но только сегодня он придумал, как делать это по кайфу! Возьмём, к примеру, таблицу размера $$$2 \times 2$$$, строки пронумерованы сверху вниз, а столбцы — слева направо. Поставим $$$1$$$ в левую верхнюю клетку, $$$2$$$ — в правую нижнюю, $$$3$$$ — в левую нижнюю и $$$4$$$ — в правую верхнюю. Большего для кайфа и не нужно!
К счастью для Вадима, у него есть таблица размером $$$2^n \times 2^n$$$. Он собирается заполнить её целыми числами от $$$1$$$ до $$$2^{2n}$$$ в порядке возрастания. Чтобы заполнить настолько большую таблицу, Вадим поделит её на $$$4$$$ равных квадратных таблицы, вначале заполнит левую верхнюю, затем правую нижнюю, после левую нижнюю и в конце правую верхнюю. Каждую меньшую таблицу при их заполнении он будет делить на меньшие до тех пор, пока не дойдёт до табличек размерами $$$2 \times 2$$$, которые будет заполнять в описанном выше порядке.
Сейчас Вадим в нетерпении начать заполнять таблицу, но у него есть $$$q$$$ вопросов двух видов:
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ $$$(1 \leq t \leq 10)$$$ — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке каждого набора данных дано целое число $$$n$$$, описывающее размер таблицы $$$(1 \le n \le 30)$$$.
Во второй строке каждого набора данных дано целое число $$$q$$$ — количество вопросов $$$(1 \le q \le 20\,000)$$$.
В следующих $$$q$$$ строках каждого набора данных описаны вопросы в следующих форматах:
Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$20\,000$$$.
Выведите ответы на каждый из вопросов в отдельной строке.
225-> 4 3<- 15<- 4-> 3 1-> 1 318-> 1 1-> 1 2-> 2 1-> 2 2<- 1<- 2<- 3<- 4
7 2 3 1 2 9 13 1 4 3 2 1 1 2 2 2 1 1 2
Так выглядит заполненная таблица из первого примера:
| Codeforces Round 1016 (Div. 3) |
|---|
| Закончено |
