Farmer John has ~m~ apple trees on his farm. It's harvesting season! The usual workforce for farmer John's apple harvesting are Bessie the cow and her friends. However, he noticed that using cows as the main workers for apple harvesting is costly (it's not cheap to take care of cows), but the amount of harvested apples came with a slight loss (maybe it's the cows??!?).

To make harvesting less costly, as well as improving the farm's automation processed, farmer John has decided to invest in ~n~ robots, numbered from ~1~ to ~n~. These robots are very versatile: they can harvest apples, as well as transfer the apples to his barn. Only one parameter seem to affect the robot's work though: their heights. The robot with the fitting height for the apple trees will actually pull the apples, while the shorter robots, will stand below, catching the falling apples from the taller robot and moving them to the barn.

Before purchasing the robots, farmer John has planned the harvest carefully for each tree. For the ~i~-th tree (~1 \le i \le m~), he will pick two robots with indices ~u_i~ and ~v_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~). He wants the taller robot of the two to have a height of exactly ~y_i~ (to pick apples), and the shorter one to have a height of exactly ~x_i~ (to catch the apples and moving them to the barn) (~x_i \le y_i~). Though he hasn't figured out yet which robot should have which height.

Bessie the cow had her usual task taken away, but now she has a new task: to help farmer John purchase these robots (as well as maintaining them). Given farmer John's harvest plan, help Bessie to pick ~n~ robots for purchasing, so as to satisfy all of his plans. If there are multiple buying plans that satisfy all of the requirements, Bessie can pick any (farming is a lucrative business). If it is impossible to satisfy all of the requirements, then you need to point this out too (so Bessie can get her old job back).

Input

The first line contains two integers ~n~ and ~m~ (~2 \le n \le 10^5~, ~1 \le m \le 10^5~), the number of robots that farmer John intends to buy, and the number of apple trees on his farm, respectively.

The ~i~-th line of the next ~m~ lines contains ~4~ positive integers ~u_i~, ~v_i~, ~x_i~ and ~y_i~ (~1 \le u_i, v_i \le n~, ~u_i \ne v_i~, ~1 \le x_i \le y_i \le 10^9~), denoting a harvest plan for the ~i~-th plan.

Output

If it's impossible to buy ~n~ robots to satisfy all of farmer John's plans, output ~-1~.

Otherwise, output ~n~ integers, the ~i~ of which denoting the height of the ~i~-th robot. The height of any robot must not be lower than ~1~, but must also not exceed ~10^9~. If there are multiple answers, output any.

Scoring

• Subtask 1 (~15~ points): ~n = 2~, ~m = 1~

• Subtask 2 (~30~ points): ~n \le 6~

• Subtask 3 (~45~ points): ~n \le 16~.

• Subtask 4 (~60~ points): No additional constraints

The total score for this problem is ~150~.

Sample Input 1

2 1
1 2 3 4

Sample Output 1

3 4

Sample Input 2

6 3
1 3 2 3
3 5 1 3
5 1 1 2

Sample Output 2

2 2 3 3 1 1

Sample Input 3

3 2
1 2 1 1
2 3 2 2

Sample Output 3

-1

Notes

Let us denote ~h_i~ as the height of the ~i~-th robot.

In the first sample, there is ~m = 1~ tree in the farm. The farmer wants this tree to be harvested by robots ~1~ and ~2~, the taller out of which needs a height of ~4~, and the shorter one needs a height of ~3~. There are two ways to purchase two robots, the first way being ~h_1 = 3~ and ~h_2 = 4~, and the second way being ~h_1 = 4~ and ~h_2 = 3~

In the second sample, farmer John wants to buy ~n = 6~ robots to harvest ~m = 3~ trees in the farm. Only the robots ~1~, ~3~, and ~5~ are used, and to fit his requirements, the only way to purchase these three robots is ~h_1 = 2~, ~h_3 = 3~ and ~h_5 = 1~. The other three robots ~2~, ~4~, ~6~ are never used, and thus can have any valid height.

In the third sample:

• Robots ~1~ and ~2~ are needed to harvest the first tree, they both need a height of ~1~.

• Robots ~2~ and ~3~ are needed to harvest the second tree, they both need a height of ~2~.

Robot ~2~ cannot have both heights ~1~ and ~2~, so it's impossible to fit in all of farmer John's requirements.