K. Wonder Egg Priority
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ohto Ai holds $$$n$$$ wonder eggs. Each of them has a priority value initially. Let's say $$$p_i$$$ is the $$$i$$$-th egg's priority value. The priority values will change since they are wonder eggs that have miraculous power. Ai has found the changing pattern.

Ai is going to observe the wonder eggs in the next $$$q$$$ moments. At each moment, one of the following events will happen:

  1. Ai gets the changing coefficient $$$k$$$ of this time, and she knows for each of the $$$l$$$-th egg to the $$$r$$$-th egg, $$$p_i$$$ will change to $$$k^{p_i}$$$.
  2. No priority value changing happens, and Ai calculates the sum of the $$$l$$$-th egg to the $$$r$$$-th egg's priority value.

Ai wants to check if she gets the correct sum values. So for each event of the second type, she wants you to output the sum modulo $$$M$$$.

Input

The first line contains three integers $$$n, q, M~(1\le n, q, M \le 10^5)$$$, denoting the number of wonder eggs, the number of moments, and the modulus respectively.

The second line contains $$$n_{}$$$ integers $$$p_1, p_2, \cdots, p_n~(1\le p_i \le 10^5)$$$, denoting the initial priority value.

Following $$$q$$$ lines will be in one of the following format:

  1. $$$1 \; l \; r \; k~(1\le l \le r \le n, 1\le k \le 10^5)$$$, denoting an event of the first type.
  2. $$$2 \; l \; r~(1 \le l \le r \le n)$$$, denoting an event of the second type.
Output

For each event of the second type, print one integer in one line, denoting the answer.

Example
Input
5 7 5
1 2 3 4 5
2 2 5
1 1 3 1
2 1 4
1 2 4 2
2 1 5
1 3 5 2
2 1 5
Output
4
2
1
0
Note
  • At the beginning, the priority values are $$$\{1, 2, 3, 4, 5\}$$$.
  • For the first event, the answer is $$$2+3+4+5 = 14 \equiv 4\pmod{5}$$$.
  • After the second event, the priority values are $$$\{1, 1, 1, 4, 5\}$$$.
  • For the third event, the answer is $$$1+1+1+4 = 7 \equiv 2 \pmod{5}$$$.
  • After the fourth event, the priority values are $$$\{1, 2, 2, 16, 5\}$$$.
  • For the fifth event, the answer is $$$1+2+2+16+5 = 26 \equiv 1\pmod{5}$$$.
  • After the sixth event, the priority values are $$$\{1, 2, 4, 65536, 32\}$$$.
  • For the seventh event, the answer is $$$1+2+4+65536+32 = 65575 \equiv 0\pmod{5}$$$.