The first line of the input contains a single integer T (1≤T≤1000), the number of test cases.
Each test case includes two lines:
The first line contains 4 integers n, v, q, k ( 3≤n≤105 , 1≤v≤2, 2≤q<n, \textbf{q is even} , 2≤k≤105 ), denoting the size of S, the version of the game, the number of the numbers already taken, the parameter denoting the length of increasing subsequence.
The second line contains q integers denoting numbers taken out alreadly in order by steps.
It is guaranteed that ∑n,∑q∈[1,106].