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:
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

// @category セグメント木 (Segment Tree)
// @title 遅延伝播セグメント木 (Lazy Segment Tree)
template <typename MonoidType, typename OperatorType>
struct LazySegmentTree {
    using MMtoM = function< MonoidType(MonoidType, MonoidType) >;
    using OOtoO = function< OperatorType(OperatorType, OperatorType) >;
    using MOtoM = function< MonoidType(MonoidType, OperatorType) >;
    using OItoO = function< OperatorType(OperatorType, int) >;

    // node, lazy, update flag (for lazy), identity element
    int n;
    vector<MonoidType> node;
    vector<OperatorType> lazy;
    vector<bool> need_update;
    MonoidType E0;
    OperatorType E1;

    // update / combine / lazy / accumulate function
    MOtoM upd_f;
    MMtoM cmb_f;
    OOtoO lzy_f;
    OItoO acc_f;

    void build(int m, vector<MonoidType> v = vector<MonoidType>()) {
        if(v != vector<MonoidType>()) m = v.size();
        n = 1; while(n < m) n *= 2;

        node = vector<MonoidType>(2*n-1, E0);
        lazy = vector<OperatorType>(2*n-1, E1);
        need_update = vector<bool>(2*n-1, false);
        if(v != vector<MonoidType>()) {
            for(int i=0; i<m; i++) {
                node[n-1+i] = v[i];
            }
            for(int i=n-2; i>=0; i--) {
                node[i] = cmb_f(node[2*i+1], node[2*i+2]);
            }
        }
    }

    // initialize
    LazySegmentTree() {}
    LazySegmentTree(int n_, MonoidType E0_, OperatorType E1_,
                    MOtoM upd_f_, MMtoM cmb_f_, OOtoO lzy_f_, OItoO acc_f_,
                    vector<MonoidType> v = vector<MonoidType>()) :
        E0(E0_), E1(E1_),
        upd_f(upd_f_), cmb_f(cmb_f_), lzy_f(lzy_f_), acc_f(acc_f_) {
        build(n_, v);
    }

    void eval(int k, int l, int r) {
        if(!need_update[k]) return;
        node[k] = upd_f(node[k], acc_f(lazy[k], r - l));
        if(r - l > 1) {
            lazy[2*k+1] = lzy_f(lazy[2*k+1], lazy[k]);
            lazy[2*k+2] = lzy_f(lazy[2*k+2], lazy[k]);
            need_update[2*k+1] = need_update[2*k+2] = true;
        }
        lazy[k] = E1;
        need_update[k] = false;
    }

    void update(int a, int b, OperatorType x, int l, int r, int k) {
        eval(k, l, r);
        if(b <= l or  r <= a) return;
        if(a <= l and r <= b) {
            lazy[k] = lzy_f(lazy[k], x);
            need_update[k] = true;
            eval(k, l, r);
        }
        else {
            int mid = (l + r) / 2;
            update(a, b, x, l, mid, 2*k+1);
            update(a, b, x, mid, r, 2*k+2);
            node[k] = cmb_f(node[2*k+1], node[2*k+2]);
        }
    }

    MonoidType query(int a, int b, int l, int r, int k) {
        if(b <= l or  r <= a) return E0;
        eval(k, l, r);
        if(a <= l and r <= b) return node[k];
        int mid = (l + r) / 2;
        MonoidType vl = query(a, b, l, mid, 2*k+1);
        MonoidType vr = query(a, b, mid, r, 2*k+2);
        return cmb_f(vl, vr);
    }

    // update [a, b)-th element (applied value, x)
    void update(int a, int b, OperatorType x) {
        update(a, b, x, 0, n, 0);
    }

    // range query for [a, b)
    MonoidType query(int a, int b) {
        return query(a, b, 0, n, 0);
    }

    void dump() {
        fprintf(stderr, "[lazy]\n");
        for(int i=0; i<2*n-1; i++) {
            if(i == n-1) fprintf(stderr, "xxx ");
            if(lazy[i] == E1) fprintf(stderr, "  E ");
            else fprintf(stderr, "%3d ", lazy[i]);
        }
        fprintf(stderr, "\n");

        fprintf(stderr, "[node]\n");
        for(int i=0; i<2*n-1; i++) {
            if(i == n-1) fprintf(stderr, "xxx ");
            if(node[i] == E0) fprintf(stderr, "  E ");
            else fprintf(stderr, "%3d ", node[i]);
        }
        fprintf(stderr, "\n");
    }
};

int main() {
    int N; scanf("%d", &N);
    string s; cin >> s;
    int Q; scanf("%d", &Q);
    
    vector<int> vec1, vec2;
    for(int i=0; i<N; i++) {
        vec1.emplace_back(s[i] - '0');
        if(i + 1 < N) vec2.emplace_back((s[i+1] - '0') * (s[i] - '0'));
    }
    
    LazySegmentTree<int, int> seg1(N, 0, 0,
                                   [](int a, int b) { return b; },
                                   [](int a, int b) { return a + b; },
                                   [](int a, int b) { return b; },
                                   [](int a, int x) { return a * x; },
                                   vec1);
    LazySegmentTree<int, int> seg2 = seg1;
    seg2.build(N-1, vec2);

    while(Q--) {
        int l, r, b; scanf("%d%d%d", &l, &r, &b); l--;
        seg1.update(l, r, b);
        if(l >= 1) {
            int v0 = seg1.query(l-1, l);
            int v1 = seg1.query(l, l+1);
            seg2.update(l-1, l, v0 * v1);
        }
        if(r+1 <= N) {
            int v0 = seg1.query(r-1, r);
            int v1 = seg1.query(r, r+1);
            seg2.update(r-1, r, v0 * v1);
        }
        seg2.update(l, r-1, b);

        int f = seg1.query(0, N);
        int g = seg2.query(0, N);
        // fprintf(stderr, "# f = %d, g = %d\n", f, g);
        printf("%d\n", f - g);
    }
    return 0;
}