题目描述

没有常人知道她在哪里——LCR 的神秘只有真正的神犇才能看到。
幸运的是，某附中确实存在一个这样的神犇。一天，神犇发现了一件事情：LCR 从自己的视野中消失了。
显然，这不可能是因为神犇变弱而失去了 LCR 的青睐，而是 LCR 离开了这座城市的缘故。
神犇踏上了寻找 LCR 的征程。
神犇走过了千山万水，一天，他遇到了 LCR 的兄长——LCT。LCT 告诉他，他的身上沾染了过多的蒟蒻气息，因此看不到 LCR。LCT 还告诉他，他需要到东海找龙王消除自己身上的蒟蒻气息。
神犇知道，普通的蒟蒻是不可能在他这样的神犇身上留下蒟蒻气息的，只有像 LCA 这样的蒟蒻才会在他的身上留下蒟蒻气息。
神犇决定超时空传送去东海。神犇现在要传送到一个有 $n$ 个传送点的网络中，传送网络中有 $m$ 条路，但神犇发现每条路上都有至少一个像 LCA 那样的蒟蒻。神犇知道，自己如果沾染了过多的蒟蒻气息，就会即使到了东海也无法消除了。根据蒟蒻学第二定律，蒟蒻气息只会从蒟蒻多的地方向蒟蒻少的地方传递，因此神犇在穿过一条路后，他身上的蒟蒻气息会变成穿过之前的值和这条路径上的蒟蒻数量的最大值。神犇还发现，在不同的时间，他的家乡和东海对应的传送网络的传送点是不同的。神犇想知道，如果他知道自己应该从哪里进入排序网络和从何处离开，他至少要沾染多少蒟蒻气息。由于传送网络中的蒟蒻气息太过浓郁，你可以认为神犇在进入时身上没有蒟蒻气息。保证传送网络中任意两点相互可达，且道路是双向的。一条道路连接的必定是两个不同的传送点，但一对传送点之间可能有两条道路。

给你一个 $n$ 个点 $m$ 条边的无向连通图，编号为 $1$ 到 $n$ ，没有自环，可能有重边，每一条边有一个正权值 $w$ 。给出 $q$ 个询问，每次给出两个不同的点 $u$ 和 $v$ ，求一条从 $u$ 到 $v$ 的路径上边权的最大值最小是多少。

输入格式

输入第一行两个整数 $n$，$m$。

接下来 $m$ 行，每行三个整数 $a_i,b_i,w_i$（$a_i\neq b_i$），表示一条连接传送点 $a_i$ 和 $b_i$ 的道路，上面的蒟蒻数量为 $w_i$。

接下来一行一个整数 $q$，表示询问数量。

接下来一行四个整数 $A,B,C,P$，表示询问的生成方式。

由于本题数据规模极大，直接输入输出会占用比计算多数倍的时间，因此对询问的输入输出进行了压缩。

输入压缩方法是：读入四个整数 $A,B,C,P$，每次询问调用以下函数生成 $u$ 和 $v$：

int A, B, C, P;

int rnd() {
    return A = (A * B + C) % P;
}

每次询问时的调用方法为：

u = rnd() % n + 1, v = rnd() % n + 1;

若 $u$ 和 $v$ 相等则答案为 $0$。

数据保证 $0\leq A<P,0\leq C<P,P(B+1)<2^{31}-1$。

输出格式

输出共一行一个整数，表示所有询问的答案之和模 $1000000007$ 的值。

由于本题数据规模极大，直接输入输出会占用比计算多数倍的时间，因此对询问的输入输出进行了压缩。

输出压缩方法是：输出所有询问的答案之和模 $1000000007$ 的值。

样例

input

5 7
1 2 8
2 3 9
3 1 2
3 4 7
1 4 4
3 5 6
1 4 9
10
233 17 66666 19260817

output

32

数据范围与提示

对于 $100\%$ 的数据，$n\leq 70000$，$m\leq 100000$，$q\leq 10^7$。