Problem Description

dkw is playing a game called ION8102. The game is divided into the prologue, Chapter 1, and Chapter 2.

She has cleared the prologue with full health and has arrived at the first level of Chapter 1.

This level is called Return Journey. She needs to reach a specified location, and along the way she must pass through $m$ mechanical doors.

Each mechanical door has a keyhole, and only a special key can be inserted. Inside there are $k$ dial locks. Each dial lock must be turned to the target position $a_i$ exactly in order to open the door. The maximum scale of each dial is $v$, with labels from $0$ to $v$. The initial position of every dial lock is $0$.

dkw has $n$ keys. Each key has $k$ rotation amounts $b_i$, meaning that if this key is turned by one full circle, it will move the corresponding dial lock in the door by that many positions.

Each mechanical door also has a turn limit $c$, which means that in total you can use keys to turn at most $c$ circles. Also, each key can only be turned forward, and only an integer number of circles can be turned.

The task requires opening these $m$ doors in order. Such an easy problem is of course solved instantly by dkw, but she is curious: for each door, how many different plans can open it successfully?

Two plans are different if and only if either the total number of circles is different, or the key used in some circle is different.

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$, with meanings as described above.

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

The next $m$ lines: first a non-negative integer $c$ representing the turn limit, followed by $k$ non-negative integers representing the target positions $a_i$ of this door in order.

Output Format

For each query, output one line with one non-negative integer representing the answer to this query, modulo $2333$.

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 

0
3
14
34
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 

4
0
0
0
465

Hint

This problem uses subtasks.

• 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 point, $v$ and $k$ are chosen from the corresponding relation in the table below.

Here, $maxk$ means that $k$ will not exceed this value.

Translated by ChatGPT 5