Practice Algebra with the exercise "Secret Message Decoding"

Learning Opportunities

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

Algebra

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 jth number in the encoding header represents how many times the jth original message part was added, while the ith encoded character of the message is the sum of the ASCII values of the ith 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 hsxhs 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 hs lines: A string containing hs + ms characters.

Output

A single line containing the decoded string.

Constraints

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

Example

Input

2
1
cg$
l?(

Output

Hi

Solve it

A higher resolution is required to access the IDE