题目描述

给定一个$n \times m$的矩形，其中有$f$个$2 \times 2$的障碍物，其中任意两个障碍物中心之间的欧几里得距离至少为6，且每个障碍物的中心到边缘的距离至少为3。请找到一条从左下角$(1,1)$出发经过所有没有障碍物的点各一次的且最后回到左下角的回路。

输入格式

第一行包含三个整数$n, m, f$ ($1 \leq n, m \leq 1000$ 且$n,m$都为偶数)。接下来$f$行，每行两个整数$x, y$ ($1 \leq x < n, 1 \leq y < m$)，表示该障碍物左下角的坐标。

输出格式

如果无解，输出NIE，否则第一行输出TAK，第二行输出方案。方案包含$n \times m - 4 \times f$个字符，表示每一步的移动方向。用G表示上，D表示下，L表示左，P表示右。

输入数据示例

12 6 2
3 3
9 3

输出数据示例

TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD