F. Farming Aura
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

One of the most popular internet slang expressions at the moment is "farming aura", which means accumulating style, charisma, respect, or presence points. The term combines the gaming expression "to farm" (repeating actions to accumulate points) with aura (a person's energy, vibe, or attitude). One of the online games where this slang became popular is Fibia, a game in which the objective is to explore a vast world represented as a two-dimensional map viewed from above.

In a certain game scenario, there are $$$N$$$ points and $$$M$$$ segments connecting pairs of these $$$N$$$ points. Each segment represents a wall in the game world. These segments do not intersect and may touch only at their endpoints, which are among the $$$N$$$ points (none of the $$$N$$$ points lies in the interior of any of the $$$M$$$ segments).

Depending on a player's position in this scenario, the player may become "trapped" by these segments; that is, the player's position lies inside a polygon bounded by the segments. When a player is in such a position, they are considered to be "losing aura", since they cannot explore the entire map unless they use some teleportation spell. Otherwise, the player is considered to be "gaining aura".

In the figure above, players at positions $$$A$$$ and $$$C$$$ are "gaining aura", while players at positions $$$B$$$ and $$$D$$$ are "losing aura".

Given the positions of $$$K$$$ players on the game map, your task is to determine which players are losing aura and which are gaining aura.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 1000$$$, $$$1 \leq M \leq \frac{N(N-1)}{2}$$$).

The next $$$N$$$ lines each contain two integers $$$X_i$$$ and $$$Y_i$$$ ($$$0 \leq X_i, Y_i \leq 10000$$$), representing the coordinates of the $$$N$$$ points in the game's Cartesian plane. All points are distinct.

The next $$$M$$$ lines each contain two integers $$$A_i$$$ and $$$B_i$$$ ($$$1 \leq A_i, B_i \leq N$$$, $$$A_i \neq B_i$$$), indicating $$$M$$$ distinct pairs of points connected by segments. It is guaranteed that no two segments intersect, although they may share endpoints. Furthermore, no segment passes through any of the other $$$N-2$$$ points besides its own endpoints.

The next line contains an integer $$$K$$$ ($$$1 \leq K \leq 1000$$$).

The following $$$K$$$ lines each contain two integers $$$KX_i$$$ and $$$KY_i$$$ ($$$0 \leq KX_i, KY_i \leq 10000$$$), representing the coordinates of the $$$K$$$ query points in order. It is guaranteed that none of these points lies on any of the $$$M$$$ segments and that none of them coincides with any of the $$$N$$$ given points.

Output

Your program must output a single line containing a sequence of $$$K$$$ characters, each either P or G, indicating, in order, whether the corresponding players are "losing aura" (P) or "gaining aura" (G).

Examples
Input
3 3
0 0
10 0
0 10
1 2
2 3
3 1
2
1 1
5 6
Output
PG
Input
9 9
1 0
1 2
4 2
4 0
3 1
5 0
7 0
8 2
6 2
1 2
2 3
3 4
4 5
5 1
6 7
7 8
8 9
9 7
4
0 1
2 1
5 1
7 1
Output
GPGP
Note

Explanation of Sample 2

This sample corresponds to the figure shown in the problem statement.