Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

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 ≤ N, Q ≤ 2 \cdot 10^{5}$
$|a_{i}| ≤ 10^{9}$ for each valid $i$
$a_{1}, a_{2}, \ldots, a_{N}$ are pairwise distinct
$|x_{i}| ≤ 10^{9}$ for each valid $i$

----- Sample Input 1 ------ 
4 6
1 3 5 100
-2
2
4
80
107
5
----- Sample Output 1 ------ 
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
0
----- explanation 1 ------ 
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 > 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 < 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 > 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.

Difficulty: MEDIUM
Tags: Square root algorithms

Matrices

Sorting

Complete search

Mathematics

Polynomials and generating functions
Skill types: Sorting

Complete search

Starter code:

Solutions:
def binary_search(s_l, c):
	low = 0
	high = len(s_l) - 1
	while low <= high:
		mid = (low + high) // 2
		if s_l[mid] == c:
			return -1
		elif s_l[mid] > c:
			high = mid - 1
		else:
			low = mid + 1
	return low
(a, b) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(b):
	c = int(input())
	a = binary_search(l, c)
	if a == -1:
		print(0)
	elif a > len(l):
		print('POSITIVE')
	elif (len(l) - a) % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
for q in range(k):
	x = int(input())
	inde = -2
	l = 0
	r = n - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			inde = 'found'
			break
		elif arr[mid] < x and (mid == n - 1 or arr[mid + 1] > x):
			inde = mid + 1
			break
		elif arr[mid] > x and mid == 0:
			inde = mid
			break
		elif arr[mid] > x:
			r = mid - 1
		else:
			l = mid + 1
	if inde == 'found':
		print(0)
	elif inde % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


(N, Q) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
arr = sorted(arr)
signs = [(-1) ** n for n in range(N + 1)]
if signs[-1] == -1:
	signs = [-1 * x for x in signs]
signs = ['POSITIVE' if x is 1 else 'NEGATIVE' for x in signs]
for _ in range(Q):
	x = int(input())
	mid = N // 2
	high = N - 1
	low = 0
	flag = -2
	while high - low >= 1 and mid >= 0 and (high <= N - 1) and (high >= 0) and (low >= 0) and (low <= N - 1):
		if high == low + 1 or high == low:
			break
		if arr[mid] < x and mid >= 1:
			low = mid + 1
		if arr[mid] > x and mid < N - 1:
			high = mid - 1
		if arr[mid] == x:
			flag = 1
			break
		mid = (high + low) // 2
	if flag == 1:
		print(0)
	else:
		if x > arr[low] and x < arr[high] and (high != N - 1):
			print(signs[high])
		if x > arr[low] and x > arr[high] and (high < N - 1):
			print(signs[high + 1])
		if x > arr[high] and high == N - 1:
			print(signs[N])
		if x < arr[low] and x < arr[high]:
			print(signs[low])
		if x == arr[low] or x == arr[high]:
			print(0)


def b(arr, x):
	l = 0
	r = len(arr)
	while l <= r:
		m = (l + r) // 2
		if arr[m] == x:
			return -1
		elif x > arr[m]:
			l = m + 1
		else:
			r = m - 1
		if l == len(arr):
			return l
	return l
(n, q) = map(int, input().split(' '))
ar = [int(x) for x in input().split(' ')]
ar = sorted(ar)
for i in range(q):
	a = b(ar, int(input()))
	if a == -1:
		print(0)
	else:
		print('POSITIVE' if a % 2 == 0 else 'NEGATIVE')


def bs(a, x):
	l = 0
	r = len(a)
	while l <= r:
		m = (l + r) // 2
		if a[m] == x:
			return -1
		elif a[m] < x:
			l = m + 1
		else:
			r = m - 1
		if l == len(a):
			return l
	return l
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(k):
	x = int(input())
	c = bs(a, x)
	if c == -1:
		print(0)
	elif c % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


