Problem: There are n football teams in the world. 

The Main Football Organization (MFO) wants to host at most m games. MFO wants the i-th game to be played between the teams a_i and b_i in one of the k stadiums. 

Let s_{ij} be the numbers of games the i-th team played in the j-th stadium. MFO does not want a team to have much more games in one stadium than in the others. Therefore, for each team i, the absolute difference between the maximum and minimum among s_{i1}, s_{i2}, …, s_{ik} should not exceed 2.

Each team has w_i — the amount of money MFO will earn for each game of the i-th team. If the i-th team plays l games, MFO will earn w_i ⋅ l.

MFO needs to find what games in what stadiums they need to host in order to earn as much money as possible, not violating the rule they set.

However, this problem is too complicated for MFO. Therefore, they are asking you to help them.

Input

The first line contains three integers n, m, k (3 ≤ n ≤ 100, 0 ≤ m ≤ 1 000, 1 ≤ k ≤ 1 000) — the number of teams, the number of games, and the number of stadiums.

The second line contains n integers w_1, w_2, …, w_n (1 ≤ w_i ≤ 1 000) — the amount of money MFO will earn for each game of the i-th game.

Each of the following m lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — the teams that can play the i-th game. It is guaranteed that each pair of teams can play at most one game.

Output

For each game in the same order, print t_i (1 ≤ t_i ≤ k) — the number of the stadium, in which a_i and b_i will play the game. If the i-th game should not be played, t_i should be equal to 0.

If there are multiple answers, print any.

Example

Input


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


Output


3
2
1
1
3
1
2
1
2
3
2

Note

One of possible solutions to the example is shown below:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = 4 * atan((long double)1);
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = cd(a, b);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  cin.sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
typedef decay<decltype(MOD)>::type T;
struct mi {
  T val;
  explicit operator T() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend void pr(const mi& a) { pr(a.val); }
  friend void re(mi& a) {
    long long x;
    re(x);
    a = mi(x);
  }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
};
template <int SZ>
struct Dinic {
  typedef long long F;
  struct Edge {
    int to, rev;
    F flow, cap;
  };
  int N, second, t;
  vector<Edge> adj[SZ];
  typename vector<Edge>::iterator cur[SZ];
  void addEdge(int u, int v, F cap) {
    assert(cap >= 0);
    Edge a{v, (int)adj[v].size(), 0, cap}, b{u, (int)adj[u].size(), 0, 0};
    adj[u].push_back(a), adj[v].push_back(b);
  }
  int level[SZ];
  bool bfs() {
    for (int i = (0); i < (N); ++i) level[i] = -1, cur[i] = begin(adj[i]);
    queue<int> q({second});
    level[second] = 0;
    while ((int)q.size()) {
      int u = q.front();
      q.pop();
      for (auto& e : adj[u])
        if (level[e.to] < 0 && e.flow < e.cap)
          q.push(e.to), level[e.to] = level[u] + 1;
    }
    return level[t] >= 0;
  }
  F sendFlow(int v, F flow) {
    if (v == t) return flow;
    for (; cur[v] != end(adj[v]); cur[v]++) {
      Edge& e = *cur[v];
      if (level[e.to] != level[v] + 1 || e.flow == e.cap) continue;
      auto df = sendFlow(e.to, min(flow, e.cap - e.flow));
      if (df) {
        e.flow += df;
        adj[e.to][e.rev].flow -= df;
        return df;
      }
    }
    return 0;
  }
  F maxFlow(int _N, int _s, int _t) {
    N = _N, second = _s, t = _t;
    if (second == t) return -1;
    F tot = 0;
    while (bfs())
      while (auto df = sendFlow(second, numeric_limits<F>::max())) tot += df;
    return tot;
  }
};
Dinic<205> D;
int n, m, t;
int tot;
bool adj[201][201];
int ldeg[201], rdeg[201], ans[201][201];
int ret = 0;
vector<pair<int, int> > ed;
void ae(int x, int y, int l, int r, bool flag) {
  if (flag) ret += r - l;
  D.addEdge(n + m + 1, y, r);
  D.addEdge(y, x, r - l);
  D.addEdge(x, n + m + 2, r);
  tot += r;
}
void solve() {
  for (int i = (0); i < (t); ++i) {
    D = Dinic<205>();
    tot = 0;
    for (int a = (1); a < (n + 1); ++a) ldeg[a] = 0;
    for (int b = (1); b < (m + 1); ++b) rdeg[b] = 0;
    for (int a = (1); a < (n + 1); ++a)
      for (int b = (1); b < (m + 1); ++b)
        if (adj[a][b]) {
          ldeg[a]++, rdeg[b]++;
          D.addEdge(a, n + b, 1);
        }
    for (int a = (1); a < (n + 1); ++a)
      ae(0, a, ldeg[a] / (t - i), (ldeg[a] + t - i - 1) / (t - i), i == 0);
    for (int b = (1); b < (m + 1); ++b)
      ae(n + b, 0, rdeg[b] / (t - i), (rdeg[b] + t - i - 1) / (t - i), i == 0);
    assert(D.maxFlow(n + m + 3, n + m + 1, n + m + 2) == tot);
    for (int a = (1); a < (n + 1); ++a)
      for (auto& t : D.adj[a])
        if (n + 1 <= t.to && t.to <= n + m && t.flow) {
          adj[a][t.to - n] = 0;
          ans[a][t.to - n] = i + 1;
        }
  }
  for (auto& t : ed) ps(ans[t.first][t.second]);
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  int z;
  re(n, z, t);
  m = n;
  vector<int> w(n);
  re(w);
  for (int i = (0); i < (z); ++i) {
    int a, b;
    re(a, b);
    ed.push_back({a, b});
    adj[a][b] = 1;
  }
  solve();
}