ნაყინის ხათრით

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2002/03, OPEN, ORANGE


ფერმერ ჯონს უყვარს ძროხებისთვის მათემატიკის სწავლება. იგი დაპირდა მათ თივა-მოყრილ ნაყინს, თუკი ისინი ამოხსნიდნენ სხვადასხვა მათემატიკურ ამოცანებს. მან უთხრა ბესის, „ამოირჩიე და მითხარი ექვსნიშნა მთელი რიცხვი. შემდეგ აიღე ამ რიცხვის შუა ოთხი ციფრისაგან შემდგარი რიცხვი და აიყვანე კვადრატში. მიღებულ რიცხვს მარცხნიდან მოაშორე ციფრები, სანამ არ მიიღებ ექვს ან ნაკლებნიშნა რიცხვს. მითხარი შედეგად მიღებული რიცხვი.“

ბესიმ ამოირჩია 655554. შემდეგ აიღო შუა ოთხი ციფრისგან შემდგარი რიცხვი: 5555 და აიყვანა კვადრატში: 30858025. შემდეგ მოაცილა ციფრები მარცხნიდან და დაიტოვა ექვსნიშნა რიცხვი: 858025. „8 5 8 0 2 5“, უთხრა მან ჯონს. ჯონს გაეღიმა ბესის მათემატიკურ ნიჭზე და უთხრა: „ახლა გააგრძელე ამ ოპერაციების ჩატარება, მანამ სანამ შედეგში მიღებული რომელიმე რიცხვი არ განმეორდება“.

ბესიმ გადაწყვიტა შეექმნა ცხრილი, რომელშიც აისახებოდა ოპერაციათა მიმდევრობა:

 

                  შუა           შუას       შემცირებული

     რიცხვი   4 ციფრი  კვადრატი   6 ან ნაკლებამდე

     655554    5555    30858025    858025

     858025    5802    33663204    663204

     663204    6320    39942400    942400

     942400    4240    17977600    977600

     977600    7760    60217600    217600 <-+

     217600    1760     3097600     97600       |

      97600    9760    95257600    257600      |

     257600    5760    33177600    177600     |

     177600    7760    60217600    217600 --+

 

ბესიმ თავისი ცხრილი ჯონს უჩვენა, რომელმაც გაიღიმა და დიდი ულუფა გემრიელი თივის ნაყინი გადასცა საჩუქრად. „სწორია, ბესი“, თქვა მან. „ციკლი სიგრძე 4 რიცხვია, რომელთაგანაც პირველად მიღებული არის 217600. ციკლი დადგენილი იქნა მეცხრე სვლაზე.“

დაეხმარეთ სხვა ძროხებს ნაყინის მოგებაში. მოცემული ექვსნიშნა რიცხვისათვის, გამოთვალეთ ციკლის დასადგენი სვლების რაოდენობა, ციკლის პირველი რიცხვი და ციკლის სიგრძე.

 

ჯონს აინტერესებდა იცოდა თუ არა ბესიმ ყველა ხრიკი და გამოსაცდელად მოამზადა შემდეგი ცხრილი:

 

                  შუა           შუას       შემცირებული

               რიცხვი     4 ციფრი      კვადრატი   6 ან ნაკლებამდე

                200023    0002       4        4

                         4         0       0        0

                         0         0       0        0         [ერთ სვლიანი ციკლი]

 

რომლის პასუხიც იქნებოდა: სამი სვლა ციკლის დასადგენად, ციკლის პირველი წევრი 0 და ციკლის სიგრძე 1.

გახსოვდეთ: თქვენს პროგრამას არ შეუძლია გამოიყენოს 16 მბ-ზე მეტი მეხსიერება.

 შეტანის ფორმატი:

 * სტრიქონი 1: ერთი ექვსნიშნა მთელი რიცხვი

გამოტანის ფორმატი:

* სტრიქონი 1: ჰარით გამოყოფილი სამი მთელი რიცხვი: ციკლის პირველი წევრი, ციკლის სიგრძე, ციკლის დასადგენი სვლების მინიმალური რაოდენობა.




მაგალითები

შესატანი მონაცემები
655554 დაკოპირება
გამოსატანი მონაცემები
217600 4 9 დაკოპირება