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.*;
import java.util.*;
public class F481
{
public static void main(String args[]) throws IOException
{
int n,k,i;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
String s[]=br.readLine().split(" ");
n=Integer.parseInt(s[0]);
k=Integer.parseInt(s[1]);
String s2[]=br.readLine().split(" ");
Pair ar[]=new Pair[n];
int ar2[]=new int[n];
ArrayList<ArrayList<Integer>> adj=new ArrayList<ArrayList<Integer>>(n);
for(i=0;i<n;i++)
{
ArrayList<Integer> list=new ArrayList<Integer>();
adj.add(list);
ar2[i]=Integer.parseInt(s2[i]);
ar[i]=new Pair(ar2[i],i);
}
for(i=1;i<=k;i++)
{
String s3[]=br.readLine().split(" ");
int e1=Integer.parseInt(s3[0])-1;
int e2=Integer.parseInt(s3[1])-1;
adj.get(e1).add(e2);
adj.get(e2).add(e1);
}
Arrays.sort(ar);
int cnt[]=new int[n];
int ans[]=new int[n];
cnt[ar[0].ind]=0;
ans[ar[0].ind]=0;
int cons=0;
for(i=1;i<n;i++)
{
int ind=ar[i].ind;
if(ar[i].s>ar[i-1].s){
cnt[ind]=cnt[ar[i-1].ind]+cons+1;
cons=0;
}
else
{
cnt[ind]=cnt[ar[i-1].ind];
cons++;
}
ans[ind]=cnt[ind];
//System.out.print(ind+1+":"+ans[ind]+"   ");
for(Integer el:adj.get(ind))
{
if(ar2[ind]>ar2[el])
ans[ind]--;
}
//System.out.println(ind+1+":"+ans[ind]+"   ");
}
for(i=0;i<n;i++)
bw.write(ans[i]+" ");
bw.flush();
}
static class Pair implements Comparable<Pair>
{
int s,ind;
Pair(int a,int b)
{
s=a;
ind=b;
}
public int compareTo(Pair p)
{
return s-p.s;
}
}
}