311304: CF1968D. Permutation Game

D. Permutation Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

The winner of the game is the player with the higher score after exactly $k$ turns.

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.

ExampleInput

10
4 2 3 2
4 1 2 3
7 2 5 6
10 8 2 10
3 1 4 5 2 7 8 10 6 9
5 10 5 1 3 7 10 15 4 3
2 1000000000 1 2
1 2
4 4
8 10 4 1
5 1 4 3 2 8 6 7
1 1 2 1 2 100 101 102
5 1 2 5
1 2 4 5 3
4 6 9 4 2
4 2 3 1
4 1 3 2
6 8 5 3
6 9 5 4
6 1 3 5 2 4
6 9 8 9 5 10
4 8 4 2
2 3 4 1
5 2 8 7
4 2 3 1
4 1 3 2
6 8 5 3
2 1000000000 1 2
1 2
1000000000 2

Output

Bodya
Sasha
Draw
Draw
Bodya
Sasha
Sasha
Sasha
Sasha
Bodya

Note

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

Turn	Bodya's position	Bodya's score	Bodya's move	Sasha's position	Sasha's score	Sasha's move
first	$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 position
final 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.

题目大意：

鲍伊亚和萨沙发现了一个长度为 n 的排列 p_1, ..., p_n 和一个数组 a_1, ..., a_n。他们决定玩一个著名的“排列游戏”。

长度为 n 的排列是一个由 1 到 n 的 n 个不同整数以任意顺序组成的数组。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是一个排列（数组中 2 出现了两次），[1,3,4] 也不是一个排列（n=3 但数组中有 4）。

他们各自在排列中选择了起始位置。

游戏持续 k 轮。玩家同时进行移动。在每一轮中，对每个玩家发生两件事：

1. 如果玩家当前的位置是 x，他的分数增加 a_x。
2. 然后，玩家可以选择留在当前位置 x，或者从 x 移动到 p_x。

游戏结束时，分数较高的玩家获胜。

已知鲍伊亚的起始位置 P_B 和萨沙的起始位置 P_S，确定如果双方都试图获胜，谁会赢得游戏。

输入输出数据格式：

输入：
- 第一行包含一个整数 t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含整数 n、k、P_B、P_S（1≤P_B,P_S≤n≤2×10^5，1≤k≤10^9）——排列的长度、游戏的持续时间、起始位置。
- 下一行包含 n 个整数 p_1, ..., p_n（1≤p_i≤n）——排列 p 的元素。
- 下一行包含 n 个整数 a_1, ..., a_n（1≤a_i≤10^9）——数组 a 的元素。
- 保证所有测试用例的 n 值之和不超过 2×10^5。

输出：
- 对于每个测试用例输出：
- 如果鲍伊亚获胜，输出“Bodya”。
- 如果萨沙获胜，输出“Sasha”。
- 如果玩家分数相同，输出“Draw”。

示例输入输出已给出，具体见题目描述。题目大意： 鲍伊亚和萨沙发现了一个长度为 n 的排列 p_1, ..., p_n 和一个数组 a_1, ..., a_n。他们决定玩一个著名的“排列游戏”。 长度为 n 的排列是一个由 1 到 n 的 n 个不同整数以任意顺序组成的数组。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是一个排列（数组中 2 出现了两次），[1,3,4] 也不是一个排列（n=3 但数组中有 4）。 他们各自在排列中选择了起始位置。 游戏持续 k 轮。玩家同时进行移动。在每一轮中，对每个玩家发生两件事： 1. 如果玩家当前的位置是 x，他的分数增加 a_x。 2. 然后，玩家可以选择留在当前位置 x，或者从 x 移动到 p_x。 游戏结束时，分数较高的玩家获胜。 已知鲍伊亚的起始位置 P_B 和萨沙的起始位置 P_S，确定如果双方都试图获胜，谁会赢得游戏。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含整数 n、k、P_B、P_S（1≤P_B,P_S≤n≤2×10^5，1≤k≤10^9）——排列的长度、游戏的持续时间、起始位置。 - 下一行包含 n 个整数 p_1, ..., p_n（1≤p_i≤n）——排列 p 的元素。 - 下一行包含 n 个整数 a_1, ..., a_n（1≤a_i≤10^9）——数组 a 的元素。 - 保证所有测试用例的 n 值之和不超过 2×10^5。 输出： - 对于每个测试用例输出： - 如果鲍伊亚获胜，输出“Bodya”。 - 如果萨沙获胜，输出“Sasha”。 - 如果玩家分数相同，输出“Draw”。 示例输入输出已给出，具体见题目描述。