AT_abc428_f [ABC428F] Pyramid Alignment

数直線上に $ N $ 個の区間があり、 $ 1 $ から $ N $ までの番号が付けられています。 区間 $ i $ の左端の座標は $ 0 $ 、右端の座標は $ W_i $ です。ここで、 $ W_1 < W_2 < \dots < W_N $ です。 $ Q $ 個のクエリが与えられるので、与えられた順に処理してください。クエリは次の $ 3 $ 種類のいずれかです。 - タイプ $ 1 $ (`1 v`): 現在の区間 $ v $ の**左端**の座標を $ l $ とする。番号が $ v $ 以下であるすべての区間をそれぞれ、**左端**の座標が $ l $ となるように平行移動する。 - タイプ $ 2 $ (`2 v`): 現在の区間 $ v $ の**右端**の座標を $ r $ とする。番号が $ v $ 以下であるすべての区間をそれぞれ、**右端**の座標が $ r $ となるように平行移動する。 - タイプ $ 3 $ (`3 x`): 座標 $ x+\frac{1}{2} $ を含む区間の現在の個数を出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ W_1 $ $ \dots $ $ W_N $ $ Q $ $ \textrm{query}_1 $ $ \textrm{query}_2 $ $ \vdots $ $ \textrm{query}_Q $ $ \textrm{query}_j $ は $ j $ 番目のクエリを表す。各クエリは以下のいずれかの形式で与えられる。 > $ 1 $ $ v $ > $ 2 $ $ v $ > $ 3 $ $ x $

タイプ $ 3 $ のクエリの回数を $ q $ として、 $ q $ 行出力せよ。 $ j $ 行目 ( $ 1 \leq j \leq q $ ) には $ j $ 番目のタイプ $ 3 $ のクエリに対する答えを出力せよ。

### Sample Explanation 1 はじめ、各区間は番号順に $ [0, 2], [0, 4], [0, 6], [0, 10] $ です。 - $ 1 $ 番目のクエリにおいて、操作前の区間 $ 3 $ の**右端**の座標は $ 6 $ なので、操作後の各区間は番号順に $ [4, 6], [2, 6], [0, 6], [0, 10] $ になります。 - $ 2 $ 番目のクエリにおいて、操作前の区間 $ 2 $ の**左端**の座標は $ 2 $ なので、操作後の各区間は番号順に $ [2, 4], [2, 6], [0, 6], [0, 10] $ になります。 - $ 3 $ 番目のクエリにおいて、座標 $ 2 + \frac{1}{2} $ を含む区間は区間 $ 1,2,3,4 $ の $ 4 $ 個なので、 $ 4 $ を出力します。 - $ 4 $ 番目のクエリにおいて、操作前の区間 $ 4 $ の**右端**の座標は $ 10 $ なので、操作後の各区間は番号順に $ [8, 10], [6, 10], [4, 10], [0, 10] $ になります。 - $ 5 $ 番目のクエリにおいて、座標 $ 1 + \frac{1}{2} $ を含む区間は区間 $ 4 $ のみの $ 1 $ 個なので、 $ 1 $ を出力します。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq W_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ) - $ W_1 < W_2 < \dots < W_N $ - タイプ $ 1,2 $ のクエリで与えられる $ v $ について、 $ 1 \leq v \leq N $ - タイプ $ 3 $ のクエリで与えられる $ x $ について、 $ 0 \leq x \leq 10^9 $ - タイプ $ 3 $ のクエリは少なくとも $ 1 $ つ与えられる - 入力される値はすべて整数