F. Энхийг эрхэмлэгч мэлхийнүүд

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

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

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

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

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

Зөвхөн арлыг эрэгтэй холбосон тэгшхэн шулууны дагуу байрласан овоонуудаар дамжин эрэгт хүрч болох байв. Бид овоонуудыг $1$-ээс $n$ хүртэл дугаарлагдсан гэж үзэх ба ямар нэгэн овооны дугаар нь уг овооноос арал хүрэх зайтай(зай нь метрээр өгөгдөнө) тэнцүү байна. Мөн $n$-дахь овоо болон эрэг 2-ын хоорондох зай нь $1$ метр байх юм.

Түмбелина ийм зайны үсрэлт хийхэд хэтэрхий балчир юм. Аз болж уг намагт амьдардаг мэлхийн гэр бүл түүнд туслахаар болжээ. Бүх мэлхийнүүд нь Түмбелина-д унуулахыг зөвшөөрөх боловч Түмбелина зөвхөн ганц л мэлхий сонгох ёстой байв. Мэлхий бүр нь тодорхой хэмжээний зайд үсэрдэг. Хэрэв Түмбелина $d$ зайд үсэрч чаддаг мэлхийг туслуулахаар сонгосон бол, тухайн мэлхий нь арлаас $d$-р овоо хүртэл үсрэх ба дараа нь $2d$-р овоо уруу, дараа нь $3d$-р овоо уруу гэх мэт эрэг хүртэл үсрэх юм. Өөрөөр хэлбэл тэд $n$-р овоог өнгөрч явтал үсэрнэ гэсэн үг.

Тэгсэн хэдий ч ингэж явахад нэг асуудал байжээ: шумуулууд нь мөн уг намагт амьдардаг байв. Шумуулууд нь өдөр унтахдаа хэсэг овоонууд дээр унтдаг ажээ. Хэрэв мэлхий нь шумуултай овоо уруу үсэрвэл тэдгээр шумуулуудыг бяцлах юм. Харин мэлхийнүүд болон Түмбелина нар энхийг эрхэмлэгчид учраас үхсэн шумуул болгоны араас ихээхэн гашуудах ажээ. Иймд Түмбелина-д туслан аль болох боломжит цөөн тооны шумуулыг бяцлан түүнийг эрэг дээр хүргэж өгөх мэлхийг сонгож өгнө үү

Оролт

Эхний мөрөнд харгалзан овоонуудын тоо, мэлхийнүүдийн тоо болон шумуулуудын тоог илэрхийлэх 3-н бүхэл тоо $n$, $m$ болон $k$ ($1 ≤ n ≤ 10^{9}$, $1 ≤ m, k ≤ 100$) өгөгдөнө. 2-дахь мөрөнд $m$ ширхэг бүхэл тоонууд $d_{i}$ ($1 ≤ d_{i} ≤ 10^{9}$)-ууд өгөгдөх ба эдгээр нь мэлхийнүүдийн үсрэлтийн уртуудыг илэрхийлнэ. 3-дахь мөрөнд $k$ ширхэг бүхэл тоонууд өгөгдөх ба эдгээр нь шумуул болгоны унтаж буй овооны дугаарыг илэрхийлнэ. Овоо болгон дээр нэгээс олонгүй шумуул унтаж байна. Мөн мөрүүдэд өгөгдөх тоонууд нь нэг хоосон зайгаар тусгаарлагдсан байна.

Гаралт

Эхний мөрөнд хамгийн бага тооны шумуул бяцлах мэлхийнүүдийн тоог хэвлэнэ үү. 2-дахь мөрөнд эдгээр мэлхийнүүдийн дугааруудыг өсөх дарааллаар нь зайгаар тусгаарлан хэвлэнэ. Мэлхийнүүд нь уртынхаа хэмжээгээр оролтод өгөгдсөн дарааллаараа $1$-ээс $m$ хүртэл дугаарлагдсан байна.

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

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

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