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

Це інтерактивна задача.

Є $n$ монет, розташованих в ряд та пронумерованих зліва направо цілими числами від $1$ до $n$.

Рівно $k$ ($k<n$) з цих монет є фальшивими, інші $(n-k)$ монет — справжні. Фальшиві монети легші за справжні. Всі справжні монети мають однакову вагу, в той час як фальшиві монети можуть мати різну вагу. Також відомо, що фальшиві монети розташовані поспіль, тобто мають номери $p,p+1,\dots ,(p+k-1)$.

Вам потрібно знайти номер найлівішої фальшивої монети. Ви можете користуватись зважуванням, що аналогічне зважуванню на двочашкових терезах: вибрати дві множини монет, що не перетинаються, і дізнатись, яка з множин важить більше, або що множини важать однаково.

Вхідні дані

У першому рядку задано три цілі числа $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\le p\le 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)))))