#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree< int ,null_type,less< int > ,rb_tree_tag,tree_order_statistics_node_update> Tree;
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
void fast_io( ) {
ios_base:: sync_with_stdio ( 0 ) ;
cin .tie ( NULL ) ;
cout .tie ( NULL ) ;
}
void io( string taskname) {
string fin = taskname + ".in" ;
string fout = taskname + ".out" ;
const char * FIN = fin.c_str ( ) ;
const char * FOUT = fout.c_str ( ) ;
freopen ( FIN, "r" , stdin ) ;
freopen ( FOUT, "w" , stdout ) ;
fast_io( ) ;
}
const int MAX = 1e5 + 5 ;
template < class T, int SZ> struct MaxSegTree {
T sum[ 2 * SZ] , mn[ 2 * SZ] , lazy[ 2 * SZ] ; // set SZ to a power of 2
void init( ) {
memset ( sum,0 ,sizeof sum) ;
memset ( mn,0 ,sizeof mn) ;
memset ( lazy,0 ,sizeof lazy) ;
}
void push( int ind, int L, int R) {
sum[ ind] + = ( R- L+ 1 ) * lazy[ ind] ;
mn[ ind] + = lazy[ ind] ;
if ( L ! = R) lazy[ 2 * ind] + = lazy[ ind] , lazy[ 2 * ind+ 1 ] + = lazy[ ind] ;
lazy[ ind] = 0 ;
}
void pull( int ind) {
sum[ ind] = sum[ 2 * ind] + sum[ 2 * ind+ 1 ] ;
mn[ ind] = max( mn[ 2 * ind] ,mn[ 2 * ind+ 1 ] ) ;
}
void build( ) {
for ( int i = SZ- 1 ; i>= 0 ; i-- ) {
pull( i) ;
}
}
T qsum( int lo, int hi, int ind = 1 , int L = 0 , int R = SZ- 1 ) {
push( ind,L,R) ;
if ( lo > R || L > hi) return 0 ;
if ( lo <= L && R <= hi) return sum[ ind] ;
int M = ( L+ R) / 2 ;
return qsum( lo,hi,2 * ind,L,M) + qsum( lo,hi,2 * ind+ 1 ,M+ 1 ,R) ;
}
T qmax( int lo, int hi, int ind = 1 , int L = 0 , int R = SZ- 1 ) {
push( ind,L,R) ;
if ( lo > R || L > hi) return 0 ;
if ( lo <= L && R <= hi) return mn[ ind] ;
int M = ( L+ R) / 2 ;
return max( qmax( lo,hi,2 * ind,L,M) , qmax( lo,hi,2 * ind+ 1 ,M+ 1 ,R) ) ;
}
void upd( int lo, int hi, ll inc, int ind = 1 , int L = 0 , int R = SZ- 1 ) {
push( ind,L,R) ;
if ( hi < L || R < lo) return ;
if ( lo <= L && R <= hi) {
lazy[ ind] = inc;
push( ind,L,R) ;
return ;
}
int M = ( L+ R) / 2 ;
upd( lo,hi,inc,2 * ind,L,M) ; upd( lo,hi,inc,2 * ind+ 1 ,M+ 1 ,R) ;
pull( ind) ;
}
} ;
template < int SZ> struct DSU{
int par[ SZ] , sz[ SZ] ;
void init( ) {
for ( int i = 0 ; i< SZ; i++ ) {
par[ i] = i;
sz[ i] = 1 ;
}
}
int get( int x) {
if ( par[ x] ! = x) {
par[ x] = get( par[ x] ) ;
}
return par[ x] ;
}
bool unite( int x, int y) {
x = get( x) ;
y = get( y) ;
if ( x == y) {
return false ;
}
if ( sz[ x] < sz[ y] ) {
swap( x, y) ;
}
sz[ x] + = sz[ y] ;
par[ y] = x;
return true ;
}
} ;
unordered_map< int , int > seg; //turns original ordering into seg tree ordering
unordered_map< int , int > comp; //finds component in dsu into the index in the forest
vector< pii> queries; //holds queries
vector< vi> forest; //forest of nodes
vector< pii> bounds;
DSU< MAX> d;
MaxSegTree< int , ( 1 << 17 ) > mst;
vi adj[ MAX] ;
int vis [ MAX] ;
int sub [ MAX] ;
int depth [ MAX] ;
int id [ MAX] ;
int isRoot[ MAX] ;
void dfs( int src, int tree) {
sub[ src] = tree;
vis[ src] = 1 ;
for ( int neigh: adj[ src] ) {
if ( vis[ neigh] == 0 ) {
if ( tree == - 1 ) {
depth[ neigh] = depth[ src] + 1 ;
dfs( neigh, neigh) ;
}
else {
depth[ neigh] = depth[ src] + 1 ;
dfs( neigh, tree) ;
}
}
}
}
int main( ) {
io( "newbarn" ) ;
int q;
cin >> q;
d.init ( ) ;
int cur = 0 ; //label of nodes
f0r( i, q) {
char c;
int p;
cin >> c >> p;
p-- ;
if ( c == 'B' ) {
if ( p ! = - 2 ) {
d.unite ( p, cur) ;
adj[ cur] .eb ( p) ;
adj[ p] .eb ( cur) ;
}
queries.eb ( mp( 0 , cur) ) ;
cur++ ;
}
else {
queries.eb ( mp( 1 , p) ) ;
}
}
int n = cur; //number of nodes
int c = 0 ;
f0r( i, n) {
id[ i] = - 1 ;
}
forest.resize ( n+ 5 ) ;
f0r( i, n) {
if ( id[ d.get ( i) ] == - 1 ) {
id[ d.get ( i) ] = c;
forest[ c] .eb ( i) ;
c++ ;
}
else {
forest[ id[ d.get ( i) ] ] .eb ( i) ;
}
}
cur = 0 ;
f0r( i, sz( forest) ) {
int st = cur;
if ( sz( forest[ i] ) == 0 ) {
continue ;
}
comp[ d.get ( forest[ i] [ 0 ] ) ] = i;
f0r( j, sz( forest[ i] ) ) {
seg[ forest[ i] [ j] ] = cur;
if ( j == sz( forest[ i] ) - 1 ) {
bounds.eb ( mp( st, cur) ) ;
}
cur++ ;
}
}
f0r( i, sz( forest) ) {
if ( sz( forest[ i] ) == 0 ) {
continue ;
}
if ( vis[ forest[ i] [ 0 ] ] == 1 ) {
continue ;
}
dfs( forest[ i] [ 0 ] , - 1 ) ;
isRoot[ forest[ i] [ 0 ] ] = 1 ;
}
mst.init ( ) ;
f0r( i, sz( queries) ) {
int type = queries[ i] .f ;
int p = queries[ i] .s ;
if ( type == 0 ) {
if ( p < 0 ) {
continue ;
}
int loc = sub[ p] ;
if ( loc< 0 ) {
continue ;
}
int amount = mst.qmax ( seg[ loc] , seg[ loc] ) ;
if ( amount< depth[ p] ) {
mst.upd ( seg[ loc] , seg[ loc] , depth[ p] - amount) ;
}
}
else {
int idx = comp[ d.get ( p) ] ;
int l = bounds[ idx] .f ;
int r = bounds[ idx] .s ;
if ( isRoot[ p] == 1 ) {
cout << mst.qmax ( l, r) << endl;
continue ;
}
int loc = sub[ p] ;
int ans = 0 ;
if ( seg[ loc] > l) {
ans = depth[ p] + mst.qmax ( l, seg[ loc] - 1 ) ;
}
if ( seg[ loc] < r) {
ans = max( ans, depth[ p] + mst.qmax ( seg[ loc] + 1 , r) ) ;
}
int chain = max( mst.qmax ( seg[ loc] , seg[ loc] ) - depth[ p] , depth[ p] ) ;
cout << max( ans, chain) << endl;
}
}
return 0 ;
}
I3ByYWdtYSBjb21tZW50KGxpbmtlciwgIi9zdGFjazoyMDAwMDAwMDAiKQovLyNwcmFnbWEgR0NDIG9wdGltaXplKCJPZmFzdCIpCi8vI3ByYWdtYSBHQ0MgdGFyZ2V0KCJzc2Usc3NlMixzc2UzLHNzc2UzLHNzZTQscG9wY250LGFibSxtbXgsYXZ4LHR1bmU9bmF0aXZlIikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPMyIpCiNwcmFnbWEgR0NDIHRhcmdldCAoInNzZTQiKQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwp0eXBlZGVmIHRyZWU8aW50LG51bGxfdHlwZSxsZXNzPGludD4scmJfdHJlZV90YWcsdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPiBUcmVlOwoKI2RlZmluZSBzeih4KSAoaW50KSh4KS5zaXplKCkKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBsZCBsb25nIGRvdWJsZQojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGViIGVtcGxhY2VfYmFjawojZGVmaW5lIHBpaSBwYWlyIDxpbnQsIGludD4KI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIGYgZmlyc3QKI2RlZmluZSBzIHNlY29uZAojZGVmaW5lIGxiIGxvd2VyX2JvdW5kCiNkZWZpbmUgdWIgdXBwZXJfYm91bmQKI2RlZmluZSBhbGwoeCkgeC5iZWdpbigpLCB4LmVuZCgpCiNkZWZpbmUgdnBpIHZlY3RvcjxwYWlyPGludCwgaW50Pj4KCiNkZWZpbmUgZjByKGksYSkgZm9yKGludCBpPTA7aTxhO2krKykKI2RlZmluZSBmMXIoaSxhLGIpIGZvcihpbnQgaT1hO2k8YjtpKyspCgp2b2lkIGZhc3RfaW8oKXsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKE5VTEwpOwogICAgY291dC50aWUoTlVMTCk7Cn0Kdm9pZCBpbyhzdHJpbmcgdGFza25hbWUpewogICAgc3RyaW5nIGZpbiA9IHRhc2tuYW1lICsgIi5pbiI7CiAgICBzdHJpbmcgZm91dCA9IHRhc2tuYW1lICsgIi5vdXQiOwogICAgY29uc3QgY2hhciogRklOID0gZmluLmNfc3RyKCk7CiAgICBjb25zdCBjaGFyKiBGT1VUID0gZm91dC5jX3N0cigpOwogICAgZnJlb3BlbihGSU4sICJyIiwgc3RkaW4pOwogICAgZnJlb3BlbihGT1VULCAidyIsIHN0ZG91dCk7CiAgICBmYXN0X2lvKCk7Cn0KY29uc3QgaW50IE1BWCA9IDFlNSs1Owp0ZW1wbGF0ZTxjbGFzcyBULCBpbnQgU1o+IHN0cnVjdCBNYXhTZWdUcmVlIHsKICAgIFQgc3VtWzIqU1pdLCBtblsyKlNaXSwgbGF6eVsyKlNaXTsgLy8gc2V0IFNaIHRvIGEgcG93ZXIgb2YgMgogICAgdm9pZCBpbml0KCkgewogICAgICAgIG1lbXNldCAoc3VtLDAsc2l6ZW9mIHN1bSk7CiAgICAgICAgbWVtc2V0IChtbiwwLHNpemVvZiBtbik7CiAgICAgICAgbWVtc2V0IChsYXp5LDAsc2l6ZW9mIGxhenkpOwogICAgfQogICAgdm9pZCBwdXNoKGludCBpbmQsIGludCBMLCBpbnQgUikgewogICAgICAgIHN1bVtpbmRdICs9IChSLUwrMSkqbGF6eVtpbmRdOwogICAgICAgIG1uW2luZF0gKz0gbGF6eVtpbmRdOwogICAgICAgIGlmIChMICE9IFIpIGxhenlbMippbmRdICs9IGxhenlbaW5kXSwgbGF6eVsyKmluZCsxXSArPSBsYXp5W2luZF07CiAgICAgICAgbGF6eVtpbmRdID0gMDsKICAgIH0KICAgIHZvaWQgcHVsbChpbnQgaW5kKSB7CiAgICAgICAgc3VtW2luZF0gPSBzdW1bMippbmRdK3N1bVsyKmluZCsxXTsKICAgICAgICBtbltpbmRdID0gbWF4KG1uWzIqaW5kXSxtblsyKmluZCsxXSk7CiAgICB9CiAgICB2b2lkIGJ1aWxkKCkgewogICAgICAgIGZvcihpbnQgaSA9IFNaLTE7IGk+PTA7IGktLSl7CiAgICAgICAgICAgIHB1bGwoaSk7CiAgICAgICAgfQogICAgfQoKICAgIFQgcXN1bShpbnQgbG8sIGludCBoaSwgaW50IGluZCA9IDEsIGludCBMID0gMCwgaW50IFIgPSBTWi0xKSB7CiAgICAgICAgcHVzaChpbmQsTCxSKTsKICAgICAgICBpZiAobG8gPiBSIHx8IEwgPiBoaSkgcmV0dXJuIDA7CiAgICAgICAgaWYgKGxvIDw9IEwgJiYgUiA8PSBoaSkgcmV0dXJuIHN1bVtpbmRdOwoKICAgICAgICBpbnQgTSA9IChMK1IpLzI7CiAgICAgICAgcmV0dXJuIHFzdW0obG8saGksMippbmQsTCxNKSArIHFzdW0obG8saGksMippbmQrMSxNKzEsUik7CiAgICB9CgogICAgVCBxbWF4KGludCBsbywgaW50IGhpLCBpbnQgaW5kID0gMSwgaW50IEwgPSAwLCBpbnQgUiA9IFNaLTEpIHsKICAgICAgICBwdXNoKGluZCxMLFIpOwogICAgICAgIGlmIChsbyA+IFIgfHwgTCA+IGhpKSByZXR1cm4gMDsKICAgICAgICBpZiAobG8gPD0gTCAmJiBSIDw9IGhpKSByZXR1cm4gbW5baW5kXTsKCiAgICAgICAgaW50IE0gPSAoTCtSKS8yOwogICAgICAgIHJldHVybiBtYXgocW1heChsbyxoaSwyKmluZCxMLE0pLCBxbWF4KGxvLGhpLDIqaW5kKzEsTSsxLFIpKTsKICAgIH0KCiAgICB2b2lkIHVwZChpbnQgbG8sIGludCBoaSwgbGwgaW5jLCBpbnQgaW5kID0gMSwgaW50IEwgPSAwLCBpbnQgUiA9IFNaLTEpIHsKICAgICAgICBwdXNoKGluZCxMLFIpOwogICAgICAgIGlmIChoaSA8IEwgfHwgUiA8IGxvKSByZXR1cm47CiAgICAgICAgaWYgKGxvIDw9IEwgJiYgUiA8PSBoaSkgewogICAgICAgICAgICBsYXp5W2luZF0gPSBpbmM7CiAgICAgICAgICAgIHB1c2goaW5kLEwsUik7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CgogICAgICAgIGludCBNID0gKEwrUikvMjsKICAgICAgICB1cGQobG8saGksaW5jLDIqaW5kLEwsTSk7IHVwZChsbyxoaSxpbmMsMippbmQrMSxNKzEsUik7CiAgICAgICAgcHVsbChpbmQpOwogICAgfQp9Owp0ZW1wbGF0ZTxpbnQgU1o+IHN0cnVjdCBEU1V7CiAgICBpbnQgcGFyW1NaXSwgc3pbU1pdOwogICAgdm9pZCBpbml0KCl7CiAgICAgICAgZm9yKGludCBpID0gMDsgaTxTWjsgaSsrKXsKICAgICAgICAgICAgcGFyW2ldID0gaTsKICAgICAgICAgICAgc3pbaV0gPSAxOwogICAgICAgIH0KICAgIH0KICAgIGludCBnZXQoaW50IHgpewogICAgICAgIGlmKHBhclt4XSAhPSB4KXsKICAgICAgICAgICAgcGFyW3hdID0gZ2V0KHBhclt4XSk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBwYXJbeF07CiAgICB9CiAgICBib29sIHVuaXRlKGludCB4LCBpbnQgeSl7CiAgICAgICAgeCA9IGdldCh4KTsKICAgICAgICB5ID0gZ2V0KHkpOwogICAgICAgIGlmKHggPT0geSl7CiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICB9CiAgICAgICAgaWYoc3pbeF0gPCBzelt5XSl7CiAgICAgICAgICAgIHN3YXAoeCwgeSk7CiAgICAgICAgfQogICAgICAgIHN6W3hdICs9IHN6W3ldOwogICAgICAgIHBhclt5XSA9IHg7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9Cn07CnVub3JkZXJlZF9tYXA8aW50LCBpbnQ+IHNlZzsgLy90dXJucyBvcmlnaW5hbCBvcmRlcmluZyBpbnRvIHNlZyB0cmVlIG9yZGVyaW5nCnVub3JkZXJlZF9tYXA8aW50LCBpbnQ+IGNvbXA7IC8vZmluZHMgY29tcG9uZW50IGluIGRzdSBpbnRvIHRoZSBpbmRleCBpbiB0aGUgZm9yZXN0Cgp2ZWN0b3I8cGlpPiBxdWVyaWVzOyAvL2hvbGRzIHF1ZXJpZXMKdmVjdG9yPHZpPiBmb3Jlc3Q7IC8vZm9yZXN0IG9mIG5vZGVzCnZlY3RvcjxwaWk+IGJvdW5kczsKCkRTVTxNQVg+IGQ7Ck1heFNlZ1RyZWU8aW50LCAoMTw8MTcpPiBtc3Q7Cgp2aSBhZGpbTUFYXTsKaW50IHZpcyBbTUFYXTsKaW50IHN1YiBbTUFYXTsKaW50IGRlcHRoIFtNQVhdOwppbnQgaWQgW01BWF07CmludCBpc1Jvb3RbTUFYXTsKCnZvaWQgZGZzKGludCBzcmMsIGludCB0cmVlKXsKICAgIHN1YltzcmNdID0gdHJlZTsKICAgIHZpc1tzcmNdID0gMTsKICAgIGZvcihpbnQgbmVpZ2g6IGFkaltzcmNdKXsKICAgICAgICBpZih2aXNbbmVpZ2hdID09IDApewogICAgICAgICAgICBpZih0cmVlID09IC0xKXsKICAgICAgICAgICAgICAgIGRlcHRoW25laWdoXSA9IGRlcHRoW3NyY10gKyAxOwogICAgICAgICAgICAgICAgZGZzKG5laWdoLCBuZWlnaCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgIGRlcHRoW25laWdoXSA9IGRlcHRoW3NyY10gKzE7CiAgICAgICAgICAgICAgICBkZnMobmVpZ2gsIHRyZWUpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CmludCBtYWluKCl7CiAgICBpbygibmV3YmFybiIpOwogICAgaW50IHE7CiAgICBjaW4gPj4gcTsKICAgIGQuaW5pdCgpOwogICAgaW50IGN1ciA9IDA7Ly9sYWJlbCBvZiBub2RlcwogICAgZjByKGksIHEpewogICAgICAgIGNoYXIgYzsKICAgICAgICBpbnQgcDsKICAgICAgICBjaW4gPj4gYyA+PiBwOwogICAgICAgIHAtLTsKICAgICAgICBpZihjID09ICdCJyl7CiAgICAgICAgICAgIGlmKHAgIT0gLTIpewogICAgICAgICAgICAgICAgZC51bml0ZShwLCBjdXIpOwogICAgICAgICAgICAgICAgYWRqW2N1cl0uZWIocCk7CiAgICAgICAgICAgICAgICBhZGpbcF0uZWIoY3VyKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBxdWVyaWVzLmViKG1wKDAsIGN1cikpOwogICAgICAgICAgICBjdXIrKzsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgcXVlcmllcy5lYihtcCgxLCBwKSk7CiAgICAgICAgfQogICAgfQogICAgaW50IG4gPSBjdXI7IC8vbnVtYmVyIG9mIG5vZGVzCiAgICBpbnQgYyA9IDA7CiAgICBmMHIoaSwgbil7CiAgICAgICAgaWRbaV0gPSAtMTsKICAgIH0KICAgIGZvcmVzdC5yZXNpemUobis1KTsKICAgIGYwcihpLCBuKXsKICAgICAgICBpZihpZFtkLmdldChpKV0gPT0gLTEpewogICAgICAgICAgICBpZFtkLmdldChpKV0gPSBjOwogICAgICAgICAgICBmb3Jlc3RbY10uZWIoaSk7CiAgICAgICAgICAgIGMrKzsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgZm9yZXN0W2lkW2QuZ2V0KGkpXV0uZWIoaSk7CiAgICAgICAgfQogICAgfQogICAgY3VyID0gMDsKICAgIGYwcihpLCBzeihmb3Jlc3QpKXsKICAgICAgICBpbnQgc3QgPSBjdXI7CiAgICAgICAgaWYoc3ooZm9yZXN0W2ldKSA9PSAwKXsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGNvbXBbZC5nZXQoZm9yZXN0W2ldWzBdKV0gPSBpOwogICAgICAgIGYwcihqLCBzeihmb3Jlc3RbaV0pKXsKICAgICAgICAgICAgc2VnW2ZvcmVzdFtpXVtqXV0gPSBjdXI7CiAgICAgICAgICAgIGlmKGogPT0gc3ooZm9yZXN0W2ldKSAtIDEpewogICAgICAgICAgICAgICAgYm91bmRzLmViKG1wKHN0LCBjdXIpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBjdXIrKzsKICAgICAgICB9CgogICAgfQogICAgZjByKGksIHN6KGZvcmVzdCkpewogICAgICAgIGlmKHN6KGZvcmVzdFtpXSkgPT0gMCl7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICBpZih2aXNbZm9yZXN0W2ldWzBdXSA9PSAxKXsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGRmcyhmb3Jlc3RbaV1bMF0sIC0xKTsKICAgICAgICBpc1Jvb3RbZm9yZXN0W2ldWzBdXSA9IDE7CiAgICB9CgogICAgbXN0LmluaXQoKTsKICAgIGYwcihpLCBzeihxdWVyaWVzKSl7CiAgICAgICAgaW50IHR5cGUgPSBxdWVyaWVzW2ldLmY7CiAgICAgICAgaW50IHAgPSBxdWVyaWVzW2ldLnM7CiAgICAgICAgaWYodHlwZSA9PSAwKXsKICAgICAgICAgICAgaWYocCA8MCl7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpbnQgbG9jID0gc3ViW3BdOwogICAgICAgICAgICBpZihsb2M8MCl7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpbnQgYW1vdW50ID0gbXN0LnFtYXgoc2VnW2xvY10sIHNlZ1tsb2NdKTsKICAgICAgICAgICAgaWYoYW1vdW50PGRlcHRoW3BdKXsKICAgICAgICAgICAgICAgIG1zdC51cGQoc2VnW2xvY10sIHNlZ1tsb2NdLCBkZXB0aFtwXSAtIGFtb3VudCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgaW50IGlkeCA9IGNvbXBbZC5nZXQocCldOwogICAgICAgICAgICBpbnQgbCA9IGJvdW5kc1tpZHhdLmY7CiAgICAgICAgICAgIGludCByID0gYm91bmRzW2lkeF0uczsKICAgICAgICAgICAgaWYoaXNSb290W3BdID09IDEpewogICAgICAgICAgICAgICAgY291dCA8PCBtc3QucW1heChsLCByKSAgPDwgZW5kbDsKICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGludCBsb2MgPSBzdWJbcF07CiAgICAgICAgICAgIGludCBhbnMgPSAwOwogICAgICAgICAgICBpZihzZWdbbG9jXSA+IGwpewogICAgICAgICAgICAgICAgYW5zID0gZGVwdGhbcF0gKyAgbXN0LnFtYXgobCwgc2VnW2xvY10tMSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYoc2VnW2xvY10gPHIpewogICAgICAgICAgICAgICAgYW5zID0gbWF4KGFucywgZGVwdGhbcF0gKyBtc3QucW1heChzZWdbbG9jXSArIDEsIHIpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpbnQgY2hhaW4gPSAgbWF4KG1zdC5xbWF4KHNlZ1tsb2NdLCBzZWdbbG9jXSkgLSBkZXB0aFtwXSwgZGVwdGhbcF0pOwogICAgICAgICAgICBjb3V0IDw8IG1heChhbnMsIGNoYWluKTw8IGVuZGw7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0K