KSA 수열과 쿼리

길이가 $N$인 수열 $A\_1, A\_2, \cdots, A\_N$과 정수 $K$가 주어진다. 이때, 다음 쿼리를 $Q$개 수행하는 프로그램을 작성해 보자.

• 1 $s\_i$ $e\_i$: $A\_{s\_i}, A\_{s\_i+1}, \cdots, A\_{e\_i}$에 $1$을 더한다.
• 2 $s\_i$ $e\_i$: $(A\_{s\_i}\bmod K) +(A\_{s\_i+1}\bmod K) +\cdots +(A\_{e\_i}\bmod K)$를 출력한다.

첫 번째 줄에 두 개의 정수 $N$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $A\_1,A\_2,\cdots,A\_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 정수 $Q$가 주어진다.

다음 $Q$개의 줄에 쿼리들의 정보가 주어지며, 그 중 $i$번째 줄에는 세 개의 정수 $q\_i$, $s\_i$, $e\_i$가 공백으로 구분되어 주어진다. $q\_i$는 $i$번째 쿼리의 종류를 나타낸다.

$q\_i = 2$인 쿼리에 대해 각 줄에 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다.

• $1\leq N\leq 2\times 10^6$
• $1\leq K\leq 10^9$
• $1\leq Q\leq 2 \times 10^4$
• $q\_i \in \\{1, 2 \\}$
• $1\leq s\_i \leq e\_i \leq N$
• $0\leq A\_i\leq 10^9$
• $q\_i=2$인 쿼리가 하나 이상 주어짐