# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Misti Chor

By noshin_faiza · 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 $n$ pieces of misti and he wants to have them all. He has $m$ patils with him. Patils are numbered from $1$ to $m$. For each patil $i (1≤ i ≤ m)$, a range $l_i$ and $r_i$ is given. Bhootu can’t take less than $l_i$ pieces of misti and more than $r_i$ pieces of misti in $i$ 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 (1 ≤ n ≤ 10^{18})$ and $m(1 ≤ m ≤ 2 × 10^{5})$— total number of misti and total number of patil respectively.

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

## Output

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

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

If it is impossible to steal misti, print $-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



### Statistics

82% Solution Ratio

HSTU_TREENITYEarliest, 2M ago

bisnu_sarkarFastest, 0.0s

bisnu_sarkarLightest, 5.9 MB

user.365105Shortest, 290B