时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}对于给定的由 n 个节点 m 条边构成的带权无向图,边的编号为 1m,你需要处理 q 次操作,这些操作有以下三个类型,初始时 {\rm idx}m
{\hspace{20pt}}_\texttt{1.}\,添加边:添加一条长度为 w,连接 xy 的无向边,{\rm idx}:={\rm idx}+1,然后定义这条边的编号为 {\rm idx}
{\hspace{20pt}}_\texttt{2.}\,删除边:删除编号为 i 的边,保证这个编号的边一定存在,删除后 {\rm idx} 不发生改变;
{\hspace{20pt}}_\texttt{3.}\,查询:输出 \sum\limits_{x=1}^n\sum\limits_{y=1}^n {\rm dist}(x,y){\rm dist}(x,y) 表示 xy 的最短路距离(特别地,x 不能到达 y{\rm dist}(x,y)=0)。由于答案可能很大,请将答案对 998\,244\,353 取模后输出。

\hspace{15pt}注意,询问中的添加边、删除边操作都是永久性的。可能出现自环与重边。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 50\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入三个整数 n,m,q\left(1\leq n,q\leq 300;\ 0 \leq m \leq \tfrac{n\times(n-1)}{2}\right) 代表节点数量、边数量、询问数量。
\hspace{15pt}此后 m 行,第 i 行输入三个整数 u_i,v_i,w_i\left(1\leq u_i,v_i\leq n;\ 1\leq w_i\leq 10^9\right) 代表第 i 条边连接节点 u_iv_i ,长度为 w_i

\hspace{15pt}此后 q 行,每行先输入一个整数 op\left(1\leq op\leq 3\right) 代表操作类型,编号同题干,随后:
\hspace{23pt}\bullet\,op=1,在同一行输入三个整数 x,y,w\left(1\leq x,y\leq n;\ 1\leq w\leq 10^9\right) 代表一次添加边操作;
\hspace{23pt}\bullet\,op=2,在同一行输入一个整数 i 代表一次删除边操作,保证这个编号的边一定存在;
\hspace{23pt}\bullet\,op=3,代表一次查询。由于答案可能很大,请将答案对 998\,244\,353 取模后输出。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 300q 之和不超过 300

输出描述:

\hspace{15pt}对于每次操作三,新起一行。输出一个整数,代表答案对 998\,244\,353 取模后的结果。
示例1

输入

复制
1
5 5 8
1 2 1
4 1 7
4 2 4
3 1 3
4 5 8
3
2 3
3
2 4
1 3 4 1
2 1
2 6
3

输出

复制
148
180
60

说明

\hspace{15pt}对于第一组测试数据,初始时图的形态如【图一】所示,模拟如下:
\hspace{23pt}\bullet\,对于第一次操作,询问,图不发生变化;
\hspace{23pt}\bullet\,对于第二次操作,删除编号为 3 的边,如【图二】所示;
\hspace{23pt}\bullet\,对于第三次操作,询问,图不发生变化;
\hspace{23pt}\bullet\,对于第四次操作,删除编号为 4 的边,如【图三】所示;
\hspace{23pt}\bullet\,对于第五次操作,添加一条长度为 1,连接节点 3 和节点 4 的边,编号为 6,如【图四】所示。