구간 위의 대수

소수 $p$가 주어진다.

아래의 모든 연산은 법 $p$에 대한 곱셈군에서 수행한다.

크기가 $n$인 배열이 주어진다. 다음 두 종류의 질의 $q$개를 처리한다.

• "1 $l$ $r$ $x$": 구간 $[l; r]$의 모든 원소에 $x$를 곱한다.
• "2 $l$ $r$": 구간 $[l; r]$의 원소들이 생성하는 부분군의 위수를 구한다.

정의는 아래 힌트를 참고한다.

첫 줄에 세 정수 $p$, $n$, $q$가 주어진다. 각각 소수, 배열의 크기, 질의의 개수이다. ($2 \le p < 10^{9}$, $p$는 소수, $1 \le n \le 10^{5}$, $1 \le q \le 10^{5}$)

둘째 줄에 크기 $n$인 초기 배열 $a$가 주어진다. ($1 \le a_i < p$)

다음 $q$개의 줄에 질의가 주어진다. 첫 번째 종류는 "1 $l$ $r$ $x$" 형식이며 ($1 \le l \le r \le n$, $1 \le x < p$), 구간 $[l; r]$의 모든 원소에 $x$를 곱한다. 두 번째 종류는 "2 $l$ $r$" 형식이며 ($1 \le l \le r \le n$), 구간 원소들이 생성하는 부분군의 위수를 구한다.

2번 종류의 각 질의에 대해 답을 한 줄에 하나씩 출력한다.

이 절은 문제에 나오는 군론 용어를 정의한다. 모든 정의는 관례적인 것이므로 기초를 아는 독자는 건너뛰어도 된다.

군은 결합법칙을 만족하는 이항 연산이 정의된 집합이다. 군은 연산에 대해 닫혀 있고, 항등원(곱셈에서의 1)이 있으며, 모든 원소에 역원이 있다.

법 $p$에 대한 곱셈군은 원소가 $1, 2, \ldots, p-1$이고, 연산이 법 $p$에 대한 곱셈인 군이다. 이것이 군임은 쉽게 확인할 수 있다.

부분군은 군 $G$의 부분집합 $H$로서, $G$와 같은 연산에 대해 그 자체로 군이 되는 것이다. 특히 연산에 대해 닫혀 있어야 한다.

집합이 생성하는 부분군은 임의의 부분집합 $S \subseteq G$에 대해, $S$를 포함하는 $G$의 가장 작은 부분군 $\langle S \rangle$이다. 이 부분군은 하나로 정해진다.

군의 위수는 군에 속한 원소의 개수이다.