Numbers

문제

Let A be a sequence of numbers from 1 to N in random order (every number from 1 to N appears exactly once). 

We define the sequence B: 

• B[k] = 1 ... if and only if the first k numbers of the sequence A constist only of numbers 1 to k in random order (every number from 1...k appears exactly once), 
• B[k] = 0 ... otherwise. 

We know the sequence B and some of the elements of the sequence A. 

You are to write a program the will reconstruct the whole string A. 

입력

First line of the input file consists of integers N and M, 1 ≤ N ≤ 100000, 0 ≤ M ≤ N. 

Second line of the input file consists of the elements of the sequence B. 

Next M lines consist of the data about the known elements of sequence A, two integers X and Y. That means that the Xth element of sequence A is Y (A[X]=Y). This information will not be contradictory.

출력

The first and only line of the output file should consist of the elements of the sequence A; the numbers should be seperated by the space character. 

If there is no sollution, your program should write '-1' in the output file. 

Note: the sollution doesn't have to be unique.