There are n reindeer at the North Pole, all battling for the highest spot on the "Top Reindeer" leaderboard on the front page of CodeNorses (a popular competitive reindeer gaming website). Interestingly, the "Top Reindeer" title is just a measure of upvotes and has nothing to do with their skill level in the reindeer games, but they still give it the utmost importance.

Currently, the i-th reindeer has a score of a_i. You would like to influence the leaderboard with some operations. In an operation, you can choose a reindeer, and either increase or decrease his score by 1 unit. Negative scores are allowed.

You have m requirements for the resulting scores. Each requirement is given by an ordered pair (u, v), meaning that after all operations, the score of reindeer u must be less than or equal to the score of reindeer v.

Your task is to perform the minimum number of operations so that all requirements will be satisfied.

Input

The first line contains two integers n and m (2≤ n≤ 1000; 1≤ m≤ 1000) — the number of reindeer and requirements, respectively.

The second line contains n integers a_1,…, a_n (1≤ a_i≤ 10^9), where a_i is the current score of reindeer i.

The next m lines describe the requirements.

The i-th of these lines contains two integers u_i and v_i (1≤ u_i, v_i≤ n; u_i≠ v_i) — the two reindeer of the i-th requirement.

Output

Print n integers b_1,…, b_n (-10^{15}≤ b_i≤ 10^{15}), where b_i is the score of the i-th reindeer after all operations.

If there are multiple solutions achieving the minimum number of operations, you may output any.

We can prove that there is always an optimal solution such that |b_i|≤ 10^{15} for all i.

Examples

Input


7 6
3 1 4 9 2 5 6
1 2
2 3
3 4
4 5
5 6
6 7


Output


1 1 4 4 4 5 6 


Input


4 6
6 5 8 2
3 1
4 1
3 2
1 2
2 3
3 1


Output


6 6 6 2 


Input


10 18
214 204 195 182 180 176 176 172 169 167
1 2
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
6 10


Output


204 204 195 182 180 167 176 172 169 167 
2 1
1 1000000000
1 2
 2 1
1 1
1 2

1 1000000000 
 1 1 

// package c1615;

import java.io.File;
import java.lang.invoke.MethodHandles;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

//
// Codeforces Global Round 18 2021-12-24 06:35
// H. Reindeer Games
// https://codeforces.com/contest/1615/problem/H
// time limit per test 2 seconds; memory limit per test 256 megabytes
// public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
//
// There are n reindeer at the North Pole, all battling for the highest spot on the "Top Reindeer"
// leaderboard on the front page of CodeNorses (a popular competitive reindeer gaming website).
// Interestingly, the "Top Reindeer" title is just a measure of upvotes and has nothing to do with
// their skill level in the reindeer games, but they still give it the utmost importance.
//
// Currently, the i-th reindeer has a score of a_i. You would like to influence the leaderboard with
// some operations. In an operation, you can choose a reindeer, and either increase or decrease his
// score by 1 unit. Negative scores are allowed.
//
// You have m requirements for the resulting scores. Each requirement is given by an ordered pair
// (u, v), meaning that after all operations, the score of reindeer u must be less than or equal to
// the score of reindeer v.
//
// Your task is to perform the minimum number of operations so that all requirements will be
// satisfied.
//
// Input
//
// The first line contains two integers n and m (2<= n<= 1000; 1<= m<= 1000)-- the number of
// reindeer and requirements, respectively.
//
// The second line contains n integers a_1,..., a_n (1<= a_i<= 10^9), where a_i is the current score
// of reindeer i.
//
// The next m lines describe the requirements.
//
// The i-th of these lines contains two integers u_i and v_i (1<= u_i, v_i<= n; u_i\ne v_i)-- the
// two reindeer of the i-th requirement.
//
// Output
//
// Print n integers b_1,..., b_n (-10^{15}<= b_i<= 10^{15}), where b_i is the score of the i-th
// reindeer after all operations.
//
// If there are multiple solutions achieving the minimum number of operations, you may output any.
//
// We can prove that there is always an optimal solution such that |b_i|<= 10^{15} for all i.
//
// Example
/*
input:
7 6
3 1 4 9 2 5 6
1 2
2 3
3 4
4 5
5 6
6 7

output:
1 1 4 4 4 5 6

input:
4 6
6 5 8 2
3 1
4 1
3 2
1 2
2 3
3 1

output:
6 6 6 2

input:
10 18
214 204 195 182 180 176 176 172 169 167
1 2
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
6 10

output:
204 204 195 182 180 167 176 172 169 167
*/
//
public class C1615H {
  static final int MOD = (int)1e9+7;
  static final Random RAND = new Random();

