Problem Description

Tomoaki loves the idols from Tenkaichi Kingdom and only sings their songs at karaoke. There are a total of $ L $ songs from the idols of Tenkaichi Kingdom that can be sung at karaoke, and they are referred to as Song $ 1 $, Song $ 2 $, ..., Song $ L $. When Tomoaki sings Song $ i $ to the best of his ability, he always scores $ K_i $ points on the karaoke scoring system. Tomoaki never disrespects the songs of the idols from Tenkaichi Kingdom, so he always sings to the best of his ability.

The ranking is determined by the sum of the "adjusted scores" from the last $ M $ performances in the month. The "adjusted score" is calculated as $x + (x - \text{the average score of the song up to that point})$, where $ x $ is the score of the performance. The "average score of the song up to that point" is the average of the scores of that song from all previous performances (including the current one) in the month.

Using his superhuman programming skills, Tomoaki has predicted the timing and scores of all the songs related to the idols from Tenkaichi Kingdom that will be sung this month. According to his prediction, the $ i $-th person this month will sing Song $ A_i $ and score $ S_i $ points. The month has just started, and no one has sung any songs from the idols of Tenkaichi Kingdom yet. Tomoaki can sing at any timing he likes, and he can sing as many times as he wants between any two people singing, as well as before the first person and after the last person. Tomoaki has not predicted next month's events and always sings to the best of his ability, so he aims to sing exactly $ M $ times this month to aim for the top of the ranking. Tomoaki wants to know the optimal strategy to maximize the sum of his adjusted scores over $ M $ performances. Therefore, assuming Tomoaki's predictions are correct, write a program to determine the optimal timing for Tomoaki to sing.

Input Format

The input is given from the standard input in the following format:

$ L $ $ N $ $ M $ $ K_1 $ $ K_2 $ .. $ K_L $ $ A_1 $ $ S_1 $ $ A_2 $ $ S_2 $ : $ A_N $ $ S_N $

• The first line contains the number of songs from the idols of Tenkaichi Kingdom, $L\ (1 ≦ L ≦ 100,000)$, the number of times other than Tomoaki will sing a song from the idols of Tenkaichi Kingdom this month, $N\ (1 ≦ N ≦ 100,000)$, and the number of times Tomoaki will sing this month, $M\ (1 ≦ M ≦ 100,000)$, separated by spaces.
• The second line contains $ L $ numbers separated by spaces, representing the possible scores Tomoaki can achieve when singing the songs from the idols of Tenkaichi Kingdom. The $i\ (1 ≦ i ≦ L)$-th number $K_i\ (68.000 ≦ K_i ≦ 100.000)$ represents the score Tomoaki can achieve with the $ i $-th song.
• The next $ N $ lines contain the data of the songs sung by others and their scores, one line per performance. The $i\ (1 ≦ i ≦ N)$-th line contains the integer $A_i\ (1 ≦ A_i ≦ L)$ representing the song number and the score $S_i\ (68.000 ≦ S_i ≦ 100.000)$ achieved at that time, separated by spaces. - $ K_i $ and $ S_i $ are given exactly 3 decimal places.

Output Format

Output $ M $ lines representing Tomoaki's optimal strategy. Each line should contain two integers $ T_i $ and $ B_i $ separated by spaces, where $ T_i $ represents the timing of the $ i $-th performance by Tomoaki and $ B_i $ represents the song he will sing. The output must satisfy $ 0 ≦ T_1 ≦ T_2 ≦ ... ≦ T_M ≦ N $. $ T_i = k $ means that Tomoaki will sing the $ i $-th song $ B_i $ right after exactly $ k $ performances by others. If there are multiple optimal strategies, output any one of them. End the output with a newline.

Sample Input and Output

Sample Input #1

1 5 3
80.000
1 68.000
1 70.000
1 85.000
1 72.000
1 68.000

Sample Output #1

2 1
2 1
5 1

Sample Input #2

2 2 2
90.000 90.000
1 80.000
2 80.000

Sample Output #2

2 2
2 1

Sample Input #3

4 8 9
78.245 74.123 79.254 81.111
1 69.241
2 68.000
3 81.255
4 80.582
4 80.895
3 87.433
2 100.000
1 76.365

Sample Output #3

1 1
1 1
4 4
5 4
5 4
5 4
5 4
5 4
5 4

Notes/Hints

Partial Points

• If you correctly solve all test cases where $ L = 1 $ and $ 1 ≦ N, M ≦ 2,000 $, you will be awarded 30 points as partial credit.
• If you correctly solve all test cases where $ 1 ≦ L, N, M ≦ 2,000 $, you will be awarded an additional 30 points as partial credit.

见题面 Input 部分

见题面 Output 部分