Problem: Write a program which manipulates a sequence A = {a0, a1, . . . , an−1} with the following operations:

* update(s, t, x): change as, as+1, ..., at to x.
* find(i): output the value of ai.



Note that the initial values of ai (i = 0, 1, . . . , n−1) are 231-1.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 0 ≤ s ≤ t < n
* 0 ≤ i < n
* 0 ≤ x < 231−1

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 i


The first digit represents the type of the query. '0' denotes update(s, t, x) and '1' denotes find(i).

Output

For each find operation, print the value.

Examples

Input

3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1


Output

1
3


Input

1 3
1 0
0 0 0 5
1 0


Output

2147483647
5

Solution (in CPP):

Solution:
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>

#define INF_LL 9000000000000000000
#define INF 2000000000

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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

class RangeSeg{
	int n;
	vector<ll> data, lazy;
public:
	RangeSeg(int n_){
		n = 1;
		while(n < n_) n <<= 1;
		REP(i, n*2-1){
			data.push_back(-1);
			lazy.push_back(-1);
		}
	}

	void push(int l, int r, int k){
		if(lazy[k] != -1){
			data[k] = lazy[k];
			if(r - l > 1){
				lazy[k*2+1] = lazy[k];
				lazy[k*2+2] = lazy[k];
			}
			lazy[k] = -1;
		}
	}

	void update(int s, int t, int l, int r, int k, int x){
		push(l, r, k);
		if(s <= l && r <= t){
			lazy[k] = x;
			push(l, r, k);
		}else if(l < t && s < r){
			update(s, t, (l+r)/2, r, k*2+2, x);
			update(s, t, l, (l+r)/2, k*2+1, x);
		}
	}

	void update(int s, int t, int x){
		update(s, t, 0, n, 0, x);
	}
	
	void show(){
		int i = 0;
		int en = 1;
		while(i < n*2-1){
			cout << "(" << data[i] << ", " << lazy[i] << ") ";
			if(i == en*2-2){
				cout << endl;
				en *= 2;
			}
			i++;
		}
	}

	ll find(int l, int r, int k, int i){
		push(l, r, k);
		if(r-l == 1){
			return data[k];
		}
		if(l <= i && i <= r){
			if((l+r)/2 <= i){
				return find((l+r)/2, r, k*2+2, i);
			}else{
				return find(l, (l+r)/2, k*2+1, i);
			}
		}else{
			return -1;
		}
	}

	ll find(int i){
		return find(0, n, 0, i);
	}	
};

int main(void){
	int n, q;
	cin >> n >> q;
	RangeSeg rs(n);
	REP(i, q){
		int com;
		cin >> com;
		if(com == 0){
			int s, t, x;
			cin >> s >> t >> x;
			rs.update(s, t+1, x);
		}else{
			int x;
			cin >> x;
			x = rs.find(x);
			if(x == -1)
				cout << ((ll)1 << 31)-1 << endl;
			else
				cout << x << endl;
		}
	}
}