시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 2 2 100.000%

문제

Tupids 교수는 최근 조사를 통해, 새로운 고고학적 문서를 발굴하는 데 성공했다.

이 문서는 c종류의 기호 n개로 이루어진 문서이며, Tupids 교수는 그 문서의 의미를 연구하기 위해, 각 기호에 1~c까지의 자연수를 부여했다. 따라서, 해당 문서는 [1:c]의 범위에 있는 n개의 자연수 수열로 표현할 수 있다.

교수는 이 기호들 사이에 나타나는 관계를 확인하기 위해, n개의 row와 c개의 column을 갖는 큰 표를 하나 작성했다. 이 표의 i번째 row, j번째 column에 나타나는 값은, 수열에서 i번째 이후에 나타나는 최초의 j의 위치를 의미한다. 만약 그런 위치가 존재하지 않으면 해당 칸은 0으로 표기한다. 예를 들어, 다음과 같은 수열이 주어졌을 때, 표의 몇몇 값을 나타내면 다음과 같다.

n = 6, c = 3, [1,3,2,2,1,3]

Array[3][2] = 4 (3번째 이후에 최초로 나타나는 2는 4번째이다.)

Array[2][3] = 6 (2번째 이후에 최초로 나타나는 3은 6번째이다.)

Array[5][2] = NULL (5번째 이후에는 1이 나타나지 않는다.)

어느 날, 연구실에 갑작스러운 화재가 발생해서 문서가 완전히 소실되었다! 다행히, 연구를 위해 새로 작성한 표는 완전히 소실되지는 않았으나, 어느 정도의 피해를 입었다. c의 값이 얼마였는지에 관한 정보가 소실되었으며, 표의 일부 칸을 알아볼 수 없었을 뿐만 아니라, 조교들의 잘못된 보관으로 인해, 각 row마다 적힌 숫자들이 완전히 뒤섞여 버렸다!

Tupids 교수는 남은 정보를 이용해 원래의 문서를 복구하고자 한다. 무한히 많은 가능성이 있을 수 있기 때문에, 교수는 사전순으로 가장 앞서는 해법을 찾기를 원한다. 다만, 표의 내용이 잘못되었다면, 원하는 해법이 존재하지 않을 수도 있다. 이 경우에는 그 슬픈 소식을 교수에게 전해주는 것으로 충분할 것이다.

위와 같이 피해를 입은 표를 입력으로 받아, 기존의 수열을 복구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 원래 수열의 길이 n (1 ≤ n ≤ 300,000)이 입력으로 주어진다.

다음 n개의 줄에는 각각 자연수 ci와, ci개의 서로 다른 자연수가 주어진다. (0 ≤ ci ≤ n-i) 이 ci개의 자연수들은 표의 i번째 row에서 알아볼 수 있도록 남아 있는 숫자들을 의미한다. (하지만, 순서는 원래 표에서의 순서와 다를 수 있다.)

모든 ci들의 합이 300,000을 넘지 않음이 보장된다.

출력

조건을 만족하는 수열이 존재한다면, 한 줄에 해당 수열을 나타내는 n개의 자연수를 출력한다. 만약 여러 개의 수열이 조건을 만족한다면, 사전 순으로 가장 앞서는 수열을 출력한다.

조건을 만족하는 수열이 존재하지 않는다면, “No Solution”을 출력한다.

예제 입력 1

4
3 2 3 4
2 4 3
1 4
0

예제 출력 1

1 1 2 3

예제 입력 2

5
1 2
1 4
1 4
1 5
0

예제 출력 2

1 1 1 2 1