<?php

class Decode
{
    private static $_dict = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
    private static $_decodedString;

    public function __construct($str)
    {
        $str = strtoupper($str);
        $length = strlen($str);
        $fib = self::FibonacciN($length);
        $s = '';

        for ($i = 0; $i < $length; ++$i)
        {
            $s .= self::GetCharacter($str[$i], -$fib[$i]);
        }

        self::$_decodedString = $s;
    }

    public static function GetConfig()
    {
        $result = array();

        preg_match('/K(\d)+/', self::$_decodedString, $matches);
        preg_match('/(\d)+/', $matches[0], $matches);
        $result['columns'] = $matches[0];

        preg_match('/W(\d)+/', self::$_decodedString, $matches);
        preg_match('/(\d)+/', $matches[0], $matches);
        $result['rows'] = $matches[0];

        preg_match('/A(\d)+/', self::$_decodedString, $matches);
        preg_match('/(\d)+/', $matches[0], $matches);
        $result['min'] = $matches[0];

        preg_match('/Z(\d)+/', self::$_decodedString, $matches);
        preg_match('/(\d)+/', $matches[0], $matches);
        $result['max'] = $matches[0];

        return $result;
    }

    public static function GetCharacter($char, $rank)
    {
        $pos = stripos(self::$_dict, $char) + $rank;

        if ($pos > 0)
        {
            while ($pos > 36)
            {
                $pos -= 36;
            }
        }
        else
        {
            while ($pos < 0)
            {
                $pos = 36 - ($pos * -1);
            }
        }

        return self::$_dict[$pos];
    }

    public static function FibonacciN($n)
    {
        $a = 0;
        $b = $n;
        $sum = 0;
        $result = array();

        for ($i = 0; $i < $n; $i++)
        {
            $sum = $a + $b;
            $a = $b;
            $b = $sum;
            $result[] = $sum;
        }

        return $result;
    }
}

class Competition
{
    private static $_sequence;

    public static function SetConfiguration($configuration)
    {
        if (self::$_sequence == null)
        {
            self::$_sequence = self::SequenceBody(
                $configuration['min'],
                $configuration['max'],
                $configuration['columns'],
                $configuration['rows']);
        }
    }

    private static function Sequence($min, $max)
    {
        return range($min, $max);
    }

    private static function SequenceBody($min, $max, $cal, $row)
    {
        $body = array();
        $sequence = self::Sequence($min, $max);
        $length = $row * $cal;
        $totalLength = ($length / count($sequence)) + 1;

        for ($i = 0; $i < $totalLength; ++$i)
        {
            $body = array_merge($body, $sequence);
        }

        return array_slice($body, 0, $length);
    }

    public static function Draw($rectangle, $rows, $cols)
    {
        $s = '';

        for($i = 0; $i < $rows; ++$i)
        {
            for($j = 0; $j < $cols; ++$j)
            {
                $s .= self::$_sequence[$rectangle[$j][$i]];
            }

            $s .= "\n";
        }

        echo $s;
    }
}

class Point
{
    public $x;
    public $y;

    public function __construct($x, $y)
    {
        $this->x = $x;
        $this->y = $y;
    }

    public function Add(Point $point)
    {
        $this->x += $point->x;
        $this->y += $point->y;
    }

    public function Remove(Point $point)
    {
        $this->x -= $point->x;
        $this->y -= $point->y;
    }
}

abstract class RectangleBase implements  IRectangle
{
    protected static $_vectorLeft;
    protected static $_vectorRight;
    protected static $_vectorUp;
    protected static $_vectorDown;
    protected $_stepStartPoint;
    protected $_vectorWeight;
    protected $_courses;
    protected $_length;
    protected $_rows;
    protected $_columns;
    protected $_courseIdx;

    public function __construct($weight, $configuration)
    {
        if (self::$_vectorLeft == null)
        {
            self::InitVectors();
        }

        $this->DetermineCourse();
        $this->_vectorWeight = $weight;
        $this->_rows = $configuration['rows'];
        $this->_columns = $configuration['columns'];
        $this->_length = $configuration['rows'] * $configuration['columns'];
    }

