Double Trouble

Time limit1sMemory limit128 MB

Summary
Given an encrypted ciphertext formed by shifting letters and reversing blocks of size m, find the shift s and block size m that make a given crib appear.
Level

Medium4 of 10

Topics
String, Brute force, Implementation, Simulation
Solved
No attempts yet

Problem

Alice and her sister Irene frequently send each other e-mails. Wary of interception and wishing to keep their correspondence private, they encrypt each message in two steps. First they remove every non-alphabetic character and convert all letters to upper case (call the result the modified plaintext); then they:

  1. replace each letter by the letter ss positions later in the alphabet (1≤s≤251 \le s \le 25) — call this a shift by ss. The alphabet wraps around, so for example when s=2s = 2, Y becomes A and Z becomes B.
  2. divide the result of step 1 into groups of mm letters (5≤m≤205 \le m \le 20) and reverse the letters within each group. If the total length is not divisible by mm, only the last kk letters (k<mk < m) are reversed.

For example, let s=2s = 2 and m=6m = 6. If the plaintext is Meet me in St. Louis, Louis., then after removing non-alphabetic characters and converting to upper case the modified plaintext is:

MEETMEINSTLOUISLOUIS

Shifting each letter by 2 gives the intermediate result:

OGGVOGKPUVNQWKUNQWKU

Finally, reversing every group of 6 letters gives (the last two letters form the final group):

GOVGGOQNVUPKWQNUKWUK

By convention the result is written in groups of 5 letters, so the ciphertext is:

GOVGG OQNVU PKWQN UKWUK

Once a ciphertext is intercepted it is not very hard to recover ss and mm, and it is even easier if you know a crib — a word that appears in the modified plaintext. In the example above, LOUIS is a crib. Your task is to find ss and mm given a ciphertext and a crib.

Input

The input consists of several problem instances. The first line contains a positive integer giving the number of instances.

Each instance spans several lines. Its first line contains the integer nn (20≤n≤50020 \le n \le 500), equal to the number of characters in the ciphertext. The following lines contain the ciphertext, all upper case, in groups of 5 letters separated by a single space (the last group may contain fewer than 5 letters). There are 10 groups per line, except possibly for the last line of ciphertext. The line following the last line of ciphertext contains the crib: a single word of between 4 and 10 upper-case characters, inclusive.

Output

Output the two integers ss and mm on a single line, separated by one space, giving the encryption key that produces the crib, where ss is the shift and mm is the reversed-group size. If there is more than one solution, output the one with the smallest ss; if several share the smallest ss, output the one with the smallest mm. If no such ss and mm exist, output Crib is not encrypted.

Examples3

  1. Example 1

    Input
    4
    83
    FIQMF IISFN QMFIB EOPFH FNQMV PSFIU IZNGP UPEUS BFPEP PEPPE
    PPEPN QMFIP EOPIS FIQMF IBSFN QMFBE OPI
    RHONDA
    105
    VDBMN DQDGS LNQEM ZLZRZ RNGVX ZALNA TERZV CZDGD MZQHZ GENKK
    KONSC DJHKC KKZAD RZAXZ SNMRH GBHGV RZVDG XZRNS XZKOS ZCNNF
    SHFMH
    BOMBAY
    50
    QFNWX YQFNW YSAQX FYNWY XQFNW SXYQF FXNYS AXYQF NASXY QFNAX
    HEAVEN
    20
    GOVGG OQNVU PKWQN UKWUK
    LOUIS
    
    Expected output
    1 6
    25 6
    Crib is not encrypted.
    2 6
    
  2. Example 2

    Input
    1
    20
    GOVGG OQNVU PKWQN UKWUK
    LOUIS
    
    Expected output
    2 6
    
  3. Example 3

    Input
    1
    28
    PMMFI EMSPX JTJIU TFUBT TTFNU FHB
    WORLD
    
    Expected output
    1 5