Bodya and Sasha found a permutation $p_1,\dots,p_n$ and an array $a_1,\dots,a_n$. They decided to play a well-known "Permutation game".

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Both of them chose a starting position in the permutation.

The game lasts $k$ turns. The players make moves simultaneously. On each turn, two things happen to each player:

• If the current position of the player is $x$, his score increases by $a_x$.
• Then the player either stays at his current position $x$ or moves from $x$ to $p_x$.

Knowing Bodya's starting position $P_B$ and Sasha's starting position $P_S$, determine who wins the game if both players are trying to win.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of testcases.

The first line of each testcase contains integers $n$, $k$, $P_B$, $P_S$ ($1\le P_B,P_S\le n\le 2\cdot 10^5$, $1\le k\le 10^9$) — length of the permutation, duration of the game, starting positions respectively.

The next line contains $n$ integers $p_1,\dots,p_n$ ($1 \le p_i \le n$) — elements of the permutation $p$.

The next line contains $n$ integers $a_1,\dots,a_n$ ($1\le a_i\le 10^9$) — elements of array $a$.

It is guaranteed that the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each testcase output:

• "Bodya" if Bodya wins the game.
• "Sasha" if Sasha wins the game.
• "Draw" if the players have the same score.

见题面 Input 部分

见题面 Output 部分

Below you can find the explanation for the first testcase, where the game consists of $k=2$ turns.

TurnBodya's positionBodya's scoreBodya's moveSasha's positionSasha's scoreSasha's movefirst$3$$0 + a_3 = 0 + 5 = 5$stays on the same position$2$$0 + a_2 = 0 + 2 = 2$moves to $p_2=1$second$3$$5 + a_3 = 5 + 5 = 10$stays on the same position$1$$2 + a_1 = 2 + 7 = 9$stays on the same positionfinal results$3$$10$$1$$9$

As we may see, Bodya's score is greater, so he wins the game. It can be shown that Bodya always can win this game.