#include<bits/stdc++.h> 
using namespace std;

#define ll long long int
#define absdiff(a,b) (a>b)?a-b:b-a
#define mp make_pair 
#define pb push_back
#define ff first
#define ss second
#define fast  ios_base::sync_with_stdio(false);cin.tie(0);
#define MOD 1000000007 
#define ll_MAX 19223372036859
#define endl "\n"
ll fast_expo(ll x,ll p){
  if(p==0) return 1;
  else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} 
  else return (x*(fast_expo(x,p-1))%MOD)%MOD;}

ll dp[1005][1005], n, m, arr1[1005], arr2[1005];
vector<ll> AdjL[1005];

int main(){
  fast
  #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
  #endif
  
  ll t_c; t_c = 1;
  // cin >> t_c;

  for(ll t_i = 0; t_i < t_c; ++t_i){
    ll n, m; cin >> n >> m;
    ll a[n + 1], b[m + 1];
    for(ll i = 1; i <= n; ++i)
      cin >> a[i];
    for(ll i = 1; i <= m; ++i)
      cin >> b[i];

    ll dp[n + 1][m + 1];
    for(ll j = 0; j <= m; ++j){
      dp[0][j] = j;
    }

    for(ll i = 1; i <= n; ++i){
      dp[i][0] = i;
      for(ll j = 1; j <= m; ++j){
        if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1];
        else dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1}); 
      }
    } 

    cout << dp[n][m];
  }
  return 0;
}
#include <bits/stdc++.h>
 
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}
ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }


struct Frac {
    // a/b
    ll a, b;
};

const int mod = 1e9 + 7;

Frac mul_f(Frac x, Frac y) {
    ll a = x.a * y.a % mod;
    ll b = x.b * y.b % mod;
    return (Frac){a, b};
}

Frac plus_f(Frac x, Frac y) {
    ll a = (x.a * y.b) % mod + (x.b * y.a) % mod;
    ll b = x.b * y.b % mod;
    return (Frac){a, b};
}

ll calc(Frac x) {
    return x.a * mod_pow(x.b, mod - 2, mod) % mod;
}

vector<vector<Frac>> mul(vector<vector<Frac>> &A, vector<vector<Frac>> &B) {
    int N = A.size(), M = B[0].size(), K = A[0].size();
    vector<vector<Frac>> C(N, vector<Frac>(K, {0, 1}));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            Frac sum = {0, 1};
            for(int k = 0; k < K; k++) {
                sum = plus_f(sum, mul_f(A[i][k], B[k][j]));
            }
            C[i][j] = sum;
        }
    }
    return C;
}

vector<vector<Frac>> retE(int n) {
    vector<vector<Frac>> ret(n, vector<Frac>(n, {0, 1}));
    for (int i = 0; i < n; i++) {
        ret[i][i] = {1, 1};
    }
    return ret;
}

vector<vector<Frac>> pow(vector<vector<Frac>> &A, int n) {
    if (n == 0) {
        return retE(A.size());
    }
    vector<vector<Frac>> ret = retE(A.size());
    if (n % 2 == 1) {
        ret = mul(ret, A);
    }
    vector<vector<Frac>> half = pow(A, n / 2);
    ret = mul(ret, half);
    ret = mul(ret, half);
    return ret;
}

void solve() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<Frac>> A(N, vector<Frac>(1, {0, 1}));
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        A[i][0] = {a, 1};
    }

    vector<vector<int>> G(N, vector<int>(N));
    vector<int> V(N);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        V[a]++; V[b]++;
        G[a][b] = 1;
        G[b][a] = 1;
    }

    vector<vector<Frac>> T(N, vector<Frac>(N, {0, 1}));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) {
                ll a = 2 * (M - V[i]) + V[i];
                ll b = 2 * M;
                T[i][j] = {a, b};
            } else {
                if (G[i][j]) {
                    T[i][j] = {1, 2 * M};
                }
            }
        }
    }
    vector<vector<Frac>> TT = pow(T, K);
    vector<vector<Frac>> ans = mul(TT, A);

    for (int i = 0; i < N; i++) {
        cout << calc(ans[i][0]) << endl;
    }

    return;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}