Cho một dãy số $A$ gồm $n$ phần tử, sau đó Gấu thực hiện $q$ truy vấn thuộc một trong ba loại sau:

• SET $l$ $r$ $x$: Đặt $A[l]=A[l+1]=...=A[r]=x$.
• ADD $l$ $r$: Tăng $A[l],A[l+1],...,A[r]$ thêm $1$ đơn vị.
• COUNT $l$ $r$ $k$: Đếm số phần tử lớn hơn bằng $k$ trong đoạn $[l...r]$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n,q$ $(1\le n,q\le {10}^5)$.
• Dòng hai chứa $n$ số nguyên mô tả dãy $A$ $(0\le A_i\le {10}^5)$.

• $q$ dòng sau, mỗi dòng chứa truy vấn thuộc một trong ba loại:

  • SET $l$ $r$ $x$ $(1\le l\le r\le n,0\le x\le {10}^5)$.
  • ADD $l$ $r$ $(1\le l\le r\le n)$.
  • COUNT $l$ $r$ $k$ $(1\le l\le r\le n,0\le k\le {10}^9)$.

Dữ liệu ra

Gồm một dòng là đáp án của mỗi truy vấn COUNT.

Tính điểm

• Subtask 1 (20% số điểm): $1\le n,q\le 1000$.
• Subtask 2 (20% số điểm): Chỉ có truy vấn COUNT.
• Subtask 3 (20% số điểm): Trong mọi truy vấn ADD hoặc SET, đều có $l=r$.
• Subtask 4 (40% số diểm): Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

8 10
2 7 0 9 2 0 0 8 
COUNT 1 8 7
ADD 2 4 
SET 5 8 3
COUNT 3 7 3
SET 1 7 2 
ADD 4 5 
COUNT 1 6 2 
ADD 1 8 
COUNT 1 4 5
COUNT 3 8 2

Dữ liệu ra

3 4 6 0 6