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 CC selecting the vertex with the largest index as the representative vertex. Write a program that prints the representative vertex, the number of males, the number of females for each component.

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

Sort the connected components by the representation vertex, respectively print out the index of the representative. number of men, and number of women .

Example

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

Output:
5 3 1
6 1 1