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 ≤ 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~</li>
• The next line consists of ~N~ strings, each of which is Nam or Nu, the corresponding ~i~-th string is the gender of the ~i~-th 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

Example Output

1 3 1
2 1 1 
3 3 1 
4 3 1 
5 3 1
6 1 1