E. Нүх

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

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

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

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

Бяцхан Петя тоглох маш их дуртай. Гэхдээ “Нүх” хэмээх тоглоомыг тоглох хамгийн их дуртай. Нэг хүн тоглоход зориулсан энэхүү тоглоомыг дараах дүрмээр тоглоно:

Нэг эгнээнд $N$ гэсэн нүхнүүд байх ба эдгээрийг зүүнээсээ баруун тийш $1$-ээс $N$ гэж дугаарлана. Нүх бүр өөрийн гэсэн хүч чадалтай ($i$ дахь нүх $a_{i}$ хүчтэй). Хэрэв $i$ нүх рүү бөмбөг шидэж оруулбал энэ нь үсрэн гарч цааш $i + a_{i}$ нүхэнд орж дахин буцаж гарч дараагийн нүх рүү орох гэх мэтчилэн үргэлжилнэ. Хэрэв ямар нэг тоо байхгүй байлаа гэхэд бөмбөг эгнээнээс үсэрч гарна. $M$ хөдөлгөөн бүрт тоглогч хоёр үйлдлийн нэгийг гүйцэтгэх боломжтой.

  • $b$ нүхний хүч чадалыг олж мэдэхийг тулд $a$ нүхний хүчийг ашиглана.

  • $a$ нүх рүү бөмбөг шидээд тус бөмбөг эгнээнээс гартал хичнээн удаа өөр нүх рүү үсэрч орохыг тоолох ба бөмбөг аль нүхнээс аль нүх рүү орж буй дарааллыг мөн бичиж авна.

Таны таамагласанаар Петя математикт тийм ч сайн биш бөгөөд та түүний өмнөөс бүх тооцоололуудыг хийх болно.

Оролт

Эхний мөр нь $N$ болон $M$ ($1 ≤ N ≤ 10^{5}$, $1 ≤ M ≤ 10^{5}$) гэсэн хоёр бүхэл тоо агуулах ба энэ нь тухайн эгнээнд буй нүхний тоо болон бөмбөгний нүүдлийн тоог илэрхийлж байна. Хоёр дахь мөр нь нүхнүүдийн чадварын анхны үнэлгээг илэрхийлэх $N$-ээс хэтрэхгүй $N$ эерэг утгатай бүхэл тоо агуулж байна.

  • $0$ $a$ $b$
  • $1$ $a$

$0$ нь $a$ -ээс $b$ хүртэл нүхний хүч чадлыг байршуулах, $1$ нь бөмбөгийг $a$ дахь нүхэнд оруулах шаардлагатай байгааг харуулна. $a$ болон $b$ нь $N$-аас хэтрэхгүй эерэг утгатай бүхэл тоонууд юм.

Гаралт

$1$ гаралтын хөдөлгөөн бүр нь салангид мөрөн дахь хоёр зайгаар тусгаарлагдсан- бөмбөг эгнээнээс гарахаас өмнө орсон хамгийн сүүлийн нүх болон бөмбөгний хийсэн үсрэлтийн тоо

Орчуулсан: Энхгэрэл

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

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