This is a data structures problem. We are given a fixed rectangle on the plane representing John Cena's "blast zone," along with the straight-line paths of ~N~ ships and ~M~ different "steps". Each ship has a value of how much damage has been done to it. Steps with ~A_i = 1~ can be considered "update" operations, while steps with ~A_i = 2~ can be considered "query" operations. Each update adds ~C_i~ damage to all of the ships in the blast zone rectangle after a certain time. Each query asks to print out the sum of the damages in a range of ships with consecutive indices.

A naïve solution would simply do exactly as the problem asks. We keep track of the current time. For each update operation, we move the time forward and loop through all of the ships. Given a particular time, we can easily tell where a ship will be by simply multiplying the time with the velocity (~dx~ and ~dy~) and adding the result to the starting coordinates respectively. If these new coordinates are within the blast zone, then we incur damage to the ship. For query operations, we just loop between the two given indices, add up the damages, and report the total.

Updating and querying each has a worst-case running time of ~\mathcal O(N)~, making the overall running time of the program ~\mathcal O(NM)~. This is clearly too slow for ~N, M \le 400\,000~ but is good enough to pass the ~N \le 500~ and ~M \le 2000~ subtask to obtain an easy ~20\%~ of the points.

For a full solution, we have to try something significantly cleverer. One key observation is that each ship will either never be within the blast zone, or will be within the blast zone for a single consecutive window of time. This interval of time (if non-empty) can be found by calculating the intersection points of the edges of the blast zone rectangle with the line along which the ship will fly. Since we're dealing with a straight line being projected through a rectangle, there are at most two intersection points.

Finding the intersection points is merely drudging geometry, the details of which will be omitted from this analysis. Instead, we suggest trying to work it out yourself. However, since each of the four edges is either horizontal or vertical, a general line intersection algorithm is not needed. Your math can thus be significantly simpler.

Now, if the line intersects with the rectangle at all, the time interval of interest can then be computed by considering the ship's velocity. Note that the interval may start or even end in the past, which is fine. There are at most ~2N~ events in which ships either enter or leave the blast zone. All of these events should then be sorted by their time of occurrence, in ~\mathcal O(N \log N)~ time.

Now, we can simulate the ~M~ steps of the plan, somehow efficiently maintaining information about two things: which ships are currently inside the blast zone, and how much damage each ship has sustained so far. At each step, we should first update the current time, and iterate over all of the previously-computed "events" which have occurred since the previous step (or, for the first step, since the beginning of time), processing which ships are entering and leaving the blast zone, one by one. We must then be able to either update the damage taken by all ships currently within the blast zone, or query the sum of a range of such values. An advanced data structure is needed in order to handle these updates and queries in less than ~\mathcal O(N)~ time each!

A segment tree with lazy propagation will do the trick. Once again, the internet is filled with great articles that you can peruse. The segment tree data structure can be used to solve problems like the dynamic range sum query (efficiently reporting the sum of any consecutive segment in an array, as the array is being constantly changed). The lazy updating, or "lazy-propagation" technique adds the support to update an entire range of values efficiently.

In this particular problem, we will need to adapt it slightly. Each node in the tree will be responsible for a consecutive interval of ships like in normal segment trees, except here, it will store three values:

1. the number of ships in this interval which are currently within the blast zone,
2. the total amount of damage sustained so far by the ships in this interval, and
3. a "lazy value" of how much damage still needs to be dealt to each ship in the interval which are currently within the blast zone.

The lazy propagation aspect works as follows: when necessary, the 3rd value is passed down from a node to each of its children, while its 2nd value should increase by the product of its 1st and 3rd values (as each ship currently within the blast zone will lazily take the appropriate amount of damage).

With all of that in place, handling the entry/exit of a single ship to/from the blast zone with this segment tree is no problem – we'll need to add either ~+1~ or ~-1~ to the 1st value of the appropriate leaf node, as well as all of its ancestors.

Dealing ~C~ damage to all ships currently within the blast zone is as simple as it gets – simply add ~C~ to the root node's 3rd value, and let the lazy propagation handle it later! Finally, querying the total amount of damage done to an interval of ships can be done by adding together the appropriate nodes' 2nd values, in standard segment tree fashion.

There are at most ~N~ events to process and ~M~ operations to handle, each invoking a corresponding operation on the segment tree, each of which taking no more than ~\mathcal O(\log N)~ amortized time. Therefore, the total time complexity of the algorithm is ~\mathcal O((N+M) \log N)~. Note that epsilon comparisons and 96-bit long doubles are necessary to preserve precision in calculations.