Let us imagine a simplified version of the task where we only have two trucks and one query. An event is defined as a pair ~(id, t)~ which denotes that the truck with index ~id~ is turning around at time ~t~ (in other words, ~t~ minutes after departure).

After calculating the events and sorting by time, we process one event at a time and keep track of the turnaround time and movement direction for each truck. This information is sufficient to calculate for each moment ~t~ which truck is located in the city with a smaller index. The encounter is detected when for times ~t_i~ and ~t_{i+1}~ (consecutive events times) the following holds:

• ~a_i < b_i~ and ~a_{i+1} > b_{i+1}~ or ~a_i > b_i~ and ~a_{i+1} < b_{i+1}~, ~a_i~ - the city in which the first truck is located at moment ~t_i~, ~b_i~ - the city in which the second truck is located at moment ~t_i~.

This claim follows from the fact that two lines can have at most one intersection or completely overlap (but they won't because of the remark from the task).

It was possible to get ~50\%~ of points if every query was individually solved in the aforementioned way. This is done by looking at events for the two trucks we wanted to know the number of encounters for in the current query.

When we solve the task for ~50\%~ of points, it becomes clear that, in order to fully solve the task, we will need to find a way to solve multiple queries at once. Let us observe the following algorithm:

• assign the query to just one truck from the pair
• calculate the events of all trucks and sort the events by time
• process events in order and while doing so keep track for every truck: the moment when it last turned around, the position it last turned around and its movement direction
• while processing event ~(id, t)~ of truck with index ~id~, for each query assigned to that truck we ask ourselves whether the other truck from the pair is located to the left or to the right of it in time ~t~; let us notice that the condition about encounters from the explanation of the ~50\%~ solution is still valid even though we are observing the relative position of trucks from the query while processing the event for only one truck from the pair (caution is needed only when processing the event after the aliens abduct a truck)

Let ~S~ be the sum of all ~K_i~. If we always assign the query to the truck with the smaller number of cities in its route, we reach a complexity of ~\mathcal O(S \sqrt S)~. It is easy to prove the complexity if we split the queries to small and large (a query is large if both trucks from the pair have more than ~\sqrt S~ cities in their route, otherwise it is small). We can have ~M~ small queries and for every small query, we need to determine the relative position of trucks at most ~\sqrt S~ times. We can have at most ~\sqrt S~ large queries (the ones with more than ~\sqrt S~ cities in their route) and for each of them, the second trucks from the query can determine the relative position at most ~S~ times. Therefore, the complexity of processing small queries is ~\mathcal O(M \sqrt S)~ and large ~\mathcal O(S \sqrt S)~ which gives us the total complexity of ~\mathcal O(S \sqrt S)~.

The task has an alternative solution of the same complexity that splits the trucks to those who have more than ~\sqrt S~ cities on their route and calculates their number of encounters with each of the other trucks and to trucks that have less than ~\sqrt S~ cities on their route and calculates only the queries that haven't been calculated while processing the large queries.