Under construction

Still being built. Things may change

Shifting Boxes and a Caesar Cipher

Interview

Time limit2sMemory limit1024 MB

Summary
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 nn 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 ss. He wondered whether ss can be transformed into the string tt, which described the previous order of nn boxes.

Sam can apply the following transformation once to the string ss:

  • Apply a Caesar cipher to all codes. Every letter is cyclically shifted back by a fixed step dd. For example, with d=4d = 4, e becomes a and c becomes y.
  • Sam takes kk (0≤k<n0 \le k < n) 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 ss by kk positions.

Help Sam find out whether some transformation turns ss into tt.

Input

The first line contains one integer nn, the number of boxes in the order (1≤n≤200 0001 \le n \le 200\,000). The second line contains the string tt of nn lowercase Latin letters, the description of the previous order. The third line contains the string ss of nn lowercase Latin letters, the description of the current order.

Output

If no transformation turns ss into tt, print Impossible. Otherwise, print Success, and on the second line print two integers kk and dd describing a transformation that turns ss into tt (0≤k<n0 \le k < n, −26<d<26-26 < d < 26). If there are several suitable answers, print any of them.

Examples4

  1. Example 1

    Input
    3
    abc
    fde
    
    Expected output
    Success
    1 3
    
  2. Example 2

    Input
    3
    abc
    aba
    
    Expected output
    Impossible
    
  3. Example 3

    Input
    1
    z
    a
    
    Expected output
    Success
    0 -25
    
  4. Example 4

    Input
    5
    abcde
    cdeab
    
    Expected output
    Success
    3 0