Subtask 1

For subtask 1, the velocity of each kangaroo never changes.

If at any point in time, all kangaroos collide, then the answer is ~1~ (for example, we could take the kangaroo with the greatest velocity and change its initial position to an arbitrarily large position). Otherwise, the answer is ~0~.

Since the velocity of each kangaroo never changes, if we were to plot the position of each kangaroo over time, we would have a collection of ~N~ straight lines, and we would be looking for an integer point where all ~N~ lines intersect.

Since each kangaroo has a distinct starting position, each line has a unique ~y~-intercept, meaning that lines cannot completely overlap. Thus, each pair of lines has at most one intersection point.

For each query of type ~2~, we can simply loop over each pair of consecutively-indexed kangaroos in the given range, and determine the time they collide (if they do collide) by calculating the intersection point of their corresponding lines. (Recall that we only care about positive integer collision times.) If all pairs of kangaroos collide at the same time, then the answer is ~1~. Otherwise, the answer is ~0~.

Time complexity: ~\mathcal{O}(NQ)~

Subtask 2

For subtask 2, we need to optimise our previous solution, as finding the answer for events of type ~2~ must be done in sublinear time.

Let's generate a list of the collision times between each pair of consecutively-indexed kangaroos. For a type ~1~ event, at most two of the elements in this list will be changed (the collision times between the queried kangaroos and its adjacent kangaroos). For a type ~2~ event, we need to determine if all numbers in the relevant sublist are equal.

There are multiple ways of performing these operations efficiently, including using a segment tree, by maintaining a set of consecutive ranges in the list which are equal, or by using square-root decomposition.

Time complexity: ~\mathcal{O}(N + Q \log N)~ or ~\mathcal{O}(N + Q \sqrt N)~

Subtask 3

For subtask 3, we need to deal with acceleration now.

Note that for any kangaroo, the velocity sequence forms an arithmetic sequence ~(v_i, v_i+a_i, v_i+2a_i, \dots)~, and that each term in the velocity sequence corresponds to the change in position of the kangaroo after each second. We can calculate the position of any kangaroo at any time as the sum of its initial position and the sum of the corresponding prefix of the velocity sequence. Using formulas for the sum of an arithmetic sequence, we can find the quadratic expression for the position of any kangaroo (there are other methods to find the quadratic expression). Instead of determining if all lines intersect at a common point, we now have to determine if all parabolas intersect at a common point.

We are no longer guaranteed that each pair of kangaroos collide at most once, since parabolas can intersect at up to two distinct points. We can find these intersection points using the quadratic formula. Keep in mind that valid solutions must be positive integers. Constraints were chosen such that all arithmetic can be performed using 64-bit integers, and we can multiply the quadratic expression by ~2~ in order to avoid floating-point numbers.

Similar to our subtask ~2~ solution, we can generate a list containing the collision times between each pair of consecutively-indexed kangaroos, where each element can have up to two different values. Finally, we need to answer queries regarding whether an integer exists that is contained by each element in the relevant subrange. We can modify our segment tree or square-root decomposition to efficiently process these queries.

Time complexity: ~\mathcal{O}(N + Q \log N)~ or ~\mathcal{O}(N + Q \sqrt N)~