Công viên giải trí Mountain vừa mở một trò tàu lượn mô phỏng. Đường ray gồm \(n\) đoạn ray nối tiếp nhau, đầu đoạn ray thứ nhất được cố định ở độ cao \(0\). Byteman, người vận hành, có thể thay đổi cấu hình đường ray bằng cách điều chỉnh độ chênh cao của một số đoạn ray liên tiếp. Độ chênh cao của các đoạn ray khác không đổi. Sau mỗi lần điều chỉnh, phần đường ray phía sau được nâng lên hoặc hạ xuống để các đoạn vẫn nối liền nhau, còn điểm bắt đầu vẫn ở độ cao \(0\).

Mỗi lượt chơi bắt đầu bằng việc phóng xe từ đầu đường ray với năng lượng đủ để đạt đến độ cao \(h\). Xe tiếp tục di chuyển chừng nào độ cao của đường ray không vượt quá \(h\) và xe chưa đến cuối đường ray. Với mỗi lượt chơi, hãy tính số đoạn ray mà xe đi qua trọn vẹn trước khi dừng lại.

Bộ mô phỏng biểu diễn đường ray bằng dãy \(n\) độ chênh cao \(d_1,\ldots,d_n\). Giá trị \(d_i\) là độ chênh cao, tính bằng xentimét, của đoạn ray thứ \(i\). Nếu sau khi đi qua \(i-1\) đoạn ray, xe ở độ cao \(H\), thì sau khi đi qua đoạn thứ \(i\), xe ở độ cao \(H+d_i\).

Ban đầu, tất cả các đoạn ray đều nằm ngang, tức là \(d_i=0\) với mọi \(i\). Các lượt chơi và các lần điều chỉnh diễn ra xen kẽ. Mỗi lần điều chỉnh được mô tả bởi ba số \(a,b,D\): đặt độ chênh cao của từng đoạn ray từ \(a\) đến \(b\), kể cả hai đầu, bằng \(D\). Nói cách khác, gán \(d_i=D\) với mọi \(a\le i\le b\).

Mỗi lượt chơi được mô tả bởi một số \(h\), là độ cao lớn nhất xe có thể đạt đến. Hãy xử lý các lần điều chỉnh và lượt chơi theo đúng thứ tự được cho.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Dòng đầu chứa số nguyên dương \(n\), là số đoạn ray.

Các dòng tiếp theo mô tả những lần điều chỉnh xen kẽ với các lượt chơi, kết thúc bằng dấu hiệu hết dữ liệu. Mỗi dòng có một trong ba dạng:

• I a b D: chữ cái in hoa I và ba số nguyên \(a,b,D\), yêu cầu gán \(d_i=D\) cho mọi \(a\le i\le b\).
• Q h: chữ cái in hoa Q và số nguyên \(h\), mô tả một lượt chơi với độ cao tối đa \(h\).
• E: chỉ chứa chữ cái in hoa E, đánh dấu kết thúc dữ liệu vào.

Các thành phần trên cùng một dòng được phân cách bởi một dấu cách.

Dữ liệu ra

Với mỗi lượt chơi, ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số đoạn ray xe đi qua trọn vẹn trong lượt đó. Dòng thứ \(i\) của kết quả ứng với lượt chơi thứ \(i\) trong dữ liệu vào.

Ràng buộc

• \(1\le n\le 1\,000\,000\,000\).
• Trong mỗi lệnh I, \(1\le a\le b\le n\) và \(-1\,000\,000\,000\le D\le 1\,000\,000\,000\).
• Trong mỗi lệnh Q, \(0\le h\le 1\,000\,000\,000\).
• Tại mọi thời điểm, độ cao của mọi điểm trên đường ray nằm trong đoạn \([0,1\,000\,000\,000]\) xentimét.
• Toàn bộ dữ liệu vào có không quá \(100\,000\) dòng.

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\le 20\,000\) và toàn bộ dữ liệu vào có không quá \(1000\) dòng.

Ví dụ

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E

4
1
0
3

Nguồn

IOI 2005.