스트릭 채우기

시간 제한1초메모리 제한1024 MB

요약
K일 각각에 어떤 문제를 제출하거나 프리즈를 쓸지 정한다. 걸리는 시간이 d인 문제는 제출일까지 d일을 차지한다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 구현
정답자
아직 제출이 없습니다

문제

solved.ac 사이트에는 문제를 며칠 연속으로 풀었는지 보여주는 지표가 있는데, 이를 스트릭이라고 한다. 그리고 문제를 풀어서 제출하지 않은 날에 사용해서 스트릭이 끊기지 않게 하는 아이템을 스트릭 프리즈라고 한다.

세우는 KK일 동안 solved.ac 스트릭을 채우기 위해 풀어야 할 NN개의 문제와 MM개의 스트릭 프리즈를 준비했다.

스트릭 KK일을 채우려면 KK일 동안 매일 이전에 풀지 않았던 문제를 11문제 이상 풀어서 제출하거나 스트릭 프리즈 11개를 사용해야 한다. 이미 푼 문제는 다시 제출해도 스트릭이 채워지지 않는다.

NN개의 문제 중 ii번 문제는 푸는데 d_id\_i일이 걸리며 ii번 문제를 푸는 동안 도중에 다른 문제를 풀 수 없다. 즉, ii번 문제를 풀기 시작한 날을 포함하여 d_i−1d\_i - 1일 동안은 스트릭 프리즈를 사용하거나 이전에 풀었던 문제를 제출해 스트릭을 채워야 하고, d_id\_i일째부터 ii번 문제의 풀이를 제출해 스트릭을 채울 수 있다.

세우가 NN개의 문제와 MM개의 스트릭 프리즈를 이용해 스트릭 KK일을 채울 수 있는지 알아보고, 채울 수 있다면 어떻게 채워야 되는지 알려주자.

입력

첫째 줄에 N,M,KN, M, K가 공백으로 구분되어 주어진다.

둘째 줄에 d_1,d_2,⋯ ,d_Nd\_1, d\_2, \cdots, d\_N이 공백으로 구분되어 주어진다.

출력

KK일 동안 스트릭을 채우는 방법이 존재한다면, 첫째 줄에 KK개의 정수를 공백으로 구분하여 다음 규칙으로 출력한다.

  • ii번째 정수는 ii일째에 스트릭을 채운 방식으로, 00이면 스트릭 프리즈를 사용한 날, jj라면 그날 jj번 문제를 제출한 것을 의미한다. (1≤j≤N)(1 \leq j \leq N)
  • 스트릭을 채우는 방법이 여러 가지라면 그중 아무거나 하나를 출력한다.

만약 KK일 동안 스트릭을 채우는 방법이 없는 경우, -1을 출력한다.

제한

  • 1≤N,M,K≤200,0001 \leq N, M, K \leq 200\\,000
  • 1≤d_i≤200,0001 \leq d\_i \leq 200\\,000

입력으로 주어지는 모든 수는 정수이다.

예제2

  1. 예제 1

    입력
    4 4 6
    3 4 2 5
    
    예상 출력
    0 0 0 2 0 3
    
  2. 예제 2

    입력
    3 2 5
    1 4 2
    
    예상 출력
    -1