問題文

$2$ 個の正整数 $N, K$ と、$9$ 個の整数 $p_{1,1}, p_{1,2}, p_{1,3}, p_{2,1}, p_{2,2}, p_{2,3}, p_{3,1}, p_{3,2}, p_{3,3}$ と、長さ $N$ の正整数列 $A = (A_{1}, A_{2}, \dots, A_{N})$ が与えられます。
また、K と P のみからなる長さ $N$ の文字列 $S$ が与えられます。以下、$S$ の先頭から $i$ $(1 \leq i \leq N)$ 番目の文字を $S_{i}$ と表します。

三次元空間上に $4$ 点 $O(0, 0, 0), P_{1}(p_{1,1}, p_{1,2}, p_{1,3}), P_{2}(p_{2,1}, p_{2,2}, p_{2,3}), P_{3}(p_{3,1}, p_{3,2}, p_{3,3})$ をとり、コアさんとパチェさんがゲームを行います。

ゲームは $N$ 回のターンからなり、$i$ $(1 \leq i \leq N)$ 回目のターンでは $S_{i}$ が K ならばコアさんが、$S_{i}$ が P ならばパチェさんが次の操作を行います。

1. まず、$1 \leq j,k \leq 3$ を満たす整数の組 $(j,k)$ を $1$ つ選ぶ（$j = k$ でも良い） 。

2. 次に、三次元空間上に $\overrightarrow{OQ} = \overrightarrow{OP_{j}} + A_{i} \overrightarrow{OP_{k}}$ を満たす点 $Q$ をとり、$P_{j}$ を $Q$ と同じ座標に移動させる。

$N$ 回のターン終了後、ゲームの結果を次の手順によって決定します。

1. $4$ 点 $O, P_{1}, P_{2}, P_{3}$ からなる四面体の体積を $V$ とする。ただし、これら $4$ 点が同一平面上に存在する場合は $V = 0$ とする。

2. $V$ が正整数でないならば、引き分けとする。

3. $V$ が正整数であり、$V$ を $101$ で割った余りが $K$ 以上ならば、コアさんの勝ちとする。

4. 上記以外の場合は、パチェさんの勝ちとする。

両者が最善を尽くしたとき、ゲームの結果がどうなるか判定してください。

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

制約

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

• $1 \leq N \leq 10^{4}$

• $1 \leq K \leq 100$

• $-10^{6} \leq p_{i,j} \leq 10^{6}$ $(1 \leq i, j \leq 3)$

• $1 \leq A_{i} \leq 99$ $(1 \leq i \leq N)$

• $S$ は K と P のみからなる長さ $N$ の文字列

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

• $S$ 以外の入力はすべて整数

入力

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

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

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

$N$ $K$
$p_{1,1}$ $p_{1,2}$ $p_{1,3}$
$p_{2,1}$ $p_{2,2}$ $p_{2,3}$
$p_{3,1}$ $p_{3,2}$ $p_{3,3}$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
$S$

出力

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

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

サンプル

4
3 10
1 2 3
6 5 4
8 7 9
2 3 2
KKP
3 30
1 2 3
6 5 4
8 7 9
2 3 2
KKP
2 1
1 1 1
2 2 2
3 3 3
10 20
PK
10 50
14092 -4810 2101
-573209 -311 9
2098 454103 -785
48 19 21 63 99 8 32 53 29 78
KKPKPPKPKP

K
D
D
P