E. Шилжих түвшин

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

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

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

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

Аль ч сүлжээний аппликэйшний хөгжүүлэлтэнд сүлжээгээр хэр их хэмжээний мэдээлэл дамжуулах вэ гэдэг нь чухал бөгөөд сонирхолтой хэсэг байдаг.

ЗептоЛаб компанид нэгэн нууц тоглоом нилээд хөгжсөн бөгөөд энэхүү тоглоом нь тойрогт байрласан $n$ ширхэг түвшингээс бүрддэг. Та түвшин $i$-ээс $i - 1$ болон $i + 1$ түвшингүүд уруу шилжих боломжтой мөн түвшин $1$-с түвшин $n$ уруу шилжих болон мөн эсрэг чиглэлд шилжих боломжтой. $i$-дэх түвшингийн хэмжээ $a_{i}$ байт.

Сүлжээний ачааллыг багасгахын тулд тоглоомын мэдээлэл дамжуулалт дараах байдлаар дамждаг. Сервер дэх бүх түвшингүүдийг $m$ бүлгүүдэд хуваах бөгөөд тоглогч анх удаа шинэ бүлэгт шилжих болгонд түүнд тухайн бүлгийн бүх түвшингүүдийн мэдээллийг нэг пакет болгон илгээх юм. Тиймээс, тоглогч нэг бүлэг дотор түвшингүүдийн хооронд шилжвэл апплекэйшнд ямар нэг шинэ мэдээлэл шаардлагагүй болно. Техникийн хязгаарлалтын улмаас нэг пакет хэдэн ч түвшингийн мэдээлэл агуулж болох боловч нийт хэмжээ $b$ байтыг хэтэрч болохгүй. Энд $b$ нь эерэг тогтмол бүхэл тоо болно.

Тоглогчид түвшингүүдийг нэг нэгээр нь дуусгадаг учир $n$ ширхэг түвшингүүдийг $m$ бүлэгт хуваахдаа дараалсан буюу хөрш түвшингүүдийг нэг бүлэгт хуваарилдаг (үүнээс гадна, нэг бүлэгт $n$, $1$ гэсэн 2 хөрш түвшин агуулагдах боломжтой). Хэрвээ бүх түвшингүүдийн нийт мэдээллийн хэмжээ нь $b$-г хэтрэхгүй байвал бүх түвшинг ганцхан бүлэг болгож нэг пакетаар ч дамжуулах боломжтой.

Дээрх нөхцлүүдийг хангасан байхаар бүх түвшингүүдийг хамгийн багадаа хэдэн бүлэг болгон хуваах боломжтойг тодорхойл.

Тоглоом хөгжүүлэх нь их удаан процесс ба технологийн хөгжил хэзээ ч зогсохгүй байгаа нь энэхүү $b$ гэх тогтмол хэмжигдхүүн хэзээ ч утгаа өөрчилж магадгүйг илтгэнэ. Тиймээс хөгжүүлэгчид таниас $b$-ийн олон утганд хариултуудыг олохыг гуйжээ.

Оролт

Эхний мөрөнд тоглоомны түвшингийн тоо болон $b$-ийн ялгаатай утгууд нийт хэд байгааг илэрхийлэх 2 бүхэл тоонууд $n$, $q$ ($2 ≤ n ≤ 10^{6}$, $1 ≤ q ≤ 50$) өгөгдөнө.

2 дахь мөрөнд бүх түвшингийн хэмжээ болох $n$ ширхэг бүхэл тоонууд $a_{i}$ ($1 ≤ a_{i} ≤ 10^{9}$) өгөгдөнө. Эдгээр нь байтаар өгөгдөж байгаа болно.

Дараагийн $q$ ширхэг мөрөнд мөр болгонд хариуг нь олох ёстой $b_{j}$ ()-ийн утгууд өгөгдөнө.

Гаралт

Оролтонд өгөгдсөн $b_{j}$ -ийн утга болгонд тохирох хамгийн бага бүлгийн тоог олж ялгаатай мөрөнд хэвлэнэ үү.

Орчуулсан: Энхлут

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

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

Тэмдэглэл

Тестэнд:

  • $b = 7$ утганд та түвшингүүдийг 2 бүлэгт хувааж болно: $2|421|32$ (Энд нэг бүлэг нь 5 дахь, 6 дахь болон 1 дэхь түвшинг агуулж байгааг анзаарна уу);
  • $b = 4$ утганд та түвшингүүдийг 4 бүлэгт хувааж болно: $2|4|21|3|2$;
  • $b = 6$ утганд та түвшингүүдийг 3 бүлэгт хувааж болно: $24|21|32|$.
Сэтгэгдлүүдийг ачааллаж байна...