#216994. [ICPC 2025 Shanghai R] No more regrets

After the provincial team selection, White fell into a long period of disappointment. She could not find any hope in her results. Even so, White continued her final training before the NOI. Besides her regular training, she also began to explore topics she had never had the chance to learn during her OI days — hoping that, before saying goodbye, there would be no more regrets.

Shaking off her wandering thoughts, White suddenly focused on a problem in front of her, a plain and boring data structure problem —

White has a sequence of integers . She will perform operations on this sequence. Each operation is one of the following three types:

• — Add to each element in the interval .
• — Assign each element in the interval to .
• — Query the value modulo .

Your task is to simulate all operations and output the results of all queries.

The st line of the input contains integers (), representing the number of elements and the number of operations.

The nd line contains integers (), representing the initial elements.

Each of the next lines describes an operation, in one of the formats:

• (, ), representing the Add operation.
• (, ), representing the Assign operation.
• (), representing the Query operation.

It’s guaranteed that for each during the whole process.

For each Query operation, print an integer in a single line — the result of the query modulo .

样例输入 1

5 8
2 3 5 4 1
3 1 5
3 2 4
2 4 5 2
3 1 5
3 2 4
1 1 2 5
3 1 5
3 2 4

样例输出 1

35
39
40
34
177
120

样例输入 2

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10 1
3 1 5
3 2 9
3 8 10
1 2 5 10
3 1 5
3 2 9
3 8 10
1 5 9 -5
3 1 5
3 2 9
3 8 10
1 2 5 -10
3 1 5
3 2 9
3 8 10
1 5 9 5
3 1 5
3 2 9
3 8 10

样例输出 2

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

In the st testcase:

The original sequence is . After the rd operation, it becomes , and after the th operation, it becomes .

For the st query, the answer is .

For the nd query, the answer is .