005 - カードの取り合い (Contingent of Cards)

問題

JOI君とIOIちゃんがカードの取り合いをします。 最初、JOI君は X 枚のカードを持っていて、IOIちゃんは Y 枚のカードを持っています。 カードの取り合いは、以下の操作を、JOI君、IOIちゃん、JOI君・・・と交互に繰り返していくことで進みます。 操作は合計で N 回行われます。 i 回目の操作では、相手の持っているカードを A_i 枚取って、自分のカードにします。 なお、その時相手が持っているカードの枚数が A_i 枚に満たない場合は、相手が持っているカードをすべて取って自分のものにします。

これから Q 回、X ,Y ,A_i いずれかの値が変化するというクエリが与えられます。 i 回目のクエリでは、 T_i=1 の時、X が V_i になり、 T_i=2 の時、Y が V_i なり、 T_i=3 の時、A_Si が V_i になります。 クエリによって変化したものは、次以降のクエリにも引き継がれます。

それぞれのクエリの直後において、JOIくんとIOIちゃんがカードの取り合いをした際に、最終的にJOI君が何枚のカードを持っているかを求めるプログラムを作成してください。

入力

N
X Y
A1 A2 ... AN
Q
T1 ...
T2 ...
:
TN ...

最初の一行には整数 N が与えられる。

続く行には整数 X ,Y が与えられる。

続く行には整数 A₁ ,A₂ ... A_N が与えられる。

続く行には整数 Q が与えられる。

続く Q 行にはクエリの情報が与えられる。

i 行目には、まず整数 T_i が与えられる。

T_i=1 ,2 の場合、同じ行に整数 V_i が続く。

T_i=3 の場合、同じ行に整数 S_i ,V_i が続く。

出力

それぞれのクエリの直後において、JOIくんとIOIちゃんがカードの取り合いをした際に、 最終的にJOI君が何枚のカードを持っているかを出力してください。

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ N ≦ 10⁵
• 1 ≦ X ,Y ≦ 10⁹
• 1 ≦ A_i ≦ 10⁹
• 1 ≦ Q ≦ 10⁵
• 1 ≦ T_i ≦ 3
• 1 ≦ S_i ≦ N
• 1 ≦ V_i ≦ 10⁹

小課題

小課題1[5点]

以下の条件を満たす。

• 1 ≦ N ≦ 1000
• 1 ≦ Q ≦ 1000

小課題2[15点]

以下の条件を満たす。

• T_i = 3

小課題3[20点]

以下の条件を満たす。

• T_i = 1 ,2

小課題4[60点]

追加の制約はない。

---

入出力例

入力例1

3
5 4
2 1 4
3
2 7
3 2 3
2 2

出力例1

10
8
7

解説

例えば、3 回目のクエリの直後にカードの取り合いを行うと、JOI君とIOIちゃんの持っているカードの枚数は以下のように変化する。

最初、二人の持っているカードの枚数は、(5,2) である。

次に、JOI君がカードを 2 枚取り、(7,0) になる。

次に、IOIちゃんがカードを 3 枚取り、(4,3) になる。

次に、JOI君がカードを 4 枚取ろうとするが、 IOIちゃんは 3 枚しかカードを持っていないので、3 枚取り、(7,0) になる。

入力例2

5
11 21
10 5 12 1 13
5
3 3 1
2 8
2 17
3 4 10
3 4 25

出力例2

29
19
28
20
13

入力例3

5
11 4
13 6 7 3 5
4
3 4 10
3 2 11
3 4 18
3 3 2

出力例3

10
6
5
5

解説

このケースは小課題2の制約を満たします。

入力例4

4
4 18
2 9 19 6
5
1 7
2 8
1 1
2 4
1 9

出力例4

13
9
3
0
7

解説

このケースは小課題3の制約を満たします。