L. Legendary Duty Scheduler
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

It was a bright morning at the Institute of Monkey Entertainment (also known as IME) when your favorite instructor of the Center of Annoyance (CA) selected you (through a totally random and unquestionably fair selection process) as the new Duty Scheduler.

For the next $$$T$$$ days, you're responsible for scheduling the daily duty roster: the schedule that determines which unfortunate student must pull duty and stand watch over some mysterious and highly classified location known as Ala.

There are $$$N$$$ students, numbered from $$$1$$$ to $$$N$$$.

  • On day $$$1$$$, student $$$1$$$ pulls duty.
  • On day $$$2$$$, student $$$2$$$ pulls duty.
  • On day $$$N + 1$$$, it wraps back.
And it goes on forever. Naturally, that would be way too simple. Now, students are coming to you with all kinds of dramatic requests:

Hey, I'm baixado now and can't pull duty for the next $$$x$$$ days. Take me off the list!

If someone gets baixado on day $$$d$$$ for $$$x$$$ days, they are taken off from the list immediately, and their turn is skipped to the next person still on the list. Then, on day $$$d + x$$$, they return to their original position on the list. Keep in mind someone can still stay baixado after the period of $$$T$$$ days, and everyone can be baixado at the same time, so the list would be empty. It is guaranteed only active people will ask to become baixado. If the list is empty (because too many people were baixado) and if some people return to the list on the same day, it'll restart normally beginning with the student with the lowest identification number.

You must now manage this chaos for the next $$$T$$$ days of scheduling while also handling $$$Q$$$ unpredictable queries from people who think you're a walking calendar. Your goal is to determine, for each day from $$$1$$$ to $$$T$$$, which person is going to pull duty on that day.

Will you rise to become the Legendary Duty Scheduler of CA? Or will you break down like every poor soul before you?

Input

The first line contains three integers $$$N$$$, $$$T$$$, and $$$Q$$$ $$$(1 \leq N, T, Q \leq 2 \cdot 10^5, Q \leq \lfloor T/2 \rfloor \cdot N)$$$ — the number of students and the number of queries. The next $$$Q$$$ lines describe the queries in the following format:

  • $$$d$$$ $$$p$$$ $$$x$$$: On day $$$d$$$, student $$$p$$$ tells you they cannot pull duty for the next $$$x$$$ days, starting from day $$$d$$$ $$$(1 \leq d \leq T, 1 \leq p \leq N, 1 ≤ x ≤ 10^9)$$$.
Each query can be given in any order.
Output

Output $$$T$$$ integers in a single line, indicating the student that is going to pull duty on each day. If there is no student to pull duty on such a day, print -1.

Examples
Input
5 5 2
1 2 2
2 3 1
Output
1 4 5 1 2
Input
5 15 3
7 3 1500
2 2 5
1 1 20000
Output
2 3 4 5 3 4 5 2 4 5 2 4 5 2 4
Input
10 30 10
6 4 3
8 8 3
4 7 5
6 1 9
11 4 5
2 5 6
16 1 3
9 2 3
11 3 3
9 9 3
Output
1 2 3 4 6 8 9 10 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 1 2 3 4 5
Note

In the first sample, 2 is off from day 1 to day 2 and 3 is off only on day 2. So the list starts with but on the second day the next available is 4 and then 5 on day 3. It cycles back to 1 and then 2 on day 5.

On the second sample case, 3 is off from day 7 to day 1500, meaning he is not returning on any day until day 15. 2 will be off from day 2 to day 6, and 1 will be off on all days until 15. The list cycles without 1 until day 5, in which 2 is out. Then the list goes on until day 8, in which 3 is out too. Here, 2 is already back and the list repeats the cycle [2, 4, 5] until the end of day 15.