AXIS - Axis of Symmetry

Given a point p and a line L on the plane, the reflection of p against L is a point q such that the segment pq is perpendicular to L and its middle point is on L. If p is on L, then p = q.

Given a set of points on the plane, an axis of symmetry is a line on the plane such that the reflection of any point of the set against that line gives a point of the set.

In this problem you are given a set of points on the plane, and you must decide whether there exists at least one axis of symmetry or not.

Input

The input contains several test cases, each one described in several lines. The first line of each test case contains an integer N indicating the number of points in the set (3 ≤ N ≤ 1000). Each of the next N lines describes a different point of the set using two integers X and Y separated by a single space (−2000 ≤ X, Y ≤ 2000); these numbers represent the coordinates of the point in the XY plane. You may assume that no two points of each test case have the same location. The last line of the input contains a single −1 and should not be processed as a test case.

Output

For each test case output a single line with an uppercase “Y” if there exists at least one axis of symmetry for the provided set of points, or an uppercase “N” otherwise.

Example

Input:
4
-10 0
10 0
10 10
10 -10
4
-10 0
10 1
10 10
10 -10
6
-1000 30
-100 20
-10 10
1000 30
100 20
10 10
-1

Output:
Y
N
Y

Added by:Pablo Ariel Heiber
Date:2010-08-19
Time limit:3.033s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2008

hide comments
2013-08-25 16:31:38 Jorge Miranda
D;
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.