C. Бяцхан Артем ба Бүжиг

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

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

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

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

Бяцхан Артем бүжигт дуртай нэгэн юм. Бүх бүжиг дундаас Артем Куб бүжиг болох рүеда гэх бүжигт хамгийн их дуртай бөгөөд уг бүжиг нь охид болон хөвгүүдийн хосууд нь нэгэн тойрог үүсгэн хамтдаа бүжиглэдэг бүжиг юм.

Илүү тодруулбал, нийтдээ $n$ ширхэг охид болон хөвгүүдийн хосууд нэгэн тойрог дээр зогсож байх юм. Анхандаа $1$ гэсэн дугаартай хөвгүүн нь $1$ гэсэн дугаартай охинтой бүжиглэх ба $2$ гэсэн дугаартай хөвгүүн нь $2$ гэсэн дугаартай охинтой бүжиглэнэ гэх мэтчилэн үргэлжлэх ажээ. Охид нь цагийн зүүний дагуу дугаарлагдсан байв. Бүжгийн дундуур ялгаатай хөдөлгөөнүүд зарлагдах ба бүх хосууд нь уг хөдөлгөөнийг гүйцэтгэнэ. Түүнчлэн хөдөлгөөнүүдийг гүйцэтгэх явцдаа хөвгүүд нь уг тойргийн дагуу хөдлөх бөгөөд охид нь үргэлж анх байсан байрандаа байх ажээ. Уг бодлогын туршид бид 2 ялгаатай төрлийн хөдөлгөөнүүдийг авч үзнэ:

  1. $x$ утга болон ямар нэгэн чиглэлийг зарлах бөгөөд бүх хөвгүүд зарласан чиглэлийн дагуу $x$ ширхэг байрлал шилжинэ.
  2. Тэгш дугаартай охидтой бүжиглэж буй хөвгүүд нь сондгой дугаартай охидтой бүжиглэж буй хөвгүүдтэй байрлалаа солино. Тодруулбал $1$ гэсэн дугаартай охинтой бүжиглэж буй хөвгүүн нь $2$ гэсэн дугаартай охинтой бүжиглэж буй хөвгүүнтэй байраа солих ба $3$ гэсэн дугаартай охинтой бүжиглэж буй хөвгүүн нь $4$ гэсэн дугаартай охинтой бүжиглэж буй хөвгүүнтэй байраа солино гэх мэтчилэн үргэлжлэх ажээ. Энд $n$ тоо нь заавал тэгш тоо байх юм.

Таны даалгавар бол хөвгүүн бүрийн хувьд эцсийн байрлалыг тогтоох явдал байв.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $q$ ($2 ≤ n ≤ 1 000 000$, $1 ≤ q ≤ 2 000 000$) өгөгдөх ба эдгээр нь харгалзан рүеда-г бүжиглэж буй хосуудын тоо болон нийт биелүүлэх ёстой хөдөлгөөний тоог тус тус илэрхийлнэ. Энд $n$ тоо нь заавал тэгш тоо байна.

Дараагийн $q$ ширхэг мөрөнд хөдөлгөөнүүдийн тайлбар өгөгдөнө. Хөдөлгөөн болгоны тайлбар нь эхлээд уг хөдөлгөөний төрлийг илэрхийлэх $1$ эсвэл $2$ гэсэн бүхэл тоо агуулсан байна. Эхний төрлийн хөдөлгөөн нь $x$ ($ - n ≤ x ≤ n$) гэж өгөгдвөл энэ нь бүх хөвгүүд цагийн зүүний дагуу чиглэлд $x$ ширхэг байрлал шилжинэ гэсэн үг бөгөөд $ - x$ гэж өгөгдсөн байвал цагийн зүүний эсрэг чиглэлд $x$ ширхэг байрлал шилжинэ гэсэн үг юм. 2-р төрлийн хөдөлгөөнүүдийн хувьд ямар нэгэн нэмэлт оролтын өгөгдөл байхгүй байна.

Гаралт

$n$ ширхэг бүхэл тоо хэвлэх ба эдгээрийн $i$-дахь тоо нь бүх $q$ ширхэг хөдөлгөөнийг гүйцэтгэсний дараагаар $i$-р охинтой бүжиглэж байх хөвгүүний дугаартай тэнцүү байх ёстой юм.

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

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

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