D. Кубууд

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

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

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

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

Нэг удаа Вася, Петя хоёр $m$ ширхэг кубыг зураг болгон угсарсан ба эдгээрийн нэг тус бүр дээр $0$-с $m - 1$ хүртэлх тооны аль нэгийг бичсэн (бүх тоо нэг удаа л харагдахаар). $OX$ хэвтээ тэнхлэгтэй, $OY$ босоо тэнхлэгтэй координатын систем гэж авч үзье. Куб бүр координаттай зүүн доод булангаараа холбогдсон ба куб бүрийн хувьд эдгээр координатууд нь бүхэл тоон утга байна.

Зураг нь тогтвортой байх ёстой. Энэ нь $X$ тэнхлэг дээр байрлаагүй ямар ч кубын хувьд түүний доор булан юмуу ирмэгээрээ холбогдсон ядаж нэг куб байна гэсэн үг. Өөрөөр $(x, y)$ кубын хувьд нэг бол $y = 0$ байна эсвэл $(x - 1, y - 1)$, $(x, y - 1)$ эсвэл $(x + 1, y - 1)$ координаттай куб байна гэсэн үг.

Одоо залуус зургийг задлаж кубуудыг нэг мөрөнд цувуулан тавихыг хүсч байна. Нэг үйлдэлд кубыг салгаад өрсөн байгаа блокуудын баруун талд нь тавих үйлдлүүд багтана. Залуус кубуудыг салгахдаа зургийг тогтвортой байлгахаар салгаж авна. Үйл явцыг илүү сонирхолтой болгох үүднээс залуус дараах тоглоомыг тоглохоор шийдсэн. Залуус зурагнаас кубыг салгахдаа ээлжлэн салгана. Зургийг салгасаны дараа $m$ кубуудын ямар ч куб дээрх цифрээс бүрдэх бүхэл тоон утгыг(тэгээр эхэлж болно) харахад амархан. Вася үүсэх тоог хамгийн их байлгахыг хүсч байгаа бол Петя эсрэгээр хамгийн бага байлгахыг хүсч байгаа. Вася тоглоомыг эхлүүлнэ.

Таны ажил бол хэрвээ залуус хамгийн тохиромжтой байдлаар тоглосон бол зургийг салгасаны дараа ямар тоо үүсэхийг тодорхойлох юм. Хариуг $10^{9} + 9$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэ.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $m$ ($2 ≤ m ≤ 10^{5}$) байна.

Дараагийн $m$ ширхэг мөрөнд кубуудын координатууд $x_{i}, y_{i}$ ($ - 10^{9} ≤ x_{i} ≤ 10^{9}$, $0 ≤ y_{i} ≤ 10^{9}$) дээр нь бичигдсэн тооныхоо өсөх дарааллаар байна. Хамгийн анхны зураг тогтвортой зураг байна.

Ямар ч хоёр куб ижил байрлалд байхгүй.

Гаралт

Бодлогын хариуг ганц мөрөнд хэвлэнэ.

Орчуулсан: Г.Мэндбаяр

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

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