わしはバイナリ大好きBonald.Brvin.Bnuthじゃ！ オフトゥンフォード大学でバイナリ列の性質を研究しておってのお、Bnuthおじさんと呼ばれて、親しまれておるぞい！ ちなみに、わしの名前「Bonald.Brvin.Bnuth」をASCIIコードからバイナリ化すると「1000010 1101111 1101110 1100001 1101100 1100100 101110 1000010 1110010 1110110 1101001 1101110 101110 1000010 1101110 1110101 1110100 1101000」になるぞい！ 楽しいのお！
今日は、弟子が何やら面白そうな実験をすると言うからのお、朝から楽しみなんじゃ！ どれどれ、どんなことをするんじゃの？
なんと！バイナリ列を書き換え続けることで、何らかの性質を見出したいとな！ ふむ！これは、重要な発見の匂いがぷんぷんするぞい！ さあ、さあ、実験を始めようではないか！ より詳細な設定を文章としてまとめておくぞい！
長さnのバイナリ列x = (x_1, ..., x_n) (x_i \in \{0,1\}, i = 1,...,n) が与えられる。バイナリ列xに対して2つの関数f(x)とg(x)を以下のように定義する。
f(x) = Σ_{i=1}^{n} x_i = x_1 + x_2 + ... + x_n
g(x) = Σ_{i=1}^{n-1} x_i x_{i+1} = x_1 x_2 + x_2 x_3 + ... x_{n-1} x_n
今、バイナリ列xに対して以下のような変更操作をq回行う。j回目の変更操作はl_j, r_j, b_j (1 \leq l_j \leq r_j \leq n, b_j \in \{0,1\}, j = 1,...,q) で与えられ、これはバイナリ列xのl_j番目からr_j番目をb_jに置き換える操作に対応する。各変更操作の後でf(x) - g(x)を求めよ。
n x q l_1 r_1 b_1 ... l_q r_q b_q
1行目にはバイナリ列の長さを表す整数nが与えられる。 2行目にはバイナリ列xを表せす文字列が与えられる。 3行目にはクエリの回数を表す整数qが与えられる。 続くq行のうちi行目には、i回目のクエリに関する情報l_i, r_i, b_iがこの順で空白区切りで与えられる。
各i=1,...,qについて、i行目にi回目のクエリを処理した後のf(x) - g(x)の値を出力せよ。
10 0101100110 3 3 3 1 1 6 0 2 5 1
2 1 2
8 00111100 3 8 8 1 4 5 0 7 8 1
2 3 2