AT_abc416_e [ABC416E] Development

AtCoder 国には $ 1 $ から $ N $ の番号がついた $ N $ 個の街と、 $ M $ 本の道路、 $ K $ 個の空港があります。 $ i $ 番目の道路は街 $ A_i $ と街 $ B_i $ を双方向に結び、移動に $ C_i $ 時間かかります。 空港は街 $ D_1,\ldots,D_K $ にあり、空港がある街同士は $ T $ 時間で移動できます。 $ Q $ 個のクエリが与えられるので順に処理してください。クエリは次の $ 3 $ 種類のいずれかです。 - `1 x y t`: 街 $ x $ と街 $ y $ を双方向に $ t $ 時間で結ぶ道路が作られる。 - `2 x`: 街 $ x $ に空港が作られる。 - `3`: $ f(x,y) $ を、街 $ x $ から街 $ y $ へ道路と空港を使って到達可能なときその最短時間、到達不可能なとき $ 0 $ とする。 $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y) $ を求める。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ K $ $ T $ $ D_1 $ $ \dots $ $ D_K $ $ Q $ $ \mathrm{Query}_1 $ $ \vdots $ $ \mathrm{Query}_Q $ $ \mathrm{Query}_i $ は $ i $ 番目のクエリを表し、その形式と意味は問題文中に与えられた通りである。

$ 3 $ 種類目のクエリの解を順に改行区切りで出力せよ。

### Sample Explanation 1 AtCoder 国には $ 4 $ つの街があり、最初、街 $ 1 $ と街 $ 2 $ の間を $ 10 $ 時間で移動できる道路と、街 $ 1 $ と街 $ 3 $ の間を $ 100 $ 時間で移動できる空港があります。 - 最初、 $ f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=100,f(2,3)=f(3,2)=110 $ であり、その他は $ 0 $ なので、 $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=440 $ です。 - 新たに街 $ 2 $ と街 $ 3 $ を $ 60 $ 時間で結ぶ道路が作られました。 - $ f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70,f(2,3)=f(3,2)=60 $ であり、その他は $ 0 $ なので、 $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=280 $ です。 - 新たに街 $ 4 $ に空港ができました。 - $ f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70,f(1,4)=f(4,1)=100,f(2,3)=f(3,2)=60,f(2,4)=f(4,2)=110,f(3,4)=f(4,3)=100 $ であり、その他は $ 0 $ なので、 $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=900 $ です。 2つの街の間に複数の道路が作られることや、1つの街に複数の空港が作られることもあります。 ### Constraints - $ 1 \leq N \leq 500 $ - $ 0 \leq M \leq 10^5 $ - $ 1 \leq A_i < B_i \leq N $ - $ 1 \leq C_i \leq 10^9 $ - $ 0 \leq K \leq N $ - $ 1 \leq T \leq 10^9 $ - $ 1 \leq D_1 < \dots < D_K \leq N $ - $ 1 \leq Q \leq 1000 $ - $ 1 $ 種類目のクエリにおいて、 $ 1\leq x < y \leq N $ , $ 1 \leq t \leq 10^9 $ - $ 2 $ 種類目のクエリにおいて、 $ 1 \leq x \leq N $ - 入力は全て整数