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.
//package com.company;

import java.io.PrintWriter;
import java.util.*;

public class Main {
    static class Task {
        void run(Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();

            Integer[] r = new Integer[n];
            for(int i = 0; i < n; ++i) {
                r[i] = in.nextInt();
            }

            ArrayList<Integer> rs = new ArrayList<>(Arrays.asList(r));
            Collections.sort(rs);

            ArrayList<ArrayList<Integer>> g = new ArrayList<>();
            for(int i = 0; i <= n; ++i) {
                g.add(new ArrayList<>());
            }

            for(int i = 0; i < m; ++i) {
                int a = in.nextInt();
                int b = in.nextInt();

                g.get(a).add(b);
                g.get(b).add(a);
            }

            for(int i = 1; i <= n; ++i) {
                int ans = lowerBound(rs, r[i - 1]);
                for(int j : g.get(i)) {
                    if(r[j - 1] < r[i - 1]) {
                        --ans;
                    }
                }

                out.println(ans);
            }
        }
    }

    static class Pair<T, U> {
        T x;
        U y;

        Pair(T x, U y) {
            this.x = x;
            this.y = y;
        }
    }

    static public <T extends Comparable<T>> int lowerBound(List<T> a, T x) {
        int l = 0;
        int r = a.size();
        while(l != r) {
            int m = (l + r) / 2;
            if(a.get(m).compareTo(x) < 0) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }

    static public <T extends Comparable<T>> int upperBound(List<T> a, T x) {
        int l = 0;
        int r = a.size();
        while(l != r) {
            int m = (l + r) / 2;
            if(a.get(m).compareTo(x) <= 0) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Task().run(in, out);
        out.flush();
    }
}