409159: GYM103447 K Wonder Egg Priority

Memory Limit:1024 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Wonder Egg Prioritytime limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard 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.

ExampleInput
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}$$$.

加入题单

上一题 下一题 算法标签: