به نام خدا

سوال 1.

ارسطو پس از اطلاع ار خبر مفقود شدن "چو" از خود بی خود شده و می خواهد خود را از طبقه ی n ام یک ساختمان بی نهایت طبقه ای به پایین بیاندازد. نقی که از این اتفاق مطلع شده می خواهد برود و جلوی ارسطو را بگیرد.او در طبقه ی همکف(0) است. از طرفی پایش شدیدا درد می کند و نمی خواهد از پله ها برود و اگر مجبور باشد از پله برود می خواهد حتما رو به پایین حرکت کند.

یک آسانسور در این ساختمان هست که کمی عجیب غریب عمل می کند. در واقغ با هر بار زدن دکمه بالا x طبقه به سمت بالا و با زدن دکمه پایین y طبفه به سمت پایین می رود.

کوچکترین ترین طبقه i را بیابید که i>=n و نقی بتواند با تعدادی مرحله استفاده از آسانسور به طبقه ی i برسد. سپس بگویید نقی چند بار باید دکمه ی بالا و چند بار دکمه ی پایین را بزتد نا به طبقه ی i برسد.

ورودی: درخط اول دو عدد x و y قرار دارند که x,y اعدا طبیعی کوچکتر از 10^5 اند و در خز بعد عدد طبیعی n قرار دارد که n<=10^18.

خروجی: در خط اول خروجی عدد i را بنویسید و در خط بعد دو عدد a و b را بنویسید به طوری که ax-by=i.

مثال:

ورودی :

2 2

7

خروجی :

8

0 4

توجه: این سوال را می توان بدون باینری سرچ هم به راحتی حل کرد. حتی میشه گفت با باینری سرچ یه lg n الکی اون وسط میافته اما با باینری سرچ هم میشه.