Fix a query of the second kind. We will consider how we can obtain the answer, which is \(\displaystyle \sum_{i=l}^r A_i\).

Here, define an integer sequence \(B\) of length \(2N\) as \(B=(A_1,A_2,\ldots,A_N,A_1,\ldots,A_N)\), which is a concatenation of two copies of \(A\) before any modification by queries of the first kind.

Then, \(\displaystyle \sum_{i=l}^r A_i\) can be represented as \(\displaystyle \sum_{i=l+C}^{r +C} B_i\), where \(C\) is the remainder when “the sum of \(c\) of all queries of the first kind given before the current query” is divided by \(N\). Since the elements of \(B\) is constant regardless of the queries, we can use precalculated cumulative sums to compute this.

The problem can be solved by appropriately implementing the algorithm above. The computational complexity is \(O(N+Q)\).

Sample code (Python 3)

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
for i in range(2 * n - 1, 0, -1):
    b[i - 1] += b[i]
rui_c = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        c = query[1]
        rui_c += c
        rui_c %= n
    else:
        l, r = query[1] - 1, query[2]
        print(b[l + rui_c] - b[r + rui_c])