Бодя и Саша нашли перестановку \(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\), определите, кто выигрывает в игре, если оба игрока пытаются победить.
Выходные данные
Для каждого набора входных данных выведите:
- «Bodya», если Бодя выигрывает игру.
- «Sasha», если Саша выигрывает игру.
- «Draw», если у игроков одинаковый счет.
Примечание
Ниже вы можете найти объяснение для первого набора входных данных, где игра состоит из \(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\) | |
Как мы видим, счет Боди больше, поэтому он выигрывает игру. Можно показать, что Бодя всегда может выиграть эту игру.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|