Description

鸡尾酒有一个奇怪的函数 $F(x)$，这个函数的输入参数是一个正整数 $x$，为了得到这个函数的运算结果，这个函数需要依次进行 $n$ 个步骤，每个步骤是如下三种形式之一：

1. $x+=val_i$
2. $x=min(x,val_i)$
3. $x=max(x,val_i)$

依次执行完这 $n$ 个步骤之后，这个函数就可以安心输出答案了。

现在，鸡尾酒得到了这个函数，他想简化这个函数，确切的来说，他有 $q$个问题，每个问题要么是修改这个函数的某一个步骤，要么给定一个$x$，询问当前 $F(x)$ 的值，请帮助他完成这个过程。

Format

Input

第一行一个正整数 $n$，表示这个函数的步骤数量。

接下来 $n$ 行，每行两个正整数"opt val"，$opt(1\leq opt \leq3)$表示这是第几种操作，$val$ 表示这一次操作对应的权值。

接下来一行一个正整数 $q$，表示问题的个数。

接下来 $q$ 行，每行要么是如下四种操作之一：

"1 pos val" 表示把第 $pos$ 个步骤改成 $x+=val_i$。

"2 pos val" 表示把第 $pos$ 个步骤改成$x=min(x,val)$。

"3 pos val" 表示把第 $pos$个步骤改成$x=max(x,val)$。

"4 x" 表示询问，此时 $F(x)$ 是多少。

Output

对于每一个操作 4，输出一行一个数字表示答案。

Samples

10
1 48
1 50
1 180
2 957
1 103
1 100
1 123
3 500
1 66
1 70
3
4 20
4 50
4 700

760
790
1419

Limitation

对于 100% 的数据：$n,q\leq 300000$，操作 2,3,4 涉及的 $val$在$[1,10^8]$之间，所有加法操作涉及的 $val$ 在 $[1,200]$之间。

特殊性质1：保证所有的 $q$个操作都是操作 $4$。

特殊性质2：保证任意时刻，操作序列中最多有 $10$个取 ax$，$min$的操作。

特殊性质3：保证任意时刻，操作序列中不存在取$max$的操作。