問題文

$1, 2, \dots, N$ の番号が付いた $N$ 個の頂点からなる無向根付き木が与えられます。頂点 $1$ が根です。
根付き木の $i$ $(1 \leq i \leq N - 1)$ 番目の辺は頂点 $X_{i}$ と頂点 $Y_{i}$ を結んでいます。

最初、頂点 $i$ $(1 \leq i \leq N)$ には $A_{i}$ 個の石が置かれています。

これから、コアさんとパチェさんがゲームを行います。 コアさんから始めて、次の操作を交互に行います。

1. まず、根付き木の頂点 $1$ を除く $N-1$ 個の頂点のうち、石が $1$ 個以上置かれているものを $1$ 個選び、これを $v$ とする。

2. 次に、$v$ から $1$ 個以上 $K$ 個以下の石を取り除き、これらをすべて $v$ の親頂点に置く。

両者のうち、先に操作を行えなくなった方の負けとします。

両者が最善を尽くしたとき、どちらが勝つか判定してください。

$T$ 個のテストケースについて答えを求めてください。

制約

• $1 \leq T \leq 10^{5}$

• $2 \leq N \leq 2 \times 10^{5}$

• $1 \leq X_{i}, Y_{i} \leq N$ $(1 \leq i \leq N - 1)$

• $1 \leq K \leq 10^{9}$

• $1 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

• $1$ つの入力で与えられる $N$ の総和は $2 \times 10^{5}$ 以下

• 入力で与えられるグラフはすべて頂点 $1$ を根とする無向根付き木

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
  $\vdots$
$\mathrm{case}_{T}$

各テストケースは次の形式で与えられます。

$N$ $K$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
   $\vdots$
$X_{N-1}$ $Y_{N-1}$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$

出力

答えを $1$ 行ずつ合計 $T$ 行に出力してください。

$i$ $(1 \leq i \leq T)$ 行目には、$i$ 個目のテストケースについてゲームを行ったときにコアさんが勝つならば K を、パチェさんが勝つならば P を出力してください。

サンプル

4
4 2
1 2
1 3
2 4
1 3 4 2
6 10
3 1
2 3
5 4
3 6
5 1
999 100 375 109 210 712
2 1
1 2
2 1
8 6
2 4
2 8
7 2
1 2
2 3
5 2
6 2
3 14 15 92 6 53 5 89

K
P
K
P