You are given an array of n integers a_1, a_2, …, 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 ≤ n,q ≤ 10^5) — the number of integers and the number of queries.

The next line contains n integers a_1, a_2, …, a_n (-10^5 ≤ a_i ≤ 10^5) — the numbers.

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

Output

Print n integers c_1, c_2, …, c_n representing the array after all operations.

Examples

Input


11 3
-5 -4 -3 -2 -1 0 1 2 3 4 5
&gt; 2
&gt; -4
&lt; 5


Output


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


Input


5 5
0 1 -2 -1 2
&lt; -2
&lt; -1
&lt; 0
&lt; 1
&lt; 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] 
import java.util.*;
import java.io.*;

public class HotIsCold {
    static int[] ans;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        int Q = scanner.nextInt();
        Pair[] vals = new Pair[N];
        ans = new int[N];
        for(int i = 0; i < N; i++) vals[i] = new Pair(scanner.nextInt(), i);
        Arrays.sort(vals);
        SegTree sg = new SegTree(N, 0, N-1, vals);
        while(Q-->0) {
            String qry = scanner.next();
            int x = scanner.nextInt();
            if (qry.equals(">")) sg.increment(1, x, 1);
            else sg.increment(1, x , -1);
//            for(int i = 0; i < N; i++) {
//                sg.query(1, i);
//            }
//            print(out, N);
        }
        for(int i = 0; i < N; i++) sg.query(1, i);
        print(out, N);
        out.flush();
    }
    
    public static void print(PrintWriter out, int N) {
        for(int i = 0; i < N; i++) {
            if (i > 0) out.print(" ");
            out.print(ans[i]);
        }
        out.println();
    }
    
    public static class SegTree {
        int sz;
        int[] hi;
        int[] lo;
        int[] orig;
        int[] max;
        int[] min;
        int[] delta;
        public SegTree(int ss, int l, int r, Pair[] vals) {
            sz = ss;
            hi = new int[ss*4+1];
            lo = new int[ss*4+1];
            orig = new int[ss*4+1];
            max = new int[ss*4+1];
            min = new int[ss*4+1];
            delta = new int[ss*4+1];
            Arrays.fill(delta, 1);
            init(1, l, r, vals);
        }
        public void init(int cur, int l, int r, Pair[] vals) {
            lo[cur] = l;
            hi[cur] = r;
            if (l == r) {
                orig[cur] = vals[l].b;
                max[cur] = vals[l].a;
                min[cur] = vals[l].a;
                return;
            }
            int mid = (l + r) /2;
            init(cur * 2, l, mid, vals);
            init(cur * 2 +1, mid + 1, r, vals);
            update(cur);
        }
        public void update(int cur) {
            max[cur] = Math.max(Math.max(delta[cur*2] * max[cur*2],
                    delta[cur*2] * min[cur*2]),Math.max(delta[cur*2+1] *max[cur*2+1],
                    delta[cur*2+1] * min[cur*2+1]));
            min[cur] = Math.min(Math.min(delta[cur*2] * max[cur*2],
                    delta[cur*2] * min[cur*2]),Math.min(delta[cur*2+1] *max[cur*2+1],
                    delta[cur*2+1] * min[cur*2+1]));
        }
        public void prop(int cur) {
            delta[cur*2] *= delta[cur];
            delta[cur*2+1] *= delta[cur];
            if (delta[cur] < 0) {
                int t = min[cur];
                min[cur] = -1 * max[cur];
                max[cur] = -1 * t;
            }
            delta[cur] = 1;
        }
        public void increment(int cur, int x, int q) {
            //no cover case
            int curMax = Math.max(delta[cur] * max[cur], delta[cur] * min[cur]);
            int curMin = Math.min(delta[cur] * min[cur], delta[cur] * max[cur]);
            //total cover
            if (q > 0 && x >= curMax || q < 0 && x <= curMin) return;
            if (q > 0 && x < curMin || q < 0 && x > curMax) {
                delta[cur] *= -1;
                return;
            }
            prop(cur);
//            System.out.println("LO: " + lo[cur] + ", HI: " + hi[cur]);
            increment(cur*2,x, q);
            increment(cur*2 + 1, x, q);
            update(cur);
        }
        public void query(int cur, int t) {
            if (t < lo[cur] || t > hi[cur]) return;
            if(t == lo[cur] && t == hi[cur]) {
                ans[orig[cur]] = delta[cur] * min[cur];
                return;
            }
            prop(cur);
            int mid = (lo[cur] + hi[cur]) /2;
            if (t <= mid) query(cur *2 , t);
            else query(cur*2 +1, t);
        }
    }
    
    public static class Pair implements Comparable<Pair>{
        int a,b;
        public Pair(int aa, int bb) {
            a = aa;
            b = bb;
        }
        public int compareTo(Pair o) {
            return Integer.compare(this.a, o.a);
        }
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}
