Вгадайте перестановку

Дано перестановку, яка складається з $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\le a_i\le n$ (зауважте, що $a$ не обов'язково є перестановкою). У відповідь ви отримуєте масив $c$ довжини $n$, який генерується таким чином:

c = масив довжини n з нулів
for i = 1 to n:
    if p[a[i]] > p[i]:
         c[a[i]] += 1
повернути c

Вам потрібно знайти загадану перестановку $p$. Максимальну кількість запитів дивіться у параграфі «Оцінювання».

Input

Перший рядок містить два цілі числа $t$ і $q$ ($1\le t,q\le 256$) — кількість наборів вхідних даних та максимальна кількість запитів, які можна використати у кожному наборі вхідних даних.

Interaction

Для кожного набору вхідних даних спочатку слід прочитати ціле число $n$($1\le n\le 1024$) — кількість елементів у перестановці $p$.

Гарантується, що $n$ є степеню двійки (тобто є таке ціле невід'ємне число $k$, що $2^k=n$).

Щоб зробити запит, виведіть «1 $a_1$ $a_2$ ...$a_n$» ($1\le a_i\le n$).

У відповідь на запит програма журі виведе масив $c$, отриманим за правилом з умови, у наступному форматі: «$c_1$ $c_2$ ...$c_n$».

Після виведення запиту не забудьте вивести символ нового рядка і скинути буфер виведення. В іншому випадку ви отримаєте вердикт Вичерпано ліміт часу. Для скидання буфера використовуйте:

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

• System.out.flush() в Java;

• flush(output) в Pascal;

• stdout.flush() в Python;

дивіться документацію для інших мов.

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

Коли ви знайдете перестановку $p$, виведіть «2 $p_1$ $p_2$ ...$p_n$».

Після цього, якщо це був останній набір вхідних даних, ви повинні завершити роботу своєї програми, в іншому випадку ви повинні продовжити роботу з наступним набором вхідних даних.

Examples

1 256
4

0 1 1 1

1 3 2 4 2

2 1 4 2 3

Note

З першого запиту дізналися, що $p_1<p_3<p_4<p_2$.

Отже, шукана перестановка має вигляд: $[1,4,2,3]$.

Scoring

$q$ — максимальна кількість запитів, яку може використати ваша програма.

1. ($3$ бали) $n\le 16,q=256,t=128$

2. ($7$ балів) $n\le 32,q=256,t=128$

3. ($8$ балів) $n\le 256,q=256,t=128$

4. ($14$ балів) $n\le 512,q=256,t=128$

5. ($20$ балів) $n\le 512,q=128,t=256$

6. (до $48$ балів) $n\le 1024,q=127,t=256$; Нехай $k$ — максимальна кількість запитів, яку ви використали у одному наборі даних. Тоді результат за цей тест буде рівний:

• $0$ балів, якщо $k>127$;

• $48-\lceil \frac{24(k-55)}{37}\rceil$ балів, якщо $55<k\le 127$;

• $48$ балів, якщо $k\le 55$;