Задачі
Ти k-ий?
Ти k-ий?
У Козака Вуса є три секретні масиви $a$, $b$, $c$ з цілих додатних чисел. Позначимо їхні довжини як $|a|$, $|b|$ та $|c|$ відповідно. Ці довжини не обов'язково однакові. Відомо, що кожен масив відсортований, тобто, кожен наступний елемент не менший за попередній.
Ви хочете отримати певну інформацію про ці масиви, а саме~--- значення $k$-го елементу у відсортованому об'єднанні масивів. Тобто, якщо з цих трьох масивів зробити один великий масив довжини $|a|+|b|+|c|$, відсортувати його, то потрібно дізнатися $k$-ий елемент у такому масиві.
Козак Вус відмовляється показувати вам ці масиви. Проте він погодився на наступне: ви можете дізнаватися значення певних чисел. Ви можете вибрати певний масив та певну позицію у цьому масиві, після чого Козак Вус повідомить вам значення цього елементу. Зверніть увагу, що ви можете робити цю операцію багато разів, не обов'язково над одним і тим же масивом. Оскільки Козак --- дуже зайнята людина, він дозволив вам поставити йому не більше ніж $Q$ питань.
Потрібно дізнатися $k$-ий найбільший елемент в об'єднанні масивів.
\InputFile
Перший рядок містить п'ять цілих чисел $|a|$, $|b|$, $|c|$, $k$, $g$ ($0 \leq |a|, |b|, |c| \leq 10^6$, $1 \leq k \leq |a| + |b| + |c|$).
Гарантується, що всі загадані числа у межах $[1, 10^9]$.
Число $g$ ($0 \leq g \leq 9$) --- номер групи тестів (див. Оцінювання).
\Interaction
Спочатку потрібно зчитати п'ять цілих чисел $|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$.
Після виведення запиту не забудьте вивести символ нового рядка і скинути буфер виведення. В іншому випадку ви отримаєте вердикт \t{Вичерпано ліміт часу}. Для скидання буфера використовуйте:
\begin{itemize}
\item \t{fflush(stdout)} або \t{cout.flush()} в C++;
\item \t{System.out.flush()} в Java;
\item \t{flush(output)} в Pascal;
\item \t{stdout.flush()} в Python;
\end{itemize}
дивіться документацію для інших мов.
Зверніть увагу, що якщо ваш запит недійсний (ліміт запитів перевищено або запит не задовільняє обмеженням), інтерактор виведе <<-1>> та припинить роботу. Якщо ви зчитаєте <<-1>>, то негайно завершіть програму, щоб отримати вердикт \t{Неправильна відповідь} замість довільного вердикту.
Коли ви знайдете відповідь $x$, виведіть <<2 $x$>>.
\Scoring
Нехай $n = \max(|a|, |b|, |c|)$, а також $m = \max(a_i, b_j, c_t)$.
\begin{enumerate}
\item ($6$ балів): $n \leq 10, Q = 150$;
\item ($4$ бали): $|b|=0, |c|=0, m \leq 2, Q = 150$;
\item ($9$ балів): $|c|=0, m \leq 2, Q = 125$;
\item ($10$ балів): $m \leq 2, Q = 125$;
\item ($13$ балів): $|c|=0, Q = 1000$;
\item ($13$ балів): $|c|=0, Q = 125$;
\item ($17$ балів): $Q = 1000$;
\item ($21$ бал): $Q = 125$;
\item ($7$ балів): $Q = 65$.
\end{enumerate}
\Example
\begin{example}
\exmp{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
}
\end{example}