The finals are coming and we, as sensitive people, cannot handle that much of stress. Each year some students will fail their tests because of nervousness or stressful situations in their normal lives, this is why the professors at a certain university have called you.

Each of the K students will tell you what they’re managing to do in some period of N days, some activities can be stressful (will be denoted by a positive integer) and some may be relaxing (denoted as a negative integer), the professors then will ask you if they put the final exams in a range of D days, how many students will be full of stress and how many students will not based on a threshold. This is, if the sum of the range of days is less or equal than a set threshold for each student.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

The first line of each test case will contain three numbers; K students, a threshold H of stress and the number N of days studied, after that, K lines will follow with N numbers separated by a space denoting the stress that the student Ki is expected to receive on the day Nj .

After that, a number Q will follow and on the next Q lines there will be two integers Ds and De denoting the days where the finals are to be applied (inclusively).

Output

For each test case you must print Q lines with two integers, the number of stressed students (if the stress exceeded the threshold) and the number of not stressed students separated by a dash and spaces for each period of days asked.

Example

Input:
1
5 10 5
5 1 2 5 -3
-1 -2 -3 -4 -5
1 6 91 1 2
1 0 9 7 2
1 1 2 3 2
4
1 5
1 3
3 5
3 3

Output:
2 - 3
1 - 4
2 - 3
1 - 4

Constraints

• 1 ≤ K ≤ 100

• 1 ≤ N ≤ 50,000

• 1 ≤ H ≤ 100,000

• -1,000 ≤ Ni ≤ 1,000

• 1 ≤ Q ≤ 20,000

• 1 ≤ Ds ≤ De ≤ N