Brother Gerolamo was asked by Abbess Martina of the nearby Qualasu Nunnery to propose simple cryptography system, which could be used by brethren here and nuns there to correspond on casual matters without their letters being read by curious courriers.
He then takes a usual postcard, draws a grid (or rather Grille) on it and cuts out small windows in certain
cells, as shown in a picture. He uses this card as a stencil - i.e. it is put over blank paper, and text
is written in small parts into those "windows", line-by-line, left-to-right, from top to bottom.
Card is then flipped left to right, so due to asymmetry holes do not match with already written fragments, and user continues write the text in the same fashion. This second step is shown in the next picture.
On the third step grille is flipped top-to-bottom, next part of text is filled again - and at last the back flip (right-to-left) follows, to allow writing fourth part of the message. It is advisable then to make back flip bottom-to-top to return the stencil to original position (to proceed with next page later).
Now, if the grille is removed, we see a beautifully arranged mess of word parts and even whole short words. If the grille is larger, attempts to decipher the message are futile. Reader, however, shall use same fashined stencil to read the hidden text (flipping it to recover every of four parts).
This method has obvious advantages - writing and reading could be delegated to any assistant without special qualification in encryption, it is really simple. Also, system doesn't depend on alphabet - it could be used to encrypt message in unknown language or even cyrillic, hieroglyphs etc.
Grille Pattern Description
The only practical issue is how to share the grille pattern between correspondents. Suppose we can pass short message by very secure channel (e.g. sending postal pigeon with small piece of parchment or trusted courier who may keep some words in memory) - but postcard itself (even its image copy) is not suitable to be sent this way.
Let's encode it! Look at the top-left quarter of our grille. Obviously, every cell of it is flipped to some cell
of each other quarter in one of the steps. E.g. if we mark cells with letters, then A0 becomes A1 on flipping
left-to-right and J0 becomes J2 on flipping top-to-bottom.
A0 B0 C0 D0 | D1 C1 B1 A1
E0 F0 G0 H0 | H1 G1 F1 E1
I0 J0 K0 L0 | L1 K1 J1 I1
------------+------------
I2 J2 K2 L2 | L3 K3 J3 I3
E2 F2 G2 H2 | H3 G3 F3 E3
A2 B2 C2 D2 | D3 C3 B3 A3
This means that of the four cells with the same letter only single one should be cut to create correct stencil.
Great! Let's just describe which cell of every group is cut, using numbers from 0 to 3, in the same
order as letter follows (i.e. line-by-line within a quarter):
0 3 2 0 // A is cut in 0-th quarter, B in 3-rd quarter, C in 2-nd quarter and so on
2 1 0 2
3 2 1 0
This pattern completely describes the grille we used in examples above! Let's just convert it to binary
using 2 bits for every number, and then concatenate a number for every of 3 lines:
00 11 10 00 -> 56
10 01 00 10 -> 146
11 10 01 00 -> 228
So for grille of size W by H it is enough to pass H/2 numbers, each of W bits!
Problem Statement
So you are asked to proof-test the system. You'll be given codes, describing the grille - and encrypted result of using the grille. Reconstruct original text (though don't attempt to concatenate word fragments - leave it to reader).
Input data gives size (W H) of the grille in first line.
Next line contains H/2 codes describing the grille pattern.
Then H lines of W fragments follow - the encrypted text.
Answer should contain decrypted text in single line of fragments.
Example:
input:
8 6
109 49 205
lik sta to en are nce th th
ere at ma ess ny fr wh om
sh sor ape ma ts ich ns is
tru th est wit ey dif ho fe
th ei ey ut wa si ri ght
or ng dol sub lk in on un
answer (wrapped for convenience):
are th ere ma ny sor ts dif fe ri ng in lik en ess fr om ma ns tru est ei dol on ...
to th at sh ape wit ho ut si ght or sub sta nce wh ich is th ey th ey wa lk un