구간 연산

정수 $n$개로 이루어진 수열 $a_1, a_2, \dots, a_n$이 주어진다. 각 원소는 $[0, k-1]$ 범위의 정수이다. 이 수열에 대해 다음 두 종류의 연산을 모두 합쳐 $m$번 수행한다.

1. 구간 합 $a_c + a_{c+1} + \dots + a_d$ 를 출력한다.
2. $c \le i \le d$ 를 만족하는 모든 $a_i$ 를 $(a_i + l) \bmod k$ 로 바꾼다.

첫째 줄에 세 정수 $n$, $k$, $m$ 이 주어진다 ($1 \le n \le 100000$, $1 \le k \le 10$, $1 \le m \le 100000$). 둘째 줄에는 수열을 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ 이 주어진다 ($0 \le a_i \le k-1$).

이어지는 $m$개의 줄은 각각 하나의 연산을 나타낸다. 각 줄은 연산의 종류를 나타내는 정수 $z$ 로 시작한다. $z = 1$ 이면 구간 합 질의이며, 뒤에 두 정수 $c$, $d$ 가 이어진다. $z = 2$ 이면 구간 변경 연산이며, 뒤에 세 정수 $c$, $d$, $l$ 이 이어진다 ($1 \le c \le d \le n$, $0 \le l \le k-1$).

각 구간 합 연산마다 계산한 결과를 한 줄에 하나씩 출력한다.