C. Discovering Ngipto
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A group of archaeologists recently discovered an ancient civilization in Egypt called Ngipto. The civilization lived in a desert, which is modeled as an infinite two-dimensional plane. In this desert, the Ngiptians built a pyramid with a polygonal base. Given a description of the pyramid and the position of the sun $$$(X_{sun}, Y_{sun}, Z_{sun})$$$, the archaeologists want to determine if there is any point in the desert where they can set up their camp sheltered from the sun.

More precisely, the base of the pyramid consists of a simple not necessarily convex polygon formed by $$$N$$$ points

$$$(X_1, Y_1, 0), (X_2, Y_2, 0), \ldots, (X_N, Y_N, 0)$$$

Where the first two coordinates represent Cartesian coordinates in the plane of the desert, and the third coordinate represents the height, which for the points of the base is $$$0$$$ since they are on the plane of the desert.

The pyramid's apex is located at the point $$$(X_{ape}, Y_{ape}, Z_{ape})$$$ with $$$Z_{ape} \gt 0$$$, i.e. located above the plane of the desert. The points of the pyramid are exactly those that lie on some segment with one endpoint inside or on the edge of the polygon, and the other endpoint at the apex.

You are asked to determine if there exists any point in the plane of the desert sheltered from the sun, that is, any point in the plane of the desert outside the polygon such that the segment connecting it to the sun intersects the pyramid.

Input

A line with an integer $$$N$$$ $$$(3 \leq N \leq 1000)$$$, the number of vertices in the polygonal base of the pyramid.

Then a line with three integers $$$X_{ape}, Y_{ape}, Z_{ape}$$$ $$$(-10^4 \leq X_{ape}, Y_{ape} \leq 10^4$$$, $$$1 \leq Z_{ape} \leq 10^4)$$$, the coordinates of the apex of the pyramid.

Then a line with three integers $$$X_{sun}, Y_{sun}, Z_{sun}$$$ $$$(-10^4 \leq X_{sun}, Y_{sun} \leq 10^4$$$, $$$Z_{ape} \lt Z_{sun} \leq 10^4)$$$, the coordinates of the sun.

Then $$$N$$$ lines that describe the vertices of the polygonal base of the pyramid. The $$$i$$$-th of these lines contains the integers $$$X_i, Y_i$$$ $$$(-10^4 \leq X_i, Y_i \leq 10^4)$$$. These points are given in clockwise order and form a simple polygon.

Output

A line with the letter "S" if there exists any point in the plane of the desert sheltered from the sun, or the letter "N" otherwise.

Examples
Input
4
2 2 4
2 2 6
0 0
0 4
4 4
4 0
Output
N
Input
4
2 2 4
6 6 6
0 0
0 4
4 4
4 0
Output
S
Input
4
2 2 4
2 2 6
0 0
0 4
1 1
4 0
Output
S
Note

The figure shows a top view of example 2. The light shaded areas are the points in the desert where the archaeologists can camp. The image contains some words in Spanish, sol means sun, and cúspide means apex.