给出一幅有n(≤20000)个点, m(≤200000)条边的无向图. 保证任意2点间都至少存在一条路径可以连通, 每条边上都有一个权值Vi(≤1000000)
不幸的是, 这m条边都被损坏了.
fold打算修复其中一些边让一些点连通, 不过, fold并不打算让全部的点连通, 而是选择一些编号特殊的点让它们连通.
fold有q(≤50000)次询问, 对于每次询问, 他会选择所有编号在[l,r]之间, 并且编号%p=c的点(保证至少存在2个这样的点), 让这些特殊点连通(任意两个特殊点之间至少存在一条路径).
这里有很多种修复方案, 每种修复方案中都有权值最大的边, fold希望找到这么多方案中: 边权最大值最小的一个方案
你能帮助fold计算出每次询问的最小值是多少吗?
这里询问是独立的, 也就是上一个询问里的修复计划并没有付诸行动.
点的编号从1开始
第一行三个正整数n. m. q, 含义如题面所述
接下来m行, 每行三个正整数Xi、Yi、Vi, 表示一条连接Xi和Yi的双向道路, 权值是Vi (1≤Vi≤1000000). 可能有自环, 可能有重边.
接下来Q行, 每行四个正整数Li、Ri、Pi、Ci, 表示这次询问的点是[Li,Ri](1≤Li<Ri≤n)区间中所有编号%Pi(1≤Pi<n)=Ci(0≤Ci<Pi)的点. (保证参与询问的特殊点至少有两个)
输出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