#!/usr/bin/python

#
# Zig-zag Cipher
# Problem 2, AIC 2004 (Senior)
# Python Sample Solution
#

#
# This solution deciphers the message by:
#  - first determining the length of the original message, textLength;
#  - encrypting the integers 0 .. textLength-1 according to the scheme in the
#    question.
#  - reading the numbers left-to-right, top-to-bottom from the step above to
#    generate a table that links index in the encrypted text to an index in
#    the plain text.
#  - use this table to decrypt the message.
#
# For example, to decrypt COPATGAHRRY in 3 rows, we consider the 12 integers
# 0, 1, 2, ... 11. Encrypting this into a 2-D array, dummyText, makes the
# array look like:
#
#   0 5 6 11
#   1 4 7 10
#   2 3 8 9
#
# We can then generate a table, decryptMap, that matches the position in the
# encrypted text to their index in the original text:
#
#            i  0    1    2    3    4    5    6    7    8    9   10   11
# decryptMap[i] 0    5    6   11    1    4    7   10    2    3    8    9
#
# We can then read the original message by printing out the characters in the
# order given by the table.
#

def main():
    input_file = file("zigin.txt", "r")
    output_file = file("zigout.txt", "w")

    # Read the number of rows the deciphered text will fill.
    rows = int(input_file.readline())

    # Start with an empty rowLen array - assume all rows are empty.
    rowLen = [0] * rows

    ciphertext = ''

    # Read in the first line of text.
    text = input_file.readline().strip()
    # If the current line of text is a "#", then we have the entire input.
    while text != "#":
        # We have a string which is not just a #
        # Append it to the existing string.
        ciphertext += text

        # Read in the next line.
        text = input_file.readline().strip()

    # The dummyText array will hold the encrypted version of the integers
    # 0 .. textLength - 1
    dummyText = []
    for i in range(rows):
        row = [0] * len(ciphertext)
        dummyText.append(row)

    # We know the length of the encrypted text and the number of rows that it
    # fills.
    #
    # Fill in the dummyText array with the encrypted version of the integers
    # 0 .. textLength-1.

    currRow = 0     # Starting at row 0.
    currDir = 1     # Heading down to begin with.

    for i in range(len(ciphertext)):
        # Mark this position in the dummy array.
        dummyText[currRow][rowLen[currRow]] = i
        rowLen[currRow] += 1

        # Move to the next row for the next character.
        currRow += currDir

        # If we are at the top or the bottom, change direction.
        if currRow == rows - 1:
            currDir = -1
        elif currRow == 0:
            currDir = 1

    # Construct the decryptMap array from the dummyText.
    # decrypt[i] = ciphertext index for plaintext[i].
    decryptMap = [0] * len(ciphertext)
    pos = 0
    for currRow in range(rows):
        for i in range(rowLen[currRow]):
            decryptMap[dummyText[currRow][i]] = pos
            pos += 1

    # We now know the order to print out the letters from the plain text.
    for pos in range(len(ciphertext)):
        output_file.write('%c' % ciphertext[decryptMap[pos]])
    output_file.write('\n')

# Call the main function.
main()