stress_example

# include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
//#pragma GNU optimize("O3")
//#pragma G++ optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma G++ optimize("no-stack-protection")
#define int long long
# define sz(x) ((int)(x).size())
# define INF (long long)1e9+1
# define mp(a, b) make_pair(a, b)
# define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
template<class T> void print(T v) {for (auto &x : v) cout << x << ' '; cout << '\n'; };
template<class T> void print_1(T v) {for (auto &x : v) cout << x + 1 << ' '; cout << '\n'; };

/*==input-define==*/

#define input(v, sz) for(int i = 0; i < sz; ++i) {int x; cin >> x; v.emplace_back(x);}

/*==templates-for-pairs==*/
#define fi first
#define se second
template<class T1, class T2> ostream& operator << (ostream &o, pair<T1, T2> x) {return o << x.fi << ' ' << x.se;}
template<class T1, class T2> istream& operator >> (istream &o, pair<T1, T2> &x) {return o >> x.fi >> x.se;}
template<class T1, class T2> pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se; return a;}
template<class T1, class T2> pair<T1, T2> operator - (pair<T1, T2> a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se; return a;}
template<class T1, class T2> void operator += (pair<T1, T2> &a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se;}
template<class T1, class T2> void operator -= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se;}

void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

std::mt19937 my_gen(std::chrono::high_resolution_clock::now().time_since_epoch().count() ^ (size_t)(new char));

int gen_int(int a, int b) {
    assert(a <= b && "Wrong using random generator!");
    return my_gen() % (b - a + 1) + a;
}

/*
@author: Shvandre
████████████████████████████████████████
████████████▓▒▒▒░░░░░░░░▒▒▒▓████████████
███████░────────────────────────▒███████
████▒──────────────────────────────▒████
███▒─────────────────────────────────███
███──────────────────────────────────▓██
██░───────────────────────────────────██
██───░███████▒────────────▒███████░───██
██──▓█▓░████████░──────░████████░▓█▓──██
█▓─░░─────░▓█████▒────▓█████▓░─────░──▓█
█▒───────────▓██▓─────░▒██▓───────────▓█
█░─────────────██──────██─────────────▒█
█░───▒███████▒──██────░▓──▒███████▒───░█
█░─▒███████████─██──────░███████████▒░░█
█░─████▓▓▓▓▓▓▒░─██░──────▒▒░░░░░▒░░░░─▒█
█░──────────────██░───────────────────░█
██─────────────░██░───────────────────░█
███────────────▓██────────────────────██
██▓█──────────▒███─────░▒───────────░███
██─████▒▒▓▒░░█████─────▒██──▒▓▒░░▒▒█▒███
███─█▓██────▒█▒─██───────▓░─░▒░▒████─███
███▒─█▒██───────█▓─────────────██─█─▒███
████░─█▓███▓░───██▒▒▒▓█░────░███─█▒─████
█████──█▓▒█████████▓███████████░█▓─█████
██████──██──▒█████░──███████▒──█▓─██████
███████──██▓──────░░░░░░──────█▒─███████
████████──██▓░▒▒░░───────────█▒─████████
█████████──█▒──░░▒████▒────░█░─█████████
██████████─░█─────███▒─────▒░─██████████
███████████░─────▒████───────███████████
█████████████────█████─────░████████████
██████████████───▓████────▓█████████████
███████████████───███░──░███████████████
█████████████████▒███▒▒█████████████████
████████████████████████████████████████
████████████████████████████████████████
██████──█──██────██─██─██───██────██████
███████───███─██─██─█─███─████─██─██████
████████─████────██──████───██────██████
███████───███─██─██─█─███─████─█████████
██████──█──██─██─██─██─██───██─█████████
████████████████████████████████████████
 */

vector<int> a;
int n, m;

struct Command {
    char t;
    int p[3];
};

vector<Command> cmd;

