C. ATM-ээр мөнгө тараах

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

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

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

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

Нэгэн жижиг орны банк хэрэглэгчдийнхээ хүссэн хэмжээний мөнгийг түгээн өгч амжихгүй байсан учраас бидний сайн мэдэх ATM-ийг байрлуулжээ. ATM-ийн бүтэц зарим нэг онцлогтой ба мөнгө түгээгчийн (АТМ-аас мөнгө шууд өгч буй төхөөрөмж) хэмжээ хязгаарлагдмал учраас та нэг удаагийн авалтаар ATM-аас хамгийн ихдээ $k$ ширхэг мөнгөн тэмдэгт авч чадна, мөн хамгийн ихдээ хоёр өөр төрлийн мөнгөн тэмдэгт авч чадна.

Жишээлбэл тухайн улсад $10$, $50$, $100$, $500$, $1000$, $5000$-тын мөнгөн дэвсгэрт ашигладаг гэж үзвэл $k = 20$ үед та ATM-ээс $100000$ болон $96000$-г авч чадна, харин $99000$ болон $101000$-г авч чадахгүй.

Тухайн улсад нийт $n$ төрлийн мөнгөн тэмдэгтүүд байдаг ба таны хэрэглэж байгаа ATM-д бүх төрлийн мөнгөн дэвсгэрт хязгааргүй олон байгаа. Та өдрийн турш $q$ удаа тодорхой хэмжээний мөнгө авах хэрэгтэй болдог. ATM таны хүссэн мөнгийг олон аргаар өгч болно, гэхдээ та аль болох цөөн тооны мөнгөн тэмдэгт өгөхийг нь сонгоно, эсвэл таны хүссэн мөнгийг өгөх боломжгүй бол дэлгэцэнд алдааны мэдээлэл гарч ирнэ. Бэлэн мөнгө авах $q$ хүсэлт бүрийн үр дүнг тодорхойл.

Оролт

Эхний мөрөнд $n$, $k$ ($1 ≤ n ≤ 5000$, $1 ≤ k ≤ 20$) бүхэл тоонууд байна.

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

Дараагийн мөрөнд таны бэлэн мөнгө авах хүсэлтийн тоо болох $q$ ($1 ≤ q ≤ 20$) бүхэл тоо байна.

Дараагийн $q$ мөрүүдэд $x_{i}$ ($1 ≤ x_{i} ≤ 2 \cdot 10^{8}$) тоонууд байна. Эдгээр нь таны ATM-аас авахыг хүссэн мөнгөний нийлбэрүүд юм.

Гаралт

Хэрвээ таны хүссэн мөнгийг өгөх боломжтой бол хүсэлт бүрийн мөнгөн дэвсгэртийн тоог (хамгийн бага) харгалзах мөрөнд хэвлэнэ, эсрэг тохиолдолд харгалзах мөрөнд "-1" гэж хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
6 20
10 50 100 500 1000 5000
8
4200
100000
95000
96000
99000
10100
2015
9950
Гаралт
6
20
19
20
-1
3
-1
-1
Оролт
5 2
1 2 3 5 8
8
1
3
5
7
9
11
13
15
Гаралт
1
1
1
2
2
2
2
-1
Сэтгэгдлүүдийг ачааллаж байна...