D. Шидтэнүүд ба Замууд

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

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

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

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

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

Уг улсад $k$ ширхэг хот байсан бөгөөд $j$-р хот нь ($1 ≤ j ≤ k$) ($x_{j}$, $y_{j}$) гэсэн цэг дээр байрлалтай байжээ. Тэд дахин $n - k$ ширхэг хот барихаар шийдсэн ба $i$-р хотыг ($k < i ≤ n$) ($x_{i}$, $y_{i}$) гэсэн координатууд бүхий цэг дээр барив:

  • $x_{i} = (a*x_{i - 1} + b) mod (10^{9} + 9)$
  • $y_{i} = (c*y_{i - 1} + d) mod (10^{9} + 9)$

Энд $a$, $b$, $c$, $d$-ууд нь анхны тоонууд байх бөгөөд $a ≠ c, b ≠ d$ байх юм.

Бүх $n$ ширхэг хотын барилгын ажил дууссаны дараагаар шидтэнүүд нэгэн гайхалтай зүйлийг анзаарчээ. Ямар ч 2 ялгаатай хотууд $i$ болон $j$-ын хувьд $x_{i} ≠ x_{j}$, $y_{i} ≠ y_{j}$ гэсэн нөхцөлүүд биелж байв.

Хотууд баригдаж дууссан бөгөөд одоо замуудыг барих цаг болжээ! Шидтэнүүд хамгийн хэцүү буюу хамгийн хүчирхэг ид шидийг замуудыг барихад хэрэглэхээр шийдэв. Хэрэв $u$, $v$ гэсэн цэгүүдийн (хотуудын) яг булан дотор(булан гэж юу болох талаар доорх зургаас харна уу) нь байрлах ямар ч $w$ хотуудын хувьд уг булан дотор агуулагдаагүй бөгөөд $w$ болон $u$ хотуудын яг хооронд $x$ координат нь байрлах $s$ хот оршин (мөн $y_{s} > y_{v}$ байх ёстой юм) байвал уг ид шидийг хэрэглэснээр бид $u$, $v$ ($y_{u}$ > $y_{v}$) хотуудын хооронд зам үүсгэж чадах юм.

$p_{2}$($x_{2}$, $y_{2}$), $p_{1}$($x_{1}$, $y_{1}$) ($y_{1} < y_{2}$) гэсэн цэгүүдийн булан гэдэг нь дараах 2 нөхцөлийн дор хаяж нэгийг нь хангах ($x, y$) цэгүүдийн олонлогийг хэлнэ:

  • $min(x_{1}, x_{2}) ≤ x ≤ max(x_{1}, x_{2})$ бөгөөд $y ≥ y_{1}$
  • $y_{1} ≤ y ≤ y_{2}$ ба $(x - x_{2})*(x_{1} - x_{2}) ≥ 0$ Уг зурагт 2 ялгаатай буланг дүрсэлсэн байна.

Уг ид шидийг шалгахын тулд шидтэнүүд $x$ координат нь $[L, R]$ гэсэн интервал дотор байх бүх хотуудын хувьд уг ид шидийг хэрэглэхээр болжээ. Замуудыг барьж дууссаны дараагаар засгийн газар хоорондоо замаар холбогдсон боломжит хамгийн олон хос хотуудыг сонгон авах бөгөөд ингэхдээ эдгээр хотуудаас аль ч хот нь 2 эсвэл түүнээс олон хос хот дотор ороогүй байхаар сонгох юм. Таны даалгавар бол $L$, $R$-ын $m$ ширхэг өгөгдсөн хувилбар бүрийн хувьд замуудыг барьж дууссаны дараагаар ийм байх хос хотуудын хамгийн их тоог олох юм. $x$ координатууд нь $[L, R]$ интервал дээр байрлаагүй хотууд замын барилгын явцад ямар нэгэн байдлаар нөлөөлөхгүй гэж үзнэ үү.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$, $k$ ($1 ≤ k ≤ n ≤ 10^{5}$, $k ≤ 30$) өгөгдөнө. Дараагийн $k$ мөрөнд хотуудын координатууд өгөгдөх ба ингэхдээ эхний хотоос $k$-р хот хүртэлх дарааллын дагуу өгөгдөнө. $j$-дэх мөрөнд зайгаар тусгаарлагдсан хос бүхэл тоо $x_{j}$, $y_{j}$ ($0 ≤ x_{j}, y_{j} < 10^{9} + 9$)-ууд өгөгдөх ба эдгээр нь $j$-р хотын координатуудыг илэрхийлнэ.

Дараагийн мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $a, b, c, d$ ($2 ≤ a, b, c, d < 10^{9} + 9$)-ууд өгөгдөнө. Эдгээр тоонууд нь анхны тоонууд байх бөгөөд $a ≠ c, b ≠ d$ гэсэн нөхцөлийг хангасан байна

Мөн ялгаатай $i$ болон $j$ гэсэн 2 хот бүрийн хувьд $x_{i} ≠ x_{j}$ болон $y_{i} ≠ y_{j}$ гэсэн нөхцөлүүд биелж байна.

Дараагийн мөрөнд бүхэл тоо $m$ ($1 ≤ m ≤ 10^{5}$) өгөгдөх ба энэ нь замуудыг барих хувилбаруудын тоог илэрхийлнэ. Дараагийн $m$ ширхэг мөрийн мөр болгонд зайгаар тусгаарлагдсан бүхэл тоонууд $L_{i}$, $R_{i}$ ($0 ≤ L_{i} ≤ R_{i} < 10^{9} + 9$)-ууд өгөгдөх ба эдгээр нь замууд барих хотуудыг сонгох хувилбаруудыг илэрхийлнэ.

Гаралт

$L_{i}$, $R_{i}$ гэсэн хос тоо бүрийн хувьд бодлогыг хариултыг дан мөрөнд хэвлэнэ үү. Эдгээр хосуудын хувьд хариултуудыг хэвлэхдээ оролтод өгөгдсөн дарааллынх нь дагуу хэвлэнэ үү.

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

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

Оролт
6 6
0 0
1 1
2 2
3 3
4 4
5 5
2 3 3 2
4
0 5
1 4
2 3
3 3
Гаралт
3
2
1
0
Оролт
6 1
0 0
3 5 23917 11
4
0 1000000008
0 10
100 150
200 10000
Гаралт
2
1
0
1

Тэмдэглэл

Эхний жишээнд замууд нь хотуудыг $x$-ын ихсэх дарааллын дагуу гинжин байдлаар холбосон байна.

2-дахь жишээнд үлдсэн 5-н хотууд нь $(5,  11); (20,  263098); (65,  292514823); (200,  76958738); (605,  622120197)$ гэсэн цэгүүд дээр байрласан байх юм.

Сэтгэгдлүүдийг ачааллаж байна...