struct NODE
{
    int zeros_cnt = 0;
    NODE(int _value)
    {
        zeros_cnt = _value;
    }
};
struct seg_tree
{
    vector<NODE> tree;
    seg_tree(int n)
    {
        tree.assign(4*n, NODE(0));
    }
    NODE combine(NODE v1, NODE v2)
    {
        return NODE(v1.zeros_cnt + v2.zeros_cnt);
    }
    void build(int x, int lx, int rx)
    {
        if(rx - lx == 1)
        {
            if(a[lx] == 0)
                tree[x] = NODE(1);
            else
                tree[x] = NODE(0);
            return;
        }
        int m = (lx+rx) / 2;
        build(x*2+1, lx, m);
        build(x*2+2, m, rx);
        tree[x] = combine(tree[x*2+1], tree[x*2+2]);
    }
    void set(int i, int value, int x, int lx, int rx)
    {
        if(rx - lx == 1)
        {
            if(value == 0)
                tree[x] = NODE(1);
            else
                tree[x] = NODE(0);
            return;
        }
        int m = (lx+rx) / 2;
        if(i < m)
        {
            set(i, value, x*2+1, lx, m);
        }
        else
        {
            set(i, value, x*2+2, m, rx);
        }
        tree[x] = combine(tree[x*2+1], tree[x*2+2]);
    }
    int ask(int k, int R, int x, int lx, int rx)
    {
        if(rx - lx == 1)
        {
            if(lx >= R) return -2; //TODO
            return lx;
        }
        int m = (lx + rx) / 2;
        if (tree[x*2+1].zeros_cnt + tree[x*2+2].zeros_cnt < k)
        {
            return -2;
        }
        else if(tree[x*2+1].zeros_cnt < k)
        {
            return ask(k - tree[x*2+1].zeros_cnt, R,  x*2+2, m, rx);
        }
        else
        {
            return ask(k, R, x*2 + 1, lx, m);
        }
    }
    NODE zero_count_until_Segment(int l, int r, int LX, int RX, int idx)
    {
        if(l >= RX || r <= LX) return 0;
        if(l <= LX && RX <= r) return tree[idx];
        int m = (RX + LX) / 2;
        return combine(zero_count_until_Segment(l, r, LX, m, idx*2+1), zero_count_until_Segment(l, r, m, RX, idx*2+2));
    }
};

vector<int> solve() {
    vector<int> r;
    seg_tree my_tree(n);
    my_tree.build(0, 0, n);
    for(int i = 0; i < m; ++i)
    {
        if(cmd[i].t == 'u')
        {
            int idx = cmd[i].p[0], value = cmd[i].p[1];
            my_tree.set(idx - 1, value, 0, 0, n);
        }
        else {
            int L = cmd[i].p[0], R = cmd[i].p[1], k = cmd[i].p[2];
            int zero_cnt = my_tree.zero_count_until_Segment(0, L - 1, 0, n, 0).zeros_cnt;
            r.push_back(my_tree.ask(zero_cnt + k, R, 0, 0, n) + 1);
        }
    }
    return r;
}

vector<int> slow() {
    vector<int> r;
    vector<int> b = a;
    for(int i = 0; i < m; ++i)
    {
        if(cmd[i].t == 'u')
        {
            int idx = cmd[i].p[0], value = cmd[i].p[1];
            b[idx-1] = value;
        }
        else {
            int L = cmd[i].p[0], R = cmd[i].p[1], k = cmd[i].p[2];
            int ans = -1, t = 0;

            for(int j = L-1; j < R; ++j) {
                if (b[j] == 0) {
                    ++t;
                }
                if (t == k) {
                    ans = j + 1;
                    break;
                }
            }

            r.push_back(ans);
        }
    }
    return r;
}

void read_data() {
    fastio();
    cin >> n;
    input(a, n)
    cin >> m;
    cmd.resize(m);
    for(int i = 0; i < m; ++i)
    {
        cin >> cmd[i].t;
        if(cmd[i].t == 'u')
        {
            cin >> cmd[i].p[0] >> cmd[i].p[1];
        } else {
            cin >> cmd[i].p[0] >> cmd[i].p[1] >> cmd[i].p[2];
        }
    }
}

void print_data() {
    cout << n << '\n';
    for(auto x: a) {
        cout << x << ' ';
    }
    cout << '\n' << m << '\n';
    for(auto c: cmd) {
        if (c.t == 'u') {
            cout << c.t << ' ' << c.p[0] << ' ' << c.p[1] << '\n';
        } else {
            cout << c.t << ' ' << c.p[0] << ' ' << c.p[1] << ' ' << c.p[2] << '\n';
        }
    }
}

void gen_data() {
    const int MAXN = 20,  MAXM = 10, MAXV = 100;

    n = gen_int(1, MAXN);
    a.resize(n);
    for(size_t i=0; i<n; ++i) {
        a[i] = gen_int(0, MAXV);
    }
    m = gen_int(1, MAXM);
    cmd.resize(m);
    for(size_t i=0; i<m; ++i) {
        int t = gen_int(0, 1);

        if (t == 0) {
            cmd[i].t = 'u';
            cmd[i].p[0] = gen_int(1, n);
            cmd[i].p[1] = gen_int(0, MAXV);
        } else {
            cmd[i].t = 's';
            cmd[i].p[0] = gen_int(1, n);
            cmd[i].p[1] = gen_int(cmd[i].p[0], n);
            cmd[i].p[2] = gen_int(1, n);
        }
    }
}

int32_t main()
{
    read_data();

    /**
    for (auto x: solve() ) {
        cout << x << '\n';
    }
    return 0;
    */

    while(true) {
        gen_data();
        if (slow() != solve()) {
            print_data();
            break;
        }
    }
    return 0;
}