22239번 - 가희와 읽기 쓰기 놀이 2 스페셜 저지

문제

가희와 친구들은 읽기 쓰기 놀이를 하고 있습니다. 읽기 쓰기 놀이는 빈 리스트를 가지고 시작합니다.

놀이에서 사용하는 카드에 적혀져 있는 연산은 하나입니다.

• add c
  • 리스트 뒤에 수 c를 추가합니다.

놀이의 규칙은 다음과 같습니다.

• 빈 리스트로 게임을 시작합니다.
• 각 턴을 수행하는 사람은 1명입니다.
• 턴을 수행하는 사람은 가지고 있는 카드에 적혀져 있는 연산을 수행하고 턴을 종료합니다.

문자열 게임에 참가하는 사람은 N명이고, 카드는 1번 카드부터 C번 카드까지 총 C장 있습니다.

N개의 제약 조건이 주어졌을 때 제약 조건에 맞게 사람들이 카드를 내서 결과 (길이가 C인) 리스트를 만들 수 있을까요?

만들 수 있다면, 각 턴마다 어떤 사람이 카드를 냈는지 구해 주세요. 그렇지 않으면 -1을 출력해 주세요.

입력

1번째 줄에 N, C가 공백으로 구분되어 주어집니다.

2번째 줄에 게임의 결과인 리스트에 있는 수들이 주어집니다. 0번째 인덱스에 있는 수부터 C-1번째 인덱스에 있는 수까지 공백으로 구분되어 주어집니다.

3번째 줄 부터 N+2번째 줄까지 1번 제약 조건부터 N번 제약 조건까지 제약 조건 N개가 주어집니다.

제약 조건이 주어질 때에는, 내야 하는 카드의 개수와 어떤 순서로 카드를 내야 하는지가 주어집니다.

예를 들어 3번째 줄에 3 2 4 5 가 있다면, 1번 사람이 2번 카드, 4번 카드, 5번 카드를 순서대로 내야 하는 것을 의미합니다.

N+3번째 줄부터 N+C+2번째 줄까지 1번 카드부터 C번 카드에 적혀져 있는 연산이 주어집니다. 카드에 있는 연산은 하나입니다.

출력

제약 조건에 맞게 게임을 해서 결과 리스트를 만들 수 있다면, 각 턴마다 어떤 사람이 카드를 내야 하는지 공백으로 구분해서 출력해 주세요.

답이 여러 개인 경우에는 아무거나 출력하고, 그렇지 않으면 -1을 출력해 주세요.

제한

• N과 C는 구간 [1, 2×10⁴]에 속하는 정수이며, N ≤ C입니다.
• 제약 조건에서 내야 하는 카드의 개수는 구간 [1, C]에 속하는 정수이며, 내야 하는 카드 개수의 합은 C입니다.
• 제약 조건에서 내야 하는 카드의 번호는 구간 [1, C]에 속하는 정수입니다.
• 1번부터 C번 카드는 N개의 제약 조건에서 총 1번만 등장합니다.
• 1번부터 C번 카드에 적혀있는 c는 [1, 10⁹]에 속하는 정수입니다.
• 결과 리스트에 있는 수는 [1, 10⁹]에 속하는 정수이며, 결과 리스트에 2번 이상 나오는 수가 나오는 횟수를 합하면 최대 6번 입니다.

노트

결과 리스트가 [2, 1, 2, 2, 3, 4, 2, 3]으로 주어졌다고 생각해 보겠습니다.

[그림 1] 유효한 결과 리스트

결과 리스트에서 두 번 이상 등장한 수는 2, 3입니다. 2가 등장한 횟수는 4번, 3이 등장한 횟수는 2번입니다.

결과 리스트에서 2번 이상 나오는 수가 나오는 횟수를 합하면 6입니다.

아래는 결과 리스트가 [2, 1, 2, 2, 3, 3, 2, 3]인 경우입니다.

[그림 2] 유효하지 않은 결과 리스트

결과 리스트에서 2번 이상 나오는 수는 2, 3입니다. 2가 나온 횟수는 4번, 3이 나온 횟수는 3번으로, 이 둘을 합하면 7입니다.

7은 6보다 크므로, 결과 리스트에 2번 이상 나오는 수가 나오는 횟수를 합하면 최대 6번이라는 제한을 만족하지 않습니다.

이러한 입력은 주어지지 않습니다.