Cho dãy ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~, số nguyên ~m~ và ~q~ truy vấn thuộc một hai loại:

1. Cho hai số nguyên ~k, x~, gán ~a_k \leftarrow a_k + x~. Test đảm bảo ~a_k~ không bao giờ âm.

2. Cho ba số nguyên ~l, r, y~, tính tổng các phần tử trong đoạn con ~a_l, a_{l+1}, \dots, a_r~ đồng dư ~y~ modulo ~m~. Nói cách khác, hãy tính:

   $$\sum_{l \leq i \leq r, \space a_i \equiv y \pmod m} a_i$$

Yêu cầu: Với mỗi truy vấn loại 2, in ra tổng cần tìm.

Input

Dòng đầu tiên chứa ba số nguyên ~n, m, q~ là kích thước mảng ~a~, hằng số cho trước và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~0 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Đối với truy vấn loại 1, dòng này chứa ba số nguyên ~1 \space k \space x~ (với ~1 \leq k \leq n~ và ~-10^9 \leq x \leq 10^9~).

• Đối với truy vấn loại 2, dòng này chứa bốn số nguyên ~2 \space l \space r \space y~ (với ~1 \leq l \leq r \leq n~ và ~0 \leq y < m~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~; ~1 \leq m \leq 10^9~.

• Subtask ~2~ (chiếm ~10\%~ số điểm): ~1 \leq n, q \leq 10^4~; ~m = 1~.

• Subtask ~3~ (chiếm ~70\%~ số điểm): ~1 \leq n, q \leq 10^4~; ~1 \leq m \leq 10~.

Sample Input 1

5 3 3
4 1 3 2 5
1 1 1
2 1 3 2
2 1 5 2

Sample Output 1

5
12