수열 B로 수열 A 복원하기

1부터 N까지의 자연수가 각각 정확히 한 번씩 나타나는 수열 A가 있다. 즉, A는 1부터 N까지의 순열이다.

수열 B는 A로부터 다음과 같이 정의된다.

• B[k] = 1 : A의 처음 k개 원소 A[1], A[2], …, A[k]가 정확히 집합 {1, 2, …, k}를 이룰 때
• B[k] = 0 : 그렇지 않을 때

수열 B 전체와, 수열 A의 일부 원소가 A[X] = Y 형태로 주어진다. 이 조건들을 모두 만족하는 수열 A를 복원하여라.

조건을 만족하는 A가 여러 개일 수 있으므로, 그러한 A 중에서 사전순으로 가장 앞서는(가장 작은) 것을 출력한다. 조건을 만족하는 A가 존재하지 않으면 -1을 출력한다.

첫째 줄에 수열 B의 크기 N과 이미 알고 있는 A 원소의 개수 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100000, 0 ≤ M ≤ N)

둘째 줄에는 수열 B의 원소 B[1], B[2], …, B[N]이 공백으로 구분되어 주어진다. 각 원소는 0 또는 1이다.

다음 M개의 줄에는 이미 알고 있는 A의 원소가 두 정수 X와 Y로 주어지며, 이는 A[X] = Y를 뜻한다. (1 ≤ X, Y ≤ N) 주어지는 이 정보들 사이에는 모순이 없다.

조건을 만족하는 수열 A가 존재하면, 그중 사전순으로 가장 작은 것을 골라 A의 원소를 공백으로 구분하여 한 줄에 출력한다. 조건을 만족하는 A가 존재하지 않으면 -1을 출력한다.