Dọc theo một con sông có ~n~ đoạn đê liên tiếp, đoạn thứ ~i~ có chiều cao ban đầu là ~a_i~. Một đoạn đê được gọi là an toàn nếu chiều cao của nó không nhỏ hơn ngưỡng ~C~. Trong mùa mưa, trung tâm điều hành phải xử lý ~Q~ yêu cầu thuộc một trong bốn loại sau:

• Loại 1: cho ba số ~l, r, h~, yêu cầu hạ toàn bộ các đoạn đê trong đoạn ~[l, r]~ xuống không vượt quá ~h~, tức gán ~a_i = \min(a_i, h)~ với mọi ~l \le i \le r~.

• Loại 2: cho hai số ~l, r~, yêu cầu tính tổng chiều cao của các đoạn đê từ ~l~ đến ~r~.

• Loại 3: cho hai số ~l, r~, yêu cầu tìm chiều cao lớn nhất của một đoạn đê trong đoạn ~[l, r]~.

• Loại 4: cho hai số ~l, r~, yêu cầu đếm số cụm an toàn trong đoạn ~[l, r]~. Một cụm an toàn là một đoạn con liên tiếp cực đại chỉ gồm các đoạn đê an toàn.

Yêu cầu: Hãy trả lời mọi truy vấn loại 2, loại 3 và loại 4.

Input

• Dòng đầu chứa ba số nguyên dương ~n, Q, C~ ~(1 \le n, Q \le 200000, 0 \le C \le 10^9)~.

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

• ~Q~ dòng tiếp theo mô tả các truy vấn. Với truy vấn loại 1, ta có ~1\ l\ r\ h~ ~(1 \le l \le r \le n, 0 \le h \le 10^9)~. Với truy vấn loại 2, 3 hoặc 4, ta có ~t\ l\ r~ với ~t \in \{2, 3, 4\}~.

Output

Với mỗi truy vấn loại 2, loại 3 và loại 4, ghi ra trên một dòng kết quả tương ứng.

Scoring

Sample Input 1

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

Sample Output 1

2
29
1
6
0

Notes

• Ban đầu các đoạn an toàn là ~1, 3, 4, 5~, nên trong đoạn ~[1, 6]~ có hai cụm an toàn: ~[1, 1]~ và ~[3, 5]~. Vì vậy truy vấn đầu tiên cho kết quả ~2~.

• Sau truy vấn hạ đoạn ~[2, 5]~ xuống không vượt quá ~6~, dãy trở thành ~7, 2, 6, 5, 6, 3~ nên tổng trên đoạn ~[1, 6]~ là ~29~.

• Tiếp tục hạ đoạn ~[1, 4]~ xuống không vượt quá ~4~, chỉ còn vị trí ~5~ là an toàn. Do đó truy vấn loại 4 tiếp theo cho kết quả ~1~, truy vấn max trên ~[1, 6]~ cho kết quả ~6~. Cuối cùng sau khi hạ vị trí ~5~ xuống ~1~ thì không còn cụm an toàn nào.