cp-problems

かっこいい電車

問題文

Shuz* 君は \(N\) 個の車両からなる電車のおもちゃを持っていて，それぞれ \(1\) から \(N\) までの番号が付いています．各車両 \(i\) には，かっこよさ \(A_i\) が付いています．

このおもちゃは， 車両 \(i\) と車両 \(i + 1\) をつなげたり切り離したりできます．

Shuz* 君はこのおもちゃで遊んでいて，時々つなげた車両のかっこよさを確認したくなります．はじめすべての車両は切り離されています．

以下のクエリを処理できるプログラムを作成してください．

1. connect \(x\) 車両 \(x\) と車両 \(x + 1\) がつながっていない場合，それらを繋げる．
2. separate \(x\) 車両 \(x\) と車両 \(x + 1\) がつながっている場合，それらを切り離す．
3. remodel \(x\) 車両 \(x\) を改造した結果，車両 \(x\) のかっこよさが \(1\) 上がった．
4. attractiveness \(x\) 車両 \(x\) と，それにつながっているすべての車両のかっこよさの合計を出力する．

制約

• \(1 \le N,\, Q\) (クエリの個数) \(\le 10^5\)
• \(1 \le A_i \le 10^9\)
• \(query\) は上述の番号 \(1 \dots 4\) に対応する
• \(query_i \le 2\) のとき、 \(1 \le x_i \lt N\)
• \(query_i \ge 3\) のとき、 \(1 \le x_i \le N\)
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます．

入力
\(N \, Q\) \(A_1 \, A_2 \, \dots\ A_N\) \(query_1 \, x_1\) \(query_2 \, x_2\) \(\vdots\) \(query_Q \, x_Q\)

出力

各 attractiveness query に対して，1 行でかっこよさを出力してください．

最後に改行してください．

解説