Руджія Лю обожнює Wario Land!#2058
Я люблю серію ігор "Wario Land", тому хочу скласти дуже складну (справді!!!) задачу про неї :) Велика подяка Erjin Zhou за ідею та еталонний код. І маленька подяка Wenbin Tang за те, що нагадав мені, що "Rujia Liu" також містить літеру L!
Припустимо, на самому початку Wario Land є місць. Земля майже покинута, тому доріг зовсім немає! Вам буде дано операцій. Виконуйте їх по черзі та виводьте результати.
Вхід містить декілька тестових випадків. У кожному тестовому випадку в першому рядку містяться три цілих числа , , (1 \leq n \leq 50\,000, 1 \leq m \leq 100\,000, 2 \leq k \leq 33\,333). Місця пронумеровані від до . У другому рядку містяться цілих чисел V_i (1 \leq V_i \leq k) — початкові значення скарбів кожного місця. Далі йдуть рядків, кожен з яких містить одну операцію. Для кожної операції 1 \leq x, y \leq n, 1 \leq v \leq k. Введення завершується кінцем файлу (EOF). Розмір вхідного файлу не перевищує МБ.
Для кожної операції типу- виведіть кількість місць та добуток їхніх скарбів за модулем . Якщо між і немає шляху або кожне місце на шляху має скарб більший за , виведіть одне число 0 (не 0 0 і не 0 1).
Обфускація
Щоб ви не змогли попередньо опрацювати операції, ми застосовуємо наступну схему обфускації:
Кожна операція типу- перетворюється на x+d y+d Кожна операція типу- перетворюється на x+d v+d Кожна операція типу- перетворюється на x+d y+d v+d
Тут — останнє ціле число, яке ви вивели перед обробкою цієї операції. Якщо ви ще нічого не вивели, d=0.
Після обфускації приклад вхідних даних виглядає так:
4 8 39 2 3 4 5 1 1 2 3 2 3 5 1 1 3 3 2 3 5 1 25 28 3 27 28 28 3 11 12 13 3 4 5 2
Саме такі вхідні дані насправді прочитає ваша програма.
Приклад 1