生成随机迷宫有几种算法上很巧妙的方法。本题考虑其中的两种。

我们将迷宫定义为一个 $100 \times 100$ 的网格，其中一些网格单元之间的边是墙，其余的是双向通道，使得所有外围边都是墙，并且通道的选择方式使得从任何网格单元到任何其他网格单元都只有一条通过通道的简单路径（即网格单元构成一棵树）。

生成随机迷宫的第一种方法类似于 Kruskal 最小生成树算法。我们从一个只有墙而没有通道的网格开始，因此所有网格单元都是断开的。然后，我们重复以下步骤：随机选择一个连接两个断开部分的墙，并将其转换为通道，直到整个迷宫成为一个整体，此时我们就完成了。

生成随机迷宫的第二种方法类似于 Prim 最小生成树算法。同样，我们从一个只有墙而没有通道的网格开始。然后，我们重复以下步骤：选择任何连接“包含左上角单元格的部分”与“尚未触及的单元格”的墙，并将其转换为通道，直到整个迷宫连通。

左图显示了 Kruskal 算法的一个中间步骤，右图显示了 Prim 算法的一个中间步骤。下一步可以移除的边（Kruskal 为 19 条边，Prim 为 10 条边）已高亮显示。

你将获得一个使用上述两种算法之一生成的迷宫。你需要找出使用了哪种算法。

输入格式

输入文件包含 100 行，每行 100 个标记。每个标记将描述从相应网格单元发出的通道。它将包含来自以下列表的一个或多个不同字母：“N”代表通往上一行的通道，“S”代表通往下一行的通道，“W”代表通往左一列的通道，“E”代表通往右一列的通道。

迷宫将根据上述两种算法之一随机生成。

输出格式

输出一个单词：如果是第一种算法，输出 KRUSKAL（不含引号）；如果是第二种算法，输出 PRIM（不含引号）。

样例

输入 1

ES WE SWE W S
N E WSEN EW NSW
ES WES NSW S NS
N SN N NE WNS
E NEW W E WN

输出 1

KRUSKAL

说明

请注意，第一个测试用例比上面的样例大，因为它是一个 $100 \times 100$ 的网格，而不是 $5 \times 5$。你可以从 http://forest.acm.petrsu.ru/tests/maze.in 下载第一个测试用例。本题共有 200 个测试用例。