KSA 수열과 쿼리

시간 제한6초메모리 제한1024 MB

문제 설명

예제1

길이가 $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$인 쿼리에 대해 각 줄에 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다.