У Казака Уса имеются три секретных массива a, b, c из натуральных чисел. Обозначим их длины как ∣a∣, ∣b∣ и ∣c∣ соответственно. Эти длины не обязательно одинаковы. Известно, что каждый массив отсортирован, то есть, каждый следующий элемент не меньше предыдущего.
Вы хотите получить определенную информацию об этих массивы, а именно — значение k -го элемента в отсортированном объединении массивов. То есть, если из этих трех массивов сделать один большой массив длины ∣a∣+∣b∣+∣c∣, отсортировать его, то следует узнать k -ый элемент в таком массиве.
Казак Ус отказывается показывать Вам эти массивы. Однако он согласился на следующее: Вы можете узнавать значение определенных чисел. Вы можете выбрать определенный массив и определенную позицию в этом массиве, после чего Казак Ус сообщит Вам значение этого элемента. Обратите внимание, что Вы можете делать эту операцию много раз, не обязательно над одним и тем же массивом. Поскольку Козак — очень занятой человек, он позволил вам задать ему не более Q вопросов
Вам следует узнать k-ый наибольший элемент в объединении массивов.
Первая строка содержит пять целых чисел ∣a∣, ∣b∣, ∣c∣, k, g (0≤∣a∣,∣b∣,∣c∣≤106, 1≤k≤∣a∣+∣b∣+∣c∣).
Гарантируется, что все упомянутые числа находятся в границах [1,109].
Число g (0≤g≤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(ai,bj,ct).
(6 баллов): n≤10,Q=150;
(4 балла): ∣b∣=0,∣c∣=0,m≤2,Q=150;
(9 баллов): ∣c∣=0,m≤2,Q=125;
(10 баллов): m≤2,Q=125;
(13 баллов): ∣c∣=0,Q=1000;
(13 баллов): ∣c∣=0,Q=125;
(17 баллов): Q=1000;
(21 балл): Q=125;
(7 баллов): Q=65.