Жуйя Лю обожает 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
Это реальные входные данные, которые ваша программа будет читать.