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 ≤ ri ≤ 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 sni, lni (1 ≤ sni, lni ≤ 1000), entry time and duration of the job for the i‐the ordinary customer, respectively. For each i < j,  sni < snj.

 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  ≤  svi,  lvi  ≤  1000,  1  ≤  bvi  ≤  B), the entry time,duration of the job and the number of i‐th VIP’s desired counter,respectively. For each i < j,  svi < svj.

 

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 43
Submit

Source: AUT 2012