PROGRAMING PROBLEMS

Сурагчдын дотуур байрны угаалгын ажилтнууд цагаан даавуугаа угааж арын хашаандаа хатаахаар өлгөв (нуглалгүйгээр). Даавуунуудаа өлгөхдөө аль даавууны үзүүрүүд давхцахгүй ба харин том даавуун дээр жижиг даавууг тохох эсвэл жижиг даавуун дээр том даавууг бүрэн бүрхэж байхаар өлгөсөн.

Ажилтнуудыг даавуугаа тохсны дараа алдартай дүрсгүй хэдэн жаал янз бүрийн өнгө (M тооны ялгаатай өнгө бий)-тэй шингэнээр шүршдэг усан буугаар тоглон орж ирэв. Зарим хүүхдийн буу ижил өнгийн шингэнтэй. Жаалууд угаасан цагаан даавуу буудаж тогтов. Тэд цагаан даавуу руу усан буугаараа буудахад шингэний өнгөтэй жижиг дугуй толбо үүсгэж, уг толбо нь давхарлаж өлгөсөн бүх цагаан даавуунд нэвтэрч байв. Жаалууд ажилтнуудыг гарч ирэхээс өмнө зугтаан алга болжээ.

Ажилтнууд гарч ирээд цагаан даавуу нь олон өнгийн толботой болсныг хараад зочирдов. Тиймээс таниас цагаан даавуу бүр дээр хэчнээн өнгийн толбо тогтсоныг тооцоолж өгөхийг хүсэж байна. Түүнд тусална уу.

Загварчлал: Сургуулийн арын хашааг хязгааргүй урт, өргөнтэй ба цагаан  даавууг координатын тэнхлэгтэй параллель тэгш өнцөгт хэлбэртэй, харин хүүхдүүдийн буудсан толбыг уг координатын систем дэх цэг гэж үзнэ.

Оролт

Эхний мөрөнд цагаан даавууны тоо N (1 ≤ N ≤ 80 000), шингэний өнгөний тоо M (1 ≤ M ≤ 80 000) гэсэн бүхэл тоонууд байна.

 Дараах N мөр бүрд дөрвөн бүхэл тоо байна. i дүгээр мөрд буй дөрвөн тоо нь i дүгээр цагаан даавууны зүүн доод булангийн координат Ai, Bi (1 ≤ Ai, Bi ≤ 10⁹) ба баруун дээд булангийн координат Ci, Di, (1 ≤ Ci, Di ≤ 10⁹) болно.

Дараах M мөрийн j дүгээрт j дүгээр усан буугаар оносон координат Xi, Yi (1 ≤ Xj, Yj ≤ 10⁹), усан бууны шингэний өнгө Kj (1 ≤ Kj ≤ 10⁹)  байна.

Гаралт

N мөртэй байх ба i дүгээр мөрд i цагаан даавууны өнгөний толбоны тоо байна.

Жишээ