AT_abc438_e [ABC438E] Heavy Buckets

There are $ N $ people and $ N $ buckets. Both the people and buckets are numbered $ 1, 2, \ldots, N $ . Initially, person $ i $ holds only bucket $ i $ , and bucket $ i $ is empty. From now on, the following operation will be performed $ 10^9 $ times: - For $ i = 1, 2, \ldots, N $ **simultaneously**, person $ i $ adds $ i $ units of water to each of the buckets they are holding and passes those buckets to person $ A_i $ . Here, there is no limit on the amount of water that can be put in a bucket. For $ i = 1, 2, \ldots, Q $ , answer the following queries: - Find the amount of water in bucket $ B_i $ immediately after the $ T_i $ -th operation.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ T_1 $ $ B_1 $ $ T_2 $ $ B_2 $ $ \vdots $ $ T_Q $ $ B_Q $

Output $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 We will explain the first query. Initially, bucket $ 3 $ is held by person $ 3 $ . Immediately after the $ 1 $ -st operation, bucket $ 3 $ is held by person $ 2 $ and contains $ 3 $ units of water. Immediately after the $ 2 $ -nd operation, bucket $ 3 $ is held by person $ 4 $ and contains $ 5 $ units of water. Immediately after the $ 3 $ -rd operation, bucket $ 3 $ is held by person $ 2 $ and contains $ 9 $ units of water. Immediately after the $ 4 $ -th operation, bucket $ 3 $ is held by person $ 4 $ and contains $ 11 $ units of water. Thus, the answer to the first query is $ 11 $ . ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq N $ - $ 1 \leq T_i \leq 10^9 $ - $ 1 \leq B_i \leq N $ - All input values are integers.