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

문제

A를 1부터 N까지 자연수가 임의의 순서로 (1과 N 사이의 모든 자연수는 1번씩 등장한다) 이루어진 수열이라고 하자.

이 때, B를 다음과 같이 정의하자.

B[k] = 1 (수열 A의 처음 k개 원소가 1과 K사이의 숫자로만 이루어져 있을 때)

       0 (위의 경우가 아닐 때)

   

수열 B와 A의 일부 원소가 주어졌을 때, 수열 A를 구하는 프로그램을 작성하시오.

입력

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

둘째 줄에는 수열 B의 원소가 주어진다.

다음 M개 줄에는 수열 A의 알고 있는 원소가 두 숫자 X와 Y로 주어진다. (A[X] = Y) 이 정보에는 모순이 존재하지 않는다.

출력

수열 A의 원소를 공백으로 구분하여 출력한다. 만약, 정답이 없다면 '-1'을 출력한다.

예제 입력

5 1
0 0 1 0 1
2 3

예제 출력

2 3 1 5 4

힌트