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 ≤ 10^5)~ and ~M~ ~(0 ≤ M ≤ 3 \times 10^5)~, 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

Example Output

5 3 1
6 1 1