Algebra on Segment

Consider a prime number $p$.

All operations below are performed in the multiplicative group modulo $p$.

You are given an array of size $n$. Process $q$ queries of two types:

• "1 $l$ $r$ $x$": multiply all elements of the segment $[l; r]$ by $x$.
• "2 $l$ $r$": find the order of the subgroup generated by the elements of the segment $[l; r]$.

See the notes below for the definitions.

The first line contains three integers $p$, $n$, $q$: the prime number, the size of the array, and the number of queries ($2 \le p < 10^{9}$, $p$ is prime, $1 \le n \le 10^{5}$, $1 \le q \le 10^{5}$).

The second line contains the initial array $a$ of size $n$ ($1 \le a_i < p$).

Each of the next $q$ lines is a query. A query of the first type has the form "1 $l$ $r$ $x$" ($1 \le l \le r \le n$, $1 \le x < p$) and multiplies all elements of $[l; r]$ by $x$. A query of the second type has the form "2 $l$ $r$" ($1 \le l \le r \le n$) and asks for the order of the subgroup generated by the elements of $[l; r]$.

For each query of the second type, print the answer on a separate line.

This section defines the group theory terms used in the statement. All definitions are standard, so readers who know the basics can skip it.

A group is a set with an associative binary operation. The group is closed under the operation, has an identity element (1 for multiplication), and every element has an inverse.

The multiplicative group modulo a prime $p$ has elements $1, 2, \ldots, p-1$, and the operation is multiplication modulo $p$. It is easy to check that this is a group.

A subgroup is a subset $H$ of a group $G$ that is itself a group under the operation of $G$. In particular, it is closed under the operation.

The subgroup generated by a set $S \subseteq G$ is $\langle S \rangle$, the smallest subgroup of $G$ that contains $S$. This subgroup is unique.

The order of a group is the number of elements in it.