G. Graph Problem
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ vertices and $$$m$$$ edges. You want to answer $$$q$$$ queries.

For each query, you are given $$$k_1, p_1,p_2, \dots, p_{k_1}$$$, $$$k_2, s_1, t_1, s_2, t_2, \dots, s_{k_2}, t_{k_2}$$$. For all $$$i$$$ ($$$1 \leq i \leq k_2$$$), answer whether there is a path from $$$s_i$$$ to $$$t_i$$$ if $$$p_1, p_2, \dots, p_{k_1}$$$ are deleted. Queries are independent.

Input

In the first line, $$$n, m$$$ ($$$1\leq n\leq 500, 0\leq m \leq n(n-1)$$$).

In the following $$$m$$$ lines, $$$u, v$$$ ($$$1\leq u, v\leq n, u\neq v$$$) — a directed edge in the graph. It's guaranteed that there is no parallel edges.

In the next line, $$$q$$$ ($$$1\leq q \leq 4\times 10^5$$$). To make sure you answer the queries online, the input is encrypted. The input can be decrypted using the following pseudocode: 


    cnt = 0
    for i = 1 ... q
        read(k1)
        for j = 1 ... k1
            read(p'[j])
            p[j] =(p'[j] + cnt - 1)         read(k2)
        for j = 1 ... k2
            read(s', t')
            s = (s' + cnt - 1)             t = (t' + cnt - 1)             cnt += query(s, t)
// if s can reach t, query return 1, otherwise, query return 0

In the following $$$2q$$$ lines, for each query:

  • In the first line, $$$k_1, p'_1, \dots, p'_{k_1}$$$. It's guaranteed that $$$p_i$$$ are distinct.
  • In the second line, $$$k_2, s'_1, t'_1, \dots, s'_{k_2}, t'_{k_2}$$$. It's guaranteed that all $$$s_i, t_i$$$ are different from all $$$p_i$$$.
  • It's guaranteed that $$$1\leq k_1\leq \min(n-2, 6), \sum {k_2} \leq 4\times 10^6, 1\leq p'_{i}, s'_i, t'_i\leq n$$$.
Output

For each query, output a binary string with length $$$k_2$$$ — the answer of query(s, t) in order.

Example
Input
5 4
1 2
2 3
3 4
4 5
2
1 4
2 1 5 1 3
3 5 3 4
1 1 2
Output
01
1
Note

It's recommended to use Fast IO.