Nick和Peter在参加计算复杂性理论讲座的时候喜欢玩如下的游戏。他们在一张纸上画出一个无向的二分图G，并在一个顶点放上棋子。之后他们轮流走棋子。Nick先走。

每一步都是将棋子沿着图中的一条边移动。之后，在这一步之前棋子所在的顶点，偕同与之相连的所有边，都被从图中删去。没有边可走的玩家输掉游戏。

给出Nick和Peter画出的图。对图中的每个顶点，计算如果最初将棋子放在这里，谁将会赢。假设Nick和Peter都执行最优策略。

输入文件的第一行有三个整数n1,n2,m——分别代表二分图左边的顶点数，右边的顶点数，和边数。1<=n1,n2<=500，0<=m<=50000.

接下来m行描述了这些边。每一行有两个数，即该边所连接的左顶点和右顶点。两边的顶点都从1开始标号。

输出两行。第一行有n1个字符，如果最初把棋子放在左边的第i个顶点，Nick会赢，第i个字符就是'N'，如果Peter会赢就是'P'。第二行以相同的格式输出n2个字符，描述右边n个顶点的必胜者。