Это интерактивная задача.

Маленький Эхаб любит ползать по своей квартире. В ней есть $$$n$$$ комнат, пронумерованных от $$$0$$$ до $$$n-1$$$. Для каждой пары комнат $$$a$$$ и $$$b$$$, либо есть прямой переход из комнаты $$$a$$$ в комнату $$$b$$$, либо наоборот из комнаты $$$b$$$ в комнату $$$a$$$, но не одновременно.

Маленький Эхаб хочет пойти поиграть с маленьким Бадави. Он хочет знать, сможет ли он добраться до него. Однако, он не знает ничего про свою квартиру, кроме количества комнат. Он может задать няне два типа вопросов:

• переход между комнатами $$$a$$$ и $$$b$$$ направлен из $$$a$$$ в $$$b$$$ или в обратную сторону?
• есть ли из комнаты $$$x$$$ переход, направленный в одну из комнат $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$?

Он может задать не более $$$9n$$$ вопросов первого типа, и не более $$$2n$$$ вопросов второго типа.

После того, как он задаст какие-то вопросы, он хочет знать для каждой пары комнат $$$a$$$ и $$$b$$$, существует ли путь из $$$a$$$ в $$$b$$$ или нет. Путь из $$$a$$$ в $$$b$$$ это последовательность переходов, которая начинается в комнате $$$a$$$ и заканчивается в комнате $$$b$$$.

Чтобы задать вопрос первого типа, используйте формат:

• $$$1$$$ $$$a$$$ $$$b$$$ ($$$0 \le a,b \le n-1$$$, $$$a \neq b$$$).
• интерактор ответит $$$1$$$, если переход ведет из $$$a$$$ в $$$b$$$, и $$$0$$$, если из $$$b$$$ в $$$a$$$.
• вы можете задать не более $$$9n$$$ вопросов этого типа в каждом наборе входных данных.

Чтобы задать вопрос второго типа, используйте формат:

• $$$2$$$ $$$x$$$ $$$k$$$ $$$s_1$$$ $$$s_2$$$ ... $$$s_k$$$ ($$$0 \le x,s_i \le n-1$$$, $$$0 \le k < n$$$, $$$x \neq s_i$$$, элементы $$$s$$$ попарно различны).
• интерактор ответит $$$1$$$, если существует переход ведущий из $$$x$$$ в какую-то из комнат из $$$s$$$, и $$$0$$$ иначе.
• вы можете задать не более $$$2n$$$ вопросов этого типа в каждом наборе входных данных.

Если интерактор ответит $$$-1$$$ вместо корректного ответа, это означает, что вы превысили разрешенное количество вопросов, или сделали некорректный вопрос. Немедленно завершитесь после получения $$$-1$$$, чтобы получить вердикт Wrong answer. Иначе, вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.

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

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы:

Первая строка должна содержать целое число $$$t$$$ — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать целое число $$$n$$$ ($$$4 \le n \le 100$$$) — количество комнат.

Каждая из следующих $$$n$$$ строк должна содержать двоичную строку длины $$$n$$$. $$$j$$$-й символ в $$$i$$$-й строке должен равняться $$$1$$$, если есть переход из комнаты $$$i$$$ в комнату $$$j$$$, и $$$0$$$ иначе. $$$i$$$-й символ в $$$i$$$-й строке должен равняться $$$0$$$.