Misti Chor

Limits 2s, 512 MB

Bhootu likes to eat misti. As he is a mischievous kid, he has decided to steal misti from the nearby shop.

Now the shop has nn pieces of misti and he wants to have them all. He has mm patils with him. Patils are numbered from 11 to mm. For each patil i(1im)i (1≤ i ≤ m), a range lil_i and rir_i is given. Bhootu can’t take less than lil_i pieces of misti and more than rir_i pieces of misti in ii th patil.

Help Bhootu to find a way to steal misti, or say that it is impossible.

Input

The first line of input contains two integers n(1n1018)n (1 ≤ n ≤ 10^{18}) and m(1m2×105) m(1 ≤ m ≤ 2 × 10^{5})— total number of misti and total number of patil respectively.

Next mm lines contains of two integers each, lil_i and rir_i (1liri1012) (1 ≤ l_i ≤ r_i ≤ 10^{12}) — minimum and maximum number of misti Bhootu can take in ii th patil.

Output

If there is a way to steal misti, you have to print mm space separated integers in one line, where ii th integer represents the number of misti Bhootu will take in ii th patil.

If there are multiple ways, you can print any of them.

If it is impossible to steal misti, print 1-1.

Samples

InputOutput
15 4
3 7
1 7
2 4
5 5
4 4 2 5

InputOutput
25 4
3 7
1 7
2 4
5 5
-1