시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 6 4 3 100.000%

문제

Gandalf and Saruman are playing a game. Gandalf has $n$ potions in a row, and Saruman has $m$ potions in a row. Each potion has a magical power, Gandalf's potions have powers $a_1, a_2, \ldots, a_n$, and Saruman's potions have powers $b_1, b_2, \ldots, b_m$. Initially both of them have no unit of mana. 

Players take turns. Gandalf moves first. 

At each turn player takes the leftmost potion he has, drinks it, and receives $x$ units of mana, where $x$ is the power of the taken potion. If player does not have any potion on his turn, he loses the game. After drinking the potion, player may use his magical powers to destroy some potions of his opponent. Destroying one potion costs one unit of mana.

Each player wants to win, and, furthermore, wants to finish the game with the maximum possible number of potions left. A player who is going to lose tries to minimize the number of potions of the opponent in the end of the game. Determine who is going to win and how many potions they have at the end of the game if both players play optimally. 

입력

The first line contains two integers $n$ and $m$ --- the number of potions that Gandalf and Saruman have, respectively ($1 \le n, m \le 200$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ --- the powers on Gandalf's potions from left to right ($0 \le a_i \le 200$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ --- the powers on Saruman's potions from left to right ($0 \le b_i \le 200$).

출력

Print the name of the player who wins the game and the number of potions that the winning player has at the end of the game.

서브태스크

번호 배점 제한
1 5

$a_i = 0, b_i = 0$

2 10

$n, m \leq 5$

3 25

$n, m \leq 20$

4 35

$n, m \leq 100$

5 25

No additional constraints.

예제 입력 1

5 4
1 0 1 4 4
2 3 0 5

예제 출력 1

Gandalf 0

예제 입력 2

3 4
1 3 4
3 2 0 0

예제 출력 2

Saruman 2

예제 입력 3

9 9
2 0 1 2 1 1 2 1 2
1 2 1 1 1 0 1 2 2

예제 출력 3

Gandalf 1

채점 및 기타 정보

  • 예제는 채점하지 않는다.