Problem Description

Today, Sherlock and Watson attended a lecture in which they were introduced to matrices. Sherlock is one of those programmers who is not really interested in linear algebra, but he did come up with a problem involving matrices for Watson to solve.

Sherlock has given Watson two one-dimensional arrays A and B; both have length $N$. He has asked Watson to form a matrix with $N$ rows and $N$ columns, in which the $j^\text{th}$ element in the $i^\text{th}$ row is the product of the i-th element of A and the j-th element of B.

Let $(x, y)$ denote the cell of the matrix in the x-th row (numbered starting from $0$, starting from the top row) and the y-th column (numbered starting from $0$, starting from the left column). Then a submatrix is defined by bottom-left and top-right cells $(a, b)$ and $(c, d)$ respectively, with $a \ge c$ and $d \ge b$, and the submatrix consists of all cells $(i, j)$ such that $c \le i \le a$ and $b \le j \le d$. The sum of a submatrix is defined as sum of all of the cells of the submatrix.

To challenge Watson, Sherlock has given him an integer $K$ and asked him to output the $K^\text{th}$ largest sum among all submatrices in Watson's matrix, with $K$ counting starting from $1$ for the largest sum. (It is possible that different values of $K$ may correspond to the same sum; that is, there may be multiple submatrices with the same sum.) Can you help Watson?

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of one line with nine integers $N$, $K$, $A_1$, $B_1$, $C$, $D$, $E_1$, $E_2$ and $F$. $N$ is the length of arrays $A$ and $B$; $K$ is the rank of the submatrix sum Watson has to output, $A$$_1$ and $B$$_1$ are the first elements of arrays A and B, respectively; and the other five values are parameters that you should use to generate the elements of the arrays, as follows:

First define $x_1 = A_1$, $y_1 = B_1$, $r_1 = 0$, $s_1 = 0$. Then, use the recurrences below to generate $x_i$ and $y_i$ for $i = 2$ to $N$:

• $x_i = (C \times x_{i-1} + D \times y_{i-1} + E_1) \pmod{F}$.
• $y_i = (D \times x_{i-1} + C \times y_{i-1} + E_2) \pmod{F}$.

Further, generate $r_i$ and $s_i$ for $i = 2$ to $N$ using following recurrences:

• $r_i = (C \times r_{i-1} + D \times s_{i-1} + E_1) \pmod{2}$.
• $s_i = (D \times r_{i-1} + C \times s_{i-1} + E_2) \pmod{2}$.

We define $A_i = (-1)^{r_i} \times x_i$ and $B_i = (-1)^{s_i} \times y_i$, for all $i = 2$ to $N$.

Output Format

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the $K^\text{th}$ largest submatrix sum in the matrix defined in the statement.

3
2 3 1 1 1 1 1 1 5
1 1 2 2 2 2 2 2 5
2 3 1 2 2 1 1 1 5

Case #1: 6
Case #2: 4
Case #3: 1

Hint

In case 1, using the generation method, the generated arrays A and B are [1, -3] and [1, -3], respectively. So, the matrix formed is

$$\begin{aligned} &[1, \ -3] \\ &[-3, \ 9] \end{aligned}$$

All possible submatrix sums in decreasing order are [9, 6, 6, 4, 1, -2, -2, -3, -3]. As K = 3, answer is 6.

In case 2, using the generation method, the generated arrays A and B are [2] and [2], respectively. So, the matrix formed is

$$\begin{aligned} &[4] \end{aligned}$$

As K = 1, answer is 4.

In case 3, using the generation method, the generated arrays A and B are [1, 0] and [2, -1] respectively. So, the matrix formed is

$$\begin{aligned} &[2, \ -1] \\ &[0, \ 0] \end{aligned}$$

All possible submatrix sums in decreasing order are [2, 2, 1, 1, 0, 0, 0, -1, -1]. As K = 3, answer is 1.

Limits

$1 \le T \le 20$.

$1 \le K \le \min(10^5, \text{total number of submatrices possible})$.

$0 \le A_1 \le 10^3$.

$0 \le B_1 \le 10^3$.

$0 \le C \le 10^3$.

$0 \le D \le 10^3$.

$0 \le E_1 \le 10^3$.

$0 \le E_2 \le 10^3$.

$1 \le F \le 10^3$.

Small dataset (Test set 1 - Visible)

$1 \le N \le 200$.

Large dataset (Test set 2 - Hidden)

$1 \le N \le 10^5$.