Ієрархія#2946

Ієрархія

3 секунди

64 мегабайти

Дуже складна

У певній організації працює $n$ співробітників. Вважається, що співробітник $A$ є підлеглим співробітника $B$ , якщо:

1. $A$ є прямим підлеглим $B$ , або 2. Існує співробітник $C$ такий, що $A$ є прямим підлеглим $C$ , а $C$ є підлеглим $B$ .

Жоден співробітник не є власним підлеглим. Передача повідомлень в організації можлива лише між $A$ та $B$ , якщо $A$ є підлеглим $B$ або навпаки. Структура організації така, що повідомлення можна передати між будь-якими двома співробітниками. Для заданих співробітників $A$ та $B$ визначте, чи є $A$ підлеглим $B$ , чи $B$ — підлеглим $A$ , чи між ними не існує жодної підлеглості.

Вхідні дані

У першому рядку міститься число співробітників $n$ та кількість запитів $q$ .

Другий і третій рядки містять параметри запитів $X$ , $a$ , $b$ та $Y$ , $c$ , $d$ .

Далі йдуть $n$ рядків, які описують структуру організації. У рядку номер $(i + 3)$ (i+3) вказана інформація про прямих підлеглих $i$ -го співробітника: $k_{i}$ k_i — кількість прямих підлеглих, далі індекси цих $k_{i}$ k_i підлеглих.

Співробітники нумеруються від $0$ до $n - 1$ n-1.

Кожен запит має вигляд $(x_{j}, y_{j})$ (x_j, y_j), і відповіддю для кожного запиту повинно бути $1$ , якщо $y_{j}$ y_j є підлеглим $x_{j}$ x_j, $1$ , якщо $x_{j}$ x_j є підлеглим $y_{j}$ y_j, або $0$ , якщо жодної підлеглості між ними немає.

Тут

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

де $j = 1.. q - 1$ j = 1..q-1, а $sum_{j - 1}$ \mathrm{sum}_{j-1} — це сума відповідей (модулів) на перші $j - 1$ j-1 запитів.

Обмеження

$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

Вихідні дані

Для кожного запиту виведіть відповідь у окремому рядку, як описано вище.

Приклади

Приклад 1