Sửa chữa nhà máy

Một nhà máy sản xuất sản phẩm theo ngày. Bình thường nhà máy sản xuất được tối đa $a$ sản phẩm mỗi ngày, nhưng hiện tại do máy móc hỏng hóc nên chỉ sản xuất được tối đa $b$ sản phẩm mỗi ngày.

Nhà máy dự định chọn một khoảng $k$ ngày liên tiếp để sửa chữa. Trong $k$ ngày sửa chữa, nhà máy không sản xuất được sản phẩm nào. Sau khi hoàn tất sửa chữa, năng lực sản xuất được khôi phục về tối đa $a$ sản phẩm mỗi ngày.

Ban đầu chưa có đơn hàng nào. Nhà máy nhận các cập nhật dạng $(d_i,a_i)$, nghĩa là có thêm $a_i$ đơn hàng được đặt cho ngày $d_i$. Mỗi đơn hàng cần đúng một sản phẩm được sản xuất chính xác vào ngày được chỉ định. Nhà máy có thể chọn hoàn thành bao nhiêu đơn hàng tùy ý trong khả năng sản xuất của ngày đó.

Xét một ngày bắt đầu sửa chữa $p$: các ngày $1,2,\dots ,p-1$ (trước khi sửa) sản xuất tối đa $b$ sản phẩm mỗi ngày; các ngày $p,p+1,\dots ,p+k-1$ (đang sửa) sản xuất $0$ sản phẩm; các ngày $p+k,\dots ,n$ (sau khi sửa) sản xuất tối đa $a$ sản phẩm mỗi ngày.

Bạn cần trả lời các truy vấn: với ngày bắt đầu sửa chữa $p$ cho trước, số đơn hàng tối đa có thể hoàn thành trong toàn bộ $n$ ngày là bao nhiêu?

Dữ liệu vào

• Dòng đầu chứa năm số nguyên $n$, $k$, $a$, $b$, $q$ — số ngày, số ngày sửa chữa, năng lực sản xuất đầy đủ, năng lực sản xuất hiện tại, và số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng là một trong hai loại:
  • 1 d a — có thêm $a$ đơn hàng cho ngày $d$.
  • 2 p — hỏi số đơn hàng tối đa có thể hoàn thành nếu bắt đầu sửa chữa vào ngày $p$.

Dữ liệu ra

Với mỗi truy vấn loại $2$, in ra một dòng chứa một số nguyên — số đơn hàng tối đa có thể hoàn thành trong $n$ ngày.

Ràng buộc

• $1\le k\le n\le 2·{10}^5$
• $1\le b<a\le {10}^4$
• $1\le q\le 2·{10}^5$
• Với truy vấn loại $1$: $1\le d\le n$, $1\le a\le {10}^4$.
• Với truy vấn loại $2$: $1\le p\le n-k+1$.
• Đảm bảo có ít nhất một truy vấn loại $2$.

Ví dụ