AT_abc416_e [ABC416E] Development

AtCoder Country has $ N $ cities numbered from $ 1 $ to $ N $ , $ M $ roads, and $ K $ airports. The $ i $ -th road connects cities $ A_i $ and $ B_i $ bidirectionally and takes $ C_i $ hours to travel. There are airports in cities $ D_1,\ldots,D_K $ , and you can travel between cities with airports in $ T $ hours. Process $ Q $ queries in order. Each query is one of the following three types: - `1 x y t`: A road connecting cities $ x $ and $ y $ bidirectionally in $ t $ hours is built. - `2 x`: An airport is built in city $ x $ . - `3`: Let $ f(x,y) $ be the smallest number of hours needed to reach city $ y $ from city $ x $ using roads and airports if reachable, and $ 0 $ if unreachable. Find $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y) $ .

The input is given from Standard Input in the following format: > $ 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 $ represents the $ i $ -th query, whose format and meaning are as given in the problem statement.

Output the answers to type $ 3 $ queries in order, separated by newlines.

### Sample Explanation 1 AtCoder Country has four cities. Initially, there is a road connecting cities $ 1 $ and $ 2 $ in $ 10 $ hours, and airports connecting cities $ 1 $ and $ 3 $ in $ 100 $ hours. - Initially, $ f(1,2)=f(2,1)=10 $ , $ f(1,3)=f(3,1)=100 $ , $ f(2,3)=f(3,2)=110 $ , and others are $ 0 $ , so $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=440 $ . - A new road connecting cities $ 2 $ and $ 3 $ in $ 60 $ hours is built. - $ f(1,2)=f(2,1)=10 $ , $ f(1,3)=f(3,1)=70 $ , $ f(2,3)=f(3,2)=60 $ , and others are $ 0 $ , so $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=280 $ . - A new airport is built in city $ 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 $ , and others are $ 0 $ , so $ \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=900 $ . Multiple roads may exist between some pair of cities. Also, a city may have multiple airports. ### 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 $ - For type $ 1 $ queries: $ 1\leq x < y \leq N $ , $ 1 \leq t \leq 10^9 $ . - For type $ 2 $ queries: $ 1 \leq x \leq N $ . - All input values are integers.