Problem Description

_O_v_O_ has arrived in a $k$-dimensional world.

The computer lab can be viewed as a $k$-dimensional cube of size $n^k$ (you can think of it as a $k$-dimensional coordinate system), where the coordinate on each dimension ranges from $1$ to $n$.

There are $m$ OIers. The $i$-th one is at $(a_{i,1},a_{i,2},\cdots,a_{i,k})$. Unfortunately, all OIers are slacking off.

There are also $x$ obstacles in the lab. The $i$-th obstacle is at $(b_{i,1},b_{i,2},\cdots,b_{i,k})$.

In addition, there are $y$ coaches. The $i$-th coach is at $(c_{i,1},c_{i,2},\cdots,c_{i,k})$.

A coach does not want to see OIers slacking off. As long as a coach and some OIer have exactly $k-1$ coordinates (dimensions) that are the same, and the line segment connecting them contains no other obstacle, OIer, or coach, then that OIer is caught slacking off.

For each coach, ask how many OIers they can catch slacking off.

Input Format

The first line contains two integers $n,k$, representing the side length of the cube and the number of dimensions.

The second line contains three integers $m,x,y$, representing the numbers of OIers, obstacles, and coaches.

Next come $m$ lines, each containing $k$ numbers. Line $i+2$ gives the position of the $i$-th OIer.

Next come $x$ lines, each containing $k$ numbers. Line $i+m+2$ gives the position of the $i$-th obstacle.

Next come $y$ lines, each containing $k$ numbers. Line $i+m+x+2$ gives the position of the $i$-th coach.

Output Format

Output one line with $y$ integers, where the $i$-th integer is the number of OIers seen by the $i$-th coach.

10 2
2 2 2
1 1
1 2
2 1
2 3
3 1
3 2

0 1

Hint

[Sample Explanation]

Pairs of an OIer and a coach that satisfy having $k-1$ equal coordinates are: OIer 1 with coach 1, and OIer 2 with coach 2. However, there is an obstacle between OIer 1 and coach 1, so the OIer will not be caught.

[Constraints]

This problem uses bundled testdata.

• Subtask #1 ($25\ \text{pts}$): $k=1$.
• Subtask #2 ($35\ \text{pts}$): $k=2$.
• Subtask #3 ($40\ \text{pts}$): $k=3$.

For $100\%$ of the testdata, $1\le n\le 10^3$, $\bf{1\le k\le 3}$, $m,x,y\ge1$, $m+x+y\le\min(10^3,n^k)$, $1\le a_{i,j} ,b_{i,j},c_{i,j} \le n$. It is guaranteed that no OIer, coach, or obstacle shares the same position.

Translated by ChatGPT 5