若ヶ松高校二年へ組の合津千里(あつちり)さんは数列が「きっちり」していなければ気がすまない。
合津さんによると、「きっちり」した数列とは、長さが偶数で左右対称である数列のことである。 すなわち、長さ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_iはl, r, xを順に1つの半角スペースで区切って与えらる。
また、次の制約を満たす。
クエリiまで処理した後の数列が「きっちり」していれば“1”を、そうでなければ“0”をi行目に出力せよ。
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 0 0 1 1 0 1
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
1 1 1 1 1