ストーリー

ここは日本のどこかにある桜で有名な公園. この公園は桜月の最後の日になると, この桜達は花びらを散らしながら, その花びらによる道が次々に作られていくという言い伝えがある.

今日は桜月の最後の日. これはそんな奇跡の $1$ 日の物語である.

問題文

サクラ公園には $N$ 本の桜の木がある. これらはそれぞれ桜 $1$, 桜 $2$, $\cdots$, 桜 $N$ と名付けられている.

現在, $0$ 時である. そして, この時点の $N$ 本の桜について, 以下のようになっている.

• $i=1,2, \dots, N$ に対して, 桜 $i$ には花びらが $A_i$ 枚ある.
• どの $2$ つの桜の間にも花びらの道は存在しない.

ここで, $1$ 以上 $N$ 以下の整数 $i$ に対して, 以下のことが起こることを「桜 $i$ の花びらが $k$ 枚散る」という.

• 散り始める直前で桜 $i$ にある花びらの数が $l$ 枚であるとする. このとき, 桜 $i$ の花びらの数が $\max(0, l-k)$ 枚になる.

さて, この $N$ 本の桜の木に対して $0$ 時から $T$ 時の間に $T$ 個のイベントが起こる. $t~(1 \leq t \leq T)$ 番目のイベントは $(t-0.8)$ 時から $(t-0.2)$ 時の間に起こった. 各イベントは以下の形式で与えられる.

• 1 X Y: 桜 $X$ と桜 $Y$ の間に花びらの道ができる ($(t-0.9)$ 時時点では桜 $X$ と桜 $Y$ の間には花びらの道が存在しないことが保証されている).
• 2 X K: 桜 $X$ の花びらが $K$ 枚散る.
• 3 X K: 桜 $X$ 及び, 桜 $X$ から $1$ 本の花びらの道をたどって到達できる全ての桜の花びらが $K$ 枚散る.
• 4 X K: 桜 $X$ 及び, 桜 $X$ からいくつかの花びらの道をたどって到達できるような全ての桜の花びらが $K$ 枚散る.

では, この $1$ 日の $N$ 本の桜の木について, 以下の $Q$ 個の質問 $q~(1 \leq q \leq Q)$ について答えよ.

• 質問 $q$ : $S_q$ 時時点での桜 $I_q$ にある花びらの枚数を答えよ.

なお, この問題における 「$t$ 時」という表現における $t$ は連続の値を取ることにする. また, この世界において $1$ 日の長さは $T$ 時間であるとし, $T$ 時は翌日の $0$ 時のことを意味する.

制約

• $2 \leq N \leq 1.5 \times 10^5$.
• $1 \leq A_i \leq 4 \times 10^{14} \quad (1 \leq i \leq N)$.
• $1 \leq T \leq 4 \times 10^5$.
• 1 X Y の形式のイベントに対する制約 ($(t-0.8)$ 時から $(t-0.2)$ 時に起こったイベント)
  • $1 \leq X \leq N$.
  • $1 \leq Y \leq N$.
  • $X \neq Y$.
  • $(t-0.9)$ 時時点で桜 $X$ と桜 $Y$ の間には花びらの道は存在しない.
• 2 X K, 3 X K, 4 X K の形式のイベントに対する制約
  • $1 \leq X \leq N$.
  • $1 \leq K \leq 10^9$.
• $1 \leq Q \leq 4 \times 10^5$.
• $T+Q \leq 4 \times 10^5$.
• $0 \leq S_q \leq T \quad (1 \leq q \leq Q)$.
• $1 \leq I_q \leq N \quad (1 \leq q \leq Q)$.
• 入力は全て整数である.

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$T$
$\textrm{Event}_1$
$\textrm{Event}_2$
$\vdots$
$\textrm{Event}_T$
$Q$
$\textrm{Question}_1$
$\textrm{Question}_2$
$\vdots$
$\textrm{Question}_Q$

$1$ $X$ $Y$

$2$ $X$ $K$

$3$ $X$ $K$

$4$ $X$ $K$

$S_q$ $I_q$

出力

出力は $Q$ 行からなる. $q~(1 \leq q \leq Q)$ 行目には質問 $q$ に対する解答を整数で出力せよ.

最後に改行を忘れないこと.

なお, 入出力が大きくなる場合があるので, 高速な方法で入出力を行うことを推奨する.

サンプル

5
10 15 20 25 30
10
2 1 7
1 1 3
1 2 3
3 3 8
1 4 5
4 5 16
1 3 4
1 5 1
3 4 8
2 5 7
8
1 1
5 1
10 1
10 2
10 3
10 4
10 5
3 4

3
0
0
7
4
1
0
25

9
2052486779 2171307413 1168176121 1168169121 1044742332 188219335 191219335 79797979 333333333
16
1 1 2
4 1 1000000000
1 2 3
2 3 10000
1 3 4
3 3 123456789
1 4 5
4 4 998244353
1 5 6
2 2 3141592
1 6 7
3 7 141421356
1 7 8
4 1 46464646
1 8 9
2 1 7777777
9
16 1
16 2
16 3
16 4
16 5
16 6
16 7
16 8
16 9

3
33
333
3333
33333
333333
3333333
33333333
333333333