loj数列分块入门（下）

typedef pair<int,int> PII;
ll n,a[maxn];
ll blk,lazy[maxn],b[maxn],sum[maxn],tot;
vector<int> vet[maxn];
void reBuild() {
  int p = 0;
  for(int i=1; i<=tot; i++) {
    for(int val : vet[i]) {
      a[++p] = val;
    }
    vet[i].clear();
  }
  blk = sqrt(p);
  tot = ceil(1.0 * p / blk);
  for(int i=1; i<=p; i++) {
    b[i] = (i - 1) / blk + 1;
    vet[b[i]].push_back(a[i]);
  }
}
PII query(ll r) {
  for(int i=1; i<=tot; i++) {
    if(r > vet[i].size()) r -= vet[i].size();
    else return {i,r-1};
  }
}
void insert(ll l,ll r) {
  PII t = query(l);
  vet[t.first].insert(vet[t.first].begin() + t.second,r);
  if(vet[t.first].size() > 10 * blk) reBuild();
}
int main() {
  n = read;
  for(int i=1; i<=n; i++) a[i] = read;
  blk = sqrt(n);
  tot = ceil(1.0*n / blk);
  for(int i=1; i<=n; i++) {
    b[i] = (i - 1) / blk + 1;
    vet[b[i]].push_back(a[i]);
  }
  for(int i=1; i<=n; i++) {
    int op = read,l = read,r = read,c = read;
    if(op == 0) insert(l,r);
    else {
      PII t = query(r);
      printf("%d\n",vet[t.first][t.second]);
    }
  }
  return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
2
3
**/

const int maxn = 1e5 + 7;
const int mod = 10007;
ll n,a[maxn];
ll blk,add[maxn],b[maxn],sum[maxn],mul[maxn];
void pushDown(int id) {
  for(int i=(id-1) * blk + 1; i<=min(id * blk,n); i++) {
    a[i] = (a[i] * mul[id] % mod + add[id] + mod) % mod;
  }
  mul[id] = 1;
  add[id] = 0;
}
void add_mul(int l,int r,ll val,int op) {
  pushDown(b[l]);
  for(int i=l; i<=min(b[l]*blk,1LL*r); i++) {
    if(op) a[i] = (a[i] * val) % mod;
    else a[i] = (a[i] + val) % mod;
  }
  if(b[l] != b[r]) {
    pushDown(b[r]);
    for(int i=(b[r]-1)*blk + 1; i<=r; i++) {
      if(op) a[i] = (a[i] * val) % mod;
      else a[i] = (a[i] + val) % mod;
    }
  }
  for(int i=b[l]+1; i<=b[r]-1; i++) {
    if(op) mul[i] = (mul[i] * val) % mod,add[i] = (add[i] * val) % mod;
    else add[i] = (add[i] + val) % mod;
  }
}
ll query(int r) {
  ll ret = 0;
  ret = (a[r] * mul[b[r]] % mod + add[b[r]]) % mod;
  return ret;
}
int main() {
  n = read;
  for(int i=1; i<=n; i++) a[i] = read;
  blk = sqrt(n);
  for(int i=1; i<=n; i++) {
    b[i] = (i - 1) / blk + 1;
    mul[b[i]] = 1;
    add[b[i]] = 0;
  }
  for(int i=1; i<=n; i++) {
    int op = read,l = read,r = read,c = read;
    if(op == 2) {
      printf("%lld\n",query(r));
    } else {
      add_mul(l,r,c,op);
    }
  }
  return 0;
}
/**
7
1 2 2 3 9 3 2
0 1 3 1
2 1 3 1
1 1 4 4
0 1 7 2
1 2 6 4
1 1 6 5
2 2 6 4
3
100
**/

ll n,a[maxn];
ll blk,add[maxn],b[maxn],upd[maxn];
void reset(int id) {
  if(upd[id] == -1) return ;
  for(int i=(id-1) * blk+1; i<=min(id*blk,n); i++) {
    a[i] = upd[id];
  }
  upd[id] = -1;
}
ll getSet(int l,int r,ll val) {
  ll ans = 0;
  reset(b[l]);
  for(int i=l; i<=min(b[l]*blk,1LL*r); i++) {
    ans += a[i] == val;
    a[i] = val;
  }
  if(b[l] != b[r]) {
    reset(b[r]);
    for(int i=(b[r]-1)*blk + 1; i<=r; i++) {
      ans += a[i] == val;
      a[i] = val;
    }
  }
  for(int i=b[l]+1; i<=b[r]-1; i++) {
    if(upd[i] == -1) {
      for(int j=(i-1)*blk+1; j<=i*blk; j++) {
        ans += a[j] == val;
      }
    } else ans += upd[i] == val?blk:0;
    upd[i] = val;
  }
  return ans;
}
int main() {
  n = read;
  for(int i=1; i<=n; i++) a[i] = read;
  blk = sqrt(n);
  for(int i=1; i<=n; i++) {
    b[i] = (i - 1) / blk + 1;
    upd[b[i]] = -1;
  }
  for(int i=1; i<=n; i++) {
    int l = read,r = read,c = read;
    ll ans = getSet(l,r,c);
    printf("%lld\n",ans);
  }
  return 0;
}
/**
4
1 2 2 4
1 3 1
1 4 4
1 2 2
1 4 2
1
1
0
2
**/

#define Clear(x,val) memset(x,val,sizeof x)
ll n,a[maxn],ans[2007][2007],b[maxn],blk,cnt[maxn],num;
vector<int> vet[maxn];
map<int,int> vis,val;
void get(int id) {
  Clear(cnt,0);
  int mx = 0,res = 0;
  for(int i=(id-1) * blk + 1; i<=n; i++) {
    int to = b[i];///cur is the b[i]-th blk
    ++ cnt[a[i]];/// the amt ++
    if(cnt[a[i]] > mx || (cnt[a[i]] == mx && val[a[i]] < val[res])) {
      res = a[i];/// set the cur mx value
      mx = cnt[a[i]];
    }
    ans[id][to] = res;/// from blk id -> blk to  the ans = res
  }
}
int getNum(int l,int r,int x) {
  int ret = 0;
  ret = upper_bound(vet[x].begin(),vet[x].end(),r) - lower_bound(vet[x].begin(),vet[x].end(),l);/// amount of x
  return ret;
}
ll query(int l,int r) {
  ll ret = ans[b[l] + 1][b[r] - 1];// center blks
  int mx = getNum(l,r,ret);// get the amount of this
  for(int i=l; i<=min(r*1LL,b[l]*blk); i++) {
    int amt = getNum(l,r,a[i]);
    if(amt > mx || (amt == mx && val[a[i]] < val[ret])) { ///val[ret]
      ret = a[i];
      mx = amt;
    }
  }
  if(b[l] != b[r]) {
    for(int i = (b[r] - 1) * blk + 1; i<=r; i++) {
      int amt = getNum(l,r,a[i]);
      if(amt > mx || (amt == mx && val[a[i]] < val[ret])) {
        ret = a[i];
        mx = amt;
      }
    }
  }
  return val[ret];
}
int main() {
  n = read;
  blk = sqrt(n);
  blk = 80;
  for(int i=1; i<=n; i++) {
    a[i] = read;
    b[i] = (i - 1) / blk + 1;
    if(!vis[a[i]]) {
      vis[a[i]] = ++ num;
      val[num] = a[i];///¶ÔÓ¦ÏÂ
    }
    a[i] = vis[a[i]];
    vet[a[i]].push_back(i);
  }
  for(int i=1; i<=b[n]; i++) get(i); /// get the i-th blk
  for(int i=1; i<=n; i++) {
    int l = read,r = read;
    if(l > r) swap(l,r);
    ll ans = query(l,r);
    printf("%lld\n",ans);
  }
  return 0;
}
/**
4
1 2 2 4
1 2
1 4
2 4
3 4
1
2
2
2
**/