Operations

You are given a sequence of $n$ integers $a_1, a_2, \dots, a_n$, where every element lies in the range $[0, k-1]$. Perform $m$ operations of the following two kinds on this sequence.

1. Report the range sum $a_c + a_{c+1} + \dots + a_d$.
2. Replace every $a_i$ with $c \le i \le d$ by $(a_i + l) \bmod k$.

The first line contains three integers $n$, $k$, and $m$ ($1 \le n \le 100000$, $1 \le k \le 10$, $1 \le m \le 100000$). The second line contains $n$ integers $a_1, a_2, \dots, a_n$ describing the sequence ($0 \le a_i \le k-1$).

Each of the next $m$ lines describes one operation. Each line begins with an integer $z$ giving the operation type. If $z = 1$, it is a range-sum query and is followed by two integers $c$ and $d$. If $z = 2$, it is a range-update operation and is followed by three integers $c$, $d$, and $l$ ($1 \le c \le d \le n$, $0 \le l \le k-1$).

For each range-sum operation, print the computed result on its own line.