E. Mesh mante2 ya zalame
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Khaled and Saleem spent months building a complex logistics network, but everything crashed right on launch day. Watching the servers collapse on the screen, Saleem slammed his hand on the desk and shouted: "Mesh mante2 ya zalame!"

To salvage what they could, Khaled realized they had to track and identify the good vertices in their directed network to correct the system's routing and avoid bankruptcy.

Their network is represented as a directed graph containing $$$N$$$ vertices and $$$M$$$ edges and dosen't have self loops or multiple edges, and they have a constant factor $$$K$$$ that controls the routing cycles.

Due to continuous failures, the system faces $$$Q$$$ queries to test the network. In each query, you are given a subset $$$S$$$ of vertices of size $$$c$$$, along with two integers $$$a$$$ and $$$b$$$.

For each query and for each vertex $$$v$$$ in the graph, we define two values:

  • $$$cnt_1$$$: is the number of vertices $$$u$$$ in $$$S$$$ such that there is at least one directed walk$$$^\dagger$$$ from $$$u$$$ to $$$v$$$ of length $$$L_1$$$ satisfying $$$L_1 \equiv a \pmod K$$$.
  • $$$cnt_2$$$: is the number of vertices $$$u$$$ in $$$S$$$ such that there is at least one directed walk from $$$u$$$ to $$$v$$$ of length $$$L_2$$$ satisfying $$$L_2 \equiv b \pmod K$$$.
A vertex $$$v$$$ is considered a good vertex if $$$cnt_1$$$ is an odd number and $$$cnt_2$$$ is a positive even number.

For each query, help Khaled and Saleem find the number of good vertices to bring the system back online and prove that things can return to making logical sense.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \le N \le 6000$$$, $$$1 \le M \le 50000$$$, $$$1 \le K \le 20$$$).

Each of the following $$$M$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$), representing a directed edge from vertex $$$u$$$ to vertex $$$v$$$.

The next line contains a single integer $$$Q$$$ ($$$1 \le Q \le 100000$$$) representing the number of queries.

Each of the following $$$Q$$$ lines describes a query. The line begins with three integers $$$c$$$, $$$a$$$, and $$$b$$$ ($$$1 \le c \le N$$$, $$$0 \le a, b \lt K$$$), followed by $$$c$$$ distinct integers $$$s_1, s_2, \dots, s_c$$$ ($$$1 \le s_i \le N$$$) representing the vertices in the subset $$$S$$$.

It is guaranteed that the sum of $$$c$$$ over all queries does not exceed $$$200000$$$.

Output

For each query, print a single line containing the number of good vertices.

Example
Input
6 5 3
1 4
2 5
5 4
3 6
6 4
2
3 1 2 1 2 3
2 2 1 2 3
Output
1
0
Note

$$$^\dagger$$$ walk is a sequence of vertices and edges where both vertices and edges can be visited multiple times. The length of a walk is defined as the total number of edges traversed in this sequence (counting repetitions), not the number of distinct edges.