#include <bits/stdc++.h>

​

using namespace std;

​

#define mp make_pair

#define pb push_back

#define F first

#define S second

typedef long long int ll;

#define pii pair<int, int>

​

const int mod = 1e9 + 7;

​

struct seg_tree{

    struct node{

        int cnt1,cnt2;

        node() : cnt1(0), cnt2(0){}

        void merge(const node& rhs){

            cnt1 += rhs.cnt1;

            cnt2 += rhs.cnt2;

        }

        void clear(){

            cnt1 = cnt2 = 0;

        }

    };

    struct lazy{

        int fg, tim;

        lazy() : fg(0), tim(0){}

        void merge(const lazy& rhs){

            if(rhs.fg == 0) return;

            fg = rhs.fg;

            //tim = rhs.tim;

        }

    };