图的顶点覆盖是指图的一个顶点集合，使得图中的每条边都至少与该集合中的一个顶点相关联。最小顶点覆盖是指基数最小的顶点覆盖。

考虑给定二分图的所有最小顶点覆盖集合。你的任务是将图的所有顶点分为三个集合。如果不存在包含某个顶点的最小顶点覆盖，则该顶点属于集合 $N$（“从不”）。如果某个顶点是给定图的每一个最小顶点覆盖的一部分，则该顶点属于集合 $A$（“总是”）。如果一个顶点既不属于 $N$ 也不属于 $A$，则它属于集合 $E$（“存在”）。

输入格式

输入的第一行包含三个整数 $n, m, k$：二分图中第一个顶点集的大小、第二个顶点集的大小以及边的数量（$1 \le n, m \le 1000$；$0 \le k \le 10^6$）。接下来的 $k$ 行包含由边连接的顶点对。第一个数字表示来自第一个集合的顶点，第二个数字表示来自第二个集合的顶点。每个集合中的顶点编号从 1 开始。没有一对顶点被多于一条边连接。

输出格式

在第一行，打印一个由 $n$ 个字母 ‘N’、‘E’、‘A’ 组成的序列，中间没有空格。第 $i$ 个位置的字母对应于第一个顶点集中第 $i$ 个顶点所属的集合。第二行必须以相同的格式包含第二个顶点集的答案。

样例

样例输入 1

11 9 22
1 1
1 2
1 3
1 8
1 9
2 1
2 3
3 2
3 4
4 3
4 5
5 2
5 4
5 6
6 6
6 7
7 5
7 7
8 7
9 7
10 7
11 7

样例输出 1

AEEEEEENNNN
EEEEEEANN