PARADOX - Paradox

A paradox is a statement or group of statements that leads to a contradiction. Consider the following two statements.

          "The statement below is false."
          "The statement above is true."

If we assume that 1st statement is true then according to 1st statement the 2nd statement is false. Since the 2nd statement is false and it says that 1st statement is true, 1st statement must be false which is a contradiction. If we assume that 1st statement is false then the 2nd statement must be true (since 1st statement says 2nd statement is false). Then according to 2nd statement 1st statement must be true which is a contradiction. Thus the statement cannot be classified as true or false. This is a paradox.

Given N statements of the form "Statement X is true/false", 1<=X<=N, your task is to find if these set of statements are paradoxical or not. A set of statements is paradoxical if one or more statements cannot be classified as true or false.

Input

Multiple test cases. Each test cases begins with an integer N representing the number of statements. 1<=N<=100. Then follow N lines, representing N statements in the order 1,2,3, ...,N. Each line contains an integer X and a string S separated by a space. 1<=X<=N. S is either "true" or "false" (quotes for clarity), which means the statement is "Statement X is S". N=0 indicates the end of testcases and should not be processed. There are atmost 10000 testcases.

Output

For each test case print "PARADOX" if the set of statements are paradoxical, else print "NOT PARADOX", in a separate line.

Example

Input:
2
2 false
1 true
2
2 false
1 false
0

Output:
PARADOX
NOT PARADOX

Added by:arun
Date:2010-01-03
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Kurukshetra OPC 2010

hide comments
2020-01-10 13:05:24
Hint:
A cycle with odd number of FALSE is always a parradox.
Enjoy
2019-12-18 08:13:46
@ekta_9 answer to your test case is PARADOX.
2019-11-08 13:43:24
can anyone suggest some corner testcases in which code can fali? please
2019-11-08 08:16:17
what should be the output of this
2
1 false
1 false
0
2019-09-18 16:55:42
nice problem :p
2018-06-02 14:07:40
simple coloring problem!
2018-06-01 10:16:32
While struggling to debug, made the mistake of looking for solutions on the web. Can't remember the last time I felt so much hate from just looking at stupid code! Eventually added 3 lines to my own program and got AC; 15 lines in Python not counting the I/O.

Do it yourself and don't lose faith in simple solutions, otherwise you'll detest the time spent working on this one.
2017-12-19 11:19:15
loved solving it
2017-12-03 06:16:35
It was really interesting!!! Enjoyed solving
2017-07-03 11:30:38
AC after a day...!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.