C. Вилбур ба цэгүүд

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

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

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

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

Вилбур координатын хавтгай дээрх $n$ ширхэг цэгүүдийн олонлогоор тоглож байв.Бүх цэгүүд нь сөрөг биш бүхэл тоон координатуудтай.Түүнчлэн,хэрэв ямар нэгэн ($x$, $y$) цэг нь уг олонлогт харьяалагддаг бол $0 ≤ x' ≤ x$ болон $0 ≤ y' ≤ y$ ийм байх бүх ($x'$, $y'$) цэгүүд нь мөн уг олонлогт харьяалагдана.

Одоо Вилбур нь өөртөө байгаа олонлогийн цэгийн тоогоор тоглохыг хүссэн ба тэдгээрийг $1$-ээс $n$ хүртэлх ялгаатай бүхэл тоонуудад хуваарилах юм.Илүү гоо сайхны тааламжтай дугаарлах үүднээс,Вилбур хэрэв ямар нэгэн ($x$, $y$) цэг нь нь $i$ тоотой байвал $x' ≥ x$ болон $y' ≥ y$ байх олонлогийн бүх ($x'$,$y'$) цэгүүд нь $i$-аас багагүй тоонд хуваарилагдсан байна гэсэн нөхцөл заажээ.Жишээлбэл ($0$, $0$), ($0$, $1$), ($1$, $0$) болон ($1$, $1$) гэсэн 4-н цэгийн олонлогийн хувьд 2 янзын гоо сайхны тааламжтай дугаарлалт байна.Нэг нь $1$, $2$, $3$, $4$ ба нөгөө нэг нь $1$, $3$, $2$, $4$ юм.

Вилбур-ын найз цуг ирсэн ба Вилбур-тай өрсөлдөх юм.Ямар ч цэгийн хувьд тэрээр уг цэгийн онцгой утга $s(x, y) = y - x$-г тодорхойлно.Одоо тэрээр Вилбур-т $w_{1}$, $w_{2}$,..., $w_{n}$ өгөх ба түүнээс $i$ тоон дээр хуваарилагдах цэгийн онцгой утга нь $w_{i}$-тай тэнцүү буюу өөрөөр хэлбэл $s(x_{i}, y_{i}) = y_{i} - x_{i} = w_{i}$ байхаар олонлог дахь цэгүүдийг гоо сайхны тааламжтай дугаарлах хуваарилалтыг олохыг асуужээ.

Одоо Вилбур таныг уг өрсөлдөөнд туслахыг хүсжээ.

Оролт

Эхний мөрөнд Вилбур-ын тоглож байгаа олонлогийн цэгийг тоог илэрхийлэх ганц бүхэл тоо $n$ ($1 ≤ n ≤ 100 000$) өгөгдөнө.

Дараагийн $n$ ширхэг мөрөнд цэгүүдийн тайлбар байна.Мөр болгонд Вилбур-ын олонлогийн нэг цэгийг өгөх 2 бүхэл тоо $x$ болон $y$ ($0 ≤ x, y ≤ 100 000$) байна.Бүх цэгүүд нь ялгаатай байна.Мөн хэрэв ($x$, $y$) цэг нь оролтод өгөгдсөн бол $0 ≤ x' ≤ x$ болон $0 ≤ y' ≤ y$ байх бүх ($x'$, $y'$) цэгүүд нь мөн оролтод өгөгдөнө.

Оролтын сүүлийн мөрөнд $n$ ширхэг бүхэл тоо өгөгдөнө.Эдгээрийн $i$-дахь нь $w_{i}$ ($ - 100 000 ≤ w_{i} ≤ 100 000$) байх ба -- энэ нь ямар нэгэн гоо сайхны тааламжтай дугаарлалтын $i$ тоотой цэгийн шаардагдсан онцгой утгыг илэрхийлнэ.

Гаралт

Хэрэв олонлогийн цэгүүдийг $s(x_{i}, y_{i}) = y_{i} - x_{i} = w_{i}$ байхаар гоо сайхны тааламжтай дугаарлах хуваарилалт байвал гаралтын эхний мөрөнд "$YES$" гэж хэвлэнэ.Бусад тохиолдолд "$NO$" гэж хэвлэнэ.

Хэрэв бодолт байвал, $n$ ширхэг мөрөнд гаралтыг хэвлэнэ.$i$-дахь мөрөнд $i$ дугаартай цэгийг хэвлэнэ.Хэрэв олон хариулт байвал алийг нь ч хэвлэсэн болно.

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

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

Оролт
5
2 0
0 0
1 0
1 1
0 1
0 -1 -2 1 0
Гаралт
YES
0 0
1 0
2 0
0 1
1 1
Оролт
3
1 0
0 0
2 0
0 1 2
Гаралт
NO

Тэмдэглэл

Эхний жишээнд, ($2$, $0$) цэг $3$ дугаартай, ($0$, $0$) цэг $1$ дугаартай, ($1$, $0$) цэг $2$ дугаартай, ($1$, $1$) цэг $5$ дугаартай ба ($0$, $1$) цэг $4$ гэсэн дугаартай байх юм.Хэн ч уг дугаарлалт нь гоо сайхны тааламжтай ба $y_{i} - x_{i} = w_{i}$ байна гэдгийг хялбархан шалгаж чадна.

2-дахь жишээнд олонлогийн цэгүүдийн онцгой утгууд нь $0$, $ - 1$, болон $ - 2$ ба найзынх нь Вилбур-т өгсөн дараалал нь $0$, $1$, $2$ байна.Иймд хариулт байхгүй.

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