Do dịch bệnh đang căng thẳng mà tóc của Hương đang phát triển rất nhanh chóng. Để ngăn chặn tóc quá dài Hương quyết định đi cắt tóc. Nhưng vì để hạn chế tiếp xúc nơi đông người nên Hương muốn biết thời gian cắt tóc của cô ấy mất bao lâu để có chiều dài không quá l tại thời diểm cô ấy quyết định đi cắt tóc. Biết tóc của Hương có n chân tóc và bạn phải xử lý m truy vấn. Biết mỗi truy vấn sẽ thuộc hai loại :

1. Hương mất bao lâu để cắt tóc (Hương đang giả định tại thời điểm hiện tại mất bao lâu để cắt tóc)
2. chân tóc thứ pi của Hương mọc ra một đoạn có độ dài d

Biết Thợ cắt tóc sẽ cắt các chân tóc liền kề nhau mất 1s

Input

• Dòng đầu tiên gồm n,m,l ( ~(1\le n,m \le 10^5) , (1 \le l \le 10^9)~ ), số chân tóc của Hương, m truy vấn và độ dài mà Hương muốn
• Dòng tiếp theo chứa n số nguyên ~ a_1, a_2, ..., a_n~ ~(1 \le ai \le 10^9)~ độ dài chân tóc tại vị trí thứ i hiện tại của Hương
• m dòng tiêp theo chứa các truy vấn.

Output

• Với mỗi loại truy vấn 0 in ra thời gian Hương cắt tóc

Sample Input

4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0

Sample Output

1
2
2
1

Nguồn đề : https://codeforces.com/contest/1055/problem/B