DUTUYEN

Cho ma trận A kích thước n*n , chỉ gồm 2 giá trị 0 và 1. 

Các hàng của ma trận được đánh số từ 1-n từ trên xuống dưới. Các cột của ma trận được đánh số từ 1-n từ trái qua phải. Ô ở hàng i cột j được gọi là ô (i,j). 

Ta định nghĩa phép nhân ma trận A kích thước n*n với ma trận B kích thước n*n : 

 AB(i,j)   = (  A(i,1)   and   B(1,j)   ) or (   A(i,2)   and  B(2,j)     )  or  ....  or  (   A(i,n)   and  B(n,j)    ) 

Trong  đó and là phép and bit kí hiệu &, or là phép or bit kí hiệu | .

Gọi  C = A^k hãy in ra tất cả các giá trị ở hàng thứ m của C biết rằng   A(i,i)  =1 với mọi i từ 1 đến n.

Input

Dòng đầu tiên chứa 3 số n,k,m ( 1 <= n <= 1000 , 1<= m <=n , k <=1000000000 ).  

N dòng sau mỗi dòng chứa n số thể hiện mảng A.

Output

Một dòng duy nhất chứa n số là các giá trị thuộc hàng m của ma trận A^k.

Example

Input:
3 1 1 

1 0 1 

0 1 0 

0 1 1

Output:
1 0 1