Byteasar 在一家大型仓库担任管理经理。由于预见到严冬即将来临，他决定在仓库中安装地暖系统。

仓库平面图是一个尺寸为 $n \times m$ 的矩形，被划分为若干个单位正方形。大部分单位正方形构成了仓库空间，但其中一些被巨大的柱子占据，为仓库结构提供额外的支撑。每根柱子在仓库平面图上占据一个 $2 \times 2$ 的正方形区域，该区域由若干单位正方形组成。柱子的排列并不密集——已知任意两根柱子之间的距离至少为 6 个单位（欧几里得距离）。此外，每根柱子的中心距离仓库的每条外墙至少 3 个单位。

供暖将通过安装在仓库地板下的一根加热管来实现。管道需要穿过所有非柱子占据的单位正方形的中心。每段管道必须平行于仓库的一面墙，且转弯处只能位于单位正方形的中心。管道必须在同一点开始和结束。在这一点，冷水被排出，热水被注入管道。

Byteasar 请你规划仓库中的管道轨迹。为了方便起见，他在仓库平面图上引入了一个直角坐标系，其中横坐标属于区间 $[0, n]$，纵坐标属于区间 $[0, m]$。所有单位正方形中心的坐标均为 $k + \frac{1}{2}$ 的形式，其中 $k \in \mathbb{N}$。

输入格式

第一行包含三个整数 $n, m$ 和 $f$ ($1 \le n, m \le 1000$，且 $n$ 和 $m$ 为偶数)，分别表示仓库的尺寸和柱子的数量。接下来的 $f$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i \le n, 0 \le y_i \le m$)，表示第 $i$ 根柱子的中心坐标。

输出格式

第一行输出一个单词 “TAK” 或 “NIE”，表示是否可以按照 Byteasar 的要求实现地暖。如果答案是 “TAK”，第二行应包含一个长度为 $nm - 4f$ 的字符串，描述管道轨迹的示例方案。我们约定管道的起点位于坐标 $(\frac{1}{2}, \frac{1}{2})$ 处。管道的后续部分标记如下：向量 $[0, 1]$ 的移动记为字母 ‘G’，向量 $[0, -1]$ 的移动记为字母 ‘D’，向量 $[1, 0]$ 的移动记为字母 ‘P’，向量 $[-1, 0]$ 的移动记为字母 ‘L’。如果存在多个正确答案，输出其中任意一个即可。

样例

输入 1

12 6 2
3 3
9 3

输出 1

TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

说明

示例输出对应于下图：