Wstęp do programowania w C++

Lewa, prawa

Miało nie być już o bieganiu, ale będzie. Jasiu długie wybiegania trenuje na ścieżkach leśnych w taki sposób, że startuje z pewnego ustalonego punktu i biegnąc zakreśla ślad będący wielokątem, kończąc w punkcie startu. Biegając w ten sposób jedna jego ręka będzie poruszać się wewnątrz wielokąta, druga zaś poza wielokątem. Powstaje pytanie, która ręka będzie zawierać się wewnątrz wielokąta? To trzeba rozstrzygnąć na podstawie danych współrzędnych geograficznych będących kolejnymi wierzchołkami wielokąta. Punkt startu jest punktem końca treningu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. Pierwszy wiersz każdego zestawu zawiera liczbę całkowitą n (3 ≤ n ≤ 1000) oznaczająca liczbę wierzchołków wielokąta. W kolejnych n wierszach podane są po dwie całkowite współrzędne x, y (-10³ ≤ x,y ≤ 10³) oznaczające koordynaty kolejnych wierzchołków. Żadne trzy kolejne punkty nie są współliniowe.

Wyjście
Dla każdego zestawu danych wypisz słowo LEWA, jeśli to lewa ręka będzie zawierać się w wielokącie, albo słowo PRAWA, gdy podczas biegu prawa ręka będzie zawierać się we wnętrzu wielokąta.

Przykład

Wejście
2
3
0 0
5 0
0 5
4
1 1
1 5
5 5
5 1

Wyjście
LEWA
PRAWA