EIU Programming Page for CIT

Ph want to find out some intesting information about his friends. He asked some friends to gather all relationship of N friends (relationship may be duplicated). With that data, Ph want to know for each his friend, how many friends of the opposite gender he/she has.

Input

The first line contains two integers N (0 <N ≤ 10⁵) and M (0 ≤ M ≤ 3 * 10⁵), the number of people in the statistics list and the number of relationships counted.

The next line consists of N strings containing only "Nam" and "Nu", the i-th sequence is the gender of your ith

In the next M lines, each line has two numbers u and v, representing u and v being friends on Facebook

Output

Output the number of friends of the opposite gender of each person on a line, separated by spaces.

Sample

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