Larry is collecting buckets of water. He has ~N~ (~1 \leq N \leq 2\cdot 10^5~) buckets in a line, each starting empty and having a capacity of ~K~ (~0 \leq K \leq 10^9~). Every once in a while, someone comes to pour some water in a continuous segment of buckets, pouring the same amount of water in each bucket.

Larry wants to know when each bucket will overflow.

Input Specification

The first line of input will consist of three integers: ~N~ ~K~ and ~Q~ ~(1 \leq Q \leq 2\cdot 10^5)~, indicating that ~Q~ pours happpened.

The next ~Q~ lines of input will each consist of three integers, ~a~, ~b~ ~(1 \leq a \leq b \leq N)~ and ~c~ ~(1 \leq c \leq 10^5)~, indicating someone poured ~c~ water into buckets in segment ~[a, b]~.

Output Specification

The output should consist of ~N~ space separated integers, the ~i~th integer indicating that the ~i~th bucket was filled after the ~a_i~th pour (starting at 1).

If a bucket is never filled, output ~-1~ instead.

Subtasks

Subtask 1 (10%)

~N,Q \leq 10^3~

Subtask 2 (90%)

No further constraints.

Sample Input

3 3 1
1 2 3

Sample Output

1 1 -1