Ти k-ий?#10446

Ти k-ий?

3 секунди

256 мегабайтів

Складна

У Козака Вуса є три секретні масиви $a$ , $b$ , $c$ з цілих додатних чисел. Позначимо їхні довжини як $∣ a ∣$ , $∣ b ∣$ та $∣ c ∣$ відповідно. Ці довжини не обов'язково однакові. Відомо, що кожен масив відсортований, тобто, кожен наступний елемент не менший за попередній.

Ви хочете отримати певну інформацію про ці масиви, а саме — значення $k$ -го елементу у відсортованому об'єднанні масивів. Тобто, якщо з цих трьох масивів зробити один великий масив довжини $∣ a ∣ + ∣ b ∣ + ∣ c ∣$ |a| + |b| + |c|, відсортувати його, то потрібно дізнатися $k$ -ий елемент у такому масиві.

Козак Вус відмовляється показувати вам ці масиви. Проте він погодився на наступне: ви можете дізнаватися значення певних чисел. Ви можете вибрати певний масив та певну позицію у цьому масиві, після чого Козак Вус повідомить вам значення цього елементу. Зверніть увагу, що ви можете робити цю операцію багато разів, не обов'язково над одним і тим же масивом. Оскільки Козак — дуже зайнята людина, він дозволив вам поставити йому не більше ніж $Q$ питань.

Потрібно дізнатися $k$ -ий найменший елемент в об'єднанні масивів.

Вхідні дані

Перший рядок містить п'ять цілих чисел $∣ a ∣$ , $∣ b ∣$ , $∣ c ∣$ , $k$ , $g$ ( $0 \leq ∣ a ∣, ∣ b ∣, ∣ c ∣ \leq 1 0^{6}$ 0 \leq |a|, |b|, |c| \leq 10^6, $1 \leq k \leq ∣ a ∣ + ∣ b ∣ + ∣ c ∣$ 1 \leq k \leq |a| + |b| + |c|).

Гарантується, що всі загадані числа у межах $[1, 1 0^{9}]$ [1, 10^9].

Число $g$ ( $0 \leq g \leq 9$ 0 \leq g \leq 9) — номер групи тестів (див. Оцінювання).

Взаємодія

Спочатку потрібно зчитати п'ять цілих чисел $∣ a ∣$ , $∣ b ∣$ , $∣ c ∣$ , $k$ , $g$ .

Щоб зробити запит, виведіть 1 $r$ $m$ . Тут $r$ — номер масиву: якщо $r = 1$ r = 1, то операція буде здійснена над масивом $a$ , якщо $r = 2$ r = 2, то над масивом $b$ , якщо $r = 3$ r = 3, то над $c$ . А $m$ — номер позиції у цьому масиві. Якщо ви, наприклад, виконуєте операцію над масивом $a$ , то, щоб отримати перший елемент, потрібно, щоб $m = 1$ m = 1, а щоб останній, потрібно, щоб $m = ∣ a ∣$ 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$ .

Приклади

Приклад

Оцінювання

Нехай $n = max (∣ a ∣, ∣ b ∣, ∣ c ∣)$ n = \max(|a|, |b|, |c|), а також $m = max (a_{i}, b_{j}, c_{t})$ m = \max(a_i, b_j, c_t).

( $6$ балів): $n \leq 10$ n \leq 10, $Q = 150$ Q = 150;
( $4$ бали): $∣ b ∣ = 0$ |b| = 0, $∣ c ∣ = 0$ |c| = 0, $m \leq 2$ m \leq 2, $Q = 150$ Q = 150;
( $9$ балів): $∣ c ∣ = 0$ |c| = 0, $m \leq 2$ m \leq 2, $Q = 125$ Q = 125;
( $10$ балів): $m \leq 2$ m \leq 2, $Q = 125$ Q = 125;
( $13$ балів): $∣ c ∣ = 0$ |c| = 0, $Q = 1000$ Q = 1000;
( $13$ балів): $∣ c ∣ = 0$ |c| = 0, $Q = 125$ Q = 125;
( $17$ балів): $Q = 1000$ Q = 1000;
( $21$ бал): $Q = 125$ Q = 125;
( $7$ балів): $Q = 65$ Q = 65.