import bisect
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(q):
	x = int(input())
	c = bisect.bisect_left(l, x)
	if c < n:
		p = n - c
		if l[c] == x:
			print(0)
		elif p % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')
	else:
		print('POSITIVE')


def greater(l, k):
	n = len(l)
	low = 0
	high = n - 1
	while low < high:
		m = (low + high) // 2
		if l[m] >= k:
			high = m
		elif l[m] < k:
			low = m + 1
	return low
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
while q > 0:
	a = int(input())
	b = greater(l, a)
	if l[b] == a:
		print('0')
	elif a > l[-1] or b & 1 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')
	q = q - 1


def find(arr, x):
	(low, high) = (0, len(arr) - 1)
	while low < high:
		mid = (low + high) // 2
		if arr[mid] >= x:
			high = mid
		elif arr[mid] < x:
			low = mid + 1
	return low
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(m):
	x = int(input())
	temp = find(l, x)
	if l[temp] == x:
		print('0')
	elif x > l[-1] or temp % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


def wave(x, a):
	(p, q) = (0, n - 1)
	while p <= q:
		avg = (p + q) // 2
		if a[avg] < x:
			p = avg + 1
		else:
			q = avg - 1
	return p
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(q):
	x = int(input())
	res = wave(x, a)
	if res >= n:
		print('POSITIVE')
	elif x == a[res]:
		print('0')
	elif n - res & 1:
		print('NEGATIVE')
	else:
		print('POSITIVE')


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(q):
	x = int(input())
	s = d = f = 0
	e = len(a) - 1
	mid = s + (e - s) // 2
	while s <= e:
		if a[mid] == x:
			print('0')
			f = 1
			break
		elif x > a[mid]:
			d = mid + 1
			s = mid + 1
		else:
			e = mid - 1
		mid = s + (e - s) // 2
	if f == 0:
		if (len(a) - d) % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')


(a, b) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(b):
	c = int(input())
	s = d = f = 0
	e = len(l) - 1
	mid = s + (e - s) // 2
	while s <= e:
		if l[mid] == c:
			print('0')
			f = 1
			break
		elif c > l[mid]:
			d = mid + 1
			s = mid + 1
		else:
			e = mid - 1
		mid = s + (e - s) // 2
	if f == 0:
		if (len(l) - d) % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')


import bisect
from bisect import bisect_left
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
l1 = []
for i in range(q):
	l1.append(int(input()))
for i in l1:
	p = bisect_left(l, i)
	if p < n and l[p] == i:
		print(0)
	elif p & 1 == 0:
		print('POSITIVE')
	elif p & 1 == 1:
		print('NEGATIVE')


import bisect
from bisect import bisect_left, bisect_right
(n, m) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
a.sort()
q = []
for _ in range(m):
	q.append(int(input()))
for p in q:
	pos = bisect_left(a, p)
	if pos < n and a[pos] == p:
		print('0')
	elif pos % 2 == 0:
		print('POSITIVE')
	elif pos % 2 != 0:
		print('NEGATIVE')


from bisect import bisect_right
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(q):
	d = int(input())
	p = bisect_right(a, d, 0, n)
	if a[p - 1] == d:
		print('0')
	elif p % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


import os, sys, io, math
from array import array
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import Counter, defaultdict
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
(n, k) = map(int, input().split())
l = I()
l.sort()
for i in range(k):
	(i, a) = (IN(), 0)
	p = bisect(l, i)
	if l[p - 1] == i:
		print(0)
	else:
		print('NEGATIVE' if n - p & 1 else 'POSITIVE')


from bisect import bisect
(n, m) = map(int, input().split())
L = list(map(int, input().split()))
L.sort()
for _ in range(m):
	q = int(input())
	pos = bisect(L, q)
	if L[pos - 1] == q:
		print(0)
	elif n - pos & 1 == 1:
		print('NEGATIVE')
	else:
		print('POSITIVE')


