Masala #0118

Sizga to’rtta: A, B, C, K butun sonlar berilgan. Siz A va B sonlaridan umumiy ko’pi bilan K ta bitni o’zgartirgan holda A' va B' sonlarini shunday hosil qilingki, bunda A'|B'=C tenglik qanoatlantirsin.

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 5) testlar soni kiritiladi. Keyin har bir test uchun dastlabki qatorda K(0 ≤ K ≤ 5×10⁵) butun soni, so’ngra keyingi uchta qatorda, A, B, C(0 < A, B, C < 16^5×104) sonlari 16 lik sanoq tizimida kiritiladi.

OUTPUT.TXT chiqish faylida har bir test uchun javoblarni quyidagicha chop eting:

Agar yechim mavjud bo’lmasa alohida qatorda -1 sonini chop eting.

Aks holda agar yechimlar ko’p bo’ladigan bo’lsa A' soni imkon qadar kichik bo’lsin, bunday holda ham yechimlar ko’p bo’ladigan bo’lsa B' soni imkon qadar kichik bo’lsin. A' va B' topilganidan so’ng ularni alohida qatorlarda chop eting(ortiqcha 0(nol)larsiz).