#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include "wall.h"
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <string> vs;
typedef vector <vector <int>> vvi;
typedef vector <vll> vvll;
typedef map<int, int> mi;
typedef map<string, int> ms;
typedef map<char, int> mc;
typedef map <int, bool> mb;
typedef map<ll, ll> mll;
typedef unordered_map<int, int> umi;
typedef unordered_map<string, int> ums;
typedef unordered_map<char, int> umc;
typedef unordered_map <int, bool> umb;
typedef unordered_map<ll, ll> umll;
typedef vector <ld> vld;
typedef vector <bool> vb;
typedef pair <int, int> pii;
typedef pair<ll, ll> pll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
#define FOR(i,N) for(ll i = 0 ; i < N;i++)
#define eFOR(i,a,b) for(ll i = a; i <=b;i++)
#define dFOR(i,N) for(ll i = N - 1; i>=0;i--)
#define edFOR(i,b,a) for(ll i = b ; i >=a;i--)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define RSORT(x) sort(x.rbegin(), x.rend())
#define UNQ(x) unique(all(x))
#define mine(x) min_element(all(x))
#define maxe(x) max_element(all(x))
#define lb(v, x) lower_bound(all(v) , x)
#define ub(v, x) upper_bound(all(v) , x)
#define pb push_back
#define FIX cout << fixed << setprecision(1)
#define g(i , a) get<i>(a)
const long double PI = 3.141592653589793;
const ll mod = 1e9;
bool prime(ll n)
{
if (n <= 1)
return false;
if (n == 2 or n == 3)
return true;
if (n % 2 == 0 or n % 3 == 0)
return false;
for (ll i = 5; i * i <= n; i += 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
ll __gcd(ll a, ll b)
{
return !b ? a : __gcd(b, a % b);
}
ll power(ll a, ll b, ll MOD)
{
ll x = a, res = 1, p = b;
while (p > 0)
{
if (p & 1)
res *= x;
x *= x;
p >>= 1;
x %= MOD, res %= MOD;
}
return res;
}
int CASE = 1;
const int mxn = 1e5 + 1;
const ll infll = 1e18;
const int infi = 1e9 + 1;
vi mx(1 << 22, 0), mn(1 << 22, 0), lazy(1 << 22, -1);
void push(int id, int half)
{
if (lazy[id] != -1)
{
mn[id << 1] = mx[id << 1] = mn[id << 1 | 1] = mx[id << 1 | 1] = lazy[id << 1] = lazy[id << 1 | 1] = lazy[id];
lazy[id] = -1;
}
}
void ope1(int u, int v, int x, int id = 1, int l = 1, int r = 1 << 21)
{
if (r < u || l > v || mn[id] >= x) return;
if (l >= u && r <= v && mx[id] <= x)
{
mn[id] = mx[id] = lazy[id] = x;
return;
}
push(id, (r - l + 1) >> 1);
int mid = (l + r) >> 1;
ope1(u, v, x, id << 1, l, mid);
ope1(u, v, x, id << 1 | 1, mid + 1, r);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}
void ope2(int u, int v, int x, int id = 1, int l = 1, int r = 1 << 21)
{
if (r < u || l > v || mx[id] <= x) return;
if (l >= u && r <= v && mn[id] >= x)
{
mn[id] = mx[id] = lazy[id] = x;
return;
}
push(id, (r - l + 1) >> 1);
int mid = (l + r) >> 1;
ope2(u, v, x, id << 1, l, mid);
ope2(u, v, x, id << 1 | 1, mid + 1, r);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}
int get(int pos, int id = 1, int l = 1, int r = 1 << 21)
{
if (pos < l || pos > r) return 0;
if (l == r) return mx[id];
push(id, (r - l + 1) >> 1);
int mid = (l + r) >> 1;
return get(pos, id << 1, l, mid) + get(pos, id << 1 | 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for (int i = 0; i < k; i++)
{
left[i]++;
right[i]++;
if (op[i] == 1)
{
ope1(left[i], right[i], height[i]);
}
else
{
ope2(left[i], right[i], height[i]);
}
}
for (int i = 1; i <= n; i++)
{
finalHeight[i - 1] = get(i);
}
}
