Hierarchy — Eolymp

Input

The first line contains the number of employees $n$ and the number of queries $q$ .

The second and third lines contain the query parameters $X$ , $a$ , $b$ and $Y$ , $c$ , $d$ .

Then $n$ lines follow describing the organization's structure. The $(i + 3)$ (i+3)-rd line contains information about the direct subordinates of the $i$ -th employee: $k_{i}$ k_i — the number of direct subordinates, followed by the indices of these $k_{i}$ k_i direct subordinates.

Employees are numbered from $0$ to $n - 1$ n-1.

Each query is of the form $(x_{j}, y_{j})$ (x_j, y_j), and the answer for each query should be $1$ if $y_{j}$ y_j is a subordinate of $x_{j}$ x_j, $1$ if $x_{j}$ x_j is a subordinate of $y_{j}$ y_j, or $0$ otherwise.

Here,

x_{0} = X, y_{0} = Y

x_0 = X,\ y_0 = Y

x_{j} = (a x_{j - 1} + b + sum_{j - 1}) mod n, y_{j} = (c y_{j - 1} + d + sum_{j - 1}) mod n

x_j = (a x_{j-1} + b + \mathrm{sum}_{j-1}) \bmod n,\quad y_j = (c y_{j-1} + d + \mathrm{sum}_{j-1}) \bmod n

where $j = 1.. q - 1$ j = 1..q-1, and $sum_{j - 1}$ \mathrm{sum}_{j-1} is the sum of the answers (moduli) to the first $j - 1$ j-1 queries.

Constraints

$1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5

$1 \leq q \leq 5 \cdot 1 0^{5}$ 1 \leq q \leq 5 \cdot 10^5

$0 \leq X, a, b, Y, c, d < n$ 0 \leq X, a, b, Y, c, d < n

$n - 1 \leq k_{i} < n + 100$ n - 1 \leq k_i < n + 100

Output

For each query, print the answer in a separate line as described above.

Examples

Example 1

Loading