Your company owns a water tower. The water tower is a cylinder of height H meters, initially completely filled with water.
The water tower is very old, so cracks and holes appear on the body of the water tower, and cause water leak. Then, you may hire someone to fix the leak. You are very interested in the water level in the water tower, but you do not want to climb the stairs to look at the tower every time.
As a programmer, please write a program to handle the following requests:
Water flows out of a hole only when the water level is above the height of the hole. The rate of water leak v means that per unit time the amount of water flowing out of the hole corresponds to v meters of water in the tower.
The first line of the input file contains an integer T (T<=50), the number of test cases.
The first line of each test case contains two integers n and H (1<= n<=105, 1<= H<=109), indicating the number of requests and the height of the water tower. Each of the following n lines describes one request. In each line, the first integer k (1<= k<=3) denotes the request type. Depending on the request type, it is followed by one to three integers t, h and v (0<= t<=109, 0<= h<= H, 1<= v<=109). Requests are listed in the order of increasing time, and no two requests have the same time.
For each type-3 request, please output a single number -- the water level in the tower at the request time.
1 6 10 1 0 1 2 3 1 3 2 2 3 1 3 4 3 5
8.0 6.0 4.0 4.0
Info: 本題輸出為浮點數，絕對或相對誤差 1e-6 以下視為正確
Migrated from old NTUJ.
St. Petersburg Olympiad team programming 2010
| No. | Testdata Range | Score |
|---|