题目描述

给定一个正整数 $p$，维护一个长度为 $n$ 的序列 $\{a\}$，支持以下四种操作或询问：

• 1 l r v，对所有整数 $i\in[l,r]$，令 $a_i\gets a_i+v$；
• 2 l r v，对所有整数 $i\in[l,r]$，令 $a_i\gets a_i\cdot v$；
• 3 l r，对所有整数 $i\in[l,r]$，令 $a_i\gets [p\nmid a_i]$；
• 4 x，求 $a_x\bmod p$ 的值。

其中 $[c]$ 是 Iverson Bracket，即若 $c$ 为真，则 $[c]=1$，否则 $[c]=0$。

注：任何数都是 $0$ 的因数，也就是 $x\mid 0$ 恒为真。

输入格式

第一行三个正整数 $n,p,q$ 表示序列长度、模数和操作或询问的个数。

第二行 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$ 描述序列 $\{a\}$。

后 $q$ 行，每行描述一个操作，形如以下四种中的一种：

• 1 l r v
• 2 l r v
• 3 l r
• 4 x

输出格式

若干行，每行回答一个询问。

样例输入

5 10 4
3 2 8 8 9
1 1 4 2
2 1 4 8
3 1 3
4 2

样例输出

1

测试点约束

本题采用捆绑测试。

数据范围：

• Subtask 1 (10pts)：$n,q\le 10^3$。
• Subtask 2 (20pts)：没有操作 3。
• Subtask 3 (30pts)：$p = 2$。
• Subtask 4 (40pts)：无特殊限制。

对于全部数据，$1\le n,q\le 2 \times 10^5$，$2\le p\le 10^9$，$0\le a_i,v<p$。