Problems
Ты 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}