from bisect import bisect, insort
(nd, qd) = map(int, input().split())
ard = list(map(int, input().split()))
ard.sort()
for _ in range(qd):
	xd = int(input())
	kd = bisect(ard, xd)
	if ard[kd - 1] == xd:
		print(0)
	elif nd - kd & 1 == 1:
		print('NEGATIVE')
	else:
		print('POSITIVE')


from bisect import bisect, insort
(n, q) = map(int, input().split())
ar = list(map(int, input().split()))
ar.sort()
for _ in range(q):
	x = int(input())
	k = bisect(ar, x)
	if ar[k - 1] == x:
		print(0)
	elif n - k & 1 == 1:
		print('NEGATIVE')
	else:
		print('POSITIVE')


def binary_search(A, l, r, x):
	if abs(r - l) <= 1 and l > r:
		if A[l] <= x:
			return l
		else:
			return r
	if r >= l:
		mid = l + (r - l) // 2
		if x == A[mid]:
			return mid
		elif x < A[mid]:
			return binary_search(A, l, mid - 1, x)
		else:
			return binary_search(A, mid + 1, r, x)
(N, Q) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
for i in range(Q):
	x = int(input())
	if N == 1:
		if x == A[0]:
			print(0)
		elif x < A[0]:
			print('NEGATIVE')
			continue
		else:
			print('POSITIVE')
			continue
	if x < A[0]:
		if N % 2 == 0:
			print('POSITIVE')
			continue
		else:
			print('NEGATIVE')
			continue
	if x > A[N - 1]:
		print('POSITIVE')
		continue
	index = binary_search(A, 0, N - 1, x)
	if x - A[index] == 0:
		print(0)
	elif (N - index - 1) % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


def floor(l, x):
	ans = -1
	(low, high) = (0, len(l) - 1)
	while low <= high:
		mid = (low + high) // 2
		if l[mid] == x:
			return -2
		elif l[mid] > x:
			high = mid - 1
		else:
			ans = mid
			low = mid + 1
	return ans
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(q):
	x = int(input())
	f = floor(l, x)
	if f == -1:
		if n & 1:
			print('NEGATIVE')
		else:
			print('POSITIVE')
	elif f == -2:
		print(0)
	elif n - f + 1 & 1:
		print('NEGATIVE')
	else:
		print('POSITIVE')


(n, q) = map(int, input().split())
input_arr = list(map(int, input().split()))
input_arr.sort()

def search_num(num):
	start = 0
	end = n - 1
	while start <= end:
		middle = (start + end) // 2
		if input_arr[middle] < num:
			start = middle + 1
		else:
			end = middle - 1
	return start
for i in range(q):
	num = int(input())
	neg_count = 0
	index = search_num(num)
	if index >= n:
		print('POSITIVE')
	elif num == input_arr[index]:
		print('0')
	elif n - index & 1:
		print('NEGATIVE')
	else:
		print('POSITIVE')


(n, q) = map(int, input().split())
input_arr = list(map(int, input().split()))
pos_arr = []
neg_arr = []
for j in input_arr:
	if j < 0:
		neg_arr.append(j)
	else:
		pos_arr.append(j)
neg_arr_len = len(neg_arr)
pos_arr_len = len(pos_arr)
neg_arr.sort()
pos_arr.sort()

def search_num(num):
	if num < 0:
		arr = neg_arr
	else:
		arr = pos_arr
	start = 0
	end = len(arr) - 1
	while start <= end:
		middle = (start + end) // 2
		if arr[middle] == num or (arr[middle] > num and arr[middle - 1] < num):
			return [middle, arr[middle]]
		elif arr[middle] < num:
			start = middle + 1
		else:
			end = middle - 1
