#include<bits/stdc++.h>
using namespace std;
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class SnapshotArray{
int cur;
vector< int > t[ 50000 ] , v[ 50000 ] ;
public :
SnapshotArray( int length) {
int i;
cur = 0 ;
for ( i= 0 ; i< ( length) ; i++ ) {
v[ i] .push_back ( 0 ) ;
}
for ( i= 0 ; i< ( length) ; i++ ) {
t[ i] .push_back ( 0 ) ;
}
}
void set( int index, int val) {
if ( t[ index] [ t[ index] .size ( ) - 1 ] == cur) {
v[ index] [ v[ index] .size ( ) - 1 ] = val;
}
else {
v[ index] .push_back ( val) ;
t[ index] .push_back ( cur) ;
}
}
int snap( ) {
return cur++ ;
}
int get( int index, int snap_id) {
int i;
i = upper_bound( t[ index] .begin ( ) , t[ index] .end ( ) , snap_id) - t[ index] .begin ( ) ;
return v[ index] [ i- 1 ] ;
}
}
;
// cLay varsion 20190810-2
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// class SnapshotArray {
// public:
// vector<int> v[50000], t[50000];
// int cur;
//
// SnapshotArray(int length) {
// int i;
// cur = 0;
// rep(i,length) v[i].push_back(0);
// rep(i,length) t[i].push_back(0);
// }
//
// void set(int index, int val) {
// if(t[index][t[index].size()-1] == cur){
// v[index][v[index].size()-1] = val;
// } else {
// v[index].push_back(val);
// t[index].push_back(cur);
// }
// }
//
// int snap() {
// return cur++;
// }
//
// int get(int index, int snap_id) {
// int i;
// i = upper_bound(t[index].begin(), t[index].end(), snap_id) - t[index].begin();
// return v[index][i-1];
// }
// };
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICByZXR1cm4gMDsKfQojdW5kZWYgbWFpbgpjbGFzcyBTbmFwc2hvdEFycmF5ewogIGludCBjdXI7CiAgdmVjdG9yPGludD4gdFs1MDAwMF0sIHZbNTAwMDBdOwogIHB1YmxpYzoKICBTbmFwc2hvdEFycmF5KGludCBsZW5ndGgpewogICAgaW50IGk7CiAgICBjdXIgPSAwOwogICAgZm9yKGk9MDtpPChsZW5ndGgpO2krKyl7CiAgICAgIHZbaV0ucHVzaF9iYWNrKDApOwogICAgfQogICAgZm9yKGk9MDtpPChsZW5ndGgpO2krKyl7CiAgICAgIHRbaV0ucHVzaF9iYWNrKDApOwogICAgfQogIH0KICB2b2lkIHNldChpbnQgaW5kZXgsIGludCB2YWwpewogICAgaWYodFtpbmRleF1bdFtpbmRleF0uc2l6ZSgpLTFdID09IGN1cil7CiAgICAgIHZbaW5kZXhdW3ZbaW5kZXhdLnNpemUoKS0xXSA9IHZhbDsKICAgIH0KICAgIGVsc2V7CiAgICAgIHZbaW5kZXhdLnB1c2hfYmFjayh2YWwpOwogICAgICB0W2luZGV4XS5wdXNoX2JhY2soY3VyKTsKICAgIH0KICB9CiAgaW50IHNuYXAoKXsKICAgIHJldHVybiBjdXIrKzsKICB9CiAgaW50IGdldChpbnQgaW5kZXgsIGludCBzbmFwX2lkKXsKICAgIGludCBpOwogICAgaSA9IHVwcGVyX2JvdW5kKHRbaW5kZXhdLmJlZ2luKCksIHRbaW5kZXhdLmVuZCgpLCBzbmFwX2lkKSAtIHRbaW5kZXhdLmJlZ2luKCk7CiAgICByZXR1cm4gdltpbmRleF1baS0xXTsKICB9Cn0KOwovLyBjTGF5IHZhcnNpb24gMjAxOTA4MTAtMgoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyBjbGFzcyBTbmFwc2hvdEFycmF5IHsKLy8gcHVibGljOgovLyAgIHZlY3RvcjxpbnQ+IHZbNTAwMDBdLCB0WzUwMDAwXTsKLy8gICBpbnQgY3VyOwovLyAgIAovLyAgIFNuYXBzaG90QXJyYXkoaW50IGxlbmd0aCkgewovLyAgICAgaW50IGk7Ci8vICAgICBjdXIgPSAwOwovLyAgICAgcmVwKGksbGVuZ3RoKSB2W2ldLnB1c2hfYmFjaygwKTsKLy8gICAgIHJlcChpLGxlbmd0aCkgdFtpXS5wdXNoX2JhY2soMCk7Ci8vICAgfQovLyAgIAovLyAgIHZvaWQgc2V0KGludCBpbmRleCwgaW50IHZhbCkgewovLyAgICAgaWYodFtpbmRleF1bdFtpbmRleF0uc2l6ZSgpLTFdID09IGN1cil7Ci8vICAgICAgIHZbaW5kZXhdW3ZbaW5kZXhdLnNpemUoKS0xXSA9IHZhbDsKLy8gICAgIH0gZWxzZSB7Ci8vICAgICAgIHZbaW5kZXhdLnB1c2hfYmFjayh2YWwpOwovLyAgICAgICB0W2luZGV4XS5wdXNoX2JhY2soY3VyKTsKLy8gICAgIH0KLy8gICB9Ci8vICAgCi8vICAgaW50IHNuYXAoKSB7Ci8vICAgICByZXR1cm4gY3VyKys7Ci8vICAgfQovLyAgIAovLyAgIGludCBnZXQoaW50IGluZGV4LCBpbnQgc25hcF9pZCkgewovLyAgICAgaW50IGk7Ci8vICAgICBpID0gdXBwZXJfYm91bmQodFtpbmRleF0uYmVnaW4oKSwgdFtpbmRleF0uZW5kKCksIHNuYXBfaWQpIC0gdFtpbmRleF0uYmVnaW4oKTsKLy8gICAgIHJldHVybiB2W2luZGV4XVtpLTFdOwovLyAgIH0KLy8gfTsK