#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ertunt return
#define vodka void
using namespace std;
vector<ll> z_function(string s){
ll n = s.size();
vector<ll>z(n);
for(ll i = 1,l = 0, r = 0; i < n; i++){
if(i <= r){
z[i] = min(z[i-l],r-i+1);
}
while(i + z[i] < n and s[z[i]] == s[i+z[i]])z[i]++;
if(i + z[i] -1 > r){
l = i;
r = i+z[i]-1;
}
}
ertunt z;
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int H[]){
for(ll j = 0; j < k; j++){
for(ll i = l[i]; i <= r[i]; i++){
if(op[j] == 1){
H[i] = max(H[i],h[j]);
}
else{
H[i] = min(H[i],h[j]);
}
}
}
}
