You are the main developer in the foreign company Nurlash and KO inc. Company needs your help to write a new feature for a sorting robot. The robot controls n compartments sequentially numbered from 1 to n, and can perform two types of operations:

1. Add a container with number C to each compartment from the L-th to R-th;

2. Remove the last container from each compartment from L-th to R-th;

Container number is a positive integer not exceeding 109. You are given operations in the order in which they were performed by the robot. Determine, for each compartment, the number of container that is the last one on it after performing all the operations.

Input

First line contains two numbers n and m (1 ≤ n, m ≤ 105) - the number of compartments and the number of operations, respectively. Each of the next m lines contains three numbers L, R and C (1 ≤ L ≤ R ≤ 105, 0 ≤ C ≤ 109) - the description of operations. If C = 0, its operation of the second type, otherwise - of the first type.

All numbers are integers, separated with one space. It is guaranteed that there will be no operations that allow removal from empty compartments.

Output

Print in a single line n numbers, separated by space. The first number is the number of the last container in the first compartment, the second number is the number of the last container in the second compartment, and so on. If the compartment is empty, output 0.