A large quantity of goods are being produced by the factory every day. Consider the carrier machine of the factory which is used to transport the finished products from the workshop to the dispatch centre.

 

Finished products are kept on the carrier machine from one end, the machine takes the products to the dispatch centre, and the products are taken out at the dispatch center.

 

The machine can take n products in t minutes and return in t minutes. m products arrive at the terminal by a given schedule. What is the earliest time that all the products can be transported to the center? What is the minimum number of trips that the operator must make to deliver all products by that time?

 

 

Input

 

The first line of input contains c, the number of test cases. Each test case begins with n, t, m. m lines follow, each giving the arrival time for a product (in minutes since the beginning of the day). The operator can run the machine whenever he or she wishes, but can take only the products that have arrived up to that time.

 

Output

 

For each test case, output a single line with two integers: the time, in minutes since the beginning of the day, when the last product is delivered to the other side of the river, and the minimum number of trips made by the machine to carry the products within that time.

 

You may assume that 0

 

Example

Input: 2 2 10 10 0 10 20 30 40 50 60 70 80 90 2 10 3 10 30 40 Output: 100 5 50 2