题目描述

小 A 有一个正整数序列 $a$ 和一个质数 $p$。他现在想让你支持 $q$ 次操作，操作分为两种：

1. 给定区间 $[l,r]$ 和一个正整数 $x$，将区间内所有 $a_i$ 都乘上 $x$。
2. 给定区间 $[l,r]$，问在这个区间内任选若干个 $a_i$，并将它们乘起来对 $p$ 取模，能得到多少种不同的结果。

选择时允许重复选相同的 $a_i$，也可以一个数都不选。若一个数都不选，则认为乘积为 $1$。

输入格式

第一行三个整数 $n,p,q$。

第二行 $n$ 个整数 $a_1,a_2,\\dots,a_n$。

接下来 $q$ 行，每行第一个整数 $op$：

• 若 $op=1$，接下来输入三个整数 $l,r,x$；
• 若 $op=2$，接下来输入两个整数 $l,r$。

输出格式

对于所有 $op=2$ 的操作，输出一行一个整数表示答案。

样例 1 输入

5 13 5
7 9 12 11 12
1 1 2 5
1 2 3 2
1 2 4 6
2 4 4
2 3 5

样例 1 输出

1
2

样例 1 解释

第一次操作后序列为：

[35, 45, 12, 11, 12]

第二次操作后序列为：

[35, 90, 24, 11, 12]

第三次操作后序列为：

[35, 540, 144, 66, 12]

第四次操作相当于询问只选择若干个 $66$ 相乘后对 $p=13$ 取模的结果数。由于

$$66^0 \equiv 66^1 \equiv 66^2 \equiv \cdots \equiv 1 \pmod {13},$$

所以只有 $1$ 种结果，答案为 $1$。

第五次操作中，所有选数方案得到的乘积对 $p=13$ 取模后只有 $1$ 和 $12$ 两种，答案为 $2$。

更多样例在下发文件中。

数据范围

对于全部测试点：

• $1\le n,q\le 10^5$；
• $1\le x,a_i<p\le 10^{14}$；
• $1\le l\le r\le n$；
• 保证 $p$ 是质数；
• 每个测试点 $5$ 分。

测试点编号	$n,q\le$	$p\le$	特殊性质
$1\sim 3$	$400$	$10^5$	无
$4\sim 6$	$5000$
$7\sim 9$	$10^5$
$10\sim 11$		$10^9$	保证当 $op=1$ 时 $l=r$
$12\sim 14$			无
$15\sim 20$		$10^{14}$