Ты k-ый?

У Казака Уса имеются три секретных массива $a$, $b$, $c$ из натуральных чисел. Обозначим их длины как $|a|$, $|b|$ и $|c|$ соответственно. Эти длины не обязательно одинаковы. Известно, что каждый массив отсортирован, то есть, каждый следующий элемент не меньше предыдущего.

Вы хотите получить определенную информацию об этих массивы, а именно — значение $k$ -го элемента в отсортированном объединении массивов. То есть, если из этих трех массивов сделать один большой массив длины $|a|+|b|+|c|$, отсортировать его, то следует узнать $k$ -ый элемент в таком массиве.

Казак Ус отказывается показывать Вам эти массивы. Однако он согласился на следующее: Вы можете узнавать значение определенных чисел. Вы можете выбрать определенный массив и определенную позицию в этом массиве, после чего Казак Ус сообщит Вам значение этого элемента. Обратите внимание, что Вы можете делать эту операцию много раз, не обязательно над одним и тем же массивом. Поскольку Козак — очень занятой человек, он позволил вам задать ему не более $Q$ вопросов

Вам следует узнать $k$-ый наибольший элемент в объединении массивов.

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

Первая строка содержит пять целых чисел $|a|$, $|b|$, $|c|$, $k$, $g$ ($0\le |a|,|b|,|c|\le 10^6$, $1\le k\le |a|+|b|+|c|$).

Гарантируется, что все упомянутые числа находятся в границах $[1,10^9]$.

Число $g$ ($0\le g\le 9$) — номер группы тестов (см. Оценивание).

Протокол взаимодействия

Сначала следует считать пять целых чисел $|a|$, $|b|$, $|c|$, $k$, $g$.

Чтобы сделать запрос, выведите «1 $r$ $m$». Здесь $r$ — номер массива: если $r=1$, то операция будет осуществлена над массивом $a$, если $r=2$, то над массивом $b$, если $r=3$, то над $c$. А $m$ — номер позиции в этом массиве. Если Вы, например, выполняете операцию над массивом $a$, то, чтобы получить первый элемент, нужно чтобы $m=1$, а чтобы получить последний, нужно чтобы $m=|a|$.

Пример запроса «1 3 10» — получить $10$-ое число в массиве $c$.

После вывода запроса не забудьте вывести символ новой строки и сбросить буфер вывода. В противном случае вы получите вердикт Исчерпан лимит времени. Для сброса буфера используйте:

• fflush(stdout) або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• stdout.flush() в Python;

смотрите документацию для других языков.

Обратите внимание, что если Ваш запрос недействителен (лимит запросов превышен или запрос не удовлетворяет ограничением), интерактор выведет «-1» и прекратит работу. Если вы считаете «-1», то немедленно завершите программу, чтобы получить вердикт Неверный ответ вместо произвольного вердикта.

Когда Вы найдете ответ $x$, выведите «2 $x$».

Примеры

3 3 3 2 0

2

5

5

2

6

6

6

7

10

1 1 1

1 1 2

1 1 3

1 2 1

1 2 2

1 2 3

1 3 1

1 3 2

1 3 3

2 2

Оценивание

Пусть $n=\max (|a|,|b|,|c|)$, а также $m=\max (a_i,b_j,c_t)$.

1. ($6$ баллов): $n\le 10,Q=150$;

2. ($4$ балла): $|b|=0,|c|=0,m\le 2,Q=150$;

3. ($9$ баллов): $|c|=0,m\le 2,Q=125$;

4. ($10$ баллов): $m\le 2,Q=125$;

5. ($13$ баллов): $|c|=0,Q=1000$;

6. ($13$ баллов): $|c|=0,Q=125$;

7. ($17$ баллов): $Q=1000$;

8. ($21$ балл): $Q=125$;

9. ($7$ баллов): $Q=65$.