E：バイナリ列 - Binary Sequence -

物語

わしはバイナリ大好き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がこの順で空白区切りで与えられる。

制約

• 2 \leq n \leq 100000
• xは’0’、’1’からなる文字列
• |x| = n
• 1 \leq q \leq 100000
• 1 \leq l_j \leq r_j \leq n, b_j \in \{0,1\}, j = 1,...,q

出力形式

各i=1,...,qについて、i行目にi回目のクエリを処理した後のf(x) - g(x)の値を出力せよ。

入力例1

10
0101100110
3
3 3 1
1 6 0
2 5 1

出力例1

2
1
2

入力例2

8
00111100
3
8 8 1
4 5 0
7 8 1

出力例2

2
3
2