C. Поликарпын шоо

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

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

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

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

Поликарпад $d_{1}, d_{2}, ..., d_{n}$ гэсэн $n$ ширхэг шоо байдаг. $i$ дэхь шоо $1$-ээс $d_{i}$ хүртэлх тоонуудын аль нэгийг буулгах боломжтой. Поликарп бүх шоог хаясаны дараа буусан тоонуудын нийлбэр $A$-тай тэнцүү байсан. Агрипина аль шоо ямар тоо буулгасаныг хараагүй, харин зөвхөн нийлбэр $A$ болон шоонуудын хамгийн их тоонууд болох $d_{1}, d_{2}, ..., d_{n}$ эдгээрийг л мэднэ. Тэрээр энэ мэдээллүүдийг ашиглан $i$ дэхь шоо $r$ гэсэн тоог буулгасан байх боломжгүй гэдгийг олно. Жишээ нь: хэрвээ Поликарпад $2$ ширхэг 6-н талт шоо байсан бөгөөд шоонуудын буусан нийлбэр $A = 11$-тэй тэнцүү байсан бол Агрипина аль ч шоо $5$-аас доош хэмжээний тоог буулгах боломжгүй гэдгийг хэлж чадна (хэрэв аль нэг нь $5$-аас доош тоотой үлдсэн бол шоо хамгийн багадаа 7 гэсэн боломжгүй тоог буулгах ёстой болно).

Хэрвээ буусан бүх тоонуудын нийлбэр $A$ бол шоо болгон хэдэн ширхэг тоог буулгаж чадахгүйг олно уу.

Оролт

Эхний мөрөнд шоонуудын тоо ба нийт буусан тоонуудын нийлбэр болох 2 ширхэг бүхэл тоонууд $n, A$ $(1 ≤ n ≤ 2 \cdot 10^{5}, n ≤ A ≤ s)$ өгөгдөнө.

Хоёр дахь мөрөнд $i$ дэхь шооны буулгаж чадах хамгийн их тоонууд $d_{i}$-нүүд болох $n$ ширхэг бүхэл тоо $d_{1}, d_{2}, ..., d_{n}$ $(1 ≤ d_{i} ≤ 10^{6})$ өгөгдөнө.

Гаралт

$n$ ширхэг бүхэл тоо болох $b_{1}, b_{2}, ..., b_{n}$ дарааллыг хэвлэнэ үү. Энд $b_{i}$ нь $i$ дэхь шооны буулгаж чадахгүй тоонуудын тоо юм.

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

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

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

Тэмдэглэл

Эхний жишээнд $A = 8$ бөгөөд энэ тохиолдолд $2$ шоо хоёул $4$ гэсэн тоог л буулгасан байх боломжтой. Тиймээс $2$ шоо $1$, $2$, эсвэл $3$ гэсэн тоонуудыг буулгасан байх боломжгүй.

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

Гурав дахь жишээнд $A$ нь $3$-тай тэнцүү учир аль нэг шоо нь $1$-ийг харин үлдсэн шоо нь $2$-ыг буулгасан байх боломжтой. Тиймээс эхний шоо бүх тоог буулгасан байх боломжтой, харин $2$ дахь шоо $3$ гэсэн тоог буулгаж чадахгүй.

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