Description

You are playing a galgame, but you find this gal confusing and give up. So you start writing a data structure problem instead.

Given a sequence of length $n$, there are $m$ operations. Each operation is one of the following:

1. Add $x$ to the range $[l, r]$.
2. For the range $[l, r]$, query

Input Format

The first line contains two integers $n, m$, the length of the sequence and the number of operations.

The second line contains $n$ integers, the sequence.

Each of the next $m$ lines is one of the following two operations.

• $1\ l\ r\ x$: add $x$ to the range $[l, r]$.
• $2\ l\ r\ p$: query the range $[l, r]$ with modulus $p$.

Output Format

For each query, output one number as the answer.

6 4
1 2 3 4 5 6
2 1 2 10000007
2 2 3 5
1 1 4 1
2 2 4 10

1
3
1

5 5
2 3 3 3 3
1 1 1 530739835
2 1 1 8356089
2 1 4 5496738
1 1 2 66050181
1 2 4 138625417

4306230
697527

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

Constraints:

• For 100% of the testdata, $n, m \le 500000$, each number in the sequence is in $[1, 2 \cdot 10^9]$, $p \le 2 \cdot 10^7$, and each added $x$ is in $[0, 2 \cdot 10^9]$.

There are 10 sets of testdata.

Translated by ChatGPT 5