If he arrives at bus stop \(i\) at time \(x_i\), then the earliest bus that he can take is the one departing at time \(\lceil \frac{x_i}{P_i} \rceil \cdot P_i\), so he arrives at bus stop \((i+1)\) at time

\[x_{i+1} := \left\lceil \frac{x_i}{P_i} \right\rceil \cdot P_i + T_i. \tag{1}\]

Thus, the duration \(f(q)\) required to get to Aoki’s house if Takahashi leaves his house at time \(q\) can be found in a total of \(\Theta(N)\) time by successively computing \(x_i\) in ascending order of \(i\) according to the equation (1) above.

However, naively evaluating \(f(q_i)\) for each of the \(Q\) queries \(q_1, q_2, \ldots, q_Q\) costs a total of \(\Theta(NQ)\) time, which is almost impossible to finish in the execution time limit.

In fact, \(f\) is periodic with period \(L \coloneqq \mathrm{lcm}(P_1, P_2, \ldots, P_{N-1}) \leq \mathrm{lcm}(1, 2, \ldots, 8) = 840\), as explained later.

Therefore, one can precompute only \(L\) values, \(f(0), f(1), \ldots\), and \(f(L-1)\), in a total of \(O(NL)\) time, so that the value \(f(q_j)\) for each query \(q_i\) can be found in an \(O(1)\) time, because \(f(q_j)\) equals \(f(q_i \% L)\), the value of \(f\) against the remainder \(q_i \% L\) when \(q_i\) is divided by \(L\). Hence, the problem can be solved in a total of \(O(NL + Q)\) time.

Proof that \(f\) has a period of \(L\)

We will show that, if \(q \equiv q' \pmod{L}\), then \(f(q) = f(q')\). We define \(x_i\) and \(x'_i\) to be the times of his arrival at bus stop \(i\) if he leaves home at times \(q\) and \(q'\), respectively; then, it is sufficient to show that

\(x_i \equiv x'_i \pmod{L}\) and \(x_i - x_{i-1} = x'_i - x'_{i-1}\) for all \(i\).

(Since \(x_i - x_{i-1}\) and \(x'_i - x'_{i-1}\) are the durations from the arrival to bus stop \((i-1)\) to that to bus stop \(i\), once we can prove that these are equal for all \(i\), we can also say that \(f(q) = f(q')\).)

We show it by induction on \(i\). First, by the assumption that \(q \equiv q' \pmod{L}\), we have \(x_1 = q + X \equiv q' + X = x'_1 \pmod{L}\). We now assume that the claim holds for \(i\) and show that it also holds for \((i+1)\).

First, regarding \(x_{i+1} - x_i\), by equation (1)

\[ \begin{aligned} x_{i+1} - x_i &= \left\lceil \frac{x_i}{P_i} \right\rceil \cdot P_i + T_i - x_i\\ &= \left\lfloor \frac{x_i + P_i - 1}{P_i} \right\rfloor \cdot P_i + T_i - x_i\\ &= (x_i + P_i - 1) - ((x_i + P_i - 1) \% P_i )+ T_i - x_i\\ &= P_i + T_i - 1 - ((x_i - 1) \% P_i ). \tag{2} \end{aligned} \]

We can do so in the same way for \(x'_{i+1} - x'_i\) as

\[ x'_{i+1} - x'_i = P_i + T_i - 1 - ((x'_i - 1) \% P_i ) \tag{3}. \]

By the assumption of the induction that \(x_i \equiv x'_i \pmod{L}\), and the fact that \(L\) is a multiple of \(P_i\), we have \(x_i \equiv x'_i \pmod{P_i}\), thus \((x_i - 1) \% P_i = (x'_i - 1) \% P_i \). Therefore, the rightmost hand side of (2) and (3) are equal, thus \(x_{i+1} - x_i = x'_{i+1} - x'_i\). Together with the assumption of the induction that \(x_i \equiv x'_i \pmod{L}\), it immediately follows that \(x_{i+1} \equiv x'_{i+1}\pmod{L}\).