CF36D - New Game with a Chess Piece

Petya and Vasya are inventing a new game that requires a rectangular board and one chess piece. At the beginning of the game the piece stands in the upper-left corner of the board. Two players move the piece in turns. Each turn the chess piece can be moved either one square to the right or one square down or jump k squares diagonally down and to the right. The player who can’t move the piece loses.

The guys haven’t yet thought what to call the game or the best size of the board for it. Your task is to write a program that can determine the outcome of the game depending on the board size.

Input

The first input line contains one integer 1  ≤  t  ≤  20202. Each of the following t  lines contains three numbers: k and n, m - the jump length and the board’s length and width (1 ≤  n, m ,k ≤ 109).

Output

Output t lines that can determine the outcomes of the game on every board. Write «+» if the first player is a winner, and «-» otherwise.

Example

Input:
10
1 1 1
1 2 1
2 1 2
2 2 2
1 3 2
2 3 2
3 1 3
3 2 3
3 3 3
4 3 3

Output:
-
+
+
-
+
+
-
+
-
-

Added by:Ruslan Sennov
Date:2010-10-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:Codeforces #36

hide comments
2021-04-05 06:00:15
Great problem. Don't believe the comments, to infer the logic you need more than the example cases.

Puneet: There is no precedence of any move, each player plays optimally.

Last edit: 2021-04-05 06:01:33
2014-06-18 09:00:03 Puneet Gupta
what is the answer of 1 3 2?? it can be + if diagonal move is given precedence and - otherwise.!
2014-02-16 13:14:27 Bhavik
test cases are enough to solve this problem:)my 200th
2013-03-21 11:41:44 raunakrocks
try the case u'll get the logic :)
AC!!
2010-11-30 05:26:30 Ruslan Sennov
2 magdi
try to replace "cin>>n>>m >>k" with "cin>>k>>n>>m"
2010-11-29 15:17:34 magdi
there is a problem in the sample
in sample 1 3 2 the wining must be - not +
-------
|+|-|+|
-------
the plus will not have a move then - is winner ??????????
THANKS :)

Last edit: 2010-12-01 13:14:33
2010-10-22 15:08:15 যোবায়ের
Edit: got it, it was my mistake in reading input.

Last edit: 2010-10-22 15:29:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.