Рус Uzb Eng

C8B. BOG’LIQLIK VA KESMA
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

Quyoncha ashula aytish, raqsga tushish va sportni yaxshi ko’radi. Shuning uchun u Sochiga olimpiadaga birdi. U Sochiga borib bir-biriga bog’kangan 5 ta xalqaga ko’zi tushdi. Unga bu bo’g’liqlik va kesishish yoqib qolfi. Olimpiada simvolini ko’tib o’zi simvol yaratishga kirishdi. Unda kesishishlar ko’p bolishi lozim.
Avval u koordinata tekisligidagi kesmalarni oldi. Bir nechta kesma chizib, u quyidagi savollarni o’yladi: chizilgan kesmalardan eng ko’pi bilan nechtasni tanlash mumkin, bunda ixtiyoriy ikkita kesma kesishishlarikesishishi lozim. Shuning uchun Quyoncha chiqilgan kesmalardan bittasi aniq tanlangan to’plamga kirishi lozim.
Quyoncha ikkita kesma kesishishini quyidagicha aniqlaydi: ikkita kesma kesishadi, agarda ularning keshishi uzunli 0 dan katta va ularning ikkalasini uzunkigidan kichik (kesmalar kesishadi, lekin ustma-ust tushmaydi). Bitta umumiy nuqtaga ega bo’lgan kesmalar kesishgan deb hisoblanmaydi. Bu masalani yechishga Quyonchaga yordam bering!

Входные данные:
Birinchi satrda kesmalar soni n ( 1 ≤ n≤ 3 000 ) berilgan. Keyingi n ta satrda ikkita son bilan kesmaning li va ri ( 1 ≤ li ≤ ri ≤ 10p ) boshi va oxirini koordinatasi berilgan. Hech qanday ikkita kesam bitta nuqtadan boshlanmaydi va bitta nuqtada tugamaydi.
n+2 satrda k ( 1 ≤ k ≤ 105 ) – so’rovlar soni berilgan. Keyingi har bir k ta satrda x ( 1 ≤ x ≤ n) son bilan kesama raqami berilgan.

Выходные данные:
K ta satrda i-satrda i-so’rovning javobini chiqaring.

Пример ввода Пример вывода
1
1 1
1
1
1
1 2
1
1
2
1 2
2 3
2
1
2
1




1




1
1
Область: Arifmetika
Источник задачи: acm.tuit.uz 8-contest

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.