D. Игра в перестановке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бодя и Саша нашли перестановку $$$p_1,\dots,p_n$$$ и массив $$$a_1,\dots,a_n$$$. Они решили сыграть в известную игру в перестановке.

Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Каждый из них выбрал стартовую позицию в перестановке.

Игра длится $$$k$$$ ходов. Игроки делают ходы одновременно. На каждом ходу с каждым игроком происходит две вещи:

  • Если текущая позиция игрока $$$x$$$, его счет увеличивается на $$$a_x$$$.
  • Затем игрок либо остается на своей текущей позиции $$$x$$$, либо перемещается с $$$x$$$ на $$$p_x$$$.
Победителем игры становится игрок с более высоким счетом после ровно $$$k$$$ ходов.

Зная стартовую позицию Боди $$$P_B$$$ и стартовую позицию Саши $$$P_S$$$, определите, кто выигрывает в игре, если оба игрока пытаются победить.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит целые числа $$$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$$$) — длина перестановки, продолжительность игры, стартовые позиции соответственно.

Следующая строка содержит $$$n$$$ целых чисел $$$p_1,\dots,p_n$$$ ($$$1 \le p_i \le n$$$) — элементы перестановки $$$p$$$.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,\dots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите:

  • «Bodya», если Бодя выигрывает игру.
  • «Sasha», если Саша выигрывает игру.
  • «Draw», если у игроков одинаковый счет.
Пример
Входные данные
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
Выходные данные
Bodya
Sasha
Draw
Draw
Bodya
Sasha
Sasha
Sasha
Sasha
Bodya
Примечание

Ниже вы можете найти объяснение для первого набора входных данных, где игра состоит из $$$k=2$$$ ходов.

ХодПозиция БодиОчки БодиХод БодиПозиция СашиОчки СашиХод Саши
первый$$$3$$$$$$0 + a_3 = 0 + 5 = 5$$$остаётся в текущей позиции$$$2$$$$$$0 + a_2 = 0 + 2 = 2$$$переходит в $$$p_2=1$$$
второй$$$3$$$$$$5 + a_3 = 5 + 5 = 10$$$остаётся в текущей позиции$$$1$$$$$$2 + a_1 = 2 + 7 = 9$$$остаётся в текущей позиции
конечный результат$$$3$$$$$$10$$$$$$1$$$$$$9$$$

Как мы видим, счет Боди больше, поэтому он выигрывает игру. Можно показать, что Бодя всегда может выиграть эту игру.