Вгадайте колір

Дано $n$ кульок, пронумерованих від $1$ до $n$. У кожної кульки є свій колір, який вам невідомий. Всього є $k$ різних кольорів.

Ви можете за один запит подивитись на кульку та дізнатись кількість кульок такого самого кольору, які ви вже бачили (включно з цією). Сам колір кульки за такого запиту ви не дізнаєтесь. Всього такий запит можна робити не більше $c$ разів.

Вам потрібно знайти такий масив $colors$ з $n$ елементів, де кожен елемент — ціле число від $1$ до $k$ такий, що $colors[i]=colors[j]$ тоді й тільки тоді, коли кульки з номерами $i$ та $j$ однакового кольору.

Протокол взаємодії

Перший рядок містить чотири цілі числа $n$, $k$, $c$ та $g$ ($1\le k\le n\le 10^4$) — кількість кульок, кількість кольорів, максимальна кількість запитів та номер блока відповідно. Обмеження на $c$ дивіться нижче.

Ви можете зробити не більше $c$ запитів. Для того, щоб зробити запит, вам потрібно вивести в одному рядку число $1$ та число $index$ ($1\le index\le n$) — позицію кульки, на яку ви хочете подивитися. Після цього вам потрібно вивести символ кінця рядка та виконати операцію 'flush'. Лише після цього ви можете зчитати відповідь.

Коли ви уже знаєте відповідь — вам потрібно вивести число $2$ та $n$ цілих чисел масиву $colors$, де кожен елемент від $1$ до $k$. Після цього вам потрібно вивести символ кінця рядка, виконати операцію 'flush' та завершити програму.

Приклади

5 3 100 0
0
0
1
1
0
2
3

1 1
1 2
1 3
1 4
1 5
1 1
1 3
2 1 2 1 2 3

Примітка

Нехай $n=5$, $k=3$, $c=100$ та $a=[21213]$.

Якщо ви подивилися на $1$ кульку, то отримаєте значення $1$. Якщо подивитеся знову на $1$ кульку, то значення буде $2$. Тепер якщо подивитися на $2$ кульку, то значення буде $1$. Потім на $3$ кульку — отримуємо $3$. На $4$ кульку — отримуємо $2$. На $5$ кульку — отримуємо $1$.

Після цього можна повернути масив $[23231]$. Ця відповідь буде правильною.

Оцінювання

1. ($7$ балів) $n\le 10^4$; $k=n-1$; $c=5\cdot 10^4$; є дві кульки однакового кольору, а решта кульок різних кольорів;

2. ($7$ балів) $n\le 10^4$; $k=2$; $c=5\cdot 10^4$;

3. ($10$ балів) $n\le 500$; $k\le n$; $c=3\cdot 10^5$;

4. ($14$ балів) $n\le 10^4$; $k\le 10$; $c=3\cdot 10^5$;

5. ($15$ балів) $n\le 10^4$; $k\le n$; $c=2\cdot 10^4$; для кожного кольору від $1$ до $k$ кількість кульок цього кольору різна; кожен колір трапляється принаймні один раз;

6. (до $47$ балів) $n\le 10^4$; $k\le n$; $c=4\cdot 10^6$:

   • $7$ балів, якщо ви використаєте не більше $4\cdot 10^6$ запитів;

   • $17$ балів, якщо ви використаєте не більше $10^6$ запитів;

   • $32$ бали, якщо ви використаєте не більше $6\cdot 10^5$ запитів;

   • $47$ балів, якщо ви використаєте не більше $3\cdot 10^5$ запитів;