Vẫn là địa điểm phòng tin 2 quen thuộc, tuy nhiên lúc này lại có đến 3 cậu bé. Gấu, Phúc và Khoa. Gấu thì vẫn nổi tiếng vì sự dễ thương và khôn ngoan của mình, còn Khoa và Phúc lại được đồn là những kẻ nghiện phim tuyệt đối.

Xem phim nhiều đến mức hai bạn tự đề ra hai chỉ số ~L~ và ~A~ để đánh giá một bộ phim. Cụ thể có ~N~ bộ phim mà hai cậu định xem, bộ phim thứ ~i~ có mức tình cảm là ~l_i~ và mức hành động là ~a_i~. Một bộ phim được hai cậu gọi là đáng xem nếu ~\max(l_i - L, 0) + \max(a_i - A, 0) \leq E~. Với ~E~ là một giá trị cảm xúc của hai cậu.

Cụ thể số ~E~ này được tính như sau: Ban đầu ~E = 0~. Sau đó, nếu các cậu xem được một bộ phim thỏa mãn biểu thức trên thì ~E~ sẽ tăng lên ~1~. Lưu ý rằng, hai cậu sẽ không xem một bộ phim quá một lần.

Là một người bạn tốt, Gấu muốn giúp các bạn thay đổi trong ~Q~ ngày. Ngày thứ ~j~, Gấu sẽ thay bộ phim thứ ~p_j~ thành bộ phim khác có mức tình cảm là ~\lambda_j~ và ~\alpha_j~, với mỗi ngày như thế, Gấu đều tính lại chỉ số ~E~ nhằm ngăn hai cậu khỏi việc nghiện phim quá mức mà quên đi chuyện học tập.

Bạn hãy giúp Gấu tính lại chỉ số ~E~ trong ~Q~ ngày này nhé.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên ~N, Q, L, A~ ~(1 \leq N, Q \leq 5*10^5, 1 \leq L, A \leq 10^6)~.
• Dòng hai chứa ~N~ số nguyên mô tả dãy ~l~ ~(1 \leq l_i \leq 10^6)~.
• Dòng ba chứa ~N~ số nguyên mô tả dãy ~a~ ~(1 \leq a_i \leq 10^6)~.
• ~Q~ dòng sau, mỗi dòng gồm ba số nguyên ~p_j, \lambda_j, \alpha_j~ mô tả sự thay đổi ~(1 \leq p_j \leq N, 1 \leq \lambda_j, \alpha_j \leq 10^6)~.

Dữ liệu ra

Gồm ~Q~ dòng là kết quả cho ~Q~ ngày.

Tính điểm

• Subtask 1 ~(30\%~ số điểm~)~: ~1 \leq N, Q \leq 1000~.
• Subtask 2 ~(70\%~ số điểm~)~: Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

4 5 20 25
1 22 1 30
1 22 50 30
3 1 25
2 23 22
4 10 27
1 21 21
3 20 26

Đầu ra

3
2
4
4
0

Giải thích

• Dãy ~l~ sau ngày đầu: ~\{1, 22, 1, 30\}~.
• Dãy ~a~ sau ngày đầu: ~\{1, 22, 25, 30\}~.
• Ban đầu ~E = 0~.
  • Phúc và Khoa xem bộ phim ~1~, ~E = 1~.
  • Phúc và Khoa xem bộ phim ~2~, ~E = 2~.
  • Phúc và Khoa xem bộ phim ~3~, ~E = 3~.
  • Phúc và Khoa không xem bộ phim ~4~ do ~\max(30-20, 0) + \max(30-25,0) > 3~.