for i in range(q):
	num = int(input())
	return_num = 10 ** 9 + 7
	neg_count = 0
	if num < 0:
		if neg_arr_len > 0:
			if num < neg_arr[0]:
				neg_count = neg_arr_len
			elif neg_arr[0] <= num <= neg_arr[-1]:
				(neg_start, return_num) = search_num(num)
				neg_count = neg_arr_len - neg_start
		neg_count += pos_arr_len
	elif pos_arr_len > 0:
		if num < pos_arr[0]:
			neg_count = pos_arr_len
		elif pos_arr[0] <= num <= pos_arr[-1]:
			(neg_start, return_num) = search_num(num)
			neg_count = pos_arr_len - neg_start
	if num == return_num:
		print('0')
	elif neg_count & 1:
		print('NEGATIVE')
	else:
		print('POSITIVE')


def search(arr, x):
	high = len(arr)
	low = 0
	while low < high:
		mid = (low + high) // 2
		if x > arr[mid]:
			low = mid + 1
		else:
			high = mid
	return low
(n, q) = map(int, input().split(' '))
roots = sorted(map(int, input().split(' ')))
queries = [int(input()) for _ in range(q)]
for q in queries:
	i = search(roots, q)
	if i >= len(roots):
		print('POSITIVE')
	elif q == roots[i]:
		print(0)
	elif (len(roots) - i) % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


import bisect
(n, q) = map(int, input().split())
poly = list(map(int, input().split()[:n]))
poly.sort()
for i in range(q):
	n1 = int(input())
	bisector = bisect.bisect_left(poly, n1)
	if bisector < n:
		k = n - bisector
		if poly[bisector] == n1:
			print(0)
		elif k % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')
	else:
		print('POSITIVE')


def bisect(roots, n, x):
	l = 0
	r = n - 1
	while r >= l:
		m = (l + r) // 2
		if x == roots[m]:
			return -2
			break
		elif x > roots[m]:
			l = m + 1
		else:
			r = m - 1
	return l
(n, q) = map(int, input().split())
roots = list(map(int, input().split()))
roots.sort()
for _ in range(q):
	x = int(input())
	if x < roots[0]:
		print('POSITIVE')
	elif x > roots[-1]:
		if n % 2 == 1:
			print('NEGATIVE')
		else:
			print('POSITIVE')
	else:
		l = bisect(roots, n, x)
		if l == -2:
			print(0)
		elif l % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')


(N, Q) = (int(x) for x in input().split(' '))
a = [int(x) for x in input().split(' ')]
a.sort()
for t in range(Q):
	flag = 1
	q = int(input())
	i = 0
	j = N - 1
	while j > i:
		mid = (i + j) // 2
		if a[mid] == q:
			print('0')
			flag = 0
			break
		elif a[mid] > q:
			j = mid - 1
		else:
			i = mid + 1
	if flag == 1:
		if a[i] == q:
			print('0')
		elif a[i] < q:
			if (N - i - 1) % 2 == 0:
				print('POSITIVE')
			else:
				print('NEGATIVE')
		elif (N - i) % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')


import sys
from bisect import bisect
[n, q] = list(map(lambda x: int(x), sys.stdin.readline().rstrip('\n').split(' ')))
ais = list(map(lambda x: int(x), sys.stdin.readline().rstrip('\n').split(' ')))
ais.sort()
for _ in range(q):
	xi = int(sys.stdin.readline().rstrip('\n'))
	b = bisect(ais, xi)
	if ais[b - 1] == xi:
		print('0')
	elif (len(ais) - b) % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


def find_index(arr, n, K):
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] == K:
			return mid
		elif arr[mid] < K:
			start = mid + 1
		else:
			end = mid - 1
	return end + 1
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(0, q):
	q1 = int(input())
	ind = find_index(a, n, q1)
	if ind != n and a[ind] == q1:
		print(0)
	elif n % 2 == 0:
		if ind % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')
	elif ind % 2 == 0:
		print('NEGATIVE')
	else:
		print('POSITIVE')


