本文共 2615 字，大约阅读时间需要 8 分钟。

There is a country with n citizens. The i-th of them initially has ai 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⋅105) — the numer of citizens.

The next line contains n integers a1, a2, …, an (0≤ai≤109) — the initial balances of citizens.

The next line contains a single integer q (1≤q≤2⋅105) — 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≤109), or 2 x (0≤x≤109). 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

两种操作，一种就是单点更新，另一种就是将1~n之间权值小于x的更新为x。 第一种就是普通的线段树就能做到的。 主要是第二种操作，我一开始是随时更新到叶子节点，结果第五个就TLE了。 那么只能是延迟更新，维护一个最小值，如果最小值大于要更新成的x，就直接返回不更新。否则就将lazy标记为x，在update和Query里面去不断的往下推，去更新节点的值。pushdown函数里面要注意条件。嘤嘤嘤 代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;const int maxx=2e5+100;struct node{	int l;	int r;	int v;	int lazy;	int _min;}p[maxx<<2];int a[maxx];int n;inline void pushup(int cur){	p[cur]._min=min(p[cur<<1]._min,p[cur<<1|1]._min);}inline void pushdown(int cur){	//cout<
       
        <
        
         >1; build(l,mid,cur<<1); build(mid+1,r,cur<<1|1); pushup(cur);}inline void update(int x,int add,int cur){ int L=p[cur].l; int R=p[cur].r; if(L==R) { p[cur]._min=p[cur].v=add; return ; } pushdown(cur); int mid=L+R>>1; if(x<=mid) update(x,add,cur<<1); else update(x,add,cur<<1|1); pushup(cur);}inline void Update(int cur,int x){ if(p[cur]._min>=x) return ; if(p[cur]._min
        
       
      
     
    
   

努力加油a啊，(^o)/~

转载地址：http://nfxvi.baihongyu.com/