You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$.

You will perform $q$ operations. In the $i$-th operation, you have a symbol $s_i$ which is either "<" or ">" and a number $x_i$.

You make a new array $b$ such that $b_j = -a_j$ if $a_j s_i x_i$ and $b_j = a_j$ otherwise (i.e. if $s_i$ is '>', then all $a_j > x_i$ will be flipped). After doing all these replacements, $a$ is set to be $b$.

You want to know what your final array looks like after all operations.


-----Input-----

The first line contains two integers $n,q$ ($1 \leq n,q \leq 10^5$) — the number of integers and the number of queries.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^5 \leq a_i \leq 10^5$) — the numbers.

Each of the next $q$ lines contains a character and an integer $s_i, x_i$. ($s_i \in \{<, >\}, -10^5 \leq x_i \leq 10^5$) – the queries.


-----Output-----

Print $n$ integers $c_1, c_2, \ldots, c_n$ representing the array after all operations.


-----Examples-----
Input
11 3
-5 -4 -3 -2 -1 0 1 2 3 4 5
> 2
> -4
< 5

Output
5 4 -3 -2 -1 0 1 2 -3 4 5

Input
5 5
0 1 -2 -1 2
< -2
< -1
< 0
< 1
< 2

Output
0 -1 2 -1 2



-----Note-----

In the first example, the array goes through the following changes:   Initial: $[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]$  $> 2$: $[-5, -4, -3, -2, -1, 0, 1, 2, -3, -4, -5]$  $> -4$: $[-5, -4, 3, 2, 1, 0, -1, -2, 3, -4, -5]$  $< 5$: $[5, 4, -3, -2, -1, 0, 1, 2, -3, 4, 5]$

Difficulty: VERY_HARD
Tags: Bit manipulation

Data structures

Implementation

Divide and conquer
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
import sys
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
Sign = [0] * (3 + 10 ** 5)
SX = [tuple(sys.stdin.readline().split()) for _ in range(Q)]
mini = 3 + 10 ** 5
Sign = [0] * (3 + 10 ** 5)
keep = 1
for (s, x) in SX[::-1]:
	x = int(x)
	ax = abs(x) + int((s == '>') ^ (x < 0))
	sin = 1 if s == '<' else -1
	if mini > ax:
		t = sin * keep
		for i in range(mini - 1, ax - 1, -1):
			Sign[i] = t
		mini = ax
	keep *= (2 * (s == '>') - 1) * (2 * (0 < x) - 1)
Ans = [None] * N
for (i, a) in enumerate(A):
	s = Sign[abs(a)]
	if s == 0:
		s = (2 * (a > 0) - 1) * keep
	Ans[i] = s * abs(a)
print(*Ans)


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
swaps = [0] * q
for i in range(q):
	b = input().split()
	b[1] = int(b[1])
	out = 1 if b[0] == '<' and b[1] <= 0 or (b[0] == '>' and b[1] >= 0) else 0
	split = b[1] + 0.5 if b[0] == '>' else b[1] - 0.5
	sign = 1 if split > 0 else -1
	split = abs(split)
	swaps[i] = (split, sign, out)
sml = 10 ** 5 + 0.5
zeros = 0
for i in range(q):
	sml = min(swaps[i][0], sml)
	zeros += 1 - swaps[i][2]
zeros %= 2
arr = [0] * 100001
big = 100000.5
flips = 1
for i in range(q):
	if swaps[-1 - i][0] < big:
		if swaps[-1 - i][2] == 1:
			for j in range(int(swaps[-1 - i][0] + 0.5), int(big + 0.5)):
				arr[j] = -swaps[-i - 1][1] * flips
		else:
			for j in range(int(swaps[-1 - i][0] + 0.5), int(big + 0.5)):
				arr[j] = swaps[-i - 1][1] * flips
		big = swaps[-1 - i][0]
	if swaps[-1 - i][2] == 0:
		flips = -flips

def func(k):
	if abs(k) < sml:
		return k if zeros == 0 else -k
	else:
		return arr[abs(k)] * abs(k)
print(' '.join([str(func(guy)) for guy in a]))