Kanna's scarf is coloured with patches of colours that can be numbered from ~1~ to ~N~. Kanna likes her scarf in a certain pattern and Edward needs to be able to recreate this scarf. Kanna is going to give sequential instructions of how she would like her scarf, starting from the default pattern where the patches are numbered in increasing order. At the ~i~-th step, she wants Edward to perform a knitting operation, taking the continuous segment of colours starting with colour ~L_i~ and ending with colour ~R_i~ and moving it right after colour ~K_i~ if ~1 \le K_i \le N~. If ~K_i = 0~, then she wants the continuous segment to be moved to the very front of the scarf.

Can you tell Edward what the scarf should look like after all ~Q~ steps?

Constraints

~1 \le N \le 10^6~

~1 \le Q \le 5 \times 10^5~

~1 \le L_i, R_i \le N~

~0 \le K_i \le N~

After the first ~i-1~ steps have been performed:

• Colour ~L_i~ appears no later than colour ~R_i~ in the scarf.
• ~K_i~ is not contained in the continuous segment of colours starting with colour ~L_i~ and ending with colour ~R_i~.

Input Specification

The first line contains ~2~ integers ~N~ and ~Q~.

The ~i~-th of the following ~Q~ lines contains ~3~ integers ~L_i~, ~R_i~, and ~K_i~.

Output Specification

As a space-separated sequence of ~N~ integers, output the sequence of colours on the scarf after all ~Q~ steps have been performed.

Sample Input

6 3
4 5 1
5 6 0
2 2 3

Sample Output

5 3 2 6 1 4

Explanation

Initially, the colours on the scarf are ~[1, 2, 3, 4, 5, 6]~.

After the first step, the colours on the scarf are ~[1, 4, 5, 2, 3, 6]~.

After the second step, the colours on the scarf are ~[5, 2, 3, 6, 1, 4]~.

After the final step, the colours on the scarf are ~[5, 3, 2, 6, 1, 4]~.