题目描述

给定$\red{N }$个点 $\red{M}$条边的带权无向图，每个点有颜色：黑或者白。

有$\red{Q }$个操作，每个操作是下面其中一种：

$\red{1 ~X ：}$表示把 $\red{x }$节点的颜色取反（黑变成白，白变成黑）；

$\red{2 ~A~ B ：}$查询两端的颜色分别是 $\red{A }$和 $\red{B}$（$\red{A/B }$取值为$\red{0/1，}$代表 黑/白）的边的权值之和。

输入格式

第一行一个数$\red{T ，}$表示$\red{T }$组数据。

每组数据第一行两个数$\red{N }$和 $\red{M}$。

接下来一行有$\red{N }$个数，$\red{A_i=0 }$表示第$\red{i }$个点初始是黑色，否则是白色。

接下来 $\red{M}$行，每行三个数，表示 $\red{u_i}$和 $\red{v_i}$有一条边，权值为 $\red{w_i}$。

接下来一行是$\red{Q }$。

接下来 $\red{Q}$行，分别是 "$\red{1~ X}$" 或者 "$\red{2~ A ~B}$" 的形式。

输出格式

对于每个"询问 $\red{2}$"，输出一行，表示两端点恰好和指定的"$\red{A/B}$"一致的边的权值和。

样例

输入样例

2
4 3
0 0 0 0
1 2 1
2 3 2
3 4 3
4
2 0 0
1 2
2 0 0
2 0 1
4 3
0 1 0 0
1 2 1
2 3 2
3 4 3
4
2 0 0
1 3
2 0 0
2 0 1

输出样例

6
3
3
3
0
4

提示

对于 $\red{10\%}$的数据，$\red{M=N-1 ，}$原图恰好是一棵树的形式；

对于另外 $\red{10\%}$的数据，$\red{N=30000 ，}$$\red{M=100000 ，}$图是完全随机构造的；

对于$\red{100\% }$的数据，$\red{T<=10,1<=N,M,Q<=100000 }$。