Hot is Cold

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

Solution:

#include <bits/stdc++.h>

using namespace std;

class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
// not necessarily neutral element!
int flip = 0;
int put = -1;
int value = 0;

void apply(int l, int r, int v) {
if (v == -1) {
flip ^= 1;
value ^= 1;
} else {
put = v;
flip = 0;
value = v;
}
}
};

node unite(const node &a, const node &b) const {
node res;
res.value = -1;
return res;
}

inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    // push from x into (x + 1) and z
    if (tree[x].put != -1) {
      tree[x + 1].apply(l, y, tree[x].put);
      tree[z].apply(y + 1, r, tree[x].put);
      tree[x].put = -1;
    }
    if (tree[x].flip != 0) {
      tree[x + 1].apply(l, y, -1);
      tree[z].apply(y + 1, r, -1);
      tree[x].flip = 0;
    }
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}

template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}

int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}

int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}

template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}

node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, tt;
  cin >> n >> tt;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
const int SHIFT = 100010;
const int MAX = 2 * SHIFT + 1;
segtree st(MAX);
while (tt--) {
char foo;
int bar;
cin >> foo >> bar;
if (foo == '<') {
      if (bar <= 0) {
        st.modify(0, (bar - 1) + SHIFT, 1);
        st.modify(-(bar - 1) + SHIFT, MAX - 1, 0);
      } else {
        st.modify(0, -bar + SHIFT, 1);
        st.modify(bar + SHIFT, MAX - 1, 0);
        st.modify(-(bar - 1) + SHIFT, (bar - 1) + SHIFT, -1);
      }
    } else {
      if (bar >= 0) {
st.modify(0, -(bar + 1) + SHIFT, 0);
st.modify((bar + 1) + SHIFT, MAX - 1, 1);
} else {
st.modify(0, bar + SHIFT, 0);
st.modify(-bar + SHIFT, MAX - 1, 1);
st.modify((bar + 1) + SHIFT, -(bar + 1) + SHIFT, -1);
}
}
}
for (int i = 0; i < n; i++) {
    if (i > 0) {
cout << " ";
    }
    int v = st.get(a[i] + SHIFT).value;
    cout << (v == 0 ? a[i] : -a[i]);
  }
  cout << '\n';
  return 0;
}