Pear市一共有N（<=50000）個居民點，居民點之間有M（<=200000）條雙向道路相連。這些居民點兩兩之間都可以通過雙向道路到達(dá)。這種情況一直持續(xù)到最近，一次嚴(yán)重的地震毀壞了全部M條道路。
震后，Pear打算修復(fù)其中一些道路，修理第i條道路需要Pi的時間。不過，Pear并不打算讓全部的點連通，而是選擇一些標(biāo)號特殊的點讓他們連通。
Pear有Q（<=50000）次詢問，每次詢問，他會選擇所有編號在[l,r]之間，并且 編號 mod K  = C 的點，修理一些路使得它們連通。由于所有道路的修理可以同時開工，所以完成修理的時間取決于花費時間最長的一條路，即涉及到的道路中Pi的最大值。

你能幫助Pear計算出每次詢問時需要花費的最少時間么？這里詢問是獨立的，也就是上一個詢問里的修理計劃并沒有付諸行動。

第一行三個正整數(shù)N、M、Q，含義如題面所述。
接下來M行，每行三個正整數(shù)Xi、Yi、Pi，表示一條連接Xi和Yi的雙向道路，修復(fù)需要Pi的時間?？赡苡凶原h(huán)，可能有重邊。1<=Pi<=1000000。

接下來Q行，每行四個正整數(shù)Li、Ri、Ki、Ci，表示這次詢問的點是[Li,Ri]區(qū)間中所有編號Mod Ki=Ci的點。保證參與詢問的點至少有兩個。

輸出Q行，每行一個正整數(shù)表示對應(yīng)詢問的答案。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點擊這里了解課程詳情

藍(lán)橋杯