Tân tự nhận mình là người đẹp trai nhất lớp Tin. Nhưng Hiếu không chịu nên đã đố Tân một bài toán đơn giản để coi ai mới là người đẹp trai nhất?

Bài toán như sau: Cho một dãy số gồm ~n~ phần tử và một giá trị ~k~ không đổi. Cho ~q~ truy vấn sau:

— ~1~ ~l~ ~r~ ~x~: Giảm đi một lượng ~x~ trong đoạn ~[l, r]~.

— ~2~ ~l~ ~r~: Đếm số lượng phần tử có giá trị không vượt quá ~k~.

Input

Dữ liệu đầu vào gồm:

• Dòng đầu tiên: ~2~ số ~n, k~ (~1 \le n \leq 5 \times 10^5, 1 \le k \leq 10^9~).

• Dòng thứ hai: dãy số ~a~ có ~n~ phần tử (~1 \le a_i \le 10^9~).

• Dòng thứ ba: số lượng truy vấn ~q~ (~1 \le q \le 5 \times 10^5~).

• ~q~ dòng tiếp theo thuộc ~1~ trong ~2~ loại truy vấn:

  — ~1~ ~l~ ~r~ ~x~: Giảm đi một lượng ~x~ trong đoạn ~[l, r]~ ~(1 \le x \le 10^9)~.

  — ~2~ ~l~ ~r~: Đếm số lượng phần tử trong đoạn ~[l, r]~ có giá trị không vượt quá ~k~.

Output

Dữ liệu đầu ra:

Đáp án cho từng truy vấn loại ~2~ trên từng dòng.

Scoring

Sample Input 1

8 4
3 10 5 8 4 1 2 1
6
2 3 7
2 2 3
1 2 6 4
2 1 5
1 1 4 9
2 1 8

Sample Output 1

3
0
4
8

Notes

Ở truy vấn đầu tiên: ~2~ ~3~ ~7~, trong đoạn vị trí ~[3; 7]~ gồm các số tương ứng là ~[5; 8; 4; 1; 2]~ có ~3~ số thoả ~\le k = 4~ là ~4; 1; 2~ nên đáp án của truy vấn này là ~3~.

Ở truy vấn thứ hai: ~2~ ~2~ ~3~, trong đoạn vị trí ~[2; 3]~ gồm các số tương ứng là ~[10; 5]~ không có số nào thoả ~\le k = 4~ nên đáp án của truy vấn là ~0~.

Trong truy vấn thứ ba: ~1~ ~2~ ~6~ ~4~, ta giảm các số trong đoạn vị trí ~[2; 6]~ xuống ~4~ đơn vị ta có được dãy sau khi thực hiện là ~[3; 6; 1; 4; 0; -3; 2; 1]~.

Ở truy vấn thứ tư: ~2~ ~1~ ~5~, trong đoạn vị trí ~[1; 5]~ gồm các số tương ứng là ~[3; 6; 1; 4; 0]~ có ~4~ số thoả ~\le k = 4~ là ~3; 1; 4; 0~ nên đáp án của truy vấn này là ~4~.

Trong truy vấn thứ năm: ~1~ ~1~ ~4~ ~9~, ta giảm các số trong đoạn vị trí ~[1; 4]~ xuống ~9~ đơn vị ta có được dãy sau khi thực hiện là ~[-6; -3; -8; -5; 0; -3; 2; 1]~.

Ở truy vấn thứ sáu: ~2~ ~1~ ~8~, trong đoạn vị trí ~[1; 8]~ gồm các số tương ứng là ~[-6; -3; -8; -5; 0; -3; 2; 1]~ có ~8~ số thoả ~\le k = 4~ là toàn bộ các số trong dãy nên đáp án của truy vấn này là ~8~.