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

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 0 /


TLE
1sec
MLE
256MB
得点
100

問題

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

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

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

入力

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

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

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

続く行には整数 A1 ,A2 ... AN が与えられる。

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

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

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

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

Ti=3 の場合、同じ行に整数 Si ,Vi が続く。

出力

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

制約

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

  • 1 ≦ N ≦ 105
  • 1 ≦ X ,Y ≦ 109
  • 1 ≦ Ai ≦ 109
  • 1 ≦ Q ≦ 105
  • 1 ≦ Ti ≦ 3
  • 1 ≦ Si ≦ N
  • 1 ≦ Vi ≦ 109

小課題

小課題1[5点]

以下の条件を満たす。

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

小課題2[15点]

以下の条件を満たす。

  • Ti = 3

小課題3[20点]

以下の条件を満たす。

  • Ti = 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の制約を満たします。