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