Uzb Eng

C8B. BOGLIQLIK VA KESMA
: 2 c
: 64

Quyoncha ashula aytish, raqsga tushish va sportni yaxshi koradi. Shuning uchun u Sochiga olimpiadaga birdi. U Sochiga borib bir-biriga bogkangan 5 ta xalqaga kozi tushdi. Unga bu bogliqlik va kesishish yoqib qolfi. Olimpiada simvolini kotib ozi simvol yaratishga kirishdi. Unda kesishishlar kop bolishi lozim.
Avval u koordinata tekisligidagi kesmalarni oldi. Bir nechta kesma chizib, u quyidagi savollarni oyladi: chizilgan kesmalardan eng kopi bilan nechtasni tanlash mumkin, bunda ixtiyoriy ikkita kesma kesishishlarikesishishi lozim. Shuning uchun Quyoncha chiqilgan kesmalardan bittasi aniq tanlangan toplamga 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 bolgan 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 ) sorovlar soni berilgan. Keyingi har bir k ta satrda x ( 1 ≤ x ≤ n) son bilan kesama raqami berilgan.

:
K ta satrda i-satrda i-sorovning 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.