Руджія Лю обожнює Wario Land!
Я великий шанувальник серії ігор "Wario Land", тому вирішив створити дуже складну (насправді!!!) задачу про неї :) Особлива подяка Ерджину Чжоу за ідею та референсний код. І невелика подяка Венбіну Тангу за те, що нагадав мені, що в імені "Rujia Liu" також є літера L!
Уявімо, що на початку Wario Land є n місць. Земля майже занепала, тому доріг зовсім немає! Вам буде надано m операцій. Виконуйте їх одну за одною та виводьте результати.
Вхідні дані
Вхід містить кілька тестових випадків. У кожному тестовому випадку перший рядок містить три цілі числа n, m, k (1 ≤ n ≤ 50,000, 1 ≤ m ≤ 100,000, 2 ≤ k ≤ 33333). Місця пронумеровані від 1 до n. Другий рядок містить n цілих чисел V[i] (1 ≤ V[i] ≤ k), що представляють початкові значення скарбів кожного місця. Кожен з наступних m рядків містить операцію. Для кожної операції, 1 ≤ x, y ≤ n, 1 ≤ v ≤ k. Вхід завершується кінцем файлу (EOF). Розмір вхідного файлу не перевищує 10 МБ.
Вихідні дані
Для кожної операції типу-3 виведіть кількість місць і добуток їхніх значень скарбів за модулем k. Якщо немає шляху між x і y, або кожне місце на шляху має значення скарбу > v, виведіть один 0 (замість 0 0 або 0 1).
Обфускація
Щоб запобігти попередній обробці операцій, ми застосовуємо наступну схему обфускації:
Кожна операція типу-1 стає 1 x+d y+d Кожна операція типу-2 стає 2 x+d v+d Кожна операція типу-3 стає 3 x+d y+d v+d
Де 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
Це реальний вхід, який ваша програма буде читати.