[AMPPZ2014]Pillars

时间限制:5s      空间限制:256MB

题目描述

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


输入格式

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


输出格式

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


样例输入

12 6 2
3 3
9 3

样例输出

TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

提示

 


题目来源

鸣谢Claris上传