A. Хантаазаа өмсөцгөө!

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

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

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

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

2-р зэргийн хаант улс маш хүнд хэцүү цаг үеийг туулж байв... Өнөө өглөө 3-р зэргийн хаант улс 2-р зэргийн хаант улсад дайн зарлажээ. Энэ зөрчилдөөн (магадгүй зэвсэглэсэн зөрчилдөөн) нь жинхэнэ эзэн нь хэн болохыг тодорхойлох юм

2-р зэргийн хаант улс нь $n$ ширхэг хүмүүсийн энгийн армитай. Цэрэг болгон нь өөрсдийгөө бүртгүүлэх ба өөрт таарах сумны хамгаалттай хантаазны хэмжээг заана: $i$-дахь цэргийн заасан хэмжээ нь $a_{i}$ байв. Цэргүүд нь илүү зангүй, энгийн даруу байх бөгөөд иймд тушаал өгөгч дарга эдгээр цэргүүдийг $a_{i} - x$-аас $a_{i} + y$ хүртэлх (эдгээр тоонууд нь өөрсдөө мөн орно) хэмжээтэй ямар ч хантаазыг өмсөж болно гэж үзэх юм ($x, y ≥ 0$ тоонууд нь өгөгдсөн байна).

2-р зэргийн хаант улсын нөөцөд $m$ ширхэг хантааз байх ба $j$-дэх хантаазны хэмжээ нь $b_{j}$-тай тэнцүү байх юм. 2-р зэргийн хаант улсын армийг дайчлахад тусална уу: үүний тулд та аль болох олон цэргийг хантааз өмсүүлсэн байна. Хантааз бүрийг нэг л цэрэг хэрэглэнэ. Хэрэв $a_{i} - x ≤ b_{j} ≤ a_{i} + y$ бол $i$-дахь цэрэг $j$-дэх хантаазыг өмсөж болох юм.

Оролт

Эхний мөрөнд харгалзан цэргүүдийн тоо, хантаазны тоо болон $x, y ≥ 0$ тоонуудын утгыг илэрхийлэх 4 бүхэл тоо $n$, $m$, $x$ болон $y$ ($1 ≤ n, m ≤ 10^{5}$, $0 ≤ x, y ≤ 10^{9}$) өгөгдөнө.

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

3-дахь мөрөнд хаант улсад байгаа хантаазны хэмжээнүүд болох зайгаар тусгаарлагдсан $m$ ширхэг бүхэл тоо $b_{1}, b_{2}, ..., b_{m}$ ($1 ≤ b_{j} ≤ 10^{9}$)-ууд үл буурах дарааллаар өгөгдөнө.

Гаралт

Эхний мөрөнд сумны хамгаалттай хантааз өмсөх хамгийн олон цэргийн тоо болох бүхэл тоо $k$-г хэвлэнэ.

Дараагийн $k$ мөрөнд $k$ ширхэг хосын нэг мөрөнд нэг хос "$u_{i}$ $v_{i}$" (хашилтгүйгээр) байхаар хэвлэнэ. ($u_{i}$, $v_{i}$) хос нь $u_{i}$ дугаартай цэрэг нь $v_{i}$ дугаартай хантаазыг өмсөнө гэдгийг илэрхийлнэ. Цэргүүд болон хантаазнууд нь оролтод өгөгдсөн дарааллаараа нэгээс эхлэн дугаарлагдсан байна. Хосууд дотор байх цэргүүдийн бүх дугаарууд нь хос хосоороо ялгаатай байх ба хосууд дотор байх хантаазнуудын дугаарууд нь хос хосоороо ялгаатай байх ёстой. Та тэдгээр хосуудыг ямар ч дарааллаар хэвлэж болно.

Хэрэв олон оновчтой хариултууд байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

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

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

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

Тэмдэглэл

Эхний жишээнд та хантаазнуудын хэмжээг яг тааруулах хэрэгтэй: эхний цэрэг эхний хантаазыг(1 хэмжээтэй), 3-дахь цэрэг 2-дахь хантаазыг(3 хэмжээтэй) өмсөнө. Уг жишээнд өөр оновчтой хариулт байна. Та 2-дахь хантаазыг 3-дахь цэрэгт өмсүүлэхийн оронд 4-дэх цэрэгт өмсүүлж болно.

2-дахь жишээнд хантаазнуудын хэмжээ нь цэргүүдийн заасан хэмжээнээс хамгийн ихдээ 2 хэмжээний зөрүүтэй байгаа тул бүх цэргүүд хантааз өмсөж болох юм.

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