ダブリングを行います。\(0 \leq d < 30\) および \(1 \leq i \leq N\) を満たす整数 \(d, i\) について \(P_{d, i}, Q_{d, i}\) を以下のように定めます。

• \(P_{d, i}\) : 人 \(i\) があるバケツを持っている状態から \(2^d\) 回操作を行ったとき、 そのバケツを持っている人の番号
• \(Q_{d, i}\) : 人 \(i\) があるバケツを持っている状態から \(2^d\) 回操作を行ったとき、そのバケツに \(2^d\) 回の操作で新たに入った水の量

\(P_{d, i}\) の計算は単なる合成であり、\(j = P_{d - 1, i}\) として \(P_{d, i} = P_{d - 1, j}\) によって行えます。

\(Q_{d, i}\) について考えます。同様に \(j = P_{d - 1, i}\) とおきます。はじめの \(2^{d-1}\) 回目の操作では水が \(Q_{d - 1, i}\) 増え、次の \(2^{d - 1}\) 回目の操作の前にはバケツは人 \(j\) が持っていることに注意すると、次の \(2^{d - 1}\) 回の操作では水が \(Q_{d - 1, j}\) 増えます。したがって、\(Q_{d, i} = Q_{d - 1, i} + Q_{d - 1, j}\) です。

以上よりダブリングのテーブルを作ることができました。

この計算結果を利用して答えを求めるには各クエリごとにシミュレートを行えばよいです。

\(d = 0, 1, \ldots, 29\) に対して \(T_i\) の（\(2\) 進表記での） \(2^d\) の位が \(1\) のとき、\(2^d\) 回の操作をシミュレートすることは作ったテーブルを利用することにより実現できます。管理するべき量は、現在入っている水の量とバケツを持っている人の \(2\) つのみです。

操作回数の上限を \(T\) とすると（本問題では \(T = 10^9\) です）、時間計算量は \(O((N + Q) \log T)\) です。なお、\(O(N + Q)\) 時間で解くこともできます。