Ferry Loading II

Interview

Time limit1sMemory limit128 MB

Summary

Given car arrival times, ferry capacity n, and one-way time t, find the earliest finish time and the fewest one-way crossings to move all cars.

Level: Medium5 of 10
Topics: Greedy, Implementation, Simulation, Array
Solved: No attempts yet

Problem

A ferry carries cars across a river. On each crossing it can take up to $n$ cars; crossing to the far bank takes $t$ minutes, and returning to the near bank also takes $t$ minutes. Cars drive onto the ferry at one end, and once it reaches the far bank they drive off at the other end.

$m$ cars arrive at the ferry terminal according to a fixed schedule. The operator may launch the ferry at any moment, but can only load the cars that have already arrived by that moment. What is the earliest time by which every car can be carried to the far side of the river? And how many one-way ferry crossings are needed, at minimum, to deliver all cars by that time?

Input

The first line contains $c$ , the number of test cases.

Each test case begins with a line containing three integers $n$ , $t$ , and $m$ . The next $m$ lines each give the arrival time of one car, measured in minutes since the beginning of the day; the arrival times are listed in non-decreasing order.

You may assume that $0 < n, t, m < 1440$ .

Output

For each test case, print a single line with two integers separated by a space: the time (in minutes since the beginning of the day) at which the last car is delivered to the other side of the river, and the minimum number of one-way trips the ferry makes to carry all cars by that time.

Examples4

Example 1

Input

Expected output

100 5
50 2

Example 2
Input
```
1
5 7 1
0
```
Expected output
```
7 1
```
Example 3
Input
```
1
3 5 3
0
100
200
```
Expected output
```
205 1
```
Example 4
Input
```
1
4 1 8
0
10
20
30
40
50
60
70
```
Expected output
```
71 2
```