<Patel Segment Tree> TEMPLATE

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>

#define read1(a) int a; scanf("%d", &a)
#define read2(a, b) int a, b; scanf("%d %d", &a, &b)
#define read3(a, b, c) int a, b, c; scanf("%d %d %d", &a, &b, &c)

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)

#define readgi(n) F0R(i, n) { scanf("%d", &arr[i]); }
#define readgs(n) F0R(i, n) { scanf(" %c", &arr[i]); }

#define f first
#define s second

const int MOD = 1000000007;
const int MAX = 100005;

int arr[MAX];
int lazy[4*MAX];
int maxi[4*MAX];

void push(int node) {
	if (lazy[node]){
		lazy[2*node]=max(lazy[2*node],lazy[node]);
		lazy[2*node+1] = max(lazy[2*node+1], lazy[node]);
		maxi[node] = max(maxi[node], lazy[node]);
		lazy[node] = 0;
	}
}
void update (int start, int end, int i, int j, int node, int v){
	push(node);
	if (start>j||end<i)return;
	if(start>=i&&end<=j){
		lazy[node] = v; push(node); return;
	}
	update (start, (start+end)/2, i, j, 2*node, v);
	update ((start+end)/2+1, end, i, j, 2*node+1, v);
	maxi[node] = max(maxi[2*node], maxi[2*node+1]);
}
int query (int start, int end, int i, int j, int node){
	push(node); if (start>j||end<i) return 0; if (start>=i && end<=j) return maxi[node];
	int f = query (start, (start+end)/2, i, j, 2*node);
	int s = query ((start+end)/2+1, end, i, j, 2*node+1); return max(f, s);
}
int main(){

}