Youtuber_TWK cho một cây gồm \(N\) đỉnh, đỉnh \(i\) có giá trị \(A_i\) và trọng số \(W_i\). Với mỗi cặp đỉnh phân biệt \({u, v}\), gọi \(P(u,v)\) là tích các giá trị \(A_x\) trên đường đi nối \(u\) và \(v\).
Cho số nguyên dương \(K\) (không phải số chính phương), cặp \({u,v}\) được gọi là tốt nếu \(P(u,v) = K·t²\) với \(t\) nguyên nào đó (tương đương: phần tự do chính phương của \(P(u,v)\) bằng phần tự do chính phương của \(K\)).

Với mỗi \(d\ =\ 0\ …\ N−1\), tính tổng \(∏\ W_x\) (theo mod \(998244353\)) trên tất cả các đường đi \({u,v}\) tốt có độ dài \(d\).

Input

• Dòng 1: hai số nguyên \(N,\ K\).
• Dòng 2: \(N−1\) số nguyên \(P_2,\ …,\ P_N\) (\(P_i\) là cha của đỉnh \(i\), \(1\ ≤\ P_i\ <\ i\)).
• Dòng 3: \(N\) số nguyên \(A_1,\ …,\ A_N\) (\(1\ ≤\ A_i\ ≤\ 10^6\)).
• Dòng 4: \(N\) số nguyên \(W_1,\ …,\ W_N\) (\(0\ ≤\ W_i\ <\ 998244353\)).

Constraints

• \(1\ ≤\ N\ ≤\ 120000\)
• \(1\ ≤\ P_i\ <\ i\)
• \(1\ ≤\ A_i\ ≤\ 10^6\)
• \(0\ ≤\ W_i\ <\ 998244353\)
• \(2\ ≤\ K\ ≤\ 10^6\), \(K\) là số tự do chính phương.

Output

• Một dòng gồm \(N\) số nguyên \(Ans[0],\ …,\ Ans[N−1]\), cách nhau bởi khoảng trắng.

Example

4 2
1 1 1
2 3 6 1
1 1 1 1

0 1 0 0

12 2
1 1 2 2 3 3 4 4 5 5 6
2 2 2 2 2 2 2 2 2 2 2 2
7 11 5 13 17 3 19 23 29 31 37 41

0 0 55118 0 9602791 0 86754360 0 0 0 0 0