Kitsuchiri

Time Limit : 5 sec, Memory Limit : 262144 KB

F: きっちり - Kitsuchiri -

問題

若ヶ松高校二年へ組の合津千里(あつちり)さんは数列が「きっちり」していなければ気がすまない。

合津さんによると、「きっちり」した数列とは、長さが偶数で左右対称である数列のことである。 すなわち、長さN(Nは偶数)の数列Sについて、次の条件を満たせば数列Sは「きっちり」している。

S_1 = S_N, S_2 = S_{N − 1}, ... , S_{N/2} = S_{N − N/2 + 1}

二年へ組の数学担当の先生は、合津さんから「きっちりしてください。」と要望され、授業で用いる数列を作り直さなければならない。

先生は、数列のl番目からr番目までのそれぞれの要素に数字xを足すクエリをいくつも適用することで、数列を「きっちり」させようと奮闘しているが、うまくいかないようだ。

二年へ組に所属する凄腕プログラマーのあなたの仕事は、先生が絶望してしまう前に、先生が作り直している数列が「きっちり」しているかを調べるプログラムを作ることだ。

入力形式

入力は以下の形式からなる。

N
S_1 ... S_N
Q
q_1
...
q_Q

Qはクエリの総数であり、1 \≤ i \≤ Qについて、各q_il, r, xを順に1つの半角スペースで区切って与えらる。

また、次の制約を満たす。

  • 2 \≤ N \≤ 500,000である。
  • Nは偶数である。
  • 1 \≤ j \≤ Nについて、−100,000,000 \≤ S_j \≤ 100,000,000である。
  • i番目の各クエリを適用した後の数列の各要素T_{i,j}−100,000,000 \≤ T_{i,j} \≤ 100,000,000を満たす。
  • 1 \≤ Q \≤ 100,000である。
  • 1 \≤ l \≤ r \≤ Nである。
  • −1,000 \≤ x \≤ 1,000である。

出力形式

クエリiまで処理した後の数列が「きっちり」していれば“1”を、そうでなければ“0”をi行目に出力せよ。

入力例1

10
0 1 2 3 4 4 3 2 1 0
7
2 6 0
2 4 5
7 9 10
2 4 5
3 8 100
4 6 1000
7 7 1000

出力例1

1
0
0
1
1
0
1

入力例2

10
4 4 4 4 4 4 4 4 6 4
5
9 9 -2
1 10 1000
1 10 -1000
3 8 100
5 6 1

出力例2

1
1
1
1
1

Source: Ritsumeikan University Programming Camp 2016 , Day 3, Shiga, Japan, 2016-03-08