There is a country with n citizens. The i-th of them initially has a_{i} money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social services mentioning the amount of money they currently have.

Sometimes the government makes payouts to the poor: all citizens who have strictly less money than x are paid accordingly so that after the payout they have exactly x money. In this case the citizens don't send a receipt.

You know the initial wealth of every citizen and the log of all events: receipts and payouts. Restore the amount of money each citizen has after all events.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^{5}) — the numer of citizens.

The next line contains n integers a_1, a_2, ..., a_n (0 ≤ a_{i} ≤ 10^{9}) — the initial balances of citizens.

The next line contains a single integer q (1 ≤ q ≤ 2 ⋅ 10^{5}) — the number of events.

Each of the next q lines contains a single event. The events are given in chronological order.

Each event is described as either 1 p x (1 ≤ p ≤ n, 0 ≤ x ≤ 10^{9}), or 2 x (0 ≤ x ≤ 10^{9}). In the first case we have a receipt that the balance of the p-th person becomes equal to x. In the second case we have a payoff with parameter x.

Output

Print n integers — the balances of all citizens after all events.

Examples

Input


4
1 2 3 4
3
2 3
1 2 2
2 1


Output


3 2 3 4 


Input


5
3 50 2 1 10
3
1 2 0
2 8
1 3 20


Output


8 8 20 8 10 

Note

In the first example the balances change as follows: 1 2 3 4 → 3 3 3 4 → 3 2 3 4 → 3 2 3 4

In the second example the balances change as follows: 3 50 2 1 10 → 3 0 2 1 10 → 8 8 8 8 10 → 8 8 20 8 10
import java.util.*;
import java.io.*;
public class A{
    static PrintWriter out;
    static InputReader in;
    public static void main(String args[]){
        out = new PrintWriter(System.out);
        in = new InputReader();
        new A();
        out.flush(); out.close();
    }   
    class pair{
        int F, S, T;
        pair(int a, int b, int c){
            F = a; S = b; T = c;
        }
    }
    int n;
    ArrayList<pair> al = new ArrayList<>();
    A(){
        n = in.nextInt();
        int a[] = new int[n + 1];
        for(int i = 1; i <= n; i++)a[i] = in.nextInt();
        int q = in.nextInt();
        for(int i = 0; i < q; i++){
            int t = in.nextInt(), p = -1, x = -1;
            if(t == 1){
                p = in.nextInt(); x = in.nextInt();
            }else{
                x = in.nextInt();
            }
            al.add(new pair(t, p, x));
        }
        boolean mark[] = new boolean[n + 1];
        int max = 0;
        for(int i = q - 1; i >= 0; i--){
            pair p = al.get(i);
            if(p.F == 1){
                if(!mark[p.S]){
                    a[p.S] = Math.max(p.T, max);
                    mark[p.S] = true;
                }
            }else{
                max = Math.max(max, p.T);
            }
        }
        for(int i = 1; i <= n; i++){
            if(!mark[i]){
                a[i] = Math.max(a[i], max);
            }
        }
        for(int i = 1; i <= n; i++){
            out.print(a[i] + " ");
        }
        // solve();
    }
    void solve(){
        int n = in.nextInt(), k = in.nextInt();
        int d = 1;
        for(int i = 0; ; i++, d *= 2){
            if(n * i > 8 * k){
                d /= 2; break;
            }
            if(d >= n) break;
        }   
        ArrayList<Integer> al = new ArrayList<>();
        for(int i = 0; i < n; i++){
            al.add(in.nextInt());
        }
        Collections.sort(al);
        ArrayList<Integer> u = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(u.size() != 0 && u.get(u.size() - 1) == al.get(i))continue;
            u.add(al.get(i));
        }
        int sz = u.size();
        if(sz <= d){
            out.print(0); return;
        }
        int f[] = new int[sz + 10], b[] = new int[sz + 10];
        int s = 0;
        for(int i = 0; i < sz; i++){
            for(int j = s; j < n; j++){
                if(al.get(j) != u.get(i)){
                    s = j; break;
                }
                f[i + 1]++; b[i + 1]++;
            }
        }
        for(int i = sz - 1; i >= 1; i--)f[i] += f[i + 1];
        for(int i = 2; i <= sz; i++)b[i] += b[i - 1];
        int ans = n;
        for(int i = 1; i <= sz - d + 1; i++){
            ans = Math.min(ans, b[i - 1] + f[i + d]);
        }
        out.print(ans);
    }
    public static class InputReader{
        BufferedReader br;
        StringTokenizer st;
        InputReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public long nextLong(){
            return Long.parseLong(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
        public String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){}
            }
            return st.nextToken();
        }
    }
}
        