D. 1709
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива целых чисел $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$. Гарантируется, что каждое целое число от $$$1$$$ до $$$2 \cdot n$$$ встречается ровно в одном массиве.

Вам нужно сделать некоторое количество операций (возможно, ноль), чтобы выполнялись оба следующих условия:

  • Для каждого $$$1 \leq i \lt n$$$ верно, что $$$a_i \lt a_{i + 1}$$$ и $$$b_i \lt b_{i + 1}$$$.
  • Для каждого $$$1 \leq i \leq n$$$ верно, что $$$a_i \lt b_i$$$.

Во время каждой операции вы можете сделать ровно одно из трёх следующих действий:

  1. Выбрать индекс $$$1 \leq i \lt n$$$ и поменять местами значения $$$a_i$$$ и $$$a_{i + 1}$$$.
  2. Выбрать индекс $$$1 \leq i \lt n$$$ и поменять местами значения $$$b_i$$$ и $$$b_{i + 1}$$$.
  3. Выбрать индекс $$$1 \leq i \leq n$$$ и поменять местами значения $$$a_i$$$ и $$$b_i$$$.

Вам не нужно минимизировать количество операций, но нужно, чтобы их число было не более $$$1709$$$. Найдите любую последовательность операций, чтобы выполнить оба условия.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 40$$$) — длина массивов $$$a$$$ и $$$b$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot n$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 2 \cdot n$$$).

Гарантируется, что каждое целое число от $$$1$$$ до $$$2 \cdot n$$$ встречается либо в массиве $$$a$$$, либо в массиве $$$b$$$.

Выходные данные

Для каждого набора входных данных выведите последовательность операций.

В первой строке для каждого набора входных данных выведите количество операций $$$k$$$. Обратите внимание, что $$$0 \leq k \leq 1709$$$.

В следующих $$$k$$$ строках для каждого набора входных данных выведите сами операции:

  • Если вы хотите поменять местами значения $$$a_i$$$ и $$$a_{i + 1}$$$, то выведите два целых числа $$$1$$$ и $$$i$$$. Обратите внимание, что $$$1 \leq i \lt n$$$.
  • Если вы хотите поменять местами значения $$$b_i$$$ и $$$b_{i + 1}$$$, то выведите два целых числа $$$2$$$ и $$$i$$$. Обратите внимание, что $$$1 \leq i \lt n$$$.
  • Если вы хотите поменять местами значения $$$a_i$$$ и $$$b_i$$$, то выведите два целых числа $$$3$$$ и $$$i$$$. Обратите внимание, что $$$1 \leq i \leq n$$$.

Можно показать, что при данных ограничениях ответ всегда существует.

Пример
Входные данные
6
1
1
2
1
2
1
2
1 3
4 2
2
1 4
3 2
3
6 5 4
3 2 1
3
5 3 4
2 6 1
Выходные данные
0
1
3 1
1
2 1
1
3 2
9
3 1
3 2
3 3
1 1
2 1
2 2
1 2
1 1
2 1
6
2 2
1 1
1 2
2 1
3 1
3 2
Примечание

В первом наборе входных данных $$$a_1 \lt b_1$$$, поэтому можно не применять операции.

Во втором наборе входных данных $$$a_1 \gt b_1$$$. После применения операции эти значения поменяются местами.

В третьем наборе входных данных после применения операции $$$a = [1, 3]$$$ и $$$b = [2, 4]$$$.

В четвёртом наборе входных данных после применения операции $$$a = [1, 2]$$$ и $$$b = [3, 4]$$$.