# E :: Easy task

Time Limit: 5 Seconds Memory Limit: 65536 KB

You are a bank teller and head of the bank asked you to do a simple job. Given the information about the entry time of customers and the duration of his job, you are to calculate at which time and which counter he will be receiving services and when he is done.

There are B counters in this bank. Two kinds of customers come to this bank: ordinary people and VIP. For each customer we know his entry time and duration of his job.

We know that N ordinary customers come to the bank. Ordinary people get a number from the machine and wait until that number is called from one of the counters. The bank tellers do not work at their best for the ordinary customers. That is why after a teller deals with an ordinary customer, he rests for some time (which might be different from teller to teller) and then calls another number.

We know that V VIP customers come to the bank. Each VIP customer only works with one of the counters which he had specified before. They also never wait in line with the ordinary customers. Assume that A is a VIP customer. He enters the bank and goes directly to his specified counter. If there are other VIP customers in that counter, he waits until they are done. When there are no more VIP customers in front of him, he will get served. Whatever else the teller was doing at that time (resting or serving an ordinary customer) is interrupted and will be resumed later in the first available time.

Note that:

If a VIP customer comes to counter i where an ordinary person is just finishing receiving services, the ordinary customer finishes first and then it is the VIP’s turn.

If a VIP customer comes to counter i and the teller in charge of counter i has just finished his rest time, he won’t call any ordinary customers and starts dealing with the VIP.

If two counters i and j want to call the next ordinary customer together, the system will automatically assign the next ordinary customer to the counter with the smaller number and the next ordinary customer to the next counter.

If the resting time of a teller is over and there are no ordinary customers, he waits for the next customer and calls as soon one comes in.

## Input

The first line begins with an integer T (T ≤ 100), the number of tests. The first line of each test contains an integer B (1 ≤ B ≤ 20), the number of counters. The second line contains B integers ri (1 ≤ r_{i} ≤ 1000), the rest time for teller at the i‐th counter.

In the following line there is an integer N (1 ≤ N ≤ 100), the number of ordinary people. The following N lines each contain two integers s_{ni}, l_{ni} (1 ≤ s_{ni}, l_{ni} ≤ 1000), entry time and duration of the job for the i‐the ordinary customer, respectively. For each i < j, s_{ni} < s_{nj}.

Next line contains an integer V(1 ≤ V ≤ 100),the number of VIPs.The following V lines each contain three integers svi, lvi, bvi (1 ≤ s_{vi}, l_{vi} ≤ 1000, 1 ≤ b_{vi} ≤ B), the entry time,duration of the job and the number of i‐th VIP’s desired counter,respectively. For each i < j, s_{vi} < s_{vj}.

## Output

For each test you should print N + V lines. The first N lines each contains three integers, i‐th of which is start and finish time of i‐th ordinary customer and the number counter at which he was served, respectively.

The remaining V lines each contains two integers, i‐th of which is start and finish time of i‐th VIP.

## Sample Input

1 2 2 1 6 1 2 9 11 10 3 40 2 42 4 43 3 7 2 1 1 5 2 1 6 1 1 7 4 2 11 1 2 15 3 2 40 3 1

## Sample Output

1 4 1 9 20 1 12 15 2 40 42 2 43 47 1 43 46 2 2 3 5 7 7 8 7 11 11 12 15 18 40 43Submit

Source: AUT 2012