Лотерея «Три Семёрки» проводилась \(m\) дней. В день \(i\) в лотерее участвовали \(n_i\) людей с номерами \(a_{i, 1}, \ldots, a_{i, n_i}\).
Известно, что в каждый из \(m\) дней из участников лотереи выбирался ровно один победитель. Победителю лотереи в день \(i\) запрещено участвовать в лотерее в дни с номерами от \(i+1\) до \(m\).
К сожалению, информация о победителях лотереи была утеряна. Вам нужно восстановить любой возможный список победителей лотереи в дни с номерами от \(1\) до \(m\) или определить, что это невозможно.
Выходные данные
Для каждого набора входных данных, если решения не существует, выведите одно целое число \(-1\).
Иначе выведите \(m\) целых чисел \(p_1, p_2, \ldots, p_m\) (\(1 \le p_i \le 50\,000\)) — номера победителей лотереи в дни с \(1\) по \(m\). Если существует несколько корректных решений, выведите любое из них.
Примечание
В первом наборе входных данных один из подходящих ответов \([8, 2, 1]\), так как участник с номером \(8\) участвовал в день \(1\), но не участвовал в дни \(2\) и \(3\); участник с номером \(2\) участвовал в день \(2\), но не участвовал в день \(3\); а участник с номером \(1\) участвовал в день \(3\). Обратите внимание, что это не единственный возможный ответ, например, \([8, 9, 4]\) также является верным ответом.
Во втором наборе входных данных оба участника лотереи участвовали в обоих днях лотереи, значит любой возможный победитель лотереи в день \(1\) обязательно участвовал в день \(2\), значит подходящего ответа не существует.
В третьем наборе входных данных в дни \(2\), \(3\) и \(4\) участвовал только один участник, а в день \(1\) единственный участник, не участвовавший в лотерее в днях \(2, 3, 4\) — это участник \(2\). Значит \([2, 1, 4, 3]\) — единственно верный ответ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
4
1 2 4 8
3
2 9 1
2
1 4
2
2
1 2
2
2 1
4
4
1 2 3 4
1
1
1
4
1
3
|
8 2 1
-1
2 1 4 3
|