Masala #0176

Xotira 64 MB Vaqt 2000 ms
14
Muallif: Sirojiddin

Uchuvchi

Shaharda 1 dan \(n\) gacha raqamlangan \(n\) ta bino bor, \(i\)-bino balandligi \(h_i\). Uchuvchini \(m\) ta samolyoti bor, \(i\)- samolyot \(a_i\) balandlikkacha ko’tarila oladi.

Uchuvchi parvozini qaysidir \(s\) shaharda boshlab, \(t\) shaharda tugatadi, bunda \(s ≤ t\) bo’lishi lozim. Ya’ni u faqat o’ng tomonga ucha oladi. Uchuvchi samolyot ko’tarila oladigan balandlikdan baland binoga bora olmaydi.

https://robocontest.uz/storage/images/m176.1.png

Sizning vazifangiz har bir samolyot uchun, necha xil parvoz uyushtirish mumkinligini topishdan iborat


Kiruvchi ma'lumotlar:

Birinchi qatorda mos ravishda binolar soni va samolyotlar sonini bildiruvchi \(n\) va \(m\) sonlari beriladi \((1 ≤ n, m ≤ 10^5)\). Ikkinchi qatorda \(n\) ta butun son \(h_1, h_2, \space\dots\space, h_n\) beriladi. Uchinchi qatorda esa \(m\) ta butun son, \(a_1, a_2, \space\dots\space, a_m\) beriladi \((1 ≤ h_i, a_i ≤ 10^6)\).


Chiquvchi ma'lumotlar:

Har bir samolyot uchun turli xil parvozlar sonini toping.


Misollar
# input.txt output.txt
1
6 3
1 3 2 4 1 2
2 3 4
5
9
21
Izoh:

Birinchi samolyot bilan uchuvchi quyidagicha parvozlarni amalga oshirishi mumkin: (1, 1), (3, 3), (5, 5), (5, 6), (6, 6).