The Dragon and the Knights

The Dragon of the Wawel Castle, following the conflict with the local Shoemakers’ Guild, decided to move its hunting grounds out of Kraków, to a less hostile neighborhood. Now it is bringing havoc and terror to the peaceful and serene Kingdom of Bytes.

In the Kingdom of Bytes there are $n$ rivers and each of them flows along a straight line (that is, you may think of the Kingdom as the Euclidean plane divided by infinite lines). No three rivers have a common point. The rivers divide the Kingdom into some districts.

Fortunately, there are $m$ valiant knights in the Kingdom. Each of them has taken his post and swore an oath to protect his district. The Kingdom is thus protected for evermore... or is it?

It is known that Dragon will not attack a district which has at least one knight inside. The knights, however, are famous for their courage in battle, not for their intelligence. They may have forgotten to protect some of the districts.

Given a map of the Kingdom and the knights’ positions, determine whether all districts are protected.


The first line of the input contains the number of test cases $T$, where $1 \le T \le 100$. The descriptions of the test cases follow:

Each test case starts with a line containing the number of rivers $n$ ($1 \leq n \leq 100$) and the number of knights $m$ ($1 \leq m \leq 50\, 000$). Then follow $n$ lines describing rivers. The $j$-th of them contains three space-separated integers $A_ j,B_ j,C_ j$ of absolute values not exceeding $10\, 000$. These integers are the coefficients of the equation $A_ j \cdot x + B_ j \cdot y + C_ j = 0$ of the line along which the $j$-th river flows. After that, there are $m$ lines describing the positions of the knights: the $i$-th of these lines contains two integers $X_ i, Y_ i$ ($-10^9 \leq X_ i,Y_ i \leq 10^9$)—the coordinates of the $i$-th knight. You may assume that no knight is standing in a river (his shining armour would quickly rust if he did). Two knights may occupy the same post (their coordinates can be equal). No two rivers flow along the same line and no three rivers have a common point. The sum of $m$ over all $T$ test cases is at most $10^6$.


Print the answers to the test cases in the order in which they appear in the input. For each test case, output a single line containing a single word PROTECTED if all districts are safe from the Dragon, and VULNERABLE otherwise.

Sample Input 1 Sample Output 1
3 7
0 1 0
1 0 0
1 1 -3
1 1
5 -1
3 2
2 -2
-2 6
-1 -2
-8 4
1 1
0 1 0
0 1
CPU Time limit 6 seconds
Memory limit 1024 MB
Difficulty 4.3medium
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in