Bao Nhiêu Số Bé Hơn

Cho một dãy gồm $n$ số nguyên và đúng $n$ thao tác. Ngoài phép cộng đoạn, bạn cần đếm trên một đoạn có bao nhiêu giá trị hiện tại nhỏ hơn $c^2$. Dấu so sánh là nghiêm ngặt: giá trị bằng đúng $c^2$ không được đếm.

Các thao tác có ý nghĩa như sau:

• $0$ $l$ $r$ $c$: cộng $c$ vào mọi $a_i$ với $l\le i\le r$.
• $1$ $l$ $r$ $c$: in số chỉ số $i\in [l,r]$ thỏa $a_i<c^2$.

Input

• Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên $a_1,\dots ,a_n$. Tiếp theo là đúng $n$ dòng, mỗi dòng chứa bốn số nguyên $opt$ $l$ $r$ $c$.

Output

• Với mỗi thao tác $opt=1$, in số vị trí thỏa điều kiện nghiêm ngặt $a_i<c^2$.

Constraints

• $1\le n\le 5\cdot 10^4$.
• $1\le l\le r\le n$.
• Mọi phần tử ban đầu và $c$ nằm trong miền số nguyên $32$ bit có dấu.
• Giá trị $c^2$ và mọi giá trị hiện tại được xử lý bằng số nguyên $64$ bit có dấu.
• Mỗi đáp án nằm trong $[0,n]$.

Scoring

• Subtask $1$ ($50$ điểm): $n\le 2000$.
• Subtask $2$ ($50$ điểm): không có ràng buộc bổ sung.

Example

5
1 4 2 8 3
1 1 5 2
0 2 4 -2
1 1 4 1
1 2 5 3
1 3 3 0

3
1
4
0