E. Петя ба Шуудан

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

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

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

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

Бяцхан Петя-ын авга ах нь шуудан зөөгч ажээ. Шуудангийн салбарууд нь нэгэн тойрог зам дээр байрласан байв. Түүнчлэн салбар болгон нь өөрийн гэсэн шатахуун түгээх станцтай(ШТС) бөгөөд уг ШТС нь тухайн шуудангийн салбарынхаа яг хажууд нь байрлаж байх юм. Петя-ын авга ах нь дараах байдлаар ажиллана: өглөөдөө тэрээр өөрийн гэрээсээ гарч явах бөгөөд ямар нэгэн шуудангийн салбар уруу явах юм. Очсон салбар дээрээ тэрээр хэсэг тооны захиа болон нэгэн машин хүлээн авна. Дараа нь тэрээр түүнд өгсөн машиныг унаж тойрог замыг яг нэг удаа тойрох ёстой бөгөөд анх явсан шуудангийн салбар дээрээ эргэн ирэх ёстой байв. Түүнчлэн авга ах нь уг тойрог замыг аль ч чиглэлийн дагуу туулж чадах бөгөөд тодруулбал цагийн зүүний эсрэг эсвэл цагийн зүүний дагуу явах юм. Уг машин нь хотын шуудангийн газарт харьяалагдах учраас машинд шатахуун нэмэхдээ зөвхөн шуудангийн газар байрлах ШТС дээр очиж шатахуун нэмэх ажээ.

Нийт ШТС-уудын тоо нь $n$-тэй тэнцүү байна. Та $i$-р ШТС дээр өөрийн машиндаа $a_{i}$ литрээс илүүгүй шатахуун хийж чадна. Түүнчлэн та ШТС бүр дээр өөрийн машиндаа нэгээс олон тооны удаа шатахуун хийж болохгүй. Мөн $1$-р болон $2$-р ШТС-уудын хоорондох зай нь $b_{1}$ километр, $2$-р болон $3$-р ШТС-уудын хоорондох зай нь $b_{2}$ километр, ..., $(n - 1)$-р болон $n$-р ШТС-уудын хоорондох зай нь $b_{n - 1}$ километр ба $n$-р болон $1$-р ШТС-уудын хоорондох зай нь $b_{n}$ километр байх юм. Петя-ын авга ахын өндөр технологийн машин нь километр тутамд зөвхөн нэг литр шатахуун хэрэглэнэ. ШТС-ууд нь ийм байдлаар байрласан болох нь мэдэгдэж байгаа ба бүх $a_{i}$-уудын нийлбэр нь бүх $b_{i}$-уудын нийлбэртэй тэнцүү байв. $i$-р ШТС болон $i$-р шуудангийн салбар нь машин ойрхон байрлах тул тэдгээрийн хоорондох зайг $0$ километр гэж үзнэ үү.

Түүнчлэн хэрэв бид ямар нэгэн шуудангийн салбараас эхэлж хөдөлсөн бол уг тойрог замыг нэг бүтэн тойрч явах нь үргэлж боломжтой биш болох нь тодорхой байв. Өөрөөр хэлбэл зарим нэг шуудангийн салбараас эхэлж хөдөлсөн тохиолдолд уг тойрог замыг бүтэн тойрч чадахгүй байх юм. Авга ах дараах асуудалтай тулгарчээ. Өглөөдөө тэрээр ямар салбар уруу очвол тойрог зам дээрх бүх салбаруудаар зорчин яг нэг тойрог зам явж чадах вэ?

Петя программчлалын хичээлд сууж байсан бөгөөд авга ахдаа сайн дураараа туслахыг хүсжээ. Гэвч түүний мэдлэг уг бодлогыг бодоход хангалтгүй болж таарсан бөгөөд иймд тэрээр танаас уг бодлогыг бодох программ бичиж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөнө. 2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{i}$-ууд өгөгдөх ба эдгээр нь $i$-р ШТС-ын шатахууны хэмжээг илэрхийлнэ. 3-дахь мөрөнд $n$ ширхэг бүхэл тоонууд $b_{1}, b_{2}, ..., b_{n}$-ууд өгөгдөнө. Эдгээр тоонууд нь харгалзан $1$-р болон $2$-р ШТС-уудын хоорондох зай, $2$-р болон $3$-р ШТС-уудын хоорондох зай, ..., $n$-р болон $1$-р ШТС-уудын хоорондох зайг илэрхийлнэ. Бүх $b_{i}$-уудын нийлбэр нь бүх $a_{i}$-уудын нийлбэртэй тэнцүү байх бөгөөд $10^{9}$-өөс ихгүй байна. $a_{i}$, $b_{i}$ гэсэн тоо бүр нь $1$-ээс багагүй байх бөгөөд $10^{9}$-өөс ихгүй байна.

Гаралт

Эхний мөрөнд $k$ тоог хэвлэх ба энэ нь машин тойрог замыг нэг тойрог явж чадах боломжит шуудангийн салбаруудын тоог илэрхийлнэ. 2-дахь мөрөнд $k$ ширхэг тоонуудыг өсөх дарааллаар хэвлэх ба эдгээр нь машин эхэлж явж болох салбаруудын дугааруудыг илэрхийлнэ.

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

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

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