Дано перестановку, яка складається з n (n — степінь двійки) чисел. Порядок елементів у перестановці вам невідомий.
Перестановка — це послідовність довжини n цілих чисел від 1 до n, в якій всі числа зустрічаються рівно по одному разу. Наприклад, [1], [4,3,5,1,2], [3,2,1] — перестановки, а [1,1], [4,3,1], [2,3,4] — ні.
Також є такий запит: ви даєте масив a довжини n, такий що 1≤ai≤n (зауважте, що a не обов'язково є перестановкою). У відповідь ви отримуєте масив c довжини n, який генерується таким чином:
Вам потрібно знайти загадану перестановку p. Максимальну кількість запитів дивіться у параграфі «Оцінювання».
Перший рядок містить два цілі числа t і q (1≤t,q≤256) — кількість наборів вхідних даних та максимальна кількість запитів, які можна використати у кожному наборі вхідних даних.
Для кожного набору вхідних даних спочатку слід прочитати ціле число n(1≤n≤1024) — кількість елементів у перестановці p.
Гарантується, що n є степеню двійки (тобто є таке ціле невід'ємне число k, що 2k=n).
Щоб зробити запит, виведіть «1 a1 a2 ...an» (1≤ai≤n).
У відповідь на запит програма журі виведе масив c, отриманим за правилом з умови, у наступному форматі: «c1 c2 ...cn».
Після виведення запиту не забудьте вивести символ нового рядка і скинути буфер виведення. В іншому випадку ви отримаєте вердикт Вичерпано ліміт часу
. Для скидання буфера використовуйте:
fflush(stdout)
або cout.flush()
в C++;
System.out.flush()
в Java;
flush(output)
в Pascal;
stdout.flush()
в Python;
дивіться документацію для інших мов.
Зверніть увагу, що якщо ваш запит недійсний (ліміт запитів перевищено або вхідний масив не задовільняє обмеженням), інтерактор виведе «-1» та припинить роботу. Якщо ви зчитаєте «-1», то негайно завершіть програму, щоб отримати вердикт Неправильна відповідь
замість довільного вердикту.
Коли ви знайдете перестановку p, виведіть «2 p1 p2 ...pn».
Після цього, якщо це був останній набір вхідних даних, ви повинні завершити роботу своєї програми, в іншому випадку ви повинні продовжити роботу з наступним набором вхідних даних.
1 256 4 0 1 1 1
1 3 2 4 2 2 1 4 2 3
З першого запиту дізналися, що p1<p3<p4<p2.
Отже, шукана перестановка має вигляд: [1,4,2,3].
q — максимальна кількість запитів, яку може використати ваша програма.
(3 бали) n≤16,q=256,t=128
(7 балів) n≤32,q=256,t=128
(8 балів) n≤256,q=256,t=128
(14 балів) n≤512,q=256,t=128
(20 балів) n≤512,q=128,t=256
(до 48 балів) n≤1024,q=127,t=256; Нехай k — максимальна кількість запитів, яку ви використали у одному наборі даних. Тоді результат за цей тест буде рівний:
0 балів, якщо k>127;
48−⌈3724(k−55)⌉ балів, якщо 55<k≤127;
48 балів, якщо k≤55;