406013: GYM102218 F Freddy and the Chocolate Factory

As you may know, Freddy is a big fan of chocolate, so he decided to open his own Chocolate factory.

He has been working for several months without any issues but this week he faced a problem. The chocolate machine is not working correctly.

He usually produces $$$a$$$ chocolates per day but the machine is defective now, so it can currently produce $$$b$$$ chocolates each day.

In order to fix the machine, Freddy will need $$$k$$$ consecutive days to do maintenance; he can not produce any chocolate during this time neither sell any of them, but after finishing, the chocolate factory will be restored to its full production.

Initially, no orders are pending. The factory receives updates of the form $$$d_i$$$, $$$a_i$$$ indicating that $$$a_i$$$ chocolates have been requested for the $$$d_i$$$-th day (adding this quantity to the previous number of chocolates requested on this day). The owner can decide to sell as many or as few chocolates in each of the days. Note that chocolates produced on a day $$$i$$$ can be used in later days.

As orders come in, Freddy would like to know the maximum number of chocolates he will be able to sell if the maintenance starts on a given day $$$p_i$$$.

Help Freddy answer these questions.

The first line contains five integers $$$n$$$, $$$k$$$, $$$a$$$, $$$b$$$ and $$$q$$$ ($$$1 \le k \le n \le 10^{5}$$$, $$$1 \le b < a \le 10^{5}$$$, $$$1 \le q \le 2*10^{5}$$$) - the number of days, the length of the repair time, the production rates of the factory, and the number of updates, respectively.

The next $$$q$$$ lines contain the descriptions of the queries. Each query is of one of the following two forms:

$$$\bullet$$$ 1 $$$d_i$$$ $$$a_i$$$ ($$$1 \le d_i \le n$$$, $$$1\le a_i \le 10^{4}$$$), representing an update of $$$a_i$$$ chocolates on day $$$d_i$$$, or

$$$\bullet$$$ 2 $$$p_i$$$ ($$$1 \le p_i \le n - k + 1$$$), representing a question: at the moment, how many chocolates can be sold if Freddy decides to start maintenance on day $$$p_i$$$?

It's guaranteed that the input will contain at least one query of the second type.

For each query of the second type, print a line containing a single integer — the maximum number of chocolates that the factory can sell all $$$n$$$ days.

5 2 2 1 8
1 1 2
1 5 3
1 2 1
2 2
1 4 2
1 3 2
2 1
2 3

4
6
4