Sapan
Fermer Con gübrə daşımağı sevmir. O, nəhəng sapand vasitəsilə gübrə qablarını havada hərəkət etdirməyi planlayır.
Conun ferması düz yol boyunca yerləşir, buna görə də fermanın istənilən nöqtəsi bu yolda bir mövqe (rəqəmli oxda bir nöqtə) ilə təsvir edilə bilər. Con n sapand qurub, i-ci sapand üç tam ədədlə təsvir olunur: x[i], y[i], t[i]. Bu, sapandın gübrəni x[i] mövqeyindən y[i] mövqeyinə t[i] vaxt vahidi ərzində hərəkət etdirə biləcəyini göstərir.
Conun daşınması üçün m gübrə qabı var. j-ci qabı a[j] mövqeyindən b[j] mövqeyinə köçürmək lazımdır. Traktorla gübrə qabını d məsafəsinə köçürmək d vaxt vahidi çəkir. Con sapandlardan istifadə edərək vaxtı azaltmağa ümid edir. Gübrəsiz traktorun hərəkət vaxtı nəzərə alınmır.
Hər bir m gübrə qabı üçün yalnız bir sapanddan istifadə etməklə mümkün olan minimum daşınma vaxtını müəyyən edin.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) və m (1 ≤ m ≤ 10^5) ədədlərini ehtiva edir. Növbəti n sətirin hər biri üç ədəd x[i], y[i], t[i] (0 ≤ x[i], y[i], t[i] ≤ 10^9) ilə bir sapandı təsvir edir. Son m sətir isə daşınması lazım olan gübrə qablarını iki tam ədəd a[j] və b[j] ilə təsvir edir.
Çıxış Məlumatları
Hər bir gübrə qabı üçün uyğun gübrə qabının daşınması üçün minimum vaxtı ehtiva edən m sətir çıxarın.
Nümunə
Burada birinci qabı 1 mövqeyindən 12 mövqeyinə köçürmək lazımdır. Sapandlardan istifadə etmədən bu 11 vaxt vahidi çəkəcək. Lakin, birinci sapanddan istifadə etsək, bu 1 vaxt vahidi çəkəcək ki, qabı 1 mövqeyindən 0 mövqeyinə (birinci sapandın başlanğıc nöqtəsi) köçürək, 1 vaxt vahidi havada 10 mövqeyinə (birinci sapandın bitiş nöqtəsi) ataq və sonra 2 vaxt vahidi traktorla 12 mövqeyinə köçürək. İkinci gübrə qabını sapanddan istifadə etmədən köçürmək daha sərfəlidir. Üçüncü gübrə qabını isə ikinci sapanddan istifadə edərək köçürmək daha sərfəlidir.