C. The Battle for the Ratings
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

During the prime time slot, television networks compete minute by minute to lead the audience ratings. From the data collected by audience meters, the number of viewers watching each channel at every instant is known.

Telemachus must analyze a time slot of $$$D$$$ minutes and determine for how long each channel has been the most watched. Specifically, the $$$D$$$ intervals $$$[m, m+1)$$$ are considered for $$$0 \le m \lt D$$$.

At minute 0, the initial audiences of all channels are known. Afterwards, updates are received: at certain minutes, the audience of some channels changes, remaining constant until the next update.

It is guaranteed that at every minute there is a unique channel with the maximum audience.

The following figure shows the evolution of the audiences in the sample input. The thicker segments indicate which channel leads during each interval.

Input

The input begins with a line containing an integer $$$T$$$ indicating the number of test cases that follow.

Each case begins with three integers $$$D$$$, $$$C$$$, and $$$N$$$: the duration of the observed time slot (in minutes), the number of channels, and the number of updates.

Then:

  • One line with $$$C$$$ integers: the audience of each channel at minute $$$0$$$, from channel $$$1$$$ to channel $$$C$$$.
  • $$$N$$$ lines, each with the format

    $$$$$$ m\ u\ c_1\ e_1\ \dots\ c_u\ e_u $$$$$$ which indicates that at minute $$$m$$$ (with $$$0 \lt m \lt D$$$) a total of $$$u$$$ channels (with $$$u \gt 0$$$) change their state: the channels $$$c_1, \dots, c_u$$$ change their audiences to $$$e_1, \dots, e_u$$$, respectively, from that minute onwards.

Updates are given in strictly increasing order of minute, and no channel appears more than once within the same update.

Output

For each case, print on separate lines every channel that has been the most watched for at least one minute, followed by the number of minutes it has led the audience.

Lines must be sorted by the number of minutes in decreasing order, and in case of a tie, by increasing channel identifier.

Scoring
  1. (8 points) $$$N = 0$$$
  2. (12 points) $$$C = 2$$$
  3. (15 points) Audiences only increase.
  4. (25 points) $$$C \le 1000$$$, $$$N \le 1000$$$
  5. (40 points) No additional constraints.
Example
Input
2
120 3 5
9000 1000 15000
15 2 1 13000 3 8000
30 1 3 11000
45 2 1 9000 2 3500
60 1 1 14000
100 3 2 5000 1 13000 3 10000
90 3 2
0 0 100
30 2 1 100 3 0
60 2 1 0 2 100
Output
1 90
3 30
1 30
2 30
3 30
Note
  • $$$1 \le T \le 1000$$$
  • $$$1 \le D \le 10^9$$$
  • $$$1 \le C \le 2\cdot 10^5$$$
  • $$$0 \le N \le 2\cdot 10^5$$$
  • $$$1 \le c_i \le C$$$, $$$0 \le e_i \le 10^9$$$
  • In an update $$$c_i\ e_i$$$, the value $$$e_i$$$ is different from the audience of channel $$$c_i$$$ immediately before minute $$$m$$$. In Subtask 3, it is strictly greater.
  • There are no ties for the maximum audience at any minute.
  • The sum of $$$C$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
  • The sum of all $$$u_i$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.