E. Мэлхийн тулаан

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

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

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

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

Остап Бендер саяхан мэлхийн фермээр зочилсон ба өөрийн гэсэн мэлхийн тоглоом бүтээх урам орсон.

Хэд хэдэн мэлхийнүүд $m$ нүдэнд хуваагдсан давтагдах тоглоомын хавтан дээр байрлана. Нүднүүд $1$-с $m$ хүртэл дугаарлагдах боловч хавтан давтагдахуйц ба $1$ дугаартай нүд $m$ дугаартай нүдний баруун талд байрлан хөдөлгөөний чигт хөдлөнө.

Мэлхийнүүд ээлжээр хөдлөх ба $1$ мэлхийн хөдөлгөөнөөр тоглоом эхэлнэ. $i$-р мэлхий өөрийн ээлжиндээ урагшаа $a_{i}$ нүд явах ба замдаа байгаа бүх мэлхийг бут цохино. Хэрвээ $i$-р мэлхийн замын сүүлийн нүдэнд мэлхий байвал уг мэлхийг ч бут цохино. Үүний дараа $a_{i}$ утга тухайн ээлжинд бут цохиулсан мэлхийнүүдийн тоогоор хорогдоно. Хэрвээ $a_{i}$ нь тэг эсвэл сөрөг болох юм бол $i$-р мэлхий дахин хөдлөхгүй.

$1$ дугаартай мэлхийн ээлж дууссаны дараа $2$ дугаартай мэлхий хөдлөж эхэлнэ тэгээд $3$ дугаартай мэлхий гээд үргэлжилнэ. $n$ дугаартай мэлхий хөдөлж дууссаны дараа $1$ дугаартай мэлхий дахин хөдлөж эхэлнэ, тэгээд $2$ дугаартай мэлхий гээд энэ үйл явц үүрд үргэлжилнэ.

Остапд тоглоомын эцэст хавтан дээр ямар мэлхийнүүд үлдэхийг тодорхойлоход туслана уу?

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n ≤ 100000, 1 ≤ m ≤ 10^{9}, n ≤ m$) байх ба харгалзан мэлхийнүүдийн тоо ба тоглоомын хавтангийн хэмжээ байна.

Дараагийн $n$ мөрөнд мэлхийнүүдийн тодорхойлолт буюу $p_{i}$ болон $a_{i}$ ($1 ≤ p_{i}, a_{i} ≤ m$) байх ба анх $i$-р мэлхийд эзлэгдсэн нүдний дугаар ба анхны үсрэлтийн урт байна. Бүх $p_{i}$ ялгаатай байх нь тодорхой.

Гаралт

Эхний мөрөнд эцсийн тоглоомын талбар дээр байх мэлхийнүүдийн тоо байна. Хоёр дахь мөрөнд мэлхийнүүдийн дугаар дурын дараалалтай байна.

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

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

Оролт
3 5
2 1
5 3
4 3
Гаралт
1
3 
Оролт
5 6
1 2
3 4
2 5
5 1
6 1
Гаралт
2
1 4 

Тэмдэглэл

Эхний жишээн дээр эхний мэлхий $1$ нүд үсрэх ба $3$ дугаартай нүдэнд бууна. Хоёрдугаар мэлхий $3$ нүд үсрэх ба $3$ дугаартай нүдэнд бууж $1$ дугаартай мэлхийг бут цохино. $2$-р мэлхийн үсрэх урт нь одоо $2$. Гуравдугаар мэлхий $2$ нүдрүү үсрэх ба тэгээд хоёрдугаар мэлхий $5$ нүдрүү үсрэнэ. Гуравдугаар мэлхийний ээлж ирж $5$ нүдэн дээр буух ба $2$ дугаартай мэлхийг тоглоомын хавтангаас бут цохино. Одоо тэр тоглоомонд үлдэж буй ганц мэлхий боллоо.

Хоёр дахь жишээн дээр эхний мэлхий $2$ нүд үсрэх ба $2$ болон $3$ нүдэнд байгаа мэлхийнүүдийг бут цохино. Түүний $a_{i}$ утга одоо $0$. Тэгээд дөрөвдүгээр мэлхий үсэрч тавдугаар мэлхийг бут цохих ба түүний $a_{i}$ утга ч бас одоо $0$. Энэ хоёр мэлхий тоглоомын хавтан дээр үүрд үлдэнэ.

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