时间限制： 1000MS 内存限制： 128MB

描述

九条可怜是一个喜欢出简单题的女孩子。顾名思义，简单题就是题目里面出现了很多 “简单”。

可怜首先给出一张简单连通无向图，每条边有一个正整数边权。特别地，可怜保证图上任意两个简单环的边权和相等。

后来可怜想要隐藏图里美好的性质，她将其中一部分边的权值改成了新的权值。因此，修改之后原本美好的性质可能就不存在了。

现在她给出修改后的图，同时给出多组询问，每次询问两点 S,T 间所有简单路径权值和。因为答案可能很大，你只需要输出答案对 998244353 取模的结果。

具体地，简单图指不存在重边和自环，简单环和简单路径指不包含重复节点。

输入描述

第一行读入三个整数 n,m,q。

接下来 m 行，每行三个整数 u,v,w，代表一条权值为 w 的无向边 (u,v)。

接下来 q 行，读入 q 组询问，每组询问读入一行两个整数 S,T。

输出描述

对于每个询问，输出一行一个整数代表答案对 998244353 取模后的结果。

样例输入 1

5 5 6 1 2 10 2 3 2 2 4 5 2 5 4 4 5 3 1 5 2 5 3 5 3 4 4 5 4 4 样例输出 1

32 12 16 16 12 0 提示

数据范围与提示 对于所有测试点，满足 1≤n,q≤5×10 5 ，n−1≤m≤6.4×10 5 ，1≤u,v,S,T≤n，1≤w≤10 6 ，无重边自环，图连通。

每个测试点的具体限制见下表：

测试点编号 特殊限制 1 特殊限制 2 1 m<n 保证存在经过所有点的简单路径 2 m<n 无 3∼5 任意一个点不在 ≥2 个简单环上 保证存在经过所有点的简单路径 6∼8 任意一个点不在 ≥2 个简单环上 无 9∼14 无 保证存在经过所有点的简单路径 15∼20 无 无