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: interview

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)

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]))