D. K-сегментийн огтлолцол

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд координатын $Ox$ тэнхлэг дээр орших $n$ ширхэг сегмент болон $k$ тоо өгөгдөв.Хэрэв ямар нэг цэг нь дор хаяж $k$ ширхэг сегментэд харьяалагдаж байвал тус цэгийг ханасан гэж үзнэ.Тэгвэл бүх ханасан цэгүүдийг агуулах бөгөөд өөр бусдын агуулаагүй $Ox$ тэнхлэг дээрх хамгийн жижиг(сегментийн тоогоороо) сегментүүдийн олонлогийг олно уу.

Оролт

Эхний мөрөнд сегментийн тоо болон $k$-ын утгыг илэрхийлэх 2 бүхэл тоо $n$ болон $k$ ($1 ≤ k ≤ n ≤ 10^{6}$) өгөгдөнө.

Дараагийн $n$ ширхэг мөрний мөр болгонд $i$-дахь сегментийн захын цэгүүдийг илэрхийлэх 2 бүхэл тоо $l_{i}, r_{i}$ ($ - 10^{9} ≤ l_{i} ≤ r_{i} ≤ 10^{9}$) өгөгдөнө.Сегментүүд нь эмх замбараагүй өгөгдөх ба хоорондоо огтлолцсон байж болно.Мөн сегментүүд нь дурын дарааллаар өгөгдөнө.

Гаралт

Эхний мөрөнд сегментүүдийнх нь хамгийн бага тоо(өөрөөр хэлбэл сегментүүдийн олонлогийн элементийн тоо)болох $m$ бүхэл тоог хэвлэнэ.

Дараагийн $m$ ширхэг мөрний мөр болгонд хариулт болох сегментүүдийн олонлогийн $j$-дэх сегментийн захын цэгүүд болох 2 бүхэл тоо $a_{j}, b_{j}$ ($a_{j} ≤ b_{j}$)-г хэвлэнэ.Сегментүүд нь зүүнээс баруун уруугаа бичигдсэн байна.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 2
0 5
-3 2
3 8
Гаралт
2
0 2
3 5
Оролт
3 2
0 5
-3 3
3 8
Гаралт
1
0 5
Сэтгэгдлүүдийг ачааллаж байна...