//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

ll qexp(ll b,ll p,int m){
    ll res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

ll inv(ll i){
	return qexp(i,MOD-2,MOD);
}

vector<vector<ll> > mul(vector<vector<ll> > i, vector<vector<ll> > j,int m){
    vector<vector<ll> > res;
    for (int x=0;x<i.size();x++){
        res.push_back(vector<ll>());
        for (int y=0;y<i.size();y++){
            res[x].push_back(0);
            for (int z=0;z<i.size();z++){
                res[x][y]=(res[x][y]+i[x][z]*j[z][y])%m;
            }
        }
    }
    return res;
}

vector<vector<ll> > mexp(vector<vector<ll> > mat,long long p,int m){
    if (p==1) return mat;
    vector<vector<ll> > res=mexp(mat,p>>1,m);
    res=mul(res,res,m);
    if (p&1) res=mul(res,mat,m);
    return res;
}

int n,m,k;
int arr[105];

vector<vector<ll> > mat;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m>>k;
	rep(x,0,n) cin>>arr[x];
	
	if (k==0){
		rep(x,0,n) cout<<arr[x]<<endl;
		return 0;
	}
	
	rep(x,0,n){
		mat.pub({});
		rep(y,0,n) mat[x].pub(0);
		mat[x][x]=1;
	}
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		a--,b--;
		
		mat[a][b]=inv(2*m%MOD);
		mat[b][a]=inv(2*m%MOD);
		mat[a][a]=(mat[a][a]-inv(2*m%MOD)+MOD)%MOD;
		mat[b][b]=(mat[b][b]-inv(2*m%MOD)+MOD)%MOD;
	}
	
	mat=mexp(mat,k,MOD);
	
	rep(x,0,n){
		int ans=0;
		rep(y,0,n) ans=(ans+mat[x][y]*arr[y])%MOD;
		
		cout<<ans<<endl;
	}
}

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7
#define INF LONG_MAX/3
#define bit(n) (1LL<<(n))

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//class -> num
map<ll, ll> stu[200005];

// 素集合データ構造
struct UnionFind
{
  // par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
  vector<int> par;
  // sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
  vector<int> sizes;

  UnionFind(int n) : par(n), sizes(n, 1) {
	  // 最初は全てのデータiがグループiに存在するものとして初期化
	  for(int i = 0; i < n; i++){
		  par[i] = i;
	  }
  }

  // データxが属する木の根を得る
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
  }

  // 2つのデータx, yが属する木をマージする
  void unite(int x, int y) {
    // データの根ノードを得る
    x = find(x);
    y = find(y);

    // 既に同じ木に属しているならマージしない
    if (x == y) return;

    // xの木がyの木より大きくなるようにする
    if (sizes[x] < sizes[y]) swap(x, y);

    // xがyの親になるように連結する
    par[y] = x;
    sizes[x] += sizes[y];
    for(auto item: stu[y]) stu[x][item.first] += item.second;
    // sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい
  }

  // 2つのデータx, yが属する木が同じならtrueを返す
  bool same(int x, int y) {
    return find(x) == find(y);
  }

  // データxが含まれる木の大きさを返す
  int size(int x) {
    return sizes[find(x)];
  }
};

int main(){
	ll N, Q;
	cin >> N >> Q;
	vector<ll> C(N);
	rep(i, N) cin >> C[i];
	rep(i, N) {
		stu[i][C[i]]++;
	}
	UnionFind uf(N);

	rep(i, Q) {
		ll op, a, b;
		cin >> op >> a >> b;
		if(op == 1) {
			a--;b--;
			uf.unite(a, b);
		} else {
			a--;
			ll g = uf.find(a);
			cout << stu[g][b] << endl;
		}
	}
}
