D. Шоколад

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

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

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

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

Поликарпус Параскевид бэлэг өгөх дуртай. Тэр дөрвөлжин нүднүүдээс тогтсон тэгш өнцөгт, хавтгай хэлбэртэй хоёр шоколад авсан байна. Эхний шоколад нь $a_{1} × b_{1}$ нүднүүдтэй ба хоёр дахь шоколад нь $a_{2} × b_{2}$ нүднүүдтэй.

Поликарпус үдийн завсарлагаар Параскевид нэг шоколадыг нь өгөөд, өөрөө нөгөөг нь идэхийг хүссэн ба үүнээс гадна Поликарпусын ухаан Параскевийн гоо үзэсгэлэн хоёр яг тохирно гэдгийг харуулахыг хүссэн. Тиймээс тэр хоёр шоколадны квадрат нүднүүдийн тоог ижил байлгах ёстой.

Шоколадны квадрат нүднүүдийн тоог ижил байлгахын тулд Поликарпус минут бүрд шоколадны багахан хэсгийг иднэ. Минут бүрд тэр доорх зүйлийг хийнэ:

  • тэр нэг шоколадыг яг дундуур нь (босоо эсвэл хэвтээ) хугалах ба шоколадны хагасыг иднэ,
  • эсвэл тэр шоколадыг яг гуравны нэгээр (босоо эсвэл хэвтээ) хуваагаад шоколадны гуравны нэгийг иднэ.

Эхний тохиолдолд түүнд шоколадны хагас нь, хоёр дахь тохиолдолд шоколадны гуравны хоёр нь үлдэнэ.

Дээрх хоёр хуваалт нь үргэлж боломжтой биш ба заримдаа Поликарпус дундуур нь эсвэл гуравны нэгээр хувааж чадахгүй. Жишээлбэл: хэрвээ шоколад $16 × 23$ нүднүүдтэй бол Поликарпус дундуур нь хувааж чадна, гэхдээ гуравны нэгээр хувааж чадахгүй. Шоколад $20 × 18$ нүднүүдтэй бол Поликарпус дундуур нь мөн гуравны нэгээр хувааж чадна. Хэрвээ шоколад $5 × 7$ нүднүүдтэй бол Поликарпус дундуур нь ч, гуравны нэгээр ч хувааж чадахгүй.

Поликарпус хоёр шоколадны квадрат нүднүүдийн тоог ижил байлгахад хамгийн багадаа хэдэн минут зарцуулах вэ? Мөн хуваалтуудын дараах шоколад бүрийн хэмжээг ол.

Оролт

Оролтын эхний мөр нь эхний хавтгай шоколадны анхны хэмжээнүүд болох $a_{1}, b_{1}$ ($1 ≤ a_{1}, b_{1} ≤ 10^{9}$) бүхэл тоонуудыг агуулна. Хоёр дахь мөр нь хоёрдугаар хавтгай шоколадны анхны хэмжээнүүд болох $a_{2}, b_{2}$ бүхэл тоонуудыг агуулна.

Та том хэмжээний бүхэл тоо ($2^{31}-1$-ээс хэтэрсэн) боловсруулахдаа int64 (Паскалд), long long (С++), long (Жавад) өгөгдлийн төрлүүдийг ашиглаж болно.

Гаралт

Эхний мөрөнд хайж буй хамгийн бага минутын тоо болох $m$ тоог хэвлэнэ. Хоёр дахь ба гурав дахь мөрүүдэд шоколадны эцсийн хэмжээг хэвлэнэ. Оролттой ижил форматаар хэмжээнүүдийг хэвлэнэ. Урт өргөнийг ямар ч дарааллаар хэвлэж болно. Хоёр дахь мөр нь эхний шоколадны хэмжээг, гурав дахь мөр нь хоёр дахь шоколадны хэмжээг илэрхийлэх ёстой. Хэрвээ олон шийд байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

Шийд байхгүй бол нэг мөрөнд "-1" гэж хэвлэнэ.

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

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

Оролт
2 6
2 3
Гаралт
1
1 6
2 3
Оролт
36 5
10 16
Гаралт
3
16 5
5 16
Оролт
3 5
2 1
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...