Gahui and the Bank

Gahui runs a bank with a single counter. When Gahui's bank opens, there are N customers in the waiting line.

[Figure 1] The counter clerk and the N customers

The information for customer x is given by Px, the id of customer x, and tx seconds, the time needed to process their task.

There are M customers who enter after the bank opens. These customers become customers N+1, N+2, ..., N+M in the order they are given in the input.

The information for these customers is given by Px, the id of customer x, tx seconds, the time needed to process their task, and the fact that they entered cx seconds after the bank opened.

A customer joins the back of the waiting queue as soon as they enter the bank. Suppose customer N+1 enters cN+1 seconds after the bank opens.

[Figure 2] The situation cN+1 seconds after the bank opens

Customer N+1 joins the back of the waiting queue as soon as they enter the bank, so the state of the waiting queue cN+1 seconds after the bank opens is as shown above.

The clerk at the counter and the customers process tasks by the following algorithm.

1. If the customer at the front of the waiting queue is customer x, the clerk at the counter

   • if tx is greater than T, processes customer x's task for T seconds. After that, tx, the time needed for customer x's task to finish, decreases by T.
   • otherwise, processes customer x's task for tx seconds. After that, tx, the time needed for customer x's task to finish, becomes 0.

2. Customer x, the customer at the front of the waiting queue,

   • if tx, the time needed to finish their task, has become 0, leaves the bank.
   • otherwise moves to the back of the waiting queue. If a customer has arrived at this moment, they go behind the arrived customer.

3. If customers remain in the waiting queue, go back to step 1.

The clerk at the counter starts working when the bank opens.

Tell us which customer's task the clerk at the counter is processing from the moment 0 seconds have passed after the bank opens until W-1 seconds have passed.

The first line gives N, T, and W, separated by spaces.

From the second line, N lines give Px and tx, the time the customer needs to process their task, separated by spaces, starting with the customer at the front of the waiting queue at time 0.

The N+2-th line gives M, the number of customers who entered the bank after 1 second.

From the N+3-th line, M lines give Px, tx, and cx, separated by spaces. In the order given, they are customers N+1, ..., N+M.

This means that the customer with id Px needs tx seconds to process their task and entered the bank cx seconds after the opening time.

On the i-th line, print the id of the customer the bank clerk is processing when i-1 seconds have passed since the bank opened.

• N, T, W, and M are integers in the range [1, 2×105].
• There is no moment from 0 seconds to W-1 seconds at which the waiting queue is empty.
• The time a customer needs to process their task is an integer in the range [1, 109].
• A customer id is an integer in the range [1, 109], and no two are equal.
• For any integer x in [N+1, N+M], cx is an integer in the range [1, 109], and no two are equal. That is, after the bank opens, no two or more customers enter at the same time.