EIU Programming Practices and Exams

Given a graph G of N vertices and M edges representing the Facebook friendship in the EIUers community. Each vertex represents an EIU student, whose gender is Male or Female. Each edge represents the Facebook friends of two students.

The graph G forms connected components, with each connected component select the vertex with the largest index as the representative vertex. For each vertex, print the number of males and females in same components

Input

The first line contains two integers N (0 <N ≤ 105) and M (0 ≤ M ≤ 3 * 105), respectively, the number of vertices and the number of edges of the graph. The vertices of the graph are numbered from 1 to N

The next line consists of N strings, each of which is "Nam" or "Nu", the corresponding i th string is the gender of the ith student.

The next M lines contain two numbers u and v, each representing u and v as Facebook friends

Output

For each vertex from 1 to N, print the vertex, the number of males, and the number of females in the connected component.

Example

Input:
6 6
Nam Nu Nu Nam Nam Nam
1 3
1 4
3 4
5 3
6 2
5 4
Output:
1 3 1
2 1 1 
3 3 1 
4 3 1 
5 3 1
6 1 1