У Козака Вуса є три секретні масиви 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.