Mamy podany ciąg n liczb całkowitych a₁, a₂, ..., a_n z przedziału [0, k-1]. Twoim zadaniem jest wykonanie na tym ciągu m operacji polegających na:</p>

1. podaniu sumy elementów a_c + a_c+1 + ... + a_d,
2. zamianie wartości każdej liczby a_i (c ≤ i ≤ d) na (a_i + 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 a₁, a₂, ..., a_n (0 ≤ a_i ≤ k - 1), gdzie a_i oznacza i-ty element ciągu. Następnych m wierszy opisuje kolejne zapytania.

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

출력 형식

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

예제 입력

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
3
3