fold的毒瘤题(mid)

给出一幅有n(≤20000)个点, m(≤200000)条边的无向图. 保证任意2点间都至少存在一条路径可以连通, 每条边上都有一个权值V_i(≤1000000)

不幸的是, 这m条边都被损坏了.

fold打算修复其中一些边让一些点连通, 不过, fold并不打算让全部的点连通, 而是选择一些编号特殊的点让它们连通.

fold有q(≤50000)次询问, 对于每次询问, 他会选择所有编号在[l,r]之间, 并且编号%p=c的点(保证至少存在2个这样的点且点数不超过20个), 让这些特殊点连通(任意两个特殊点之间至少存在一条路径).

这里有很多种修复方案, 每种修复方案中都有权值最大的边, fold希望找到这么多方案中: 边权最大值最小的一个方案

你能帮助fold计算出每次询问的最小值是多少吗?

这里询问是独立的, 也就是上一个询问里的修复计划并没有付诸行动.

点的编号从1开始

第一行三个正整数n. m. q, 含义如题面所述
接下来m行, 每行三个正整数X_i、Y_i、V_i, 表示一条连接X_i和Y_i的双向道路, 权值是V_i (1≤V_i≤1000000). 可能有自环, 可能有重边.
接下来Q行, 每行四个正整数L_i、R_i、P_i、C_i, 表示这次询问的点是[L_i,R_i](1≤L_i<R_i≤n)区间中所有编号%P_i(1≤P_i<n)=C_i(0≤C_i<P_i)的点. (保证参与询问的特殊点至少有两个且不超过20个)

输出q行, 每行一个正整数表示对应询问的答案.

5 5 2
1 2 5
5 1 5
3 1 1
4 2 9
1 1 5
1 4 1 0
2 3 1 0

9
5