Ти 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$.