题目描述

小C作为A省的新上任的省长，准备更新本省的交通系统，一共有$N$个城市，每个城市之间至少有一条路径，一共有$M$条路径。

所谓旧的不去新的不来，小C把这$M$条路径都摧毁了，然后打算修复重建，但是小C只打算修复其中一些路径让一些城市连通, 并不打算让全部的城市连通, 而是选择一些特殊的城市让它们连通。

每个城市都有一个独自的编号，一共有$Q$次询问, 对于每次询问, 他会选择所有编号在$[l,r]$之间, 并且编号$\mod P = C$的城市(保证至少存在2个这样的城市且不超过20个), 让这些特殊的城市连通(任意两个特殊城市之间至少存在一条路径).

这里有很多种修复方案, 但是修复不同路径要花费不同的价钱，每种修复方案中都有花费最多的路径, 小C希望找到这么多方案中: 修复路径花费最大值最小的一个方案

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

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

输入

第一行三个正整数$N, M, Q$, 含义如题面所述 接下来$M$行, 每行三个正整数$X_i, Y_i, V_i$, 表示一条连接$X_i, Y_i$的双向道路, 权值是$V_i$, 可能有自环, 可能有重边. 接下来$Q$行, 每行四个正整数$L_i、R_i、P_i、C_i$, 表示这次询问的城市是$[Li,Ri]$区间中所有编号$\mod P_i=C_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

数据范围

其实这个真实数据划分范围我给忘了，反正小数据有点分是不是这么多不确定

对于10%数据满足

• $1 \leq N \leq 100$
• $1 \leq M \leq 1000$
• $1 \leq Q \leq 10$

对于30%数据满足

• $1 \leq N \leq 1000$
• $1 \leq M \leq 10000$
• $1 \leq Q \leq 100$

对于100% 数据满足

• $1 \leq N \leq 2*10^4$
• $1 \leq M \leq 2*10^5$
• $1 \leq V_i \leq 10^6$
• $1 \leq Q \leq 5*10^4$
• $1 \leq P_i \leq N-1$
• $0 \leq C_i \leq P_i-1$