CF1109E Sasha and a Very Easy Test

Egor 喜欢数学，不久前他在数学界获得了最高的认可——Egor 成为了红名数学家。为此，Sasha 决定祝贺 Egor，并送给他一道数学测试题作为礼物。这个测试包含一个长度为 $n$ 的整数数组 $a$，以及恰好 $q$ 个操作。操作分为三种类型： 1. “1 l r x”——将区间 $l$ 到 $r$ 内的每个数都乘以 $x$。 2. “2 p x”——将第 $p$ 个位置的数除以 $x$（保证可以整除）。 3. “3 l r”——查询区间 $l$ 到 $r$ 内所有元素的和。 由于和可能很大，Sasha 要求 Egor 计算的和需要对某个整数 $mod$ 取模。 但 Egor 作为红名数学家，没时间做这么简单的题目，同时又不想惹 Sasha 生气，于是他请你帮忙，计算所有第 $3$ 类操作的答案。

第一行包含两个整数 $n$ 和 $mod$（$1 \le n \le 10^5$，$2 \le mod \le 10^9 + 9$），分别表示数组的长度和取模的数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$），表示数组本身。 第三行包含一个整数 $q$（$1 \le q \le 10^5$），表示操作的个数。 接下来的 $q$ 行，每行满足以下三种格式之一： - 1 l r x（$1 \le l \le r \le n$，$1 \le x \le 10^5$），表示将区间 $l$ 到 $r$ 内的每个数都乘以 $x$。 - 2 p x（$1 \le p \le n$，$1 \le x \le 10^5$），表示将第 $p$ 个位置的数除以 $x$（保证可以整除）。 - 3 l r（$1 \le l \le r \le n$），表示查询区间 $l$ 到 $r$ 内所有元素的和。 保证至少有一个第 $3$ 类操作。

对于每个第 $3$ 类操作，输出一行答案，对 $mod$ 取模。

第一个样例： 初始数组为 $[4, 1, 2, 3, 5]$。 - 第一个操作，查询整个数组的和，$(4 + 1 + 2 + 3 + 5) \bmod 100 = 15 \bmod 100 = 15$。 - 第二个操作，将区间 $2$ 到 $3$ 的每个数都乘以 $6$，结果数组为 $[4, 6, 12, 3, 5]$。 - 第三个操作，查询区间 $1$ 到 $2$ 的和，$(4 + 6) \bmod 100 = 10 \bmod 100 = 10$。 - 第四个操作，将区间 $1$ 到 $5$ 的每个数都乘以 $1$，乘以 $1$ 不影响数组。 - 第五个操作，查询区间 $2$ 到 $4$ 的和，$(6 + 12 + 3) \bmod 100 = 21 \bmod 100 = 21$。 第二个样例： 初始数组为 $[4, 1, 2, 3, 5]$。 - 第一个操作，查询整个数组的和，$(4 + 1 + 2 + 3 + 5) \bmod 2 = 15 \bmod 2 = 1$。 - 第二个操作，将区间 $2$ 到 $3$ 的每个数都乘以 $6$，结果数组为 $[4, 6, 12, 3, 5]$。 - 第三个操作，查询区间 $1$ 到 $2$ 的和，$(4 + 6) \bmod 2 = 10 \bmod 2 = 0$。 - 第四个操作，将区间 $1$ 到 $5$ 的每个数都乘以 $1$，乘以 $1$ 不影响数组。 - 第五个操作，查询区间 $2$ 到 $4$ 的和，$(6 + 12 + 3) \bmod 2 = 21 \bmod 2 = 1$。 - 第六个操作，将第 $3$ 个位置的数除以 $4$，$\frac{12}{4}=3$，数组变为 $[4, 6, 3, 3, 5]$。 - 第七个操作，查询区间 $3$ 到 $4$ 的和，$(3 + 3) \bmod 2 = 6 \bmod 2 = 0$。 由 ChatGPT 4.1 翻译