AT_abc438_e [ABC438E] Heavy Buckets

$ N $ 人の人がおり、 $ N $ 個のバケツがあります。人とバケツにはそれぞれ $ 1, 2, \ldots, N $ の番号が付けられています。 人 $ i $ ははじめバケツ $ i $ のみを持っており、バケツ $ i $ には何も入っていません。 これから、以下の操作を $ 10^9 $ 回行います。 - $ i = 1, 2, \ldots, N $ について**同時**に、人 $ i $ が持っているバケツすべてに水を $ i $ ずつ入れ、それらのバケツを人 $ A_i $ に渡す。 ただし、バケツに入れることのできる水の量に制限はありません。 $ i = 1, 2, \ldots, Q $ について以下の形式のクエリに答えてください。 - $ T_i $ 回目の操作の直後にバケツ $ B_i $ に入っている水の量を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ T_1 $ $ B_1 $ $ T_2 $ $ B_2 $ $ \vdots $ $ T_Q $ $ B_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリに対する説明を行います。 はじめ、バケツ $ 3 $ は人 $ 3 $ が持っています。 $ 1 $ 回目の操作の直後、バケツ $ 3 $ は人 $ 2 $ が持っており、水が $ 3 $ 入っています。 $ 2 $ 回目の操作の直後、バケツ $ 3 $ は人 $ 4 $ が持っており、水が $ 5 $ 入っています。 $ 3 $ 回目の操作の直後、バケツ $ 3 $ は人 $ 2 $ が持っており、水が $ 9 $ 入っています。 $ 4 $ 回目の操作の直後、バケツ $ 3 $ は人 $ 4 $ が持っており、水が $ 11 $ 入っています。 したがって、 $ 1 $ 番目のクエリに対する答えは $ 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 $ - 入力される値はすべて整数