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

struct SegmentTree{
	typedef pair<int, int> pii;
    static const int sz = 1 << 17; // sz > MAX_SIZE
    static const int inf = 1e9+7;
    static pii merge(pii a, pii b){
        if(a.first > b.first) return a;
        if(a.first < b.first) return b;
        if(a.second < b.second) return a;
        return b;
    }
    int n;
    pii tree[sz << 1];
    int lazy[sz << 1];
    bool haveLazy[sz << 1];
    void init(int _n){
    	n = _n;
    	memset(haveLazy, 0, sizeof haveLazy);
        for(int i=0; i<n; i++) tree[i+sz] = pii(-inf, i);
        for(int i=sz-1; i>=1; i--) tree[i] = merge(tree[i*2], tree[i*2+1]);
    }
    void push(int node, int s, int e){
    	if(!haveLazy[node]) return;
    	tree[node] = pii(lazy[node], s);
    	if(s != e){
    		lazy[node*2] = lazy[node];
    		lazy[node*2+1] = lazy[node];
    		haveLazy[node*2] = 1;
    		haveLazy[node*2+1] = 1;
    	}
    	haveLazy[node] = 0;
    }
    void update(int l, int r, int v, int node, int s, int e){
    	push(node, s, e);
    	if(r < s || e < l) return;
    	if(l <= s && e <= r){
    		lazy[node] = v;
    		haveLazy[node] = 1;
    		push(node, s, e);
    		return;
    	}
    	int m = (s + e) / 2;
    	update(l, r, v, node*2, s, m);
    	update(l, r, v, node*2+1, m+1, e);
    	tree[node] = merge(tree[node*2], tree[node*2+1]);
    }
    void update(int l, int r, int v){ update(l, r, v, 1, 0, n-1); }
    pii query(int l, int r, int node, int s, int e){
    	push(node, s, e);
    	if(r < s || e < l) return pii(-inf, inf);
    	if(l <= s && e <= r) return tree[node];
    	int m = (s + e) / 2;
    	pii t1 = query(l, r, node*2, s, m);
    	pii t2 = query(l, r, node*2+1, m+1, e);
    	return merge(t1, t2);
    }
    int query(int l, int r){ return query(l, r, 1, 0, n-1).second; }
};
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int initialArray[4] = {5, 4, 3, 9};
    SegmentTree ST; ST.init(4);
    for(int i=0; i<4; i++) ST.update(i, i, initialArray[i]);
 
    ST.update(1, 2, 4); // first query (2, 3, 4), [5, 4, 4, 9]
    for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
    cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 3
    ST.update(0, 3, 100); // first query (0, 100), [100, 100, 100, 100]
    for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
    cout << ST.query(0, 3) << "\n"; // second query (0, 3), expected : 0
    ST.update(1, 2, 4); // first query (3, 100), [100, 4, 4, 100]
    for(int i=0; i<4; i++) cout << ST.query(i, i, 1, 0, 4-1).first << " "; cout << "\n";
    cout << ST.query(0, 1) << "\n"; // second query (0, 1), expected : 0
}