시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB27222720484.298%

문제

자대 배치 전 특기 교육을 받는 보라매 학교에 하늘이를 포함해 총 $N$명의 학생이 새로이 입교하였다.

이번에 발표된 자대의 수는 총 $M$개로, 편의를 위해 각 자대에 $1$부터 $M$까지의 번호를 붙였다. 또한 $i$번 자대에는 $A_i$개의 티오가 발표되었다.

학생들은 모든 평가가 끝나고 각자 1, 2, 3지망 자대를 적어 제출했고, 결과만을 기다리고 있다.

하늘이는 자대 배치 결과가 너무 궁금했던 나머지 발품을 팔아 모두의 성적과 1, 2, 3지망 자대를 알아냈고, 모든 사람의 자대 배치 결과를 미리 계산하여 알려줄 것을 약속하였다. 하늘이를 도와 모든 사람의 자대 배치 결과를 구해보자.

자대 배치 규칙은 다음과 같다.

  • 성적에 따라 $1$등부터 순서대로 1, 2, 3지망 중 티오가 남아있는 최선의 자대에 배치한다.
  • 만약 1, 2, 3지망 자대에 모두 자리가 남아있지 않다면 후순위로 밀려 최종적으로 남아있는 자대 중에서 적절한 곳에 배치된다.

입력

첫번째 줄에 $N$, $M$이 공백으로 구분되어 주어진다. ($3 \leq M \leq N \leq 100$)

두번째 줄에 $A_1$, $A_2$, $\cdots$, $A_M$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq N$, $\sum A_i = N$)

다음 $N$개의 줄에 걸쳐서 $1$등부터 $N$등을 한 학생의 1, 2, 3지망 자대 번호가 공백으로 구분되어 주어진다. 각 사람의 1, 2, 3지망 자대 번호는 $1$ 이상 $M$ 이하의 정수이며 서로 다르다.

출력

$1$등부터 $N$등 학생이 배치받은 자대 번호를 공백으로 구분하여 순서대로 출력한다.

만약 1, 2, 3지망 자대에 배치되지 못하고 후순위로 밀려났을 경우 $-1$을 대신 출력한다.

예제 입력 1

5 4
1 2 1 1
3 4 2
3 1 2
3 1 2
3 1 4
3 1 4

예제 출력 1

3 1 2 4 -1

예제 입력 2

5 5
1 1 1 1 1
1 2 3
2 3 4
3 4 5
3 4 5
3 4 5

예제 출력 2

1 2 3 4 5

출처

Contest > 보라매컵 > 제6회 보라매컵 A번