  static class MaxFlow {
    // Flow network structures
    static int n;
    static int edgesLen[], edges[][], capsLen, caps[];

    static void init() {
      edgesLen = new int[n];
      edges = new int[n][6];
      capsLen = 0;
      caps = new int[6];
    }

    static int addEdge(int from, int to, int capacity, int reverseCapacity) {
      int cap = capsLen;
      if (caps.length == cap) {
        caps = Arrays.copyOf(caps, (cap << 1) + 2);
      }
      caps[cap] = capacity;
      caps[cap + 1] = reverseCapacity;
      capsLen = cap + 2;
      int e1s[] = edges[from], e1 = edgesLen[from];
      if (e1s.length == e1) {
        e1s = edges[from] = Arrays.copyOf(e1s, (e1 << 1) + 2);
      }
      e1s[e1] = to;
      e1s[e1 + 1] = cap;
      edgesLen[from] = e1 + 2;
      int e2s[] = edges[to], e2 = edgesLen[to];
      if (e2s.length == e2) {
        e2s = edges[to] = Arrays.copyOf(e2s, (e2 << 1) + 2);
      }
      e2s[e2] = from;
      e2s[e2 + 1] = cap + 1;
      edgesLen[to] = e2 + 2;
      return cap;
    }

    static int dist[];

    // Dinic�s algorithm for Maximum Flow
    static int dinic(int source, int sink) {
      dist = new int[n];
      int curEdge[] = new int[n];
      int queue[] = new int[n];
      int flow = 0;
      while (true) {
        Arrays.fill(dist, -1);
        dist[source] = 0;
        queue[0] = source;
        int queueHead = 0;
        int queueTail = 1;
        do {
          int cur = queue[queueHead++];
          int ndist = dist[cur] + 1;
          for (int i = 0, e[] = edges[cur], en = edgesLen[cur]; i < en; i += 2) {
            if (caps[e[i + 1]] == 0) {
              continue;
            }
            int to = e[i];
            if (dist[to] < 0) {
              dist[to] = ndist;
              queue[queueTail++] = to;
            }
          }
        } while (queueHead < queueTail);
        if (dist[sink] < 0) {
          return flow;
        }
        Arrays.fill(curEdge, 0);
        int stackSize = 0;
        int cur = source;
        int eNum = 0;
        cur: while (true) {
          if (cur == sink) {
            int curFlow = Integer.MAX_VALUE;
            for (int i = 0; i < stackSize; i++) {
              int c = queue[i];
              curFlow = Math.min(curFlow, caps[edges[c][curEdge[c] + 1]]);
            }
            for (int i = 0; i < stackSize; i++) {
              int c = queue[i];
              int cap = edges[c][curEdge[c] + 1];
              caps[cap] -= curFlow;
              caps[cap ^ 1] += curFlow;
            }
            flow += curFlow;
            stackSize = 0;
            cur = source;
            eNum = curEdge[source];
            continue;
          }
          int ndist = stackSize + 1;
          for (int e[] = edges[cur], en = edgesLen[cur]; eNum < en; eNum += 2) {
            int next = e[eNum];
            if (caps[e[eNum + 1]] != 0 && dist[next] == ndist) {
              curEdge[cur] = eNum;
              queue[stackSize++] = cur;
              cur = next;
              eNum = curEdge[cur];
              continue cur;
            }
          }
          curEdge[cur] = eNum;
          if (stackSize == 0) {
            break;
          }
          cur = queue[--stackSize];
          eNum = curEdge[cur] + 2;
        }
      }
    }
  }