import bisect
(n, q) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
mini = min(arr)
maxi = max(arr)
arr.sort()
for i in range(q):
	pin = int(input())
	bisector = bisect.bisect_left(arr, pin)
	if bisector < n:
		k = n - bisector
		if arr[bisector] == pin:
			print(0)
		elif k % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')
	else:
		print('POSITIVE')


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(10000000.0) + 9
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr, start: enumerate(itr, start)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def seive(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = is_prime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if is_prime[i]:
			for j in range(i * i, n + 1, i):
				is_prime[j] = False
	return is_prime[n]

def get_negatives(arr, val):
	(l, r) = (0, len(arr) - 1)
	res = -1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] - val == 0:
			return -1
		if val - arr[mid] < 0:
			res = mid
			r -= 1
		else:
			l += 1
	return len(arr) - l

def solve(*args, **kwargs):
	(n, q, arr1, arr2) = args
	arr1.sort()
	res = []
	for val in arr2:
		positives = bisect_left(arr1, val)
		negatives = n - positives
		if positives < n:
			if arr1[positives] == val:
				res.append('0')
			elif negatives & 1:
				res.append('NEGATIVE')
			else:
				res.append('POSITIVE')
		else:
			res.append('POSITIVE')
	return res

def main(*args, **kwargs):
	arg1 = inp_vars(int, SPACE)
	arg3 = inp_vars(int, SPACE)
	arg4 = [inp(int) for _ in range(arg1[1])]
	res = solve(*(*arg1, arg3, arg4))
	if type(res) in {list, tuple, set}:
		print(*res, sep='\n')
	else:
		print(res)
main()


import bisect
(N, Q) = map(int, input().split())
Ni = sorted(list(map(int, input().split())))
for _ in range(Q):
	X = int(input())
	g = bisect.bisect_left(Ni, X)
	if g < N:
		k = N - g
		if Ni[g] == X:
			print(0)
		elif k % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')
	else:
		print('POSITIVE')


import bisect
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
m1 = min(a)
m2 = max(a)
a.sort()
for i in range(q):
	p = int(input())
	g = bisect.bisect_left(a, p)
	if g < n:
		k = n - g
		if a[g] == p:
			print(0)
		elif k % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')
	else:
		print('POSITIVE')


import bisect
(N, Q) = map(int, input().split(' '))
factors = list(map(int, input().split(' ')))
factors.sort()
for i in range(Q):
	x = int(input())
	idx = bisect.bisect_left(factors, x)
	if idx == N:
		print('POSITIVE')
	elif factors[idx] == x:
		print(0)
	else:
		(l, r) = (idx, N - idx)
		if r % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')


class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
(n, q) = map(int, input().split())
roots = list(map(int, input().split()))
roots = SortedList(roots)
for i in range(q):
	negative_count = 0
	point = int(input())
	if point in roots:
		print(0)
	elif roots.bisect_right(point) % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')


import bisect
(N, Q) = input().split()
roots = [int(x) for x in input().split()]
roots.sort()
N = int(N)
Q = int(Q)
for _ in range(Q):
	ip = int(input())
	idx = bisect.bisect_left(roots, ip)
	if idx == N:
		print('POSITIVE')
	elif roots[idx] == ip:
		print(0)
	else:
		(l, r) = (idx, N - idx)
		if r % 2 == 0:
			print('POSITIVE')
		else:
			print('NEGATIVE')


def search(a, v):
	hi = len(a)
	lo = 0
	while lo < hi:
		mid = (lo + hi) // 2
		if v > a[mid]:
			lo = mid + 1
		else:
			hi = mid
	return lo
(n, q) = map(int, input().split(' '))
roots = sorted(map(int, input().split(' ')))
queries = [int(input()) for _ in range(q)]
for q in queries:
	i = search(roots, q)
	if i >= len(roots):
		print('POSITIVE')
	elif q == roots[i]:
		print(0)
	elif (len(roots) - i) % 2 == 0:
		print('POSITIVE')
	else:
		print('NEGATIVE')