- 16

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

You are Catherine, you know that Alice and Bob are chatting secretly and you want to be the woman in the middle; ie you want to intercept Alice and Bob’s messages, to read them and to send them messages that you cipher in place of theirs. If Alice sent Bob a message, Bob will never receive Alice’s message but yours instead.You are lucky: you caught a ciphered text and its clear version and you know that they are using the Hill cipher method.

You have to find the Hill matrix in order to decipher a text from Alice or Bob and to cipher the text you want to send instead.

The texts are using the 45 symbols of the alphanumeric encoding of the QR codes:

**How to**:

The Hill cipher uses matrix multiplication (here, with a modulus of 45).

For example, you have to cipher

`CODINGAME.`with A, a 2×2 matrix.

`CODINGAME.`is

`12 24 13 18 23 16 10 22 14 42`(because

If A is:

⎡6 5⎤

⎣7 6⎦

The first pair of ciphered symbols will be:

`6×12+5×24 mod 45 = 192 mod 45 = 12`that is

`7×12+6×24 mod 45 = 228 mod 45 = 3`that is

Thus,

Finally, the ciphered text is

If the matrix’s size is 3, you will cipher 3 characters at a time.

For this puzzle, you have to find the cipher matrix (and its size) and how to decipher.

Input

**Line 1**: The ciphered text

**Line 2**: The clear text

**Line 3**: The ciphered text you have to decipher

**Line 4**: The clear text you have to cipher

Output

**Line 1**: Line 3 deciphered

**Line 2**: Line 4 ciphered

Constraints

You can assume that the size of the cipher matrix divides the length of all the messages (but it’s not 1).

Just to help you:

* The clear texts of a test and validator pair will be the same but the Hill matrix won’t be the same.

* Test 1/validator 1 and test 2/validator 2’s Hill matrices are the same.

* Test 2/validator 2 and test 3/validator 3’s clear texts are the same.

* There are no trailing spaces in the clear texts but there might be some in the ciphered texts (as in the example).

Just to help you:

* The clear texts of a test and validator pair will be the same but the Hill matrix won’t be the same.

* Test 1/validator 1 and test 2/validator 2’s Hill matrices are the same.

* Test 2/validator 2 and test 3/validator 3’s clear texts are the same.

* There are no trailing spaces in the clear texts but there might be some in the ciphered texts (as in the example).

Example

Input

C3XJ%WZMOZ CODINGAME. 6-85OXC HELLO WORLD.

Output

BONJOUR. $N639O.8.0IS

A higher resolution is required to access the IDE