Problem Statement

You are given $2$ positive integers $N, K$, $9$ integers $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}$, and a sequence of positive integers of length $N$, $A = (A_{1}, A_{2}, \dots, A_{N})$.
You are also given a string $S$ of length $N$ consisting only of K and P. Below, the $i$-th $(1 \leq i \leq N)$ character from the beginning of $S$ is denoted by $S_{i}$.

Take $4$ points $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})$ in three-dimensional space. Koa and Pache play a game.

The game consists of $N$ turns. In the $i$-th $(1 \leq i \leq N)$ turn, if $S_{i}$ is K, Koa performs the following operation, and if $S_{i}$ is P, Pache performs it.

1. First, choose $1$ pair of integers $(j,k)$ satisfying $1 \leq j,k \leq 3$ ($j = k$ is allowed).

2. Next, take the point $Q$ in three-dimensional space satisfying $\overrightarrow{OQ} = \overrightarrow{OP_{j}} + A_{i} \overrightarrow{OP_{k}}$, and move $P_{j}$ to the same coordinates as $Q$.

After the $N$ turns have ended, the result of the game is determined by the following procedure.

1. Let $V$ be the volume of the tetrahedron formed by the $4$ points $O, P_{1}, P_{2}, P_{3}$. If these $4$ points lie on the same plane, let $V = 0$.

2. If $V$ is not a positive integer, the game is a draw.

3. If $V$ is a positive integer and the remainder when $V$ is divided by $101$ is at least $K$, Koa wins.

4. Otherwise, Pache wins.

Determine the result of the game when both players play optimally.

Find the answer for each of the $T$ test cases.

Constraints

• $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$ is a string of length $N$ consisting only of K and P.

• In $1$ input, the sum of $N$ is at most $10^{4}$.

• All values in the input other than $S$ are integers.

Input

The input is given in the following format.

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

Each test case is given in the following format.

$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$

Output

Print the answers, $1$ per line, for a total of $T$ lines.

On the $i$-th $(1 \leq i \leq T)$ line, for the game played on the $i$-th test case, print: if Koa wins, K; if Pache wins, P; if it is a draw, D.

Sample

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