The Wave Solution

 Problem

Chef is stuck in the wavey world of polynomials. You are given all $N$ roots of a polynomial $P(x) = \prod_{i=1}^N (x - a_i)$. The roots are pairwise distinct integers, but they are not given in any particular order.

To help Chef escape, you should answer $Q$ queries (numbered $1$ through $Q$). For each valid $i$, in the $i$-th query, you are given an integer $x_i$ and you have to determine whether $P(x_i)$ is positive, negative or $0$.

Input

• The first line of the input contains two space-separated integers $N$ and $Q$.
• The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$.
• $Q$ lines follow. For each valid $i$, the $i$-th of these lines contains a single integer $x_i$ describing the $i$-th query.

Output

For each query, print a single line containing the string "POSITIVE", "NEGATIVE" or "0" (without quotes) describing the value of the polynomial for the $i$-th query.

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 pairwise distinct
• $|x_i| \le 10^9$ for each valid $i$

Sample 1:

Input

Output

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

POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
0

Explanation:

The given polynomial is $(x-1)\cdot (x-3)\cdot (x-5)\cdot (x-100)$.

Query $1$: $x = -2$. This means that $P(-2) = (-2-1)\cdot (-2-3)\cdot (-2-5)\cdot (-2-100) = (-3)\cdot (-5)\cdot (-7)\cdot (-102) = 10710 \gt 0$. Thus, the answer is POSITIVE.

Query $2$: $x = 2$. This means that $P(2) = (2-1)\cdot (2-3)\cdot (2-5)\cdot (2-100) = (1)\cdot (-1)\cdot (-3)\cdot (-98) = -294 \lt 0$. Thus, the answer is NEGATIVE.

Query $3$: $x = 4$. This means that $P(4) = (4-1)\cdot (4-3)\cdot (4-5)\cdot (4-100) = (3)\cdot (1)\cdot (-1)\cdot (-96) = 288 \gt 0$. Thus, the answer is POSITIVE.

Query $6$: $x = 5$. This means that $P(5) = (5-1)\cdot (5-3)\cdot (5-5)\cdot (5-100) = (4)\cdot (2)\cdot (0)\cdot (-95) = 0$. Thus, the answer is 0.

Program :

/* package codechef; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Codechef

{

public static void main (String[] args) throws java.lang.Exception

{

// your code goes here

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int q = sc.nextInt();

int[] a = new int[n];

for(int i=0;i<n;i++)

a[i] = sc.nextInt();

Arrays.sort(a);

while(q-->0)

{

    int x = sc.nextInt();

    int s =0;

    int e = n;

    while(s<e)

    {

        int m = (s+e)/2;

        if(x>a[m])

        s = m+1;

        else

        e = m;

    }

    int l = n-s;

    if(l==0)

    System.out.println("POSITIVE");

    else if(a[s]==x)

    System.out.println("0");

    else if(l%2!=0)

    System.out.println("NEGATIVE");

    else

    System.out.println("POSITIVE");

}

}

}