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 pieces of misti and he wants to have them all. He has patils with him. Patils are numbered from to . For each patil , a range and is given. Bhootu can’t take less than pieces of misti and more than pieces of misti in th patil.
Help Bhootu to find a way to steal misti, or say that it is impossible.
The first line of input contains two integers and — total number of misti and total number of patil respectively.
Next lines contains of two integers each, and — minimum and maximum number of misti Bhootu can take in th patil.
If there is a way to steal misti, you have to print space separated integers in one line, where th integer represents the number of misti Bhootu will take in th patil.
If there are multiple ways, you can print any of them.
If it is impossible to steal misti, print .
Input | Output |
---|---|
15 4 3 7 1 7 2 4 5 5 | 4 4 2 5 |
Input | Output |
---|---|
25 4 3 7 1 7 2 4 5 5 | -1 |