თაგვი და მარცვლები

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

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

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

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


მოცემულია მართხკუთხა ფორმის იატაკი,  გაფორმებული 1x1 კვადრატული ფილებით. თითოეულზე დაყრილია 0-დან K  მარცვლამდე (k<=30000).  იატაკის ზომა არის MxN. თაგვი გამორბის ტაძრის მარცხენა ქვედა კუთხიდან და მოძრაობს  ხვრელისკენ, რომელიც მდებარეობს საპირისპირო ზედა მარჯვენა კუთხეში. თაგვს შეუძლია მოძრაობა მხოლოდ მარჯვნივ, ან მხოლოდ წინ და აგროვებს ყველა მარცვალს, იმ ფილიდან რომელზეც იმყოფება.

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

შემავალი მონაცემები: პირველი სტრიქონი შეიცავს M და N იატაკის ზომებს  (1 ≤ M,N ≤ 100). შემდეგ შემოდის M სტრიქონი, დაწყებული ზევიდან, მასში განლაგებულია N რიცხვი - რაოდენობა მარცვლების შესაბამის ფილაზე.

გამომავალი მონაცემი: გამოვიტანოთ თაგვის მოძრაობის მარშრუტი ფორმატში : RRFFFRF (ნაბიჯი წინ, R ნაბიჯი მარჯვნივ).




მაგალითები

შესატანი მონაცემები
2 3 3 2 4 1 5 1 დაკოპირება
გამოსატანი მონაცემები
RFR დაკოპირება