Масив монет і запити зважування

Вхідні дані

У першому рядку задано три цілі числа $n$, $k$, $g$ (1 \le k < n \le 10^4, 0 \le g \le 6) — загальна кількість монет, кількість фальшивих монет та номер блоку тестів відповідно.

Взаємодія

Щоб виконати запит зважування виведіть «? s_1 s_2 a_1 a_2 $\dots$ a_{s_1} b_1 b_2 $\dots$ b_{s_2}», де s_1 та s_2 позначають розміри множин які зважуються, а масиви $a$ та $b$ позначають номери монет, що належать першій та другій множинам відповідно.

У відповідь на запит програма журі виведе одне ціле число $x$ (x \in \{0,1,2\}). Якщо x = 1, то перша множина важча за другу; якщо x = 2, то друга множина важча за першу; якщо x = 0, то множини мають однакову вагу.

Якщо запит невалідний (тобто перевищено максимальну кількість запитів або параметри запиту є невалідними), програма журі виведе -1 та припинить роботу. У такому випадку завершіть роботу програми, щоб отримати вердикт Неправильна відповідь.

Подбайте про виклик методу flush після виводу кожного рядка. Для цього можна використовувати:

• fflush(stdout), cout << endl або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• sys.stdout.flush() в Python;

• дивіться документації для інших мов програмування.

Вихідні дані

Для того, щоб дати відповідь, виведіть єдиний рядок у форматі «! $p$», де $p$ (1 \leq p \leq n) — номер найлівішої фальшивої монети.

Приклади

4 1 0

0

0

2

? 1 1 1 2

? 1 1 2 4

? 1 1 3 4

! 3

Оцінювання

Визначимо $q$ як максимальну кількість запитів зважування, яку ви можете виконати у тестах певного блоку.

1. ($5$ балів): n \le 16, q=16;

2. ($9$ балів): k=1, q=16;

3. ($7$ балів): k=1, q=11;

4. ($16$ балів): k \le 16, q=11;

5. ($9$ балів): ваги всіх фальшивих монет однакові, q=11;

6. (до $54$ балів): q=300. Нехай максимальна кількість використаних зважувань дорівнює $c$. Якщо c \le 9, то ви отримаєте $54$ бали, а інакше ви отримаєте \lfloor 54 \cdot \max(-0.0004 \cdot c + 0.3134, 0.018 + \frac{9.0773}{c}) \rfloor балів.

Код на мові C++, який обчислює кількість балів за останній блок тестів залежно від кількості використаних зважувань:

((c <= 9) ? 54 : int(54 * (max((-0.0004 * c + 0.3134), (0.018 + 9.0773 / c)))))