시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111100.000%

문제

Mamy podany ciąg n liczb całkowitych a1, a2, ..., an z przedziału [0, k-1]. Twoim zadaniem jest wykonanie na tym ciągu m operacji polegających na:

  1. podaniu sumy elementów ac + ac+1 + ... + ad,
  2. zamianie wartości każdej liczby ai (cid) na (ai + l) modulo k.

입력

W pierwszym wierszu wejścia znajdują się cztery liczby całkowite n, k, m (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10, 1 ≤ m ≤ 100 000). W kolejnym wierszu znajduje się n liczb całkowitych a1, a2, ..., an (0 ≤ aik - 1), gdzie ai oznacza i-ty element ciągu. Następnych m wierszy opisuje kolejne zapytania.

Na początku każdego zapytania pojawi się liczba zi, oznaczająca rodzaj zapytania. Jeżeli zi = 1, to jest to zapytanie o sumę elementów. Wówczas po liczbie zi pojawią się dwie liczby całkowite c, d. Natomiast jeżeli zi = 2, to zapytanie oznacza zmianę elementów w przedziale i po liczbie zi pojawią się trzy liczby całkowite c, d, l (1 ≤ cdn, 0 ≤ lk - 1), oznaczające liczby potrzebne do wykonania danej operacji.

출력

Dla każdej operacji sumowania należy wypisać w oddzielnym wierszu obliczony wynik.

예제 입력 1

4 3 6
0 0 0 0
2 1 1 1
1 1 4
2 1 2 1
1 1 4
2 1 3 1
1 1 4

예제 출력 1

1
3
3