Петя и Вася придумывают новую игру. Для игры нужна прямоугольная доска и одна шахматная фигура. В начале игры фигура стоит в левом верхнем углу доски. Два игрока по очереди делают ходы. За ход можно передвинуть фигуру либо на 1 клетку вправо, либо на 1 клетку вниз, либо совершить прыжок на k клеток по диагонали вправо и вниз. Проигрывает тот, кто не может сделать ход.
Ребята еще не определились с названием игры, а также с оптимальным размером доски для нее. Ваша задача — написать программу, определяющую исход игры для различных досок.
В первой строке входного файла содержатся два целых числа t и k (1 ≤ t ≤ 20, 1 ≤ k ≤ 109). Каждая из следующих t строк содержат пару чисел n, m — размеры доски (1 ≤ n, m ≤ 109).
Выведите t строк, соответствующих исходам игры на каждой из досок. Выведите «+», если в данном случае первый игрок имеет выигрышную стратегию, и «-» иначе.
10 2 1 1 1 2 2 1 2 2 1 3 2 3 3 1 3 2 3 3 4 3
- + + - - + - + + +
2000 ms 64 Mb Правила оформления программ и список ошибок при автоматической проверке задач