Problem: E: Binary Sequence-Binary Sequence-

story

I love binaries Bonald.Brvin.Bnuth! He is known as Uncle Bnuth, who is studying the nature of binary sequences at Offtunford University! By the way, if my name "Bonald.Brvin.Bnuth" is binarized from ASCII code, it will be "1000010 1101111 1101110 1100001 1101100 1100100 101110 1000010 1110010 1110110 1101001 1101110 101110 1000010 1101110 1110101 1110100 1101000"! It's fun!

I'm looking forward to it from the morning because my disciples are going to do some interesting experiments today! What are you doing?

What! I want to discover some properties by continuing to rewrite binary strings! HM! This is the scent of an important discovery! Let's start the experiment! Let's summarize more detailed settings as sentences!

problem

Given a binary sequence of length n x = (x_1, ..., x_n) (x_i \ in \\ {0,1 \\}, i = 1, ..., n). For the binary string x, we define two functions f (x) and g (x) as follows.


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


Now, perform the following change operation on the binary string x q times. The jth change operation is given by l_j, r_j, b_j (1 \ leq l_j \ leq r_j \ leq n, b_j \ in \\ {0,1 \\}, j = 1, ..., q). This corresponds to the operation of replacing the l_jth to r_jths of the binary string x with b_j. Find f (x) --g (x) after each change operation.

Input format


n
x
q
l_1 r_1 b_1
...
l_q r_q b_q


The first line is given the integer n that represents the length of the binary column. The second line is given a string that represents the binary column x. The third line is given the integer q, which represents the number of queries. In the following q lines, the i-th line is given information about the i-th query l_i, r_i, b_i in this order, separated by blanks.

Constraint

* 2 \ leq n \ leq 100000
* x is a character string consisting of ‘0’ and ‘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



Output format

For each i = 1, ..., q, output the value of f (x) --g (x) after processing the i-th query on the i-line.

Input example 1


Ten
0101100110
3
3 3 1
1 6 0
2 5 1


Output example 1


2
1
2


Input example 2


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


Output example 2


2
3
2






Example

Input

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


Output

2
1
2

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100000

enum Type{
	F,
	G,
};

struct Info{
	Info(int arg_left,int arg_right){
		left = arg_left;
		right = arg_right;
	}
	int left,right;
};

int N = 1;
int data[4*NUM][2];
char buf[NUM+1];

void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int update_left,int update_right,int new_value,int node_id,int node_left,int node_right,Type type){
	if(update_right < node_left || update_left > node_right)return; //区間に重なりがなければreturn
	else if(update_left <= node_left && update_right >= node_right){ //このノードがカバーしている区間が、更新区間の部分区間である場合
		data[node_id][type] = new_value;
	}else{ //一部に重なりがある場合
		//データを左右の子に引き継ぐ
		if(data[node_id][type] != -1){ //もし区間が値を保持しているなら→区間の一様性が壊れたので、今持っている値を子に投げる
			data[2*node_id+1][type] = data[node_id][type]; //逆に言えば、更新データがないなら、子が更新データをもっている可能性があるので、値(-1)を引き継いではいけない
			data[2*node_id+2][type] = data[node_id][type];
			data[node_id][type] = -1; //-1:一様性が壊れたことの記録
		}
		update(update_left,update_right,new_value,2*node_id+1,node_left,(node_left+node_right)/2,type);
		update(update_left,update_right,new_value,2*node_id+2,(node_left+node_right)/2+1,node_right,type);
	}
}

//1の個数を計上する関数
int getSum(int search_left,int search_right,int node_id,int node_left,int node_right,Type type){
	if(search_right < node_left || search_left > node_right){ //区間の重なりがない場合
		return 0;
	}else{
		if(data[node_id][type] == -1){ //区間の重なりはあるが、一様性が壊れている場合→データは子が持っているので、子にクエリを投げる
			int left = getSum(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2,type);
			int right = getSum(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right,type);
			return left+right;
		}else{	//区間の重なりがあり、かつ一様性が壊れていない場合

			/*
			 * 左にはみ出す等の部分一致をしている場合、親から降ってくるクエリが割れるので、
			 * 割れた区間の相和については考えなくて良い
			 *
			 * */
			return (min(search_right,node_right)-max(search_left,node_left)+1)*data[node_id][type]; //重なってる区間の長さ*一様な値を返却値に加える
		}
	}
}

//特定の場所の値を取得する関数
int query(int search_left,int search_right,int node_id,int node_left,int node_right,Type type){
	if(search_right < node_left || search_left > node_right){ //区間に重なりがない場合は-1をreturn
		return -1;
	}else if(node_left <= search_left && node_right >= search_right && data[node_id][type] != -1){ //検索区間が、このノードがカバーしている区間の部分区間である場合(★部分区間なのは、検索区間★)
		return data[node_id][type]; //更新データが「壊れて」いなければreturn
	}else{ //一部の区間に重なりがある、またはこの区間がカバーしている区間が検索区間の部分区間で、かつこの区間の更新データが「壊れている」場合、左右の子に処理を投げる
		int left = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2,type);
		int right = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right,type);
		return max(left,right);
	}
}

int main(){

	int first_N;
	scanf("%d",&first_N);

	init(first_N);

	//セグメント木の初期化
	for(int i = 0; i <= 2*N-2; i++){
		data[i][F] = 0;
		data[i][G] = 0;
	}

	scanf("%s",buf);

	vector<Info> V;
	//最初の更新区間を調べる
	for(int i = 0; buf[i] != '\0';){
		if(buf[i] == '1'){
			int k = i;
			while(buf[k] != '\0' && buf[k] == '1')k++;
			k--;
			V.push_back(Info(i,k));
			i = k+1;
		}else{
			i += 1;
		}
	}

	//F,Gそれぞれを更新する
	for(int i = 0; i < V.size(); i++){
		update(V[i].left,V[i].right,1,0,0,N-1,F);
		update(V[i].left+1,V[i].right,1,0,0,N-1,G); //Gは左隣が1で、かつ自分が1の場合のみ1が立つ
	}

	int Q;
	scanf("%d",&Q);

	int left,right,value;
	int sum_F,sum_G,tmp;

	for(int loop = 0; loop < Q; loop++){
		scanf("%d %d %d",&left,&right,&value);
		left--;
		right--;

		if(value == 0){

			//とりあえず更新
			update(left,right,0,0,0,N-1,F);
			update(left,right,0,0,0,N-1,G);

			if(right == first_N-1){
				//Do nothing
			}else{
				//rightが0になることで、仮にright+1が1ならば0にする
				tmp = query(right+1,right+1,0,0,N-1,G);
				if(tmp == 1){
					update(right+1,right+1,0,0,0,N-1,G);
				}
			}

		}else{ //value == 1

			update(left,right,1,0,0,N-1,F);

			//更新区間の両端の値を調べる
			if(left > 0){
				tmp = query(left-1,left-1,0,0,N-1,F); //Fにおいて、left-1がどうなっているか調べる
				if(tmp == 0){
					left += 1;
				}
			}else{
				left += 1;
			}

			if(right <= first_N-2){
				if(getSum(right+1,right+1,0,0,N-1,F) == 1){ //Fにおいて、rightの右が1ならば、rightは左に1がいないことでGにおいて0である可能性があるので、
															//機械的に1で更新する
					right += 1;
				}
			}
			update(left,right,1,0,0,N-1,G);
		}

		sum_F = getSum(0,first_N-1,0,0,N-1,F);
		sum_G = getSum(0,first_N-1,0,0,N-1,G);

		printf("%d\n",sum_F-sum_G);
	}
}