B. Adventure for Black
time limit per test
4 s
memory limit per test
256 megabytes
input
standard input
output
standard output

To make her adventure more fascinating, Kamome created a special lock for a treasure box said to contain "the island's secret." To make it challenging, she designed the lock to work with an initial sequence of numbers (let's call this sequence $$$a$$$). An adventurer trying to open the box would face a series of $$$q$$$ questions, or queries, one by one. Only by answering each query correctly would the next one be revealed. If any query was answered incorrectly, the adventurer would have to start over from the very first query. These queries come in two types:

  • $$$1$$$ $$$l$$$ $$$r$$$: Let $$$f(x,y)=\min\{a_x,a_{x+1},\dots,a_y\}$$$, the adventurer needs to answer $$$\displaystyle\sum_{i=l}^{r}f(i,r)$$$.
  • $$$2$$$ $$$u$$$: Append $$$u$$$ to the end of $$$a$$$. Note that it increases the length of $$$a$$$ by $$$1$$$.

Kamome, being the creator, naturally knew all the answers. However, fast forward 10 years, and you've just found this intriguing box. Unfortunately, time has taken its toll, and Kamome has forgotten all the crucial details and answers. Your task is to help Kamome open this box!

Input

The first line of each test contains three integers $$$n$$$, $$$q$$$, and $$$M$$$ ($$$1\le n,q\le 4\cdot 10^5$$$, $$$10^8\le M \lt 10^9$$$).

The second line of each test contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \lt M$$$).

Each of the following $$$q$$$ lines of each test contains three integers $$$p^\prime$$$, $$$x$$$, and $$$y$$$ ($$$0 \le p^\prime, x, y \lt 2^{31}$$$) that describe a query. To prevent you from knowing the query parameters directly, they are given in an obfuscated form. Let $$$Z$$$ be the answer to the most recent Type $$$1$$$ query you answered (if there hasn't been a Type $$$1$$$ query yet, then $$$Z$$$ is 0). You need to compute $$$p=(p^\prime+Z)\bmod 2+1$$$ to determine the type of the query:

  • For Type $$$1$$$ queries ($$$p=1$$$), the actual $$$l$$$ and $$$r$$$ are calculated as $$$l=(x+Z)\bmod N+1$$$ and $$$r=(y+Z)\bmod N+1$$$, where $$$N$$$ is the current length of $$$a$$$ at this point. It is guaranteed that $$$l\le r$$$.
  • For Type $$$2$$$ queries ($$$p=2$$$), the actual $$$u$$$ is calculated as $$$u=(x+Z)\bmod M$$$, and the integer $$$y$$$ has no meaning and can be ignored.

It is guaranteed that at least one of the queries is of Type $$$1$$$.

Output

For each Type $$$1$$$ query, output an integer — the answer to the query.

Example
Input
4 3 100000000
2 1 2 1
0 0 2
1 99999999 2121
2 7 20
Output
4
6
Note

In the first query, $$$Z=0$$$, $$$p=(0+0)\bmod 2+1=1$$$. So $$$l=(0+0) \bmod 4+1=1$$$ and $$$r=(2+0) \bmod 4+1=3$$$. The answer is $$$\min\{2,1,2\}+\min\{1,2\}+\min\{2\}=1+1+2=4$$$.

In the second query, $$$Z=4$$$, $$$p=(0+4)\bmod 2+1=2$$$. So $$$u=(99999999+4)\bmod M=3$$$, and the array becomes $$$[2,1,2,1,3]$$$.

In the third query, $$$Z=4$$$, $$$p=(2+4)\bmod 2+1=1$$$. So $$$l=(7+4) \bmod 5+1=2$$$ and $$$r=(20+4) \bmod 5+1=5$$$. The answer is $$$\min\{1,2,1,3\}+\min\{2,1,3\}+\min\{1,3\}+\min\{3\}=1+1+1+3=6$$$.