Strongly Connected Components

A direced graph is strongly connected if every two nodes are reachable from each other. In a strongly connected component of a directed graph, every two nodes of the component are mutually reachable.

Constraints

• 1 ≤ |V| ≤ 10,000
• 0 ≤ |E| ≤ 30,000
• 1 ≤ Q ≤ 100,000

Input

A directed graph G(V, E) and a sequence of queries where each query contains a pair of nodes u and v.

|V| |E| s0 t0 s1 t1 : s|E|-1 t|E|-1 Q u0 v0 u1 v1 : uQ-1 vQ-1

|V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (directed).

ui and vi represent a pair of nodes given as the i-th query.

Output

For each query, pinrt "1" if the given nodes belong to the same strongly connected component, "0" otherwise.

Example

Input

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

Output

1 0 1 1

inputFormat

Input

A directed graph G(V, E) and a sequence of queries where each query contains a pair of nodes u and v.

|V| |E| s0 t0 s1 t1 : s|E|-1 t|E|-1 Q u0 v0 u1 v1 : uQ-1 vQ-1

|V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (directed).

ui and vi represent a pair of nodes given as the i-th query.

outputFormat

Output

For each query, pinrt "1" if the given nodes belong to the same strongly connected component, "0" otherwise.

Example

Input

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

Output

1 0 1 1

样例

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

1
0
1
1

</p>