#4643. 模板.最小瓶颈路(加强版)

模板.最小瓶颈路(加强版)

Description

给定一个 nn 个点 mm 条边的无向连通图,编号为 11nn ,没有自环,可能有重边,每一条边有一个正权值 ww 。 给出 qq 个询问,每次给出两个不同的点 uuvv ,求一条从 uuvv 的路径上边权的最大值最小是多少。

Input

输入第一行两个整数 n,mn, m

接下来 mm 行,每行三个整数 ai,bi,wi(aibi)a_i,b_i,w_i(a_i\neq b_i),表示一条边 (ai,bi)(a_i,b_i),边权为 wiw_i

接下来一行一个整数 qq,表示询问数量。

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

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

输入压缩方法是:读入4个整数 A,B,C,PA,B,C,P,每次询问调用以下函数生成 uuvv

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

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

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

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

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

Output

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

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

输出压缩方法是:输出所有询问的答案之和模 10000000071000000007 的值。

Samples

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
32

Limitation

对于所有数据,n70000n\leq 70000m100000m\leq 100000q107q\leq 10^7

题目和数据复制自寻找 LCR