SCROLL - Spreadsheet scrolling

no tags 

Sruthi is looking at a spreadsheet containing N rows. Only K rows of the spreadsheet are visible at a time (If the top row is i, the bottom row will be i+K-1). In the beginning, rows 1..K are visible. Sruthi needs to read certain values from rows r1,r2...rM in that order. It is possible to scroll the spreadsheet so that the rows j..j+K-1 can be viewed instead of the current i..i+K-1. This operation counts as one scroll and its scroll length is defined as |j-i|

Find the minimum number of scrolls required so that Sruthi can read of all the M values in the given order. As there may be more than one way to do this, also find the minimum total scroll length required to do the reading in so many scrolls.

Input

The first line of the input contains the integer T (<=20), the number of test cases to follow.

The description of each test case begins with a line containing 3 integers N(<=10^8), K(<=10^8) and M(<=50000) as defined in the problem. Following this are M lines giving the row numbers from which values have to be read sequentially.

Output

Output two space separated integers in a line per test case : The minimum number of scrolls required and the minimum scroll length required for the minimum number of scrolls.

Example

Input:
2
20 10 2
10
20
20 10 2
10
7

Output:
1 10
0 0

hide comments
Savan Popat: 2014-02-18 16:18:38

use long long instead of int

devu: 2012-07-16 15:03:57

Last edit: 2012-07-16 15:23:58
Raziman T V: 2011-10-26 05:01:52

Yes, do not assume any specific kind of ordering

Seshadri R: 2011-03-21 10:22:12

Can the M values in M lines be in any order (ascending, descending and random)?


Added by:Raziman T V
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOPC2011