INOROUT - Inside or outside?

Given N points in counterclockwise order, which represent a convex polygon with N edges and N vertexes, you must answer Q queries, each of them represents one point. Use cross product to determine if the point is inside or outside the polygon.

Input

The first line contains 2 integers, N and Q, each of them lower than 10^3.

The second line has 2*N integers, with vales between -10^6 and 10^6, separated by a single space that represent the Xi and Yi coordinates of the i-th vertex of the polygon in counterclockwise order.

Format: X1 Y1 X2 Y2 ... XN YN

Next you will receive Q lines. Each line has two integers X and Y separated by space between -10^6 and 10^6 representing a query.

Note:

  1. It is guaranteed that the given polygon has no repeated vertices, but it may have collinear points.
  2. If a point lies on an edge of the polygon it must be considered inside the polygon.

Output

For each query (in the given order) print a single line that contains a letter 'D' if the point is inside the polygon or a letter 'F' if it's outside.

Example

Input:
3 3
0 0 3 0 0 3
-1 -1
0 0
1 1

Output:
F
D
D

Added by:BerSub
Date:2016-12-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2021-06-21 21:48:35
Weak tests. Case with query on the same line with two points isn't included.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.