[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]

Ignacio liked to take part in programming competitions such as the Argentinian Programming Tournament during his years as a university student. He was very happy, and when he graduated he got a good job. However, with time routine and life in the big city started to make him feel uneasy. So one day he decided to move to the countryside and start a new life as a farmer. He hadn't saved a lot of money, but it was enough to buy a circular field.

His life as a farmer didn't have a good start, as tragedy came before being able to enjoy his first crop. In the middle of his field a scarecrow was in charge of keeping birds at bay, but for some strange reason it was connected to a radioactive gas pipe coming from a nuclear plant close by. One morning the pipe broke and the gas escaped, destroying most of his field. Ignacio couldn't do anything about it, so only a thin strip on the border of his field remained intact. But that was not all, as the few surviving plants were soon attacked by a swarm of mutant insects. This time Ignacio wouldn't stand still, so he decided to fight the insect invasion with trained frogs.

On the perimeter of his circular field he created N ponds for the frogs, which he numbered from 1 to N in clockwise order. Then he bought R frogs in a shop specializing in trained circus frogs, and numbered them from 1 to R. During the night he put the frogs in the ponds, placing the i-th frog in pond number B_i. The frogs are very well trained, so at first light they will start to jump at a rate of one jump per minute. Each frog repeats a pattern of jumps every K minutes. The i-th frog will jump advancing A_i,1 ponds in clockwise direction during the first minute; it will then jump advancing A_i,2ponds in the same direction, and so on until the K-th minute, in which it will jump advancing A_i,K ponds. After that, the same pattern will be repeated, advancing A_i,1 ponds in the K+1-th minute, A_i,2 ponds in the K+2-th minute, etc. For example, let's consider the case with N = 5 ponds and K = 3. In this case, if frog number 1 starts in pond B₁ = 2, being its jumping pattern A_1,1 = 1, A_1,2 = 2 and A_1,3 = 1, during its fist few jumps it will land in the ponds in the following order: 2, 3, 5, 1, 2, 4, 5, 1, 3, 4, 5, ...

Ignacio is really quite unlucky, because the first frog suffers from a contagious disease which has turned it into a vegetarian. When the sun comes out and all the frogs start jumping, if a sick frog meets a healthy one in some pond, it will transmit it this disease. In our example with N = 5 and K = 3 if there are R = 2 frogs and the second frog starts at pond B₂ = 4 with a jumping pattern given by A_2,1 = 1, A_2,2 = 1 and A_2,3 = 1, it will visit the ponds in the order 4, 5, 1, 2, 3, 4, ... . Therefore, the first frog will transmit its disease to the second one after 5 minutes, when both meet at pond number 4. Generically, more and more frogs will get infected until either all of them are sick, or the remaining healthy frogs never meet with the sick ones, reaching at that point the maximum number of infected frogs.

While writing this story the night has gone by, and even if Ignacio noticed that the first frog is sick, he is now unable to catch it because it is trained so well. He will have to go directly to the trained circus frog shop to complain. As he wants to ask for a refund, he should wait until the disease spreads completely, reaching the maximum number of infected frogs. Ignacio doesn't want to wait longer than necessary, so in order to help him you should answer two questions: What is the maximum number of infected frogs? In which minute will the last transmission of the sickness take place?

Input

There are multiple test cases in the input file. For each test case, the first line contains three integer numbers N, R and K. The integer N represents the number of ponds in the field (2 ≤ N ≤ 10⁹), R represents the number of frogs (2 ≤ R ≤ 200) and K represents the number of minutes after which the frogs repeat their jumping pattern (1 ≤ K ≤ 200). The second line contains R integer numbers B₁, B₂, ..., B_R, representing the i-th number the initial position of the i-th frog (1 ≤ B_i ≤ N for i = 1, ..., R, with B_i≠ B_j if i ≠ j). The following R lines describe the behavior of the frogs. The i-th of these lines contains K integer numbers A_i,1, A_i,2, ..., A_i,K, representing the number of ponds the i-th frog advances in each of its K jumps, in the order in which they occur (1 ≤ A_i,j < N for i = 1, 2, ..., R and j = 1, 2, ..., K).

Output

For each test case, print a single line containing two integer numbers, representing the maximum number of infected frogs and the minute in which the last transmission of the disease takes place, respectively.

Example

Input:
5 2 3
2 4
1 2 1
1 1 1
1234 4 4
23 25 1000 67
20 4 26 222
18 28 1232 222
2 4 6 222
2 2 2 2
2 2 1
1 2
1
1

Output:
2 5
3 2
1 0