Петя и Вася придумывают новую игру. Для игры нужна прямоугольная доска и одна шахматная фигура. В начале игры фигура стоит в левом верхнем углу доски. Два игрока по очереди делают ходы. За ход можно передвинуть фигуру либо на 1 клетку вправо, либо на 1 клетку вниз, либо совершить прыжок на k клеток по диагонали вправо и вниз. Проигрывает тот, кто не может сделать ход.
Ребята еще не определились с названием игры, а также с оптимальным размером доски для нее. Ваша задача — написать программу, определяющую исход игры для различных досок.
Выходные данные
Выведите t строк, соответствующих исходам игры на каждой из досок. Выведите «+», если в данном случае первый игрок имеет выигрышную стратегию, и «-» иначе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2
1 1
1 2
2 1
2 2
1 3
2 3
3 1
3 2
3 3
4 3
|
-
+
+
-
-
+
-
+
+
+
|