Подарунок Леді

На свій день народження Леді отримала подарунок — мережу. Мережа містить $n$ вузлів, пронумерованих цілими числами від $1$ до $n$. На кожному вузлі записана певна літера, для вузла з номером $i$ позначимо цю літеру як $s_i$.

Між деякими парами вузлів є односторонні зв'язки. З кожного вузла виходить рівно один односторонній зв'язок. Нехай для вузла з номером $i$ такий зв'язок веде у вузол з номером $x_i$. Зауважте, що $x_i$ може бути рівним $i$ — у такому випадку вважається, що зв'язок з вузла з номером $i$ веде в цей самий вузол.

Нехай $p_{i,0}=i$ та $p_{i,k}=p_{x_i,k-1}$. Тобто $p_{i,k}$ — номер вузла, у якому опиниться фішка, якщо її помістити у вузол з номером $i$ та $k$ разів перенести її по зв'язку з поточного вузла.

Леді створила матрицю $a$ розміру $n\times (3\cdot n)$, де $a_{i,j}=s_{p_{i,j-1}}$. Тобто $i$-й рядок матриці $a$ це послідовність з $3\cdot n$ літер, де перша літера дорівнює $s_i$, друга літера  — $s_{x_i}$, третя — $s_{x_{x_i}}$, і так далі...

Леді повідомила деякі рядки матриці $a$ та просить Вас побудувати будь-яку мережу, що відповідає відомим рядкам матриці $a$.

Вхідні дані

У першому рядку задано одне ціле число $n$ $(1\le n\le 2\cdot {10}^3)$ — кількість вузлів мережі.

У наступних $n$ рядках задано опис матриці $a$. У кожному з рядків задано $3\cdot n$ маленьких літер латинського алфавіту, що позначають відповідний рядок матриці $a$, або один символ «?», якщо відповідний рядок Леді не повідомила.

Гарантується, що існує хоча б одна мережа, яка відповідає заданим умовам.

Вихідні дані

У першому рядку виведіть рядок $s$ з $n$ маленьких літер латинського алфавіту — літери записані на вузлах мережі.

У другому рядку виведіть $n$ цілих чисел $x_1,x_2,\dots ,x_n$ $(1\le x_i\le n)$ — номери вузлів, у які ведуть зв'язки з відповідних вузлів.

Матриця, яка відповідає цій мережі має бути рівною матриці $a$ в усіх рядках, які повідомила Леді.

Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них.

Приклади

Примітка

У першому прикладі $x_1=2$ і $x_2=3$, тому $p_{1,0}=1,p_{1,1}=2,p_{1,2}=3$. Через те, що $x_3=3$, усі $p_{1,k}$ для $k\ge 3$ теж дорівнюють $3$. Відповідно друга літера першого рядка дорівнює $s_2$, а третя — $s_3$.

Знизу зображенні мережі з прикладів. Числа в кутку позначають номери вузлів, літери позначають записані на відповідних вузлах значення, а стрілки — односторонні зв'язки.

Мережа з першого прикладу

Мережа з другого прикладу

Оцінювання

Нехай $q$ — кількість рядків, які Леді не повідомила.

Назвемо мережу набором пар та одиничних вузлів, якщо мережу можна розбити на вузли, з яких зв'язок веде у самих себе (тобто $x_v=v$), та на пари вузлів $(a,b)$ таких, що $x_a=b$ та $x_b=a$.

Назвемо мережу набором зірок, якщо мережу можна розбити на окремі «зірки», кожна з яких складається з головного вузла $v$, з якого зв'язок веде у самого себе (тобто $x_v=v$), та набору другорядних вузлів $y=\{y_1,y_2,\dots ,y_k\}$ такого, що $x_{y_i}=v$ для $1\le i\le k$. Зауважте, що зірки в мережі можуть мати різні розміри та складатися лише з одного головного вузла.

Назвемо мережу деревом з коренем у вузлі $v$, якщо з вузла $v$ зв'язок веде у самого себе (тобто $x_v=v$), та для кожного іншого вузла можливо потрапити до вузла $v$, використовуючи зв'язки мережі (тобто для кожного $1\le i\le n$ існує таке $k$, що $p_{i,k}=v$).

Назвемо мережу циклом, якщо почавши у будь-якому вузлі можливо потрапити до будь-якого іншого вузла, використовуючи зв'язки мережі (тобто для усіх $1\le i,j\le n$ існує таке $k$, що $p_{i,k}=j$).

1. ($10$ балів): $n\le 5$, $q=0$;

2. ($6$ балів): $n\le 300$, $q=0$, $x_{x_i}=i$ для $1\le i\le n$ (мережа є набором пар та одиничних вузлів);

3. ($6$ балів): $n\le 300$, $q=0$, $x_{x_i}=x_i$ для $1\le i\le n$ (мережа є набором зірок);

4. ($9$ балів): $n\le 300$, $q=0$, $x_1=1$ та $x_i<i$ для $2\le i\le n$ (мережа є деревом з коренем у вузлі $1$);

5. ($9$ балів): $n\le 300$, $q=0$, для усіх $1\le i,j\le n$ існує таке $k$, що $p_{i,k}=j$ (мережа є циклом);

6. ($13$ балів): $n\le 300$, $q=0$;

7. ($25$ балів): $n\le 300$;

8. ($10$ балів): $n\le 2\cdot {10}^3$, $q=0$;

9. ($12$ балів): без додаткових обмежень.