#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// typedef tree<int,null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;
#define dbg if(0)
const ll MOD = 998244353;
const ll INFLL = 1e18;
const int INF = 1e9;
const int maxN = 2e5+6;
const int maxK = 10;
void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
#define gbit(x, i) (((1<<i)&(x))!=0)
template <typename T>
class MINT{
T x;
public:
static T MOD;
MINT(T _x){x = (_x%MOD+MOD)%MOD;}
MINT():MINT(0){}
explicit operator ll(){return x;}
friend MINT operator+(const MINT& m1, const MINT& m2){return MINT((m1.x + m2.x)%MOD);};
friend MINT operator-(const MINT& m1, const MINT& m2){return MINT(((m1.x - m2.x)%MOD + MOD)%MOD);};
friend MINT operator*(const MINT& m1, const MINT& m2){return MINT((m1.x * m2.x)%MOD);};
MINT& operator+=(const MINT& m2){return *this = *this + m2;};
MINT& operator-=(const MINT& m2){return *this = *this - m2;};
MINT& operator*=(const MINT& m2){return *this = *this * m2;};
friend bool operator==(const MINT& m1, const MINT& m2){return m1.x==m2.x;};
friend istream& operator>>(istream& in, const MINT& m){in>>m.x;return in;};
friend ostream& operator<<(ostream& out, const MINT& m){out<<m.x;return out;};
};
template <typename T>
T MINT<T>::MOD = 998244353;
typedef MINT<ll> mll;
typedef pair<mll, mll> pmll;
#define lt(x) ((x)<<1)
#define rt(x) ((x)<<1|1)
struct Node {
ll h, mx, mn;
Node(ll x):h(x), mx(INF), mn(0){}
Node():Node(0){}
};
vector<Node> tree;
int n;
void init(int _n){
n = 1;
while(n<_n) n<<=1;
tree.assign(2*n, Node());
}
void opt(Node& par, Node& chi){
chi.mx = min(chi.mx, par.mx);
chi.mx = max(chi.mx, par.mn);
chi.mn = max(chi.mn, par.mn);
chi.mn = min(chi.mn, par.mx);
}
void pushdown(int x){
if (x>=n) return;
opt(tree[x], tree[lt(x)]);
opt(tree[x], tree[rt(x)]);
tree[x].mn = 0;
tree[x].mx = INF;
}
// void build(vector<ll>& v){
// for (int i = 0;i<sz(v);i++) tree[i+n] = v[i];
// for (int i = n-1;i>0;i--) pushup(i);
// }
void updatemx(int l, int r, int x, int lx, int rx, ll val){
if (l<=lx && rx<=r) {
tree[x].mx = min(tree[x].mx, val);
tree[x].mn = min(tree[x].mn, val);
return;
}
if (l>=rx || r<=lx) return;
int m = (lx+rx)/2;
pushdown(x);
updatemx(l, r, lt(x), lx, m, val);
updatemx(l, r, rt(x), m, rx, val);
// pushup(x);
}
void updatemx(int l, int r, ll val){
updatemx(l, r, 1, 0, n, val);
}
void updatemn(int l, int r, int x, int lx, int rx, ll val){
if (l<=lx && rx<=r) {
tree[x].mx = max(tree[x].mx, val);
tree[x].mn = max(tree[x].mn, val);
return;
}
if (l>=rx || r<=lx) return;
int m = (lx+rx)/2;
pushdown(x);
updatemn(l, r, lt(x), lx, m, val);
updatemn(l, r, rt(x), m, rx, val);
// pushup(x);
}
void updatemn(int l, int r, ll val){
updatemn(l, r, 1, 0, n, val);
}
// ll querysm(int l, int r, int x, int lx, int rx){
// if (l<=lx && rx<=r) return tree[x].s;
// else if (l>=rx || r<=lx) return 0;
// else {
// int m = (lx+rx)/2;
// pushdown(x, lx, m, rx);
// return (querysm(l, r, lt(x), lx, m)+querysm(l,r , rt(x), m, rx));
// }
// }
// ll querysm(int l, int r){
// return querysm(l, r, 1, 0, n);
// }
// ll querymin(int l, int r, int x, int lx, int rx){
// if (l<=lx && rx<=r) return tree[x].m;
// else if (l>=rx || r<=lx) return -INFLL;
// else {
// int m = (lx+rx)/2;
// pushdown(x, lx, m, rx);
// return max(querymin(l, r, lt(x), lx, m), querymin(l, r, rt(x), m, rx));
// }
// }
// ll querymin(int l, int r){
// return querymin(l, r, 1, 0, n);
// }
template <class T>
istream& operator>>(istream& in, vector<T>& v){
for (T& x:v) in>>x;
return in;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
init(n);
vi h(n);
// for (int i = 0;i<n;i++) h[i] = height[i];
// build(h);
for (int i = 0;i<k;i++){
if (op[i]==1) updatemn(left[i], right[i]+1, height[i]);
else updatemx(left[i], right[i]+1, height[i]);
}
for (int i = 1;i<::n;i++) pushdown(i);
for (int i = 0;i<n;i++) finalHeight[i] = min(tree[i+::n].mn, tree[i+::n].mx);
}
// void solve(){
// }
// int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
// // #define _DEBUG
// #ifdef _DEBUG
// freopen("haybales.in", "r", stdin);
// freopen("haybales.out", "w", stdout);
// int tt = clock();
// #endif
// int t=1, i = 1;
// // cin>>t;
// while(t--){
// // cout<<"Case #"<<i++<<": ";
// solve();
// // cout<<'\n';
// }
// #ifdef _DEBUG
// cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
// tt = clock();
// #endif
// }
// int main()
// {
// int n;
// int k;
// int i, j;
// int status = 0;
// status = scanf("%d%d", &n, &k);
// assert(status == 2);
// int* op = (int*)calloc(sizeof(int), k);
// int* left = (int*)calloc(sizeof(int), k);
// int* right = (int*)calloc(sizeof(int), k);
// int* height = (int*)calloc(sizeof(int), k);
// int* finalHeight = (int*)calloc(sizeof(int), n);
// for (i = 0; i < k; i++){
// status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
// assert(status == 4);
// }
// buildWall(n, k, op, left, right, height, finalHeight);
// for (j = 0; j < n; j++)
// printf("%d\n", finalHeight[j]);
// return 0;
// }
