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^5)~ and ~M~ ~(0≤M≤ 3\times 10^5)~, 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 ithIn the next ~M~ lines, each line has two numbers ~u~ and ~v~, representing ~u~ and ~v~ being friends on Facebook.
• The next line consists of ~N~ strings containing only Nam and Nu, the i-th sequence is the gender of your i-th.
• 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

Sample Output

2 2 1 0 1