Pillars

Byteasar is the administrative manager of a large warehouse. Expecting a severe winter, he has decided to install underfloor heating in the warehouse.

The warehouse plan is a rectangle of even dimensions n × m divided into unit squares. Most of the unit squares are warehouse space, but some are occupied by massive pillars that give the structure additional support. Each pillar occupies a 2 × 2 square of four unit squares on the plan. The pillars are not arranged densely: the centres of any two of them are at least 6 units apart in the Euclidean metric. Also, the centre of each pillar is at least 3 units away from each of the outer walls of the warehouse.

Heating is done by one heating pipe installed under the floor. The pipe has to pass through the centres of all unit squares except those occupied by pillars. Each section of the pipe must run parallel to one of the walls, and the pipe may turn only at the centres of unit squares. The pipe must begin and end at the same place. At that point the cold water is discharged outside and hot water is fed into the pipe.

Byteasar has asked you to plan the route of the pipe in the warehouse. To help you, he has introduced a rectangular coordinate system on the plan: the x coordinates lie in the interval [0, n] and the y coordinates in the interval [0, m]. The centres of all unit squares have coordinates of the form k + 1/2 for k ∈ ℕ.

The first line contains three integers n, m and f (1 ≤ n, m ≤ 1,000, n and m are even): the dimensions of the warehouse and the number of pillars. Each of the next f lines contains two integers $x_i$ and $y_i$ (0 ≤ $x_i$ ≤ n, 0 ≤ $y_i$ ≤ m), the coordinates of the centre of the i-th pillar.

In the first line print the word TAK (yes) if underfloor heating that meets Byteasar's requirements can be installed, and NIE (no) otherwise. If the answer is TAK, the second line has to describe the route of the pipe as a string of nm - 4f letters. The pipe begins at the point with coordinates (1/2, 1/2). A move by the vector [0, 1] is written as G, by [0, -1] as D, by [1, 0] as P, and by [-1, 0] as L.

Several routes may be valid, so only the one route fixed by the rule below is accepted. Call the unit square with centre (x + 1/2, y + 1/2) cell (x, y), where 0 ≤ x < n and 0 ≤ y < m. A pillar with centre (a, b) occupies the cells (a-1, b-1), (a, b-1), (a-1, b) and (a, b). A cell not occupied by a pillar is free.

1. Group the rows into pairs {0, 1}, {2, 3}, ..., {m-2, m-1}. In the row pair {2k, 2k+1} a column c is blocked if a pillar occupies at least one of the cells (c, 2k) and (c, 2k+1). A maximal interval [a, b] of consecutive unblocked columns together with the two rows of the pair forms a 2 × (b - a + 1) rectangle called a strip. For every strip select all edges of the circuit around its border: every edge between two horizontally adjacent cells of the strip, and the two vertical edges that join the two cells in column a and the two cells in column b.
2. The free cells that belong to no strip appear only in the row directly below and the row directly above a pillar whose centre has an even y coordinate, as pairs of horizontally adjacent cells. Select the edge between the two cells of each such pair.
3. For every strip in a row pair {2k, 2k+1} with k ≥ 1, let a be its leftmost column. Deselect the edges (a, 2k)-(a+1, 2k) and (a, 2k-1)-(a+1, 2k-1), and select the edges (a, 2k-1)-(a, 2k) and (a+1, 2k-1)-(a+1, 2k).
4. For every pair of cells (c, y), (c+1, y) from step 2: if it lies directly below a pillar, that is, a pillar occupies (c, y+1), deselect the edge (c, y-1)-(c+1, y-1) and select the edges (c, y-1)-(c, y) and (c+1, y-1)-(c+1, y). If it lies directly above a pillar, deselect the edge (c, y+1)-(c+1, y+1) and select the edges (c, y)-(c, y+1) and (c+1, y)-(c+1, y+1).

The selected edges form one closed route that visits every free cell exactly once. Print that route starting from cell (0, 0) in the direction whose first move is P.

The sample output corresponds to the following figure.