#605 Sliding Window RMQ

Statement

Statement language

You are given a sequence $A_1,A_2,\ldots,A_N$ and an integer $K$ . For each $i=K,K+1,\ldots,N$ , consider the minimum of the $K$ consecutive elements $A_{i-K+1},\ldots,A_i$ .

The sequence is generated rather than provided directly. For every $i\geq1$ ,

A_i=(aA_{i-1}+c)\bmod m.

The values $A_0,a,c,m$ are given in the input.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each case, let $B_i=\min(A_{i-K+1},\ldots,A_i)$ for . Print on one line, where denotes bitwise XOR.

Constraints

$1\leq T\leq100\,000$ .
$1\leq K\leq10^6$ .

Subtasks

#	Score	Constraints
1	15	$N\leq2000$ . The sum of $N$ over all cases is at most $20\,000$ . The sum of $NK$ over all cases is at most .

Samples

Input

Output

5
0