题目描述

You have a square $N$ by $N$ matrix $M$ of nonnegative integers. We would like to make a list of the maximum values in every sub-matrix of size $K$ by $K$ within $M$, and then find the sum of those values together. (Note that the same entry of $M$ might be the maximum value in more than one sub-matrix, in which case it will show up multiple times in the list.) Can you find that sum?

To simplify the input of the matrix, you are given two arrays $\mathbf{A}$ and $\mathbf{B}$ of length $N$, and two integers $\mathbf{C}$ and $\mathbf{X}$. Then the entry $M_{ij}$ (for the $i$th row and $j$th column of the matrix) equals $(\mathbf{A}_i \times i + \mathbf{B}_j \times j + \mathbf{C}) \pmod{\mathbf{X}}$, where $i$ and $j$ are in the range $[1, N]$.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with one line with four integers, $N$, $K$, $C$ and $X$. Then there are two lines with $N$ integers each, representing the arrays $\mathbf{A}$ and $\mathbf{B}$.

输出格式

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 sum of the maximum values in all sub-matrices of size $K$ by $K$.

3
1 1 1 5
1
1
2 1 5 11
1 2
3 4
3 2 3 109
6 4 3
2 1 5

Case #1: 3
Case #2: 19
Case #3: 80

提示

In the first test case, the matrix is:

3

So the sum of maximum values is $3$.

In the second test case, the matrix is:

9 3
1 6

So the sum of maximum values is $19$.

In the third test case, the matrix is:

11 11 24
13 13 26
14 14 27

Limits

$1 \le T \le 100$.

$1 \le A_i, B_i \le 100000$.

$1 \le C \le 100000$.

$1 \le X \le 1000000007$.

$1 \le K \le N$.

Small dataset (Test Set 1 - Visible)

$1 \le N \le 50$.

Large dataset (Test Set 2 - Hidden)

$1 \le N \le 3000$.