Math Graph

Cho đồ thị có hướng $n$ đỉnh và $m$ cạnh và không quá $1$ cạnh nối từ đỉnh $u$ đến đỉnh $v$ ($\forall u,v\le n$). Ta định nghĩa trọng số thứ $k$ của đỉnh $u$ sẽ là:

• $w_k(u)=\sum\limits_{v\in in_u}a_vw_{k-1}(v)$. Tức là các đỉnh $v$ có hướng nối đến $u$, nếu không có thì $w_k(u)=0$.
• $w_0(u)=p_u$

Cho biết số nguyên dương $k$ và dãy $P=(p_1;p_2;...;p_n)$. Tính $w_k(1),w_k(2),...,w_k(n)$.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên dương $n,m,k$ ($n\le 100, m\le \frac{n\times(n+1)}{2}, k\le 10^9$);
• Dòng tiếp theo chứa $n$ số nguyên dương $a_1,a_2,...,a_n$ ($a_i\le 10^9, \forall i=1,2,...,n$);
• Dòng tiếp theo chứa $n$ số nguyên dương $p_1,p_2,...,p_n$ ($p_i\le 10^9, \forall i=1,2,...,n$);
• $m$ dòng tiếp theo, mỗi dòng chứa $2$ số nguyên dương $u, v$ ($u,v\le n$) - Cho biết có cạnh nối từ $u$ đến $v$.

Kết quả

• In ra dãy $w_k(1),w_k(2),...,w_k(n)$. Do kết quả có thể rất lớn nên hãy in ra sau khi chia lấy dư cho $10^9+201009$.

Ví dụ

Input

4 8 2
1 1 1 1
2 3 9 1
1 2 
3 4
4 1
2 3
1 1
2 2
3 3
4 4 

13 8 17 22