  // Sort a by v.
  // Example: a: [0, 1, 2, 3, 4, 5, 6]
  //          v: [3, 1, 4, 9, 2, 5, 6]
  // Result:  a: [1, 4, 0, 2, 5, 6, 3]
  // Performance:
  //      n        sortBy()   sortWithIdx()
  //   n = 100000   27 msec    51 msec
  //   n = 1000000 279 msec   489 msec
  static void sortBy(int a[], int n, int v[]) {
    // System.out.format("    a: %s\n", Arrays.toString(a));
    // System.out.format("    v: %s\n", Arrays.toString(v));
    if (n == 0) {
      return;
    }
    for (int i = 1; i < n; i++) {
      int j = i;
      int ca = a[i];
      int cv = v[ca];
      do {
        int nj = (j - 1) >> 1;
        int na = a[nj];
        if (cv <= v[na]) {
          break;
        }
        a[j] = na;
        j = nj;
      } while (j != 0);
      a[j] = ca;
    }
    int ca = a[0];
    for (int i = n - 1; i > 0; i--) {
      int j = 0;
      while ((j << 1) + 2 + Integer.MIN_VALUE < i + Integer.MIN_VALUE) {
        j <<= 1;
        j += (v[a[j + 2]] > v[a[j + 1]]) ? 2 : 1;
      }
      if ((j << 1) + 2 == i) {
        j = (j << 1) + 1;
      }
      int na = a[i];
      a[i] = ca;
      ca = na;
      int cv = v[ca];
      while (j != 0 && v[a[j]] < cv) {
        j = (j - 1) >> 1;
      }
      while (j != 0) {
        na = a[j];
        a[j] = ca;
        ca = na;
        j = (j - 1) >> 1;
      }
    }
    a[0] = ca;
    // System.out.format("    a: %s\n", Arrays.toString(a));
  }

  static int[][] sortWithIdx(int[] a) {
    int n = a.length;
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; i++) {
      arr[i][0] = a[i];
      arr[i][1] = i;
    }
    Arrays.sort(arr, (x,y) -> x[0] != y[1] ? x[0] - y[0] : x[1] - y[1]);
    return arr;
  }

  static void solve(int[] a, int[][] uv) {
    int n = a.length;
    int m = uv.length;
    int[] idx = new int[n];
    for (int i = 0; i < n; i++) {
      idx[i] = i;
    }
    sortBy(idx, n, a);
    // System.out.format("    a: %s\n", Arrays.toString(a));
    // System.out.format("  idx: %s\n", Arrays.toString(idx));

    MaxFlow.n = n + 2;
    MaxFlow.init();
    for (int[] e : uv) {
      int u = e[0] - 1;
      int v = e[1] - 1;
      MaxFlow.addEdge(v, u, Integer.MAX_VALUE / 2, 0);
    }
    for (int i = 0; i < n; i++) {
      MaxFlow.addEdge(i, n + 1, 1, 0);
    }

    int ans[] = new int[n];
    for (int i: idx) {
      MaxFlow.addEdge(n, i, 2, 0);
      MaxFlow.dinic(n, n + 1);
      for (int j = 0; j < n; j++) {
        if (ans[j] == 0 && MaxFlow.dist[j] >= 0) {
          ans[j] = a[i];
        }
      }
    }
    StringBuilder sb = new StringBuilder();
    for (int v : ans) {
      sb.append(v);
      sb.append(' ');
    }
    System.out.println(sb.toString());
    // 3 1 4 9 2 5 6
    // 3 3 4 5 5 5 6 (9)
    // 1 1 4 4 4 5 6 (9)
  }

  static void doTest() {
    int n = 1000000;
    int[] a = new int[n];
    long t0 = System.currentTimeMillis();
    int[] idx = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = RAND.nextInt(1000000);
      idx[i] = i;
    }
    // int[][] arr = new int[n][2];
    // sortBy(idx, n, a);
    sortWithIdx(a);
    System.out.format("%d msec\n", System.currentTimeMillis() - t0);
    System.exit(0);
  }

  public static void main(String[] args) {
    // doTest();
    Scanner in = getInputScanner();
    int n = in.nextInt();
    int m = in.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = in.nextInt();
    }
    int[][] uv = new int[m][2];
    for (int i = 0; i < m; i++) {
      uv[i][0] = in.nextInt();
      uv[i][1] = in.nextInt();
    }
    solve(a, uv);
    in.close();
  }

  static Scanner getInputScanner() {
    try {
      final String USERDIR = System.getProperty("user.dir");
      final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
      final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
      return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
    } catch (Exception e) {
      return new Scanner(System.in);
    }
  }
}