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

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

30 seconds
256 megabytes
Very hard

Дано перестановку, яка складається з ( — степінь двійки) чисел. Порядок елементів у перестановці вам невідомий.

Перестановка — це послідовність довжини цілих чисел від до , в якій всі числа зустрічаються рівно по одному разу. Наприклад, , [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

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

Input

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

Interaction

Для кожного набору вхідних даних спочатку слід прочитати ціле число (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».

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

Examples

Example

Input
1 256
4

0 1 1 1
Output


1 3 2 4 2

2 1 4 2 3

Note

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

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

Scoring

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

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

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

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

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

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

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

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

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

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