Bessie is going on a hiking excursion! The trail that she is currently traversing consists of n checkpoints labeled 1..n.

There are k tickets available for purchase. The i-th ticket can be purchased at checkpoint ci for price pi and provides access to all of checkpoints [ai, bi]. Before entering any checkpoint, Bessie must have purchased a ticket that allows access to that checkpoint. Once Bessie has access to a checkpoint, she may return to it at any point in the future. She may travel between two checkpoints to which she has access, regardless of whether their labels differ by 1 or not.

For each of i ∈ [1, n], output the minimum total price required to purchase access to both checkpoints 1 and n if Bessie initially has access to only checkpoint i. If it is impossible to do so, print −1 instead.

Input

The first line contains n (1 ≤ n ≤ 105) and k (1 ≤ k ≤ 105).

Each of the next k lines contains four integers ci (1 ≤ ci ≤ n), pi (1 ≤ pi ≤ 109), ai and bi (1 ≤ ai ≤ bi ≤ n) for each i (1 ≤ i ≤ k).

Output

Print n lines, one for each checkpoint.

Example

If Bessie starts at checkpoint i = 4, then one way for Bessie to purchase access to checkpoints 1 and n is as follows:

• Purchase the first ticket at checkpoint 4, giving Bessie access to checkpoints 2 and 3.
• Purchase the third ticket at checkpoint 2, giving Bessie access to checkpoint 7.
• Return to checkpoint 4 and purchase the second ticket, giving Bessie access to checkpoints 5 and 6.
• Purchase the fourth ticket at checkpoint 6, giving Bessie access to checkpoint 1.