409411: GYM103505 B In Heaters

All are old and all renewed, except for the recent increase in taxes. Nelu, unable to change his financial situation, has to deal with the following problem:

Nelu has $$$N$$$ wet laundry items that he would like to dry off by placing them on the heater in his flat. Each laundry item is characterized by three integers $$$x_i$$$ — where on the heater Nelu will place this item, $$$c_i$$$ — the amount of water contained in that item. and $$$t_i$$$ — the moment when Nelu will place that item on the heater.

After placing a laundry item on the heater at time $$$t_i$$$, vapors will start to form above it for the next $$$c_i$$$ seconds, indicating that the drying process is effective (a.k.a. Danut Nicolae wasn't harsh enough on the tax reforms). More formally, for every second $$$T \in [t_i,t_i+c_i-1]$$$, all the previous vapors would rise up by $$$1$$$ height unit, and a new vapor will form just above the laundry item at $$$1$$$ height unit.

After all vapors have been realeased, they will continue their course towards the ceiling at $$$H$$$ height units above the heater. Consequently, a vapor generated at time $$$T$$$ will reach altitude $$$Y$$$ at time $$$Y+T$$$.

Unfortunately for Nelu, some safety measures were implemented in his flat so the ceiling won't become as yellow as his teeth. Fortunately for Nelu, the safety features are $$$M$$$ sponges on his wall. For each sponge, the following are also known:

• its position relative to the heater (i.e. its X-coordinate), denoted with $$$x_i$$$
• the height above the heater at which it is placed (i.e. the Y-coordinate in the afferent xOy plane, where the Ox line is the heater), denoted with $$$y_i$$$
• the maximum amount of water/vapor that sponge can retain, denoted with $$$w_i$$$. After a sponge exceeds its maximum capacity, it will fall onto the floor and be never heard from again.

When some vapor reaches the exact position of a sponge, that sponge will lose $$$1$$$ unit of water from its capacity. After the sponge absorbs $$$w_i$$$ vapors, the sponge will fall, and all subsequent vapors will continue rising to the ceiling.

Once $$$W$$$ vapors reach the ceiling, the latter will form a hole, similar to those on Nelu's morals, creating a liability to the structural integrity of the building. To prevent this, the administrator has decided calculate at which time the building would collapse. But because Nelu is very unpredictable, he will add $$$Q$$$ elements in the configuration, and after each and one of these he wants to know at what time he should evacuate the building. But since this is very hard, he is asking you to do this while he is booking a flight to Cancun.

The first line of input contains five integers: $$$N$$$ ($$$1\le N \le 10^5$$$) — the number of laundry items, $$$M$$$ ($$$1\le M \le 10^5$$$) — the number of initial sponges, $$$Q$$$ ($$$1\le Q \le 10^5$$$)— the number of new items, $$$W$$$ ($$$1 \le W \le 10^9$$$) — the number of vapors required to break the ceiling, and $$$H$$$ ($$$1\le H \le 5 \cdot 10^5$$$) — the height of the ceiling.

On the following $$$N$$$ lines, it will be described by $$$x_i$$$, $$$c_i$$$, $$$t_i$$$, the parameters of the i-th sock that will appear initially on the heater.

On the following $$$M$$$ lines, it will be described by $$$x_i$$$, $$$y_i$$$, $$$w_i$$$, the parameters of the i-th sponge that will appear initially on the heater.

On the following $$$Q$$$ lines, there will be four numbers. The first of them will be $$$type_i$$$, denoting the type of the update. If $$$type_i = 1$$$, then the following numbers will describe a sock by $$$x_i, c_i, t_i$$$. Otherwise, the following numbers will describe a sponge by $$$x_i, y_i, w_i$$$.

For every sock (including one from a query), $$$1 \le x_i, c_i, t_i \le 10^5$$$

For every sponge (including one from a query), $$$1 \le x_i \le 10^5, 1 \le y_i < H, 1 \le w_i \le 10^5$$$

On the first line of output there should be printed the answer for the After each new item is added to the configuration, print one integer: the number of seconds before the ceiling of Nelu's flat would form holes. In the case when the building would never collapse, it should be printed -1

4 5 4 1 10
1 3 5
2 7 4
3 4 7
4 1 3
1 4 4
2 3 3
3 8 4
2 5 1
4 6 1
2 2 5 6
1 4 1 18
1 3 5 5
1 1 3 1

18
-1
28
18
16

At the beggining, the hole will form at the position with X-coordinate = 2. The vapors generated at position 2 at the seconds 4, 5, 6 will be retained in the first sponge at the seconds 7, 8, 9, thus at time $$$T = 9$$$ the first sponge will fall. Then, the vapor generated at the second 7 will be retained in the second sponge at the seconds 12, thus at time $$$T = 12$$$ the second sponge will fall. The vapor formed at the second 8 will not have any other sponge in its way (since all the vapors generated before him filled all the sponges in its way), so at time $$$T = 18$$$, the vapor will be retained in the ceiling, and the building will collapse. We leave as an exercise to the reader the explication for the following queries