AT_abc453_g [ABC453G] Copy Query

$ N $ 個の長さ $ M $ の数列 $ A_1,A_2,\dots,A_N $ があります。最初は全ての数列の全ての要素が $ 0 $ です。 以降、数列 $ A_i $ の $ j $ 項目を $ A_{i,j} $ と表します。 以下の $ 3 $ 種類のクエリを、与えられた順に合計 $ Q $ 個処理してください。 - タイプ $ 1 $ : 数列 $ A_{X_i} $ を数列 $ A_{Y_i} $ で上書きする。つまり、全ての整数 $ j $ ( $ 1 \le j \le M $ ) について、 $ A_{X_i,j} $ を $ A_{Y_i,j} $ に変更する。 - タイプ $ 2 $ : 数列 $ A_{X_i} $ の $ Y_i $ 項目、すなわち $ A_{X_i,Y_i} $ を $ Z_i $ に変更する。 - タイプ $ 3 $ : 数列 $ A_{X_i} $ について、 $ L_i $ 項目から $ R_i $ 項目までの和、すなわち $ A_{X_i,L_i}+A_{X_i,L_i+1}+\dots+A_{X_i,R_i} $ を出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ {\rm Query}_1 $ $ {\rm Query}_2 $ $ \vdots $ $ {\rm Query}_Q $ ただし、 $ {\rm Query}_i $ は $ i $ 個目のクエリを表す。 タイプ $ 1 $ のクエリは以下の形式で与えられる。 > 1 $ X_i $ $ Y_i $ タイプ $ 2 $ のクエリは以下の形式で与えられる。 > 2 $ X_i $ $ Y_i $ $ Z_i $ タイプ $ 3 $ のクエリは以下の形式で与えられる。 > 3 $ X_i $ $ L_i $ $ R_i $

タイプ $ 3 $ のクエリが与えられるごとに、そのクエリに対する答えを出力せよ。 タイプ $ 3 $ のクエリが存在しない場合、出力は空とせよ。

### Sample Explanation 1 この入力では、 $ 4 $ 個の長さ $ 5 $ の数列を用意します。 - $ 1 $ 個目のクエリで、 $ A_{2,1}=2 $ とする。この時点で数列 $ A_2=(2,0,0,0,0) $ である。 - $ 2 $ 個目のクエリで、 $ A_{2,2}=7 $ とする。この時点で数列 $ A_2=(2,7,0,0,0) $ である。 - $ 3 $ 個目のクエリで、 $ A_{2,4}=8 $ とする。この時点で数列 $ A_2=(2,7,0,8,0) $ である。 - $ 4 $ 個目のクエリで、数列 $ A_1 $ を数列 $ A_2 $ で上書きする。この時点で数列 $ A_1=(2,7,0,8,0) $ である。 - $ 5 $ 個目のクエリで、 $ A_{2,3}=1 $ とする。この時点で数列 $ A_2=(2,7,1,8,0) $ である。 - $ 6 $ 個目のクエリで、数列 $ A_3 $ を数列 $ A_2 $ で上書きする。この時点で数列 $ A_3=(2,7,1,8,0) $ である。 - $ 7 $ 個目のクエリで、 $ A_{3,2}=10 $ とする。この時点で数列 $ A_3=(2,10,1,8,0) $ である。 - $ 8 $ 個目のクエリで、 $ A_{1,2}+A_{1,3}+A_{1,4}=7+0+8=15 $ を答える。 - $ 9 $ 個目のクエリで、 $ A_{2,1}+A_{2,2}+A_{2,3}+A_{2,4}=2+7+1+8=18 $ を答える。 - $ 10 $ 個目のクエリで、 $ A_{3,2}=10 $ を答える。 ### Constraints - $ 1 \le N,M \le 2 \times 10^5 $ - $ 1 \le Q \le 2 \times 10^5 $ - タイプ $ 1 $ のクエリは以下の制約を満たす - $ 1 \le X_i,Y_i \le N $ - タイプ $ 2 $ のクエリは以下の制約を満たす - $ 1 \le X_i \le N $ - $ 1 \le Y_i \le M $ - $ 0 \le Z_i \le 10^9 $ - タイプ $ 3 $ のクエリは以下の制約を満たす - $ 1 \le X_i \le N $ - $ 1 \le L_i \le R_i \le M $ - 入力はすべて整数