In BerSoft n programmers work, the programmer i is characterized by a skill r_i.

A programmer a can be a mentor of a programmer b if and only if the skill of the programmer a is strictly greater than the skill of the programmer b (r_a > r_b) and programmers a and b are not in a quarrel.

You are given the skills of each programmers and a list of k pairs of the programmers, which are in a quarrel (pairs are unordered). For each programmer i, find the number of programmers, for which the programmer i can be a mentor.

Input

The first line contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ k ≤ min(2 ⋅ 10^5, (n ⋅ (n - 1))/(2))) — total number of programmers and number of pairs of programmers which are in a quarrel.

The second line contains a sequence of integers r_1, r_2, ..., r_n (1 ≤ r_i ≤ 10^{9}), where r_i equals to the skill of the i-th programmer.

Each of the following k lines contains two distinct integers x, y (1 ≤ x, y ≤ n, x ≠ y) — pair of programmers in a quarrel. The pairs are unordered, it means that if x is in a quarrel with y then y is in a quarrel with x. Guaranteed, that for each pair (x, y) there are no other pairs (x, y) and (y, x) in the input.

Output

Print n integers, the i-th number should be equal to the number of programmers, for which the i-th programmer can be a mentor. Programmers are numbered in the same order that their skills are given in the input.

Examples

Input

4 2
10 4 10 15
1 2
4 3


Output

0 0 1 2 


Input

10 4
5 4 1 5 4 3 7 1 2 5
4 6
2 1
10 8
3 5


Output

5 4 0 5 3 3 9 0 2 5 

Note

In the first example, the first programmer can not be mentor of any other (because only the second programmer has a skill, lower than first programmer skill, but they are in a quarrel). The second programmer can not be mentor of any other programmer, because his skill is minimal among others. The third programmer can be a mentor of the second programmer. The fourth programmer can be a mentor of the first and of the second programmers. He can not be a mentor of the third programmer, because they are in a quarrel.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
  
  private static class Worker {
    private final int skill;
    private final int idx;
    
    Worker(final int skill, final int idx) {
      this.skill = skill;
      this.idx = idx;
    }
    
    int getSkill() {
      return this.skill;
    }
    
    int getIdx() {
      return this.idx;
    }
  }
  
  public static void main(String args[]) throws IOException {
    BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
    //BufferedReader bi = new BufferedReader(new FileReader(new File("E:\\test.txt")));
    
    String[] paramsStr = bi.readLine().split(" ");
    int nWorkers = Integer.parseInt(paramsStr[0]);
    int nQuarrels = Integer.parseInt(paramsStr[1]);
    
    List<Worker> workers = new ArrayList<>();
    
    String[] skillsStr = bi.readLine().split(" ");
    for (int i = 0; i < nWorkers; ++i) {
      workers.add(new Worker(Integer.parseInt(skillsStr[i]), i + 1));
    }
    
    int[] excludedBcsQuarrel = new int[nWorkers];
    
    for (int i = 0; i < nQuarrels; ++i) {
      String[] quarrelsStr = bi.readLine().split(" ");
      int a = Integer.parseInt(quarrelsStr[0]);
      int b = Integer.parseInt(quarrelsStr[1]);
      if (workers.get(a - 1).getSkill() > workers.get(b - 1).getSkill()) excludedBcsQuarrel[a - 1]++;
      else if (workers.get(b - 1).getSkill() > workers.get(a - 1).getSkill()) excludedBcsQuarrel[b - 1]++;
    }
    
    //long startTime = System.currentTimeMillis();
    
    workers.sort(new Comparator<Worker>() {
      @Override
      public int compare(Worker o1, Worker o2) {
        return (o2.getSkill() - o1.getSkill());
      }
    });
    
    int[] finalResults = new int[nWorkers + 1];
    int j = 0;
    int curValue = -1;
    for (int i = 0; i < nWorkers; ++i) {
      int nbMentorable = 0;
      if (curValue != workers.get(i).getSkill()) {
        curValue = workers.get(i).getSkill();
        j = i + 1;
        while (j < nWorkers && workers.get(i).getSkill() == workers.get(j).getSkill()) j++;
      }
      nbMentorable = nWorkers - j - excludedBcsQuarrel[workers.get(i).getIdx() - 1];
      finalResults[workers.get(i).getIdx()] = nbMentorable;
    }
    
    for (int i = 1; i <= nWorkers; ++i) System.out.print(finalResults[i] + " ");
    
    bi.close();
    
    //System.out.println("Time in ms : " + (System.currentTimeMillis() - startTime));
  }

}
