Shifting Boxes and a Caesar Cipher
InterviewTime limit2sMemory limit1024 MB
Find a cyclic shift k and a Caesar shift d that turn string s into string t, or report that no such pair exists.
- Level
Medium6 of 10
- Topics
- String, String matching, Math
- Solved
- No attempts yet
Statement
Sam Porter is a post-apocalyptic courier. He does not enjoy the job, so he studies each order carefully to make it easier on himself.
Today Sam received an order of boxes. Each box has a product code given by a lowercase Latin letter. Sam stacked all the boxes in some order, then wrote the codes from the top box to the bottom box, which gave him a string . He wondered whether can be transformed into the string , which described the previous order of boxes.
Sam can apply the following transformation once to the string :
- Apply a Caesar cipher to all codes. Every letter is cyclically shifted back by a fixed step . For example, with ,
ebecomesaandcbecomesy. - Sam takes () boxes from the top of the stack, sets them on the floor, and puts the rest of the stack on top of them. This is a cyclic shift of the string by positions.
Help Sam find out whether some transformation turns into .
Input
The first line contains one integer , the number of boxes in the order (). The second line contains the string of lowercase Latin letters, the description of the previous order. The third line contains the string of lowercase Latin letters, the description of the current order.
Output
If no transformation turns into , print Impossible. Otherwise, print Success, and on the second line print two integers and describing a transformation that turns into (, ). If there are several suitable answers, print any of them.