Дано перестановку, яка складається з ( — степінь двійки) чисел. Порядок елементів у перестановці вам невідомий.
Перестановка — це послідовність довжини цілих чисел від до , в якій всі числа зустрічаються рівно по одному разу. Наприклад, , [4, 3, 5, 1, 2], [3, 2, 1] — перестановки, а , [4, 3, 1], [2, 3, 4] — ні.
Також є такий запит: ви даєте масив довжини , такий що 1 \le a_i \le n (зауважте, що не обов'язково є перестановкою). У відповідь ви отримуєте масив довжини , який генерується таким чином:
c = масив довжини n з нулів
for i = 1 to n:
if p[a[i]] > p[i]:
c[a[i]] += 1
повернути cВам потрібно знайти загадану перестановку . Максимальну кількість запитів дивіться у параграфі «Оцінювання».
Перший рядок містить два цілі числа і (1 \le t, q \le 256) — кількість наборів вхідних даних та максимальна кількість запитів, які можна використати у кожному наборі вхідних даних.
Для кожного набору вхідних даних спочатку слід прочитати ціле число (1 \le n \le 1024) — кількість елементів у перестановці .
Гарантується, що є степеню двійки (тобто є таке ціле невід'ємне число , що 2^k=n).
Щоб зробити запит, виведіть «1 a_1 a_2 ...a_n» (1 \le a_i \le n).
У відповідь на запит програма журі виведе масив , отриманим за правилом з умови, у наступному форматі: «c_1 c_2 ...c_n».
Після виведення запиту не забудьте вивести символ нового рядка і скинути буфер виведення. В іншому випадку ви отримаєте вердикт Вичерпано ліміт часу. Для скидання буфера використовуйте:
fflush(stdout) або cout.flush() в C++;
System.out.flush() в Java;
flush(output) в Pascal;
stdout.flush() в Python;
дивіться документацію для інших мов.
Зверніть увагу, що якщо ваш запит недійсний (ліміт запитів перевищено або вхідний масив не задовільняє обмеженням), інтерактор виведе «-1» та припинить роботу. Якщо ви зчитаєте «-1», то негайно завершіть програму, щоб отримати вердикт Неправильна відповідь замість довільного вердикту.
Коли ви знайдете перестановку , виведіть «2 p_1 p_2 ...p_n».
Після цього, якщо це був останній набір вхідних даних, ви повинні завершити роботу своєї програми, в іншому випадку ви повинні продовжити роботу з наступним набором вхідних даних.
Example
1 256
4
0 1 1 1
1 3 2 4 2
2 1 4 2 3З першого запиту дізналися, що p_1<p_3<p_4<p_2.
Отже, шукана перестановка має вигляд: [1, 4, 2, 3].
— максимальна кількість запитів, яку може використати ваша програма.
( бали) n \le 16, q=256, t=128
( балів) n \le 32, q=256, t=128
( балів) n \le 256, q=256, t=128
( балів) n \le 512, q=256, t=128
( балів) n \le 512, q=128, t=256
(до балів) n \le 1024, q=127, t=256; Нехай — максимальна кількість запитів, яку ви використали у одному наборі даних. Тоді результат за цей тест буде рівний:
балів, якщо k > 127;
48- \lceil \frac{24(k-55)}{37}\rceil балів, якщо 55 < k \le 127;
балів, якщо k \le 55;