Problem Description

dkw is playing a game called "ION8102," which consists of a prologue, the first chapter, and the second chapter.

She has successfully completed the prologue with full health and has now reached the first level of the first chapter.

This level is named "The Return," and she needs to reach a designated location, passing through $m$ mechanical doors along the way.

Each mechanical door has a keyhole that only accepts a special key. Inside, there are $k$ rotary locks, each of which must be precisely rotated to the target position $a_i$ to open the door. Each rotary lock has a maximum scale of $v$, numbered from $0$ to $v$, and each lock starts at position $0$.

dkw has $n$ keys, each with $k$ rotation amounts $b_i$, representing how many positions the corresponding rotary lock in the door can move per full rotation of the key.

Each mechanical door also has a rotation limit $c$, meaning that the total number of key rotations is limited to at most $c$, and each key can only be rotated in the forward direction, in integer increments.

The task requires sequentially opening these $m$ doors. This simple problem is easily solved by dkw, but she is curious: for each door, how many different ways are there to open it successfully?

Two methods are considered different if and only if the total number of rotations differs or if a different key is used for any rotation.

If you satisfy dkw's curiosity, you will receive a big gift from her—100 points!

Input Format

The first line contains four positive integers $n, m, k, v$, as described in the problem statement.

The next $n$ lines each contain $k$ non-negative integers, representing the rotation amounts $b_i$ for each key.

The following $m$ lines each start with a non-negative integer $c$ representing the rotation limit, followed by $k$ non-negative integers representing the target positions $a_i$ for the door.

Output Format

For each query, output a single non-negative integer representing the answer to that query, modulo $2333$.

Sample Input and Output

Input Sample #1

5 5 2 3
0 0 
1 2 
3 3 
2 1 
3 2 
1 3 0 
2 1 2 
3 0 1 
4 1 2 
2 0 1 

Output Sample #1

0
3
14
34
2

Input Sample #2

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

Output Sample #2

4
0
0
0
465

Notes/Hints

This problem uses subtask testing.

• Subtask 1 (9pts): $1 \le n, m, k, c, v \le 5$
• Subtask 2 (16pts): $1 \le n \le 10^5, 1 \le m, c \le 100, v = 1, k \le 12$
• Subtask 3 (17pts): $1 \le n \le 10^5, 1 \le m, c \le 100, v = 2, k \le 8$
• Subtask 4 (19pts): $1 \le n \le 10^5, 1 \le m, c \le 100, v = 3, k \le 6$
• Subtask 5 (16pts): $1 \le n \le 10^5, 1 \le m, c \le 100$
• Subtask 6 (23pts): $1 \le n \le 10^5, 1 \le m \le 5, 1 \le c \le 10^9$

For each test case, the values of $v$ and $k$ will be selected from the following table, where $maxk$ represents the maximum value for $k$.

见题面 Input 部分

见题面 Output 部分