Add By Permutation

 You're given an array of integers 

A$A$ and a permutation P$P$, each of size N$N$. Recall that a permutation of length N$N$ is an array where every element from 1$1$ to N$N$ occurs exactly once.

The following operation is performed on the array K$K$ times:

• For each index i$i$ (1≤i≤N$1\le i\le N$), add APi$A_{P_i}$ to Ai$A_i$ simultaneously.

For example, if A=[2,6,1,7]$A=[2,6,1,7]$ and P=[3,1,4,2]$P=[3,1,4,2]$, after one operation A=[2+A3,6+A1,1+A4,7+A2]=[3,8,8,13]$A=[2+A_3,6+A_1,1+A_4,7+A_2]=[3,8,8,13]$.

Find the values of A$A$ modulo 998244353$998244353$, after performing the above operation K$K$ times.

Input Format

• The first line contains two space separated integers N$N$ and K$K$.
• The second line contains N$N$ space separated integers A1,A2,…AN$A_1,A_2,\dots A_N$, the elements of the array A$A$.
• The third line contains N$N$ space separated integers P1,P2,…PN$P_1,P_2,\dots P_N$, the elements of the permutation P$P$.

Output Format

Print N$N$ space separated integers, the elements of the array A$A$ modulo 998244353$998244353$ after performing the above operation K$K$ times.

Constraints

• 1≤N,K≤2⋅105$1\le N,K\le 2\cdot {10}^5$
• 1≤Ai<998244353$1\le A_i<998244353$
• 1≤Pi≤N$1\le P_i\le N$
• It is guaranteed that P$P$ is a permutation.

Sample Input 1 

4 3
2 6 1 7
3 1 4 2

Sample Output 1 

32 22 42 32

Explanation

The array A$A$ evolves as follows

• A0=[2,6,1,7]$A^0=[2,6,1,7]$
• A1=[3,8,8,13]$A^1=[3,8,8,13]$
• A2=[11,11,21,21]$A^2=[11,11,21,21]$
• A3=[32,22,42,32]$A^3=[32,22,42,32]$

where Ai$A^i$ denotes the array after i$i$ operations.

Thus, finally the elements of A$A$ read [32,22,42,32]$[32,22,42,32]$.