# Polynomial Waves Challenge

Hard
4.3% Acceptance

Explore polynomial puzzles in the realm of Codedamn! You're given all $N$ distinct integer roots of a polynomial $P(x) = \prod_{i=1}^N (x - a_i)$, arranged in no specific order.

Dive into solving $Q$ challenges, where for each challenge $i$, an integer $x_i$ is presented. Your task is to figure out if $P(x_i)$ is positive, negative, or $0$.

### Input

• Begin with a line containing two integers separated by a space, $N$ and $Q$.
• The following line has $N$ integers separated by spaces, $a_1, a_2, \ldots, a_N$.
• Then, $Q$ lines come next. Each line, for a valid $i$, contains a single integer $x_i$, representing the $i$-th challenge.

### Output

For every challenge, output a line with either "POSITIVE", "NEGATIVE", or "0", which reflects the value of the polynomial for that challenge.

### Constraints

• $1 \le N, Q \le 2 \cdot 10^5$
• $|a_i| \le 10^9$ for each valid $i$
• $a_1, a_2, \ldots, a_N$ are distinct
• $|x_i| \le 10^9$ for each valid $i$

### Sample Test Cases

#### Case #1:

Input:

4 6
1 3 5 100
-2
2
4
80
107
5

Output:

POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
0

#### Explanation

For the polynomial $(x-1)\cdot (x-3)\cdot (x-5)\cdot (x-100)$:

• Query $1$: $x = -2$ results in $P(-2) = (-2-1)\cdot (-2-3)\cdot (-2-5)\cdot (-2-100) = (-3)\cdot (-5)\cdot (-7)\cdot (-102) > 0$, hence POSITIVE.
• Query $2$: $x = 2$ leads to $P(2) = (2-1)\cdot (2-3)\cdot (2-5)\cdot (2-100) = (1)\cdot (-1)\cdot (-3)\cdot (-98) < 0$, so it's NEGATIVE.
• Query $3$: For $x = 4$, we get $P(4) = (4-1)\cdot (4-3)\cdot (4-5)\cdot (4-100) = (3)\cdot (1)\cdot (-1)\cdot (-96) > 0, thus POSITIVE. • Query $6$: $x = 5$ makes$P(5) = (5-1)\cdot (5-3)\cdot (5-5)\cdot (5-100) = 0, leading to 0.