ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Nikifor's Walk

Time limit: 0.25 second
Memory limit: 64 MB
Little Nikifor wouldn't stay long without movement. It's boring to run in one direction for a long time, as well. A wise nanny knows that when Nikifor goes playing outdoors he moves along vectors a1, a2, …, an; each time his displacement is either equal to the next in turn vector or to the vector opposite to it. A pedagogical influence of the nanny with Nikifor is rather strong, so each time she can point out which one of the two possible directions he should choose.
The nanny knows that length of each of the vectors a1, a2, …, an doesn't exceed L. Nikifor starts his walk from the nanny and she wants him to move off her not farther than by the square root of 2 multiplied by L (sqrt(2)L) in the end of his walk. What directions should she point out in order not to let the child move too far off her pedagogical influence in the end of the walk?


The first line contains an integer n, 0 < n ≤ 10000. The second line contains a non-negative integer L, L < 100. The next n lines contain coordinates of the vectors. The coordinates are integer.


The first line is to contain the word “YES” if the nanny can cope with her task, and “WRONG ANSWER” otherwise. If the answer is “YES” then the next line should consist of n symbols “+” or “-”. There is the symbol “+” at the i-th position if Nikifor runs along the vector ai, and there's a symbol “-” if Nikifor runs along the vector −ai. If there are several solutions it's enough to output an arbitrary one.


5 0
0 5
0 0
-3 4
Problem Author: Dmitry Filimonenkov
Problem Source: VI Ural State University Collegiate Programming Contest (21.10.2001)
To submit the solution for this problem go to the Problem set: 1130. Nikifor's Walk