/*
・ビット列について
ビット列は、一番左から0がいくつ連続するか、一番右から0がいくつ連続するか、ビット列の長さ、現在のビット列内に含まれる連続する0の長さの最大値の4つを持っておければ、結合も含めて管理できる。
(ただし、32bit整数型に収まらない場合に注意せよ。)
各タイプについて、セグメント木を用いれば求まる。
・答えについて
Undoするクエリがない場合、普通のUnionFindと同じである。
ただしUndoするクエリがあるので、永続化する必要がある。
セグメント木に各要素を持たせて永続unionfind木を実装すると、満点が得られる。
*/
//以下自分のコード
//このくらいのメモリ使用は許容したいなあという感じで書いたので、もっとメモリ制限きつくても解けます
#include <cstdio>
#include <vector>
#include <cstring>
#include <functional>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <queue>
#include <assert.h>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <complex>
#include <numeric>
#include <map>
#include <time.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<int,ull> piu;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
typedef pair<pii,ll> ppl;
typedef pair<ll,pii> plp;
typedef pair<ll,pll> plP;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
typedef pair<double,int> pdi;
typedef pair<int,double> pid;
typedef pair<double,pii> pdp;
typedef pair<double,double> pdd;
typedef pair<pdd,double> pd3;
typedef vector<int> vec;
typedef vector<vec> mat;
#define rep(i,n) for (int (i) = 0; (i) < (n); (i)++)
#define repn(i,a,n) for (int (i) = (a); (i) < (n); (i)++)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define SORT(x) sort((x).begin(),(x).end())
#define SORTN(x,n) sort((x),(x)+(n))
#define ERASE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define COUNT(x,c) count((x).begin(),(x).end(),(c))
#define REMOVE(x,c) (x).erase(remove((x).begin(),(x).end(),(c)),(x).end())
#define REVERSE(x) reverse((x).begin(),(x).end())
#define FORIT(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))-(x).begin()
#define lb(x,a) lower_bound((x).begin(),(x).end(),(a))
#define LBN(x,a,n) lower_bound((x),(x)+(n),(a))-(x)
#define lbN(x,a,n) lower_bound((x),(x)+(n),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))-(x).begin()
#define ub(x,a) upper_bound((x).begin(),(x).end(),(a))
#define BS(x,a) binary_search((x).begin(),(x).end(),(a))
#define BS2(x,n,a) binary_search((x),(x)+(n),(a))
#define NB(x) (((x)&~((x)+((x)&-(x))))/((x)&-(x))>>1)|((x)+((x)&-(x)))
#define NP(x) next_permutation((x).begin(),(x).end())
#define MM(x,p) memset((x),(p),sizeof(x))
#define SQ(x) (x)*(x)
#define SC(c1,c2) strcmp(c1,c2)==0
#define mp make_pair
#define INF (1<<28)
#define INFL (1LL<<61)
#define fi first
#define se second
#define MOD 1000000007
#define EPS 1e-9
#define MIN(x,a) x=min(x,a)
#define MAX(x,a) x=max(x,a)
#define madd(x,a) x=(x+a)%MOD
#define msub(x,a) x=(x+MOD-a)%MOD
#define OUTPUT(x) rep(__,x.size())printf("%d%c",x[__],__+1==x.size()?'\n':' ');
int T,Q,L,R;
const int n=1<<17;
char S[n];
struct Query
{
ll lq,rq,sz,q;
};
Query merge(Query p1,Query p2)
{
Query res;
if(p1.lq==-1)res=p2;
else if(p2.lq==-1)res=p1;
else
{
if(p1.lq==p1.sz)res.lq=p1.sz+p2.lq;
else res.lq=p1.lq;
if(p2.rq==p2.sz)res.rq=p1.rq+p2.sz;
else res.rq=p2.rq;
res.sz=p1.sz+p2.sz;
res.q=max(p1.q,p2.q);
MAX(res.q,p1.rq+p2.lq);
MAX(res.q,res.lq);
MAX(res.q,res.rq);
}
return res;
}
struct Node
{
int l,r,par,ra;
Query q;
Node(){par=-1,ra=0,l=r=-1;}
}nd[5000000];
int pos[5000000];
int ndptr=n+n-1;
struct SegTree
{
SegTree()
{
rep(i,n-1)nd[i].l=i*2+1,nd[i].r=i*2+2;
}
int gt(int a,int b,int k,int l,int r)
{
if(r<=a||b<=l)return -1;
if(a<=l&&r<=b)return k;
return max(gt(a,b,nd[k].l,l,(l+r)/2),gt(a,b,nd[k].r,(l+r)/2,r));
}
int update(int a,int b,int k,int l,int r,Node sss)
{
if(r<=a||b<=l)return k;
if(a<=l&&r<=b)
{
pos[ndptr]=l;
nd[ndptr++]=sss;
return ndptr-1;
}
int x=ndptr++;
nd[x].l=update(a,b,nd[k].l,l,(l+r)/2,sss);
nd[x].r=update(a,b,nd[k].r,(l+r)/2,r,sss);
return x;
}
}seg;
struct SegDat
{
Query q[n*2-1];
void init()
{
rep(i,n)
{
if(S[i]=='0')q[i+n-1].lq=q[i+n-1].rq=q[i+n-1].q=1;
else q[i+n-1].lq=q[i+n-1].rq=q[i+n-1].q=0;
q[i+n-1].sz=1;
}
for(int i=n-2;i>=0;i--)q[i]=merge(q[i*2+1],q[i*2+2]);
}
Query query(int a,int b,int k,int l,int r)
{
if(r<=a||b<=l)
{
Query res;
res.lq=-1;
return res;
}
if(a<=l&&r<=b)return q[k];
return merge(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
}
}ss;
int root[1000001];
int t,a,b;
int main()
{
scanf("%d",&T);
scanf("%s",&S);
ss.init();
rep(i,T)
{
scanf("%d%d",&L,&R);L--;
nd[i+n-1].q=ss.query(L,R,0,0,n);
nd[i+n-1].par=i;
nd[i+n-1].ra=1;
pos[i+n-1]=i;
}
scanf("%d",&Q);
repn(i,1,Q+1)
{
scanf("%d",&t);
if(t==0)
{
scanf("%d",&a);a--;
root[i]=root[i-1];
int p1=seg.gt(a,a+1,root[i],0,n);
if(nd[p1].par!=pos[p1])
{
vector<int> lis;
lis.pb(p1);
while(nd[lis.back()].par!=pos[lis.back()])
{
int tt=lis.back();
lis.pb(seg.gt(nd[tt].par,nd[tt].par+1,root[i],0,n));
}
rep(j,lis.size()-2)
{
Node tmp=nd[lis[j]];
tmp.par=pos[lis.back()];
root[i]=seg.update(pos[lis[j]],pos[lis[j]]+1,root[i],0,n,tmp);
}
p1=lis.back();
}
printf("%lld\n",nd[p1].q.q);
}
else if(t==1)
{
scanf("%d",&a);
root[i]=root[a];
}
else
{
scanf("%d%d",&a,&b);a--,b--;
root[i]=root[i-1];
int p1=seg.gt(a,a+1,root[i],0,n);
if(nd[p1].par!=pos[p1])
{
vector<int> lis;
lis.pb(p1);
while(nd[lis.back()].par!=pos[lis.back()])
{
int tt=lis.back();
lis.pb(seg.gt(nd[tt].par,nd[tt].par+1,root[i],0,n));
}
rep(j,lis.size()-2)
{
Node tmp=nd[lis[j]];
tmp.par=pos[lis.back()];
root[i]=seg.update(pos[lis[j]],pos[lis[j]]+1,root[i],0,n,tmp);
}
p1=lis.back();
}
int p2=seg.gt(b,b+1,root[i],0,n);
if(nd[p2].par!=pos[p2])
{
vector<int> lis;
lis.pb(p2);
while(nd[lis.back()].par!=pos[lis.back()])
{
int tt=lis.back();
lis.pb(seg.gt(nd[tt].par,nd[tt].par+1,root[i],0,n));
}
rep(j,lis.size()-2)
{
Node tmp=nd[lis[j]];
tmp.par=pos[lis.back()];
root[i]=seg.update(pos[lis[j]],pos[lis[j]]+1,root[i],0,n,tmp);
}
p2=lis.back();
}
if(p1==p2)continue;
Query tt=merge(nd[p1].q,nd[p2].q);
if(nd[p1].ra<nd[p2].ra)swap(p1,p2),swap(a,b);
a=pos[p1],b=pos[p2];
Node res=nd[p1];
res.q=tt;
if(nd[p1].ra==nd[p2].ra)res.ra++;
root[i]=seg.update(a,a+1,root[i],0,n,res);
Node nw=nd[p2];
nw.par=a;
root[i]=seg.update(b,b+1,root[i],0,n,nw);
}
}
}
LyoK44O744OT44OD44OI5YiX44Gr44Gk44GE44GmCuOAgOODk+ODg+ODiOWIl+OBr+OAgeS4gOeVquW3puOBi+OCiTDjgYzjgYTjgY/jgaTpgKPntprjgZnjgovjgYvjgIHkuIDnlarlj7PjgYvjgokw44GM44GE44GP44Gk6YCj57aa44GZ44KL44GL44CB44OT44OD44OI5YiX44Gu6ZW344GV44CB54++5Zyo44Gu44OT44OD44OI5YiX5YaF44Gr5ZCr44G+44KM44KL6YCj57aa44GZ44KLMOOBrumVt+OBleOBruacgOWkp+WApOOBrjTjgaTjgpLmjIHjgaPjgabjgYrjgZHjgozjgbDjgIHntZDlkIjjgoLlkKvjgoHjgabnrqHnkIbjgafjgY3jgovjgIIKKOOBn+OBoOOBl+OAgTMyYml05pW05pWw5Z6L44Gr5Y+O44G+44KJ44Gq44GE5aC05ZCI44Gr5rOo5oSP44Gb44KI44CCKQrjgIDlkITjgr/jgqTjg5fjgavjgaTjgYTjgabjgIHjgrvjgrDjg6Hjg7Pjg4jmnKjjgpLnlKjjgYTjgozjgbDmsYLjgb7jgovjgIIKCuODu+etlOOBiOOBq+OBpOOBhOOBpgrjgIBVbmRv44GZ44KL44Kv44Ko44Oq44GM44Gq44GE5aC05ZCI44CB5pmu6YCa44GuVW5pb25GaW5k44Go5ZCM44GY44Gn44GC44KL44CCCuOAgOOBn+OBoOOBl1VuZG/jgZnjgovjgq/jgqjjg6rjgYzjgYLjgovjga7jgafjgIHmsLjntprljJbjgZnjgovlv4XopoHjgYzjgYLjgovjgIIK44CA44K744Kw44Oh44Oz44OI5pyo44Gr5ZCE6KaB57Sg44KS5oyB44Gf44Gb44Gm5rC457aadW5pb25maW5k5pyo44KS5a6f6KOF44GZ44KL44Go44CB5rqA54K544GM5b6X44KJ44KM44KL44CCCiovCgovL+S7peS4i+iHquWIhuOBruOCs+ODvOODiQovL+OBk+OBruOBj+OCieOBhOOBruODoeODouODquS9v+eUqOOBr+ioseWuueOBl+OBn+OBhOOBquOBguOBqOOBhOOBhuaEn+OBmOOBp+abuOOBhOOBn+OBruOBp+OAgeOCguOBo+OBqOODoeODouODquWItumZkOOBjeOBpOOBj+OBpuOCguino+OBkeOBvuOBmQoKCiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPGNvbXBsZXg+CiNpbmNsdWRlIDxudW1lcmljPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8dGltZS5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIHVuc2lnbmVkIGludCB1aW50Owp0eXBlZGVmIHBhaXI8aW50LGludD4gcGlpOwp0eXBlZGVmIHBhaXI8aW50LGxsPiBwaWw7CnR5cGVkZWYgcGFpcjxpbnQsdWxsPiBwaXU7CnR5cGVkZWYgcGFpcjxsbCxpbnQ+IHBsaTsKdHlwZWRlZiBwYWlyPGxsLGxsPiBwbGw7CnR5cGVkZWYgcGFpcjxwaWksbGw+IHBwbDsKdHlwZWRlZiBwYWlyPGxsLHBpaT4gcGxwOwp0eXBlZGVmIHBhaXI8bGwscGxsPiBwbFA7CnR5cGVkZWYgcGFpcjxpbnQscGlpPiBwaXA7CnR5cGVkZWYgcGFpcjxwaWksaW50PiBwcGk7CnR5cGVkZWYgcGFpcjxwaWkscGlpPiBwcHA7CnR5cGVkZWYgcGFpcjxkb3VibGUsaW50PiBwZGk7CnR5cGVkZWYgcGFpcjxpbnQsZG91YmxlPiBwaWQ7CnR5cGVkZWYgcGFpcjxkb3VibGUscGlpPiBwZHA7CnR5cGVkZWYgcGFpcjxkb3VibGUsZG91YmxlPiBwZGQ7CnR5cGVkZWYgcGFpcjxwZGQsZG91YmxlPiBwZDM7CnR5cGVkZWYgdmVjdG9yPGludD4gdmVjOwp0eXBlZGVmIHZlY3Rvcjx2ZWM+IG1hdDsKI2RlZmluZSByZXAoaSxuKSBmb3IgKGludCAoaSkgPSAwOyAoaSkgPCAobik7IChpKSsrKQojZGVmaW5lIHJlcG4oaSxhLG4pIGZvciAoaW50IChpKSA9IChhKTsgKGkpIDwgKG4pOyAoaSkrKykKI2RlZmluZSBBTEwoeCkgKHgpLmJlZ2luKCksKHgpLmVuZCgpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgU09SVCh4KSBzb3J0KCh4KS5iZWdpbigpLCh4KS5lbmQoKSkKI2RlZmluZSBTT1JUTih4LG4pIHNvcnQoKHgpLCh4KSsobikpCiNkZWZpbmUgRVJBU0UoeCkgKHgpLmVyYXNlKHVuaXF1ZSgoeCkuYmVnaW4oKSwoeCkuZW5kKCkpLCh4KS5lbmQoKSkKI2RlZmluZSBDT1VOVCh4LGMpIGNvdW50KCh4KS5iZWdpbigpLCh4KS5lbmQoKSwoYykpCiNkZWZpbmUgUkVNT1ZFKHgsYykgKHgpLmVyYXNlKHJlbW92ZSgoeCkuYmVnaW4oKSwoeCkuZW5kKCksKGMpKSwoeCkuZW5kKCkpCiNkZWZpbmUgUkVWRVJTRSh4KSByZXZlcnNlKCh4KS5iZWdpbigpLCh4KS5lbmQoKSkKI2RlZmluZSBGT1JJVChpdCx2KSBmb3IoX190eXBlb2YoKHYpLmJlZ2luKCkpIGl0PSh2KS5iZWdpbigpO2l0IT0odikuZW5kKCk7aXQrKykKI2RlZmluZSBMQih4LGEpIGxvd2VyX2JvdW5kKCh4KS5iZWdpbigpLCh4KS5lbmQoKSwoYSkpLSh4KS5iZWdpbigpCiNkZWZpbmUgbGIoeCxhKSBsb3dlcl9ib3VuZCgoeCkuYmVnaW4oKSwoeCkuZW5kKCksKGEpKQojZGVmaW5lIExCTih4LGEsbikgbG93ZXJfYm91bmQoKHgpLCh4KSsobiksKGEpKS0oeCkKI2RlZmluZSBsYk4oeCxhLG4pIGxvd2VyX2JvdW5kKCh4KSwoeCkrKG4pLChhKSkKI2RlZmluZSBVQih4LGEpIHVwcGVyX2JvdW5kKCh4KS5iZWdpbigpLCh4KS5lbmQoKSwoYSkpLSh4KS5iZWdpbigpCiNkZWZpbmUgdWIoeCxhKSB1cHBlcl9ib3VuZCgoeCkuYmVnaW4oKSwoeCkuZW5kKCksKGEpKQojZGVmaW5lIEJTKHgsYSkgYmluYXJ5X3NlYXJjaCgoeCkuYmVnaW4oKSwoeCkuZW5kKCksKGEpKQojZGVmaW5lIEJTMih4LG4sYSkgYmluYXJ5X3NlYXJjaCgoeCksKHgpKyhuKSwoYSkpCiNkZWZpbmUgTkIoeCkgKCgoeCkmfigoeCkrKCh4KSYtKHgpKSkpLygoeCkmLSh4KSk+PjEpfCgoeCkrKCh4KSYtKHgpKSkKI2RlZmluZSBOUCh4KSBuZXh0X3Blcm11dGF0aW9uKCh4KS5iZWdpbigpLCh4KS5lbmQoKSkKI2RlZmluZSBNTSh4LHApIG1lbXNldCgoeCksKHApLHNpemVvZih4KSkKI2RlZmluZSBTUSh4KSAoeCkqKHgpCiNkZWZpbmUgU0MoYzEsYzIpIHN0cmNtcChjMSxjMik9PTAKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBJTkYgKDE8PDI4KQojZGVmaW5lIElORkwgKDFMTDw8NjEpCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwojZGVmaW5lIEVQUyAxZS05CiNkZWZpbmUgTUlOKHgsYSkgeD1taW4oeCxhKQojZGVmaW5lIE1BWCh4LGEpIHg9bWF4KHgsYSkKI2RlZmluZSBtYWRkKHgsYSkgeD0oeCthKSVNT0QKI2RlZmluZSBtc3ViKHgsYSkgeD0oeCtNT0QtYSklTU9ECiNkZWZpbmUgT1VUUFVUKHgpIHJlcChfXyx4LnNpemUoKSlwcmludGYoIiVkJWMiLHhbX19dLF9fKzE9PXguc2l6ZSgpPydcbic6JyAnKTsKCmludCBULFEsTCxSOwpjb25zdCBpbnQgbj0xPDwxNzsKY2hhciBTW25dOwpzdHJ1Y3QgUXVlcnkKewoJbGwgbHEscnEsc3oscTsKfTsKUXVlcnkgbWVyZ2UoUXVlcnkgcDEsUXVlcnkgcDIpCnsKCVF1ZXJ5IHJlczsKCWlmKHAxLmxxPT0tMSlyZXM9cDI7CgllbHNlIGlmKHAyLmxxPT0tMSlyZXM9cDE7CgllbHNlCgl7CgkJaWYocDEubHE9PXAxLnN6KXJlcy5scT1wMS5zeitwMi5scTsKCQllbHNlIHJlcy5scT1wMS5scTsKCQlpZihwMi5ycT09cDIuc3opcmVzLnJxPXAxLnJxK3AyLnN6OwoJCWVsc2UgcmVzLnJxPXAyLnJxOwoJCXJlcy5zej1wMS5zeitwMi5zejsKCQlyZXMucT1tYXgocDEucSxwMi5xKTsKCQlNQVgocmVzLnEscDEucnErcDIubHEpOwoJCU1BWChyZXMucSxyZXMubHEpOwoJCU1BWChyZXMucSxyZXMucnEpOwoJfQoJcmV0dXJuIHJlczsKfQpzdHJ1Y3QgTm9kZQp7CglpbnQgbCxyLHBhcixyYTsKCVF1ZXJ5IHE7CglOb2RlKCl7cGFyPS0xLHJhPTAsbD1yPS0xO30KfW5kWzUwMDAwMDBdOwppbnQgcG9zWzUwMDAwMDBdOwppbnQgbmRwdHI9bituLTE7CgpzdHJ1Y3QgU2VnVHJlZQp7CglTZWdUcmVlKCkKCXsKCQlyZXAoaSxuLTEpbmRbaV0ubD1pKjIrMSxuZFtpXS5yPWkqMisyOwoJfQoJaW50IGd0KGludCBhLGludCBiLGludCBrLGludCBsLGludCByKQoJewoJCWlmKHI8PWF8fGI8PWwpcmV0dXJuIC0xOwoJCWlmKGE8PWwmJnI8PWIpcmV0dXJuIGs7CgkJcmV0dXJuIG1heChndChhLGIsbmRba10ubCxsLChsK3IpLzIpLGd0KGEsYixuZFtrXS5yLChsK3IpLzIscikpOwoJfQoJaW50IHVwZGF0ZShpbnQgYSxpbnQgYixpbnQgayxpbnQgbCxpbnQgcixOb2RlIHNzcykKCXsKCQlpZihyPD1hfHxiPD1sKXJldHVybiBrOwoJCWlmKGE8PWwmJnI8PWIpCgkJewoJCQlwb3NbbmRwdHJdPWw7CgkJCW5kW25kcHRyKytdPXNzczsKCQkJcmV0dXJuIG5kcHRyLTE7CgkJfQoJCWludCB4PW5kcHRyKys7CgkJbmRbeF0ubD11cGRhdGUoYSxiLG5kW2tdLmwsbCwobCtyKS8yLHNzcyk7CgkJbmRbeF0ucj11cGRhdGUoYSxiLG5kW2tdLnIsKGwrcikvMixyLHNzcyk7CgkJcmV0dXJuIHg7Cgl9Cn1zZWc7CnN0cnVjdCBTZWdEYXQKewoJUXVlcnkgcVtuKjItMV07Cgl2b2lkIGluaXQoKQoJewoJCXJlcChpLG4pCgkJewoJCQlpZihTW2ldPT0nMCcpcVtpK24tMV0ubHE9cVtpK24tMV0ucnE9cVtpK24tMV0ucT0xOwoJCQllbHNlIHFbaStuLTFdLmxxPXFbaStuLTFdLnJxPXFbaStuLTFdLnE9MDsKCQkJcVtpK24tMV0uc3o9MTsKCQl9CgkJZm9yKGludCBpPW4tMjtpPj0wO2ktLSlxW2ldPW1lcmdlKHFbaSoyKzFdLHFbaSoyKzJdKTsKCX0KCVF1ZXJ5IHF1ZXJ5KGludCBhLGludCBiLGludCBrLGludCBsLGludCByKQoJewoJCWlmKHI8PWF8fGI8PWwpCgkJewoJCQlRdWVyeSByZXM7CgkJCXJlcy5scT0tMTsKCQkJcmV0dXJuIHJlczsKCQl9CgkJaWYoYTw9bCYmcjw9YilyZXR1cm4gcVtrXTsKCQlyZXR1cm4gbWVyZ2UocXVlcnkoYSxiLGsqMisxLGwsKGwrcikvMikscXVlcnkoYSxiLGsqMisyLChsK3IpLzIscikpOwoJfQp9c3M7CmludCByb290WzEwMDAwMDFdOwppbnQgdCxhLGI7CgppbnQgbWFpbigpCnsKCXNjYW5mKCIlZCIsJlQpOwoJc2NhbmYoIiVzIiwmUyk7Cglzcy5pbml0KCk7CglyZXAoaSxUKQoJewoJCXNjYW5mKCIlZCVkIiwmTCwmUik7TC0tOwoJCW5kW2krbi0xXS5xPXNzLnF1ZXJ5KEwsUiwwLDAsbik7CgkJbmRbaStuLTFdLnBhcj1pOwoJCW5kW2krbi0xXS5yYT0xOwoJCXBvc1tpK24tMV09aTsKCX0KCXNjYW5mKCIlZCIsJlEpOwoJcmVwbihpLDEsUSsxKQoJewoJCXNjYW5mKCIlZCIsJnQpOwoJCWlmKHQ9PTApCgkJewoJCQlzY2FuZigiJWQiLCZhKTthLS07CgkJCXJvb3RbaV09cm9vdFtpLTFdOwoJCQlpbnQgcDE9c2VnLmd0KGEsYSsxLHJvb3RbaV0sMCxuKTsKCQkJaWYobmRbcDFdLnBhciE9cG9zW3AxXSkKCQkJewoJCQkJdmVjdG9yPGludD4gbGlzOwoJCQkJbGlzLnBiKHAxKTsKCQkJCXdoaWxlKG5kW2xpcy5iYWNrKCldLnBhciE9cG9zW2xpcy5iYWNrKCldKQoJCQkJewoJCQkJCWludCB0dD1saXMuYmFjaygpOwoJCQkJCWxpcy5wYihzZWcuZ3QobmRbdHRdLnBhcixuZFt0dF0ucGFyKzEscm9vdFtpXSwwLG4pKTsKCQkJCX0KCQkJCXJlcChqLGxpcy5zaXplKCktMikKCQkJCXsKCQkJCQlOb2RlIHRtcD1uZFtsaXNbal1dOwoJCQkJCXRtcC5wYXI9cG9zW2xpcy5iYWNrKCldOwoJCQkJCXJvb3RbaV09c2VnLnVwZGF0ZShwb3NbbGlzW2pdXSxwb3NbbGlzW2pdXSsxLHJvb3RbaV0sMCxuLHRtcCk7CgkJCQl9CgkJCQlwMT1saXMuYmFjaygpOwoJCQl9CgkJCXByaW50ZigiJWxsZFxuIixuZFtwMV0ucS5xKTsKCQl9CgkJZWxzZSBpZih0PT0xKQoJCXsKCQkJc2NhbmYoIiVkIiwmYSk7CgkJCXJvb3RbaV09cm9vdFthXTsKCQl9CgkJZWxzZQoJCXsKCQkJc2NhbmYoIiVkJWQiLCZhLCZiKTthLS0sYi0tOwoJCQlyb290W2ldPXJvb3RbaS0xXTsKCQkJaW50IHAxPXNlZy5ndChhLGErMSxyb290W2ldLDAsbik7CgkJCWlmKG5kW3AxXS5wYXIhPXBvc1twMV0pCgkJCXsKCQkJCXZlY3RvcjxpbnQ+IGxpczsKCQkJCWxpcy5wYihwMSk7CgkJCQl3aGlsZShuZFtsaXMuYmFjaygpXS5wYXIhPXBvc1tsaXMuYmFjaygpXSkKCQkJCXsKCQkJCQlpbnQgdHQ9bGlzLmJhY2soKTsKCQkJCQlsaXMucGIoc2VnLmd0KG5kW3R0XS5wYXIsbmRbdHRdLnBhcisxLHJvb3RbaV0sMCxuKSk7CgkJCQl9CgkJCQlyZXAoaixsaXMuc2l6ZSgpLTIpCgkJCQl7CgkJCQkJTm9kZSB0bXA9bmRbbGlzW2pdXTsKCQkJCQl0bXAucGFyPXBvc1tsaXMuYmFjaygpXTsKCQkJCQlyb290W2ldPXNlZy51cGRhdGUocG9zW2xpc1tqXV0scG9zW2xpc1tqXV0rMSxyb290W2ldLDAsbix0bXApOwoJCQkJfQoJCQkJcDE9bGlzLmJhY2soKTsKCQkJfQoJCQlpbnQgcDI9c2VnLmd0KGIsYisxLHJvb3RbaV0sMCxuKTsKCQkJaWYobmRbcDJdLnBhciE9cG9zW3AyXSkKCQkJewoJCQkJdmVjdG9yPGludD4gbGlzOwoJCQkJbGlzLnBiKHAyKTsKCQkJCXdoaWxlKG5kW2xpcy5iYWNrKCldLnBhciE9cG9zW2xpcy5iYWNrKCldKQoJCQkJewoJCQkJCWludCB0dD1saXMuYmFjaygpOwoJCQkJCWxpcy5wYihzZWcuZ3QobmRbdHRdLnBhcixuZFt0dF0ucGFyKzEscm9vdFtpXSwwLG4pKTsKCQkJCX0KCQkJCXJlcChqLGxpcy5zaXplKCktMikKCQkJCXsKCQkJCQlOb2RlIHRtcD1uZFtsaXNbal1dOwoJCQkJCXRtcC5wYXI9cG9zW2xpcy5iYWNrKCldOwoJCQkJCXJvb3RbaV09c2VnLnVwZGF0ZShwb3NbbGlzW2pdXSxwb3NbbGlzW2pdXSsxLHJvb3RbaV0sMCxuLHRtcCk7CgkJCQl9CgkJCQlwMj1saXMuYmFjaygpOwoJCQl9CgkJCWlmKHAxPT1wMiljb250aW51ZTsKCQkJUXVlcnkgdHQ9bWVyZ2UobmRbcDFdLnEsbmRbcDJdLnEpOwoJCQlpZihuZFtwMV0ucmE8bmRbcDJdLnJhKXN3YXAocDEscDIpLHN3YXAoYSxiKTsKCQkJYT1wb3NbcDFdLGI9cG9zW3AyXTsKCQkJTm9kZSByZXM9bmRbcDFdOwoJCQlyZXMucT10dDsKCQkJaWYobmRbcDFdLnJhPT1uZFtwMl0ucmEpcmVzLnJhKys7CgkJCQoJCQlyb290W2ldPXNlZy51cGRhdGUoYSxhKzEscm9vdFtpXSwwLG4scmVzKTsKCQkJCgkJCU5vZGUgbnc9bmRbcDJdOwoJCQludy5wYXI9YTsKCQkJCgkJCXJvb3RbaV09c2VnLnVwZGF0ZShiLGIrMSxyb290W2ldLDAsbixudyk7CgkJfQoJfQp9