#include <bits/stdc++.h> using namespace std; #define ll int #define ff first #define ss second #define pb push_back #define all(x) (x).begin(), (x).end() #define ertunt return vector<ll> f(200005), inv(200005); ll mod = 998244353; ll modpow(ll a, ll b){ ll res = 1; while(b){ if(b&1){ res*=a; res%=mod; } a*=a; a%=mod; b >>= 1; } ertunt res; } ll nCk(ll n, ll k){ if(k < 0 || k > n) ertunt 0; ertunt 1ll * f[n] * inv[k] % mod * inv[n-k] % mod; } void buildWall(int n, int k, int op[], int l[], int r[], int h[], int H[]){ vector<array<ll,3>> add, rem; for(ll i = 0; i < n; i++) H[i] = 0; for(ll i = 0; i < k; i++){ if(op[i] == 1) add.pb({h[i], l[i], r[i]}); else rem.pb({h[i], l[i], r[i]}); } sort(all(add), [](const array<ll,3> &a, const array<ll,3> &b){ return a[0] > b[0]; }); sort(all(rem)); vector<ll> p(n+1), q(n+1); for(ll i = 0; i <= n; i++) p[i] = q[i] = i; for(ll i = 0; i < (ll)add.size(); i++){ ll x = add[i][0], L = add[i][1], R = add[i][2]; ll j = L; while(true){ ll u = j; while(u <= R && p[u] != u) u = p[u]; if(u > R) break; H[u] = x; p[u] = u + 1; j = u + 1; } } for(ll i = 0; i < (ll)rem.size(); i++){ ll x = rem[i][0], L = rem[i][1], R = rem[i][2]; ll j = L; while(true){ ll u = j; while(u <= R && q[u] != u) u = q[u]; if(u > R) break; if(H[u] > x) H[u] = x; q[u] = u + 1; j = u + 1; } } }