#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
#define all(x) x.begin(), x.end()
const ll mod = 1e9 + 7;
ll mod_exp(ll a, ll n) {
   if (a < 0ll)   return 0;
   if (n < 0ll)   return 0;
   ll res = 1ll;
   while (n > 0) {
      if (n & 1)   res = (res * a) % mod;
      a = (a * a) % mod;
      n = n >> 1;
   }
   return res;
}
void solve() {
   int n, m, k, u, v;
   cin >> n >> m >> k;
   const ll c = mod_exp(2 * m, mod - 2);
   vector <ll> d(n);
   vector <vector <ll>> p(n, vector <ll> (n)), e(1, vector <ll> (n));
   for (auto &i : e[0])
      cin >> i;
   for (int i = 0; i < m; i++) {
      cin >> u >> v;
      u--, v--;
      p[u][v] = c;
      p[v][u] = c;
      d[u]++, d[v]++;
   }
   for (int i = 0; i < n; i++)
      p[i][i] = (1 - (d[i] * c) % mod + mod) % mod;
   auto multiply = [&](const auto & a, const auto & b) {
      vector <vector <ll>> c(a.size(), vector <ll> (b[0].size()));
      rep(i, a.size())rep(j, b[0].size())rep(k, b.size()) {
         (c[i][j] += (a[i][k] * b[k][j]) % mod) %= mod;
      }
      return c;
   };
   while (k > 0) {
      if (k & 1)
         e = multiply(e, p);
      p = multiply(p, p);
      k >>= 1;
   }
   for (auto i : e[0])
      cout << i << '\n';
}
int main() {
#ifndef ONLINE_JUDGE
   freopen("inp.in", "r", stdin);      freopen("outp.in", "w", stdout);
#endif
   ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);
   solve();
   return 0;
}
/****************************************** By Lord Sanskar Bhargava******************************/  
#include<bits/stdc++.h>
#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define mp make_pair
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define set1(x) __builtin_popcount(x)
#define gcd(a,b) __gcd(a,b)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define bk(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define mid(l,r) (l+(r-l)/2)
#define inf 1e18
template <typename T> T gcd(T a, T b){if(a%b) return gcd(b,a%b);return b;}
template <typename T> T lcm(T a, T b){return (a*(b/gcd(a,b)));}
#define fastio ios::sync_with_stdio(0);cin.tie(0);
 
template<typename T_vector>
void output_vector(const T_vector &v, bool add_one = false, int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());
 
    for (int i = start; i < end; i++)
        cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
}

unsigned mod_pow(unsigned a, unsigned b, unsigned mod) 
{
    unsigned result = 1;

    while (b > 0) {
        if (b & 1)
            result = unsigned(uint64_t(result) * a % mod);

        a = unsigned(uint64_t(a) * a % mod);
        b >>= 1;
    }

    return result;
}

bool miller_rabin(unsigned n) {
    if (n < 2)
        return false;

    // Check small primes.
    for (unsigned p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29})
        if (n % p == 0)
            return n == p;

    int r = __builtin_ctz(n - 1);
    unsigned d = (n - 1) >> r;


    for (unsigned a : {2, 7, 61}) {
        unsigned x = mod_pow(a % n, d, n);

        if (x <= 1 || x == n - 1)
            continue;

        for (int i = 0; i < r - 1 && x != n - 1; i++)
            x = unsigned(uint64_t(x) * x % n);

        if (x != n - 1)
            return false;
    }

    return true;
}

int find_prime(int n) {
    while (!miller_rabin(n))
        n++;

    return n;
}

void run_test_cases()
{
  int n;
  cin>>n;
  vector<pair<int,string>>vp(n);
  for(int i=0;i<n;i++)
  {
    string s;
    int t;
    cin>>s>>t;
    vp.emplace_back(t,s);
  }
  sort(all(vp));
  reverse(all(vp));
  cout<<vp[1].ss<<endl;

}
int main(int argc, char const *argv[]) 
{
    clock_t begin = clock();
    fastio;
    int tt=1;
    //cin>>tt;
    while(tt--)
    {
        run_test_cases();
    }

return 0;
}