#1636 Point In Polygon

39  5 s   128 MB  

Description

Given a test point, (X, Y), and the vertices of a simple polygon, vertices, determine if the test point is in the interior, in the exterior or on the boundary of the polygon. Output the string "INTERIOR", "EXTERIOR", or "BOUNDARY".
For simplicity, all sides of the polygon will be horizontal or vertical, and the vertices and the test point will all be at integer coordinates. There is an edge from i-th vertex to (i+1)-th vertex for i from 0 to n-2, and an edge from (n-1)-th vertex to 0-th vertex where n is the number of vertices (and the number of edges) in the polygon.
A simple polygon is a polygon that may or may not be convex, but self-intersection is not allowed. Not even at a single point.

Input

The first line of input contains the number of test cases T (T ≤ 100).

For each test case, the first line contains three integers N (4 ≤ N ≤ 50), X and Y (-1000 ≤ X, Y ≤ 1000).  

Following N lines will contain corresponding x- and y-coordinates for each vertex (-1000 ≤ xy ≤ 1000). No three consecutive vertices will be colinear.

Output

For each test case, output a single line containing "INTERIOR", "EXTERIOR", or "BOUNDARY".

Sample Input

Sample Output

8
4 5 5
0 0
0 10
10 10
10 0
4 10 15
0 0
0 10
10 10
10 0
4 5 10
0 0
0 10
10 10
10 0
12 0 0
-100 -90
-100 100
100 100
100 -100
-120 -100
-120 100
-130 100
-130 -110
110 -110
110 110
-110 110
-110 -90
12 100 500
0 0
0 1000
1000 1000
1000 800
200 800
200 600
600 600
600 400
200 400
200 200
1000 200
1000 0
12 322 333
0 1000
1000 1000
1000 800
200 800
200 600
600 600
600 400
200 400
200 200
1000 200
1000 0
0 0
40 200 200
500 0
500 100
400 100
400 200
300 200
300 300
200 300
200 400
100 400
100 500
0 500
0 400
-100 400
-100 300
-200 300
-200 200
-300 200
-300 100
-400 100
-400 0
-500 0
-500 -100
-400 -100
-400 -200
-300 -200
-300 -300
-200 -300
-200 -400
-100 -400
-100 -500
0 -500
0 -400
100 -400
100 -300
200 -300
200 -200
300 -200
300 -100
400 -100
400 0
46 0 0
1 0
2 0
2 1
3 1
3 0
4 0
4 -1
5 -1
5 0
6 0
6 2
0 2
0 3
-1 3
-1 4
0 4
0 6
1 6
1 7
0 7
0 8
-2 8
-2 2
-8 2
-8 0
-7 0
-7 -1
-6 -1
-6 0
-4 0
-4 1
-3 1
-3 0
-2 0
-2 -6
0 -6
0 -5
1 -5
1 -4
0 -4
0 -3
-1 -3
-1 -2
0 -2
0 -1
1 -1
INTERIOR
EXTERIOR
BOUNDARY
EXTERIOR
INTERIOR
EXTERIOR
INTERIOR
INTERIOR

HINT