考虑一个素数 $p$。 以下所有运算均在模 $p$ 的乘法群中进行。 给定一个大小为 $n$ 的数组，处理 $q$ 个两种类型的询问：

• “$1\ l\ r\ x$”：将区间 $[l; r]$ 内的所有元素乘以 $x$；
• “$2\ l\ r$”：求由区间 $[l; r]$ 内的元素集合所生成的子群的阶。

关于部分定义的复习，请参阅下方的说明。

输入格式

输入的第一行包含三个整数 $p, n, q$：素数 $p$，数组大小 $n$ 以及询问次数（$2 \le p < 10^9$，$p$ 为素数，$1 \le n \le 10^5$，$1 \le q \le 10^5$）。 输入的第二行包含初始数组 $a$，大小为 $n$（$1 \le a_i < p$）。 接下来的 $q$ 行描述了询问。 第一类询问描述为 “$1\ l\ r\ x$”：将区间 $[l; r]$ 内的所有元素乘以 $x$（$1 \le l \le r \le n$，$1 \le x < p$）。 第二类询问描述为 “$2\ l\ r$”：求由区间 $[l; r]$ 内的元素集合所生成的子群的阶（$1 \le l \le r \le n$）。

输出格式

对于每个第二类询问，在单独的一行中输出答案。

样例

输入 1

17 3 7
10 16 2
2 2 3
2 1 2
2 2 2
1 1 2 3
2 1 1
2 3 3
2 1 3

输出 1

8
16
2
4
8
16

说明

在本节中，我们将给出题目中出现的所有群论术语的定义。所有定义均为常规定义，如果您熟悉群论基础知识，可以跳过本节。

群是一个具有结合律二元运算的集合。群在其运算下是封闭的：对于群中的任意两个元素 $a$ 和 $b$，$a \circ b$ 也是该群的一个元素，其中 $\circ$ 是二元运算。群中存在单位元（相当于乘法中的 1），并且每个元素都有逆元。

模素数 $p$ 的乘法群定义如下：群的元素是模 $p$ 的非零余数，即 $1, 2, \dots, p-1$。运算是模 $p$ 乘法。容易看出这是一个群。

子群是群 $G$ 的一个子集 $H$，它本身在 $G$ 的相同运算下构成一个群：特别地，它在二元运算下是封闭的。

由集合生成的子群：对于任意子集 $S \subseteq G$，$\langle S \rangle$ 是包含 $S$ 的最小子群 $G$。该子群是唯一的。

群的阶是群中元素的个数。