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<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


template< typename OperatorMonoid >
struct DuelSegTree {
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

  int sz, height;
  vector< OperatorMonoid > lazy;
  const H h;
  const OperatorMonoid OM0;


  DuelSegTree(int n, const H h, const OperatorMonoid OM0)
      : h(h), OM0(OM0) {
    sz = 1;
    height = 0;
    while(sz < n) sz <<= 1, height++;
    lazy.assign(2 * sz, OM0);
  }

  inline void propagate(int k) {
    if(lazy[k] != OM0) {
      lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      lazy[k] = OM0;
    }
  }

  inline void thrust(int k) {
    for(int i = height; i > 0; i--) propagate(k >> i);
  }

  void update(int a, int b, const OperatorMonoid &x) {
    thrust(a += sz);
    thrust(b += sz - 1);
    for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if(l & 1) lazy[l] = h(lazy[l], x), ++l;
      if(r & 1) --r, lazy[r] = h(lazy[r], x);
    }
  }

  OperatorMonoid operator[](int k) {
    thrust(k += sz);
    return lazy[k];
  }
};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int n,q;
  cin>>n>>q;
  auto h=[](int a,int b){return b;};
  DuelSegTree<int> seg(n,h,inf);

  while(q--){
    int t;
    cin>>t;
    if(t==0){
      int l,r,x;
      cin>>l>>r>>x;
      seg.update(l,r+1,x);
    }else{
      int x;
      cin>>x;
      cout<<seg[x]<<endl;
    }
  }




}