Дано простое число p.

Дальше всё происходит в мультипликативной группе по модулю p.

Дан массив длины n и q запросов двух типов:

В первой строке записаны 3 целых числа p, n, q — простой модуль, размер массива и количество запросов (2 ≤ p < 10⁹, p — простое, 1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵).

Во второй строке записан изначальный массив a длины n (1 ≤ a_i < p).

В следующих q строках описаны запросы.

Запрос первого типа имеет вид “1 l r x” — все числа на отрезке [l; r] умножить на x (1 ≤ l ≤ r ≤ n, 1 ≤ x < p).

Запрос второго типа имеет вид “2 l r” — найти порядок подгруппы, порождённой элементами отрезка [l; r] (1 ≤ l ≤ r ≤ n).

На каждый запрос второго типа выведите ответ в отдельной строке.

Оригинально в этой задаче был TL = 10 sec. Возможно, вам потребуются неасимптотические оптимизации для получения AC. Have fun :)

В этой секции будут даны определения всем понятиям из алгебры, которые встречаются в тексте условия. Все определения совпадают с обычными, поэтому если вы знакомы с основами алгебры, можно пропускать секцию.

Группа — множество, на котором определена ассоциативная бинарная операция. Группа замкнута относительно операции: для любых двух элементов a и b группы a ○ b также является элементом группы, где ○ - бинарная операция. В группе имеется нейтральный элемент (аналог 1 для умножения), и каждый элемент множества имеет обратный.

Мультипликативная группа по простому модулю p задаётся следующим образом. Элементы группы — ненулевые остатки по модулю p, т.е. 1, 2, …, p−1. Операция — умножение по модулю p. Легко видеть, что это действительно группа.

Подгруппа — подмножество H группы G, которое является группой относительно операции, определённой в G.

Подгруппа, порождённая множеством. Для произвольного подмножества S ⊆ G, ⟨S⟩ обозначает наименьшую подгруппу G, содержащую S. Такая подгруппа определяется единственным образом.

Порядок группы — количество элементов группы.