Yukikaze 收到一个数组 $(a_1, a_2, \dots, a_n)$ 作为礼物。她决定玩弄这个数组。游戏包含 $q$ 个回合。在每一回合中，她会对数组 $a$ 的一个子区间内的所有元素执行某种操作（如下所示）：

1. 给定 $l, r, k$，对于子区间 $(a_l, a_{l+1}, \dots, a_r)$ 中的每个元素 $a_i$，将 $a_i$ 替换为 $a_i + k$。
2. 给定 $l, r, k$，对于子区间 $(a_l, a_{l+1}, \dots, a_r)$ 中的每个元素 $a_i$，将 $a_i$ 替换为 $a_i \times k$。
3. 给定 $l, r, k$，对于子区间 $(a_l, a_{l+1}, \dots, a_r)$ 中的每个元素 $a_i$，将 $a_i$ 替换为 $a_i^k$。
4. 给定 $l, r, k$，求子区间 $(a_l, a_{l+1}, \dots, a_r)$ 中所有元素 $k$ 次幂的和。换句话说，求 $\sum_{i=l}^r a_i^k$ 的值。
5. 给定 $l, r$，求子区间 $(a_l, a_{l+1}, \dots, a_r)$ 中所有元素的乘积。换句话说，求 $\prod_{i=l}^r a_i$ 的值。

在本题中，我们定义 $0^0 = 1$。

由于后两种操作的结果可能很大，你只需要求出它们对一个小整数 $p$ 取模后的结果。

输入格式

第一行包含两个整数 $n, p$ ($1 \le n \le 10^5, 2 \le p \le 30$)，表示数组 $a$ 的元素个数以及第 4 和第 5 种操作的模数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示数组 $a$ 的初始元素。

第三行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示要执行的操作次数。

接下来的 $q$ 行，每行包含 4 个整数 $t, l, r, k$ ($1 \le t \le 5, 1 \le l \le r \le n, 0 \le k \le 10^9$)，表示一种类型为 $t$ 的操作。注意，如果 $t = 5$，则保证 $k = 0$。

输出格式

对于每种类型为 4 或 5 的操作，输出结果对 $p$ 取模后的整数，每行输出一个。

样例

样例输入 1

5 29
5 2 4 1 3
9
4 2 4 1
1 1 3 2
2 2 4 3
3 3 5 2
5 3 3 0
4 1 5 2
2 3 5 0
3 2 4 0
4 3 4 1

样例输出 1

7
5
3
2