小镇上, nnn 个人两两之间的关系交织成一张关系网. 这张关系网定义如下:
部分人之间有直接联系，每一对直接联系都是单向的，并带有亲密度。任意两人间的完全亲密度就是这种直接联系的最短路。
现在，不安定因子出现了。每天，不安定因子会增加一条直接联系，总计操作 ddd 天。显然，每天的完全亲密度会因此而改变。每天的完全亲密度改变后，Sheauhaw想进行几次查询，你可以帮助他吗？
第一行两个数字 n,m,dn,m,dn,m,d.
之后 mmm 行, 每行三个数字 i,j,gi,j,gi,j,g, 表示 iii 到 jjj 之间有亲密度为 ggg 的直接联系。
之后 ddd 组输入，表示每天发生的事件：
第一行三个数字 i,j,hi, j, hi,j,h，表示在 iii 到 jjj 之间新增亲密度为 hhh 的直接联系。
第二行一个数字 qqq，表示这一天的询问次数。
之后 qqq 行，每行两个数字 i,ji,ji,j，表示询问 iii 到 jjj 之间的完全亲密度。
对于每次询问，输出一行答案。
3 3 1 1 2 0 2 3 1 3 1 -2 2 1 654 3 1 1 3 2 2 2
-1 -3 -1
1≤n,d≤5001\le n, d\le 5001≤n,d≤500
1≤m≤1041\le m\le 10^41≤m≤104
−105≤g≤105-10^5\le g\le 10^5−105≤g≤105
1≤h≤1091\le h\le 10^91≤h≤109
1≤∑q≤1051\le\sum q\le 10^51≤∑q≤105