A higher resolution is required to access the IDE

- 4

## Learning Opportunities

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

## Statement

## Goal

An agent undercover sends encoded secret message parts to the headquarters through public communication channels such as e-mail, text message and social media. Our task at the headquarters is to decode and assemble the original message.**Encoding process:**

The agent wants to send the message ‘Hello!’. As only two channels are available at this time, e.g., e-mail and Twitter, she divides it into

`hs`= 2 equal length parts, each containing

`ms`= 3 original characters ('Hel' and 'lo!') given by their ASCII representation, i.e., 72 101 108 and 108 111 33, respectively. Furthermore, an identity matrix called

**encoding header**with size

`hs`is attached in front of the

**original message parts**:

**Original Part 1**: [1 0] [72 101 108]

**Original Part 2**: [0 1] [108 111 33]

Next, the agent linearly combines the message parts using modulo arithmetic over Galois Field GF(127), i.e., modulo addition and multiplication over finite field with characteristic of 127. The

**j**th number in the

**encoding header**represents how many times the

**j**th original message part was added, while the

**i**th

**encoded character**of the message is the sum of the ASCII values of the

**i**th characters in the original message parts modulo 127. For example, the 2nd encoded character 69 in

**Part 2**below is the product of the encoding header [113 74] and the 2nd characters of the original message parts [101 111], i.e., (113*101 + 74*111) mod 127 =

**69**:

**Encoded Part 1**: [122 122] [116 83 57]

**Encoded Part 2**: [113 74] [126

**69**41]

Finally, the corresponding characters in

**Part 1**and

**Part 2**are sent in e-mail:

**zztS9**and tweeted in a post:

**qJ~E)**, respectively.

**Decoding example:**

After at the headquarters the two messages

**zztS9**and

**qJ~E)**were detected, the operators calculate

`hs`= 2 and

`ms`= 5 - 2 = 3, which gives the following ASCII representation:

**Encoded Part 1**: [122 122] [116 83 57]

**Encoded Part 2**: [113 74] [126 69 41]

Following the reverse process of encoding, the operators use finite field arithmetics to calculate the multiplicative inverse of elements to obtain the identity matrix on the

`hs`x

`hs`

**encoding header**part, while the same operations are performed on the

**encoded characters**as well:

**Decoded Part 1**: [1 0] [72 101 108]

**Decoded Part 2**: [0 1] [108 111 33]

As a result, appending the decoded ASCII characters 72 101 108 and 108 111 33 reveals the original secret message ‘Hello!’.

Input

**Line 1:**An integer

`hs`for the size of the

**encoding header**.

**Line 2:**An integer

`ms`for the number of the

**encoded characters**in each encoded message part.

**Next**A string containing

`hs`lines:`hs`+

`ms`characters.

Output

A single line containing the decoded string.

Constraints

1 ≤

1 ≤

The input strings contain printable ASCII characters (from the range of 33 to 126).

`hs`≤ 101 ≤

`ms`≤ 40The input strings contain printable ASCII characters (from the range of 33 to 126).

Example

Input

2 1 cg$ l?(

Output

Hi

A higher resolution is required to access the IDE