    public function Run()
    {
        $result = array();
        $idx = 0;
        $this->_courseIdx = 0;
        $count = count($this->_courses);

        while($idx < $this->_length)
        {
            if ($count == $this->_courseIdx)
            {
                $this->_courseIdx = 0;
            }

            $course = $this->_courses[$this->_courseIdx];
            $steps = $this->DetermineStep();

            for($i = 0; $i < $steps; ++$i)
            {
                $result[$this->_stepStartPoint->x][$this->_stepStartPoint->y] = ++$idx - 1;
                $this->_stepStartPoint->Add($course);
            }

            $this->_stepStartPoint->Remove($course);
            $this->UpdateStepStartPoint();
            $this->_stepStartPoint->Add($this->_vectorWeight);
            ++$this->_courseIdx;
        }

        return $result;
    }

    private static function InitVectors()
    {
        self::$_vectorLeft = new Point(-1, 0);
        self::$_vectorRight = new Point(1, 0);
        self::$_vectorUp = new Point(0, -1);
        self::$_vectorDown = new Point(0, 1);
    }
}

interface IRectangle
{
    public function DetermineCourse();
    public function DetermineStep();
    public function UpdateStepStartPoint();
}

class Snake extends RectangleBase
{
    public function __construct($configuration)
    {
        parent::__construct(new Point(1, 0), $configuration);
        $this->_stepStartPoint = new Point(0, $configuration['rows'] - 1);
    }

    public function DetermineCourse()
    {
        $this->_courses[] = self::$_vectorUp;
        $this->_courses[] = self::$_vectorDown;
    }

    public function DetermineStep()
    {
        return $this->_rows;
    }

    public function UpdateStepStartPoint() { }
}

class Rows extends RectangleBase
{
    public function __construct($configuration)
    {
        parent::__construct(new Point($configuration['columns'] - 1, -1), $configuration);
        $this->_stepStartPoint = new Point($configuration['columns'] - 1, $configuration['rows'] - 1);
    }

    public function DetermineCourse()
    {
        $this->_courses[] = self::$_vectorLeft;
    }

    public function DetermineStep()
    {
        return $this->_columns;
    }

    public function UpdateStepStartPoint() { }
}

class Spiral extends RectangleBase
{
    private $_spiralRows;
    private $_spiralColumns;

    public function __construct($configuration)
    {
        parent::__construct(new Point(0, 0), $configuration);
        $this->_stepStartPoint = new Point(0, 0);
        $this->_spiralRows = $configuration['rows'];
        $this->_spiralColumns = $configuration['columns'];
    }

    public function DetermineCourse()
    {
        $this->_courses[] = self::$_vectorRight;
        $this->_courses[] = self::$_vectorDown;
        $this->_courses[] = self::$_vectorLeft;
        $this->_courses[] = self::$_vectorUp;
    }

    public function DetermineStep()
    {
        switch($this->_courseIdx)
        {
            case 0:
                $this->_spiralRows -= 1;
                return $this->_spiralColumns;
            case 1:
                $this->_spiralColumns -= 1;
                return $this->_spiralRows;
            case 2:
                $this->_spiralRows -= 1;
                return $this->_spiralColumns;
            case 3:
                $this->_spiralColumns -= 1;
                return $this->_spiralRows;
        }
    }

    public function UpdateStepStartPoint()
    {
        switch($this->_courseIdx)
        {
            case 0:
                $this->_stepStartPoint->Add(new Point(0, 1));
                break;
            case 1:
                $this->_stepStartPoint->Remove(new Point(1, 0));
                break;
            case 2:
                $this->_stepStartPoint->Remove(new Point(0, 1));
                break;
            case 3:
                $this->_stepStartPoint->Add(new Point(1, 0));
                break;
        }
    }
}

$konkurs = new Decode('UMUAAM4G9Z'); //new Decode($argv[1]);
$configuration = Decode::GetConfig();

Competition::SetConfiguration($configuration);
$rectangle = new Spiral($configuration);
Competition::Draw($rectangle->Run(), $configuration['rows'], $configuration['columns']);
echo "\n";
$rectangle = new Snake($configuration);
Competition::Draw($rectangle->Run(), $configuration['rows'], $configuration['columns']);
echo "\n";
$rectangle = new Rows($configuration);
Competition::Draw($rectangle->Run(), $configuration['rows'], $configuration['columns']);