#include <bits/stdc++.h>
//#include "wall.h"
using namespace std;
int lazy[8000005][2][2];
int n;
void build(){
for(int i=1; i<2*n; i++){
lazy[i][0][0]=1e9;
lazy[i][1][0]=0;
lazy[i][0][1]=0;
lazy[i][1][1]=0;
}
}
void setmax(int l, int r, int range_l, int range_r, int val, int pri){
if (l>range_r || r<range_l)return;
if (l>=range_l && r<=range_r){
int x = l+n, y=r+n;
while(x!=y){x>>=1; y>>=1;}
if((val >= lazy[x][1][0]) || (lazy[x][1][1] < lazy[x][0][1] && (lazy[x][0][0] < val || val > lazy[x][1][0]))){
lazy[x][1][0] = val;
lazy[x][1][1] = pri;
}
return;
}
int mid = (l+r)/2;
setmax(l, mid, range_l, range_r, val, pri);
setmax(mid+1, r, range_l, range_r, val, pri);
}
void setmin(int l, int r, int range_l, int range_r, int val, int pri){
if (l>range_r || r<range_l)return;
if (l>=range_l && r<=range_r){
int x = l+n, y=r+n;
while(x!=y){x>>=1; y>>=1;}
if(val <=lazy[x][0][0] || (lazy[x][0][1] < lazy[x][1][1] && ((lazy[x][0][0] > val || val < lazy[x][1][0])))){
lazy[x][0][0] = val;
lazy[x][0][1] = pri;
}
return;
}
int mid = (l+r)/2;
setmin(l, mid, range_l, range_r, val, pri);
setmin(mid+1, r, range_l, range_r, val, pri);
}
int n_act;
void solve(int ans[]){
for(int i=0; i<n_act; i++){
ans[i]=0;
vector<vector<int>> op;
for(int x=i+n; x>0; x>>=1){
if(lazy[x][1][1]>0) op.push_back({lazy[x][1][1], 1, lazy[x][1][0]});
if(lazy[x][0][1]>0) op.push_back({lazy[x][0][1], 2, lazy[x][0][0]});
}
sort(op.begin(), op.end(), [](vector<int> a, vector<int> b){return a[0]<b[0];});
if(i==4)cout<<ans[i]<<endl;
for(vector<int> o: op){
if(o[1]==1) ans[i]=max(ans[i], o[2]);
else ans[i]=min(ans[i], o[2]);
if(i==4)cout<<ans[i]<<' '<<o[0]<<endl;
}
}
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalheight[]){
n_act=N;
n = pow(2, ceil(log2(N)));
build();
for(int i=0; i<k; i++){
if(op[i] == 1){
setmax(0, n-1, left[i], right[i], height[i], i+1);
}
else{
setmin(0, n-1, left[i], right[i], height[i], i+1);
}
}
solve(finalheight);
}
/*
int main(){
int a[10];
const int v=8;
int b[v] = {1,2,2,1,1,2,1,2};
int c[v] = {1,4,3,0,2,6,7,4};
int d[v] = {8,9,6,5,2,7,9,7};
int e[v] = {4,1,5,3,5,0,1,2};
buildWall(10, 6, b, c, d, e, a);
for(int i=0; i<n_act; i++){cout << a[i] << ' ';}
}
*/
