#include <bits/stdc++.h>
using namespace std;
const int alph=256;
const int INF=1e9;
const int MPOW=16;
const int N=1<<MPOW-1;
const int N2=N<<1;
struct sg_tree
{
int arr[N2];
void build(vector<int> x,int n)
{
fill(arr,arr+N2,INF);
for(int i=0;i<n;i++)
arr[i+N]=x[i];
for(int i=N-1;i>0;i--)
arr[i]=min(arr[i<<1],arr[(i<<1)+1]);
}
int get_min(int c,int cl,int cr,int l,int r)
{
if(l==cl && r==cr)
return arr[c];
if(l>r)
return INF;
int cm=cl+cr>>1;
return min(get_min(c<<1,cl,cm,l,min(r,cm)),get_min((c<<1)+1,cm+1,cr,max(l,cm+1),r));
}
int get_min(int l,int r)
{
return get_min(1,0,N-1,l,r);
}
};
pair<vector<int>,vector<int>> compute(string &s)
{
int n=s.size();
int maxn=n+alph;
vector<int> p(n),c(n),cnt(maxn,0);
for(int i=0;i<n;i++)
cnt[s[i]]++;
for(int i=1;i<maxn;i++)
cnt[i]+=cnt[i-1];
for(int i=0;i<n;i++)
p[--cnt[s[i]]]=i;
int cl=0;
c[p[0]]=cl;
for(int i=1;i<n;i++)
{
if(s[p[i]]!=s[p[i-1]])cl++;
c[p[i]]=cl;
}
vector<int> lcp(n,0);
for(int i=1;i<n;i++)
lcp[i]=c[p[i]]==c[p[i-1]];
vector<int> pn(n),cn(n),lcpn(n);
vector<int> rpos(n),lpos(n);
sg_tree rmq;
int k=1;
while(k<n)
{
fill(begin(cnt),end(cnt),0);
for(int i=0;i<n;i++)
rpos[c[p[i]]]=i;
for(int i=n-1;i>=0;i--)
lpos[c[p[i]]]=i;
for(int i=0;i<n;i++)
{
pn[i]=p[i]-k;
if(pn[i]<0)pn[i]+=n;
}
for(int i=0;i<n;i++)
cnt[c[i]]++;
for(int i=1;i<maxn;i++)
cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;i--)
p[--cnt[c[pn[i]]]]=pn[i];
cl=0;
cn[p[0]]=0;
for(int i=1;i<n;i++)
{
int m1=(p[i]+k)%n,m2=(p[i-1]+k)%n;
if(c[p[i]]!=c[p[i-1]] || c[m1]!=c[m2])cl++;
cn[p[i]]=cl;
}
rmq.build(lcp,n);
for(int i=1;i<n;i++)
{
int a=p[i],b=p[i-1];
if(c[a]!=c[b])
lcpn[i]=lcp[lpos[c[a]]];
else
{
int aa=(a+k)%n,bb=(b+k)%n;
if(c[aa]==c[bb])
lcpn[i]=k<<1;
else
lcpn[i]=k+rmq.get_min(lpos[c[bb]]+1,rpos[c[aa]]);
}
lcpn[i]=min(n,lcpn[i]);
}
copy(begin(cn),end(cn),begin(c));
copy(begin(lcpn),end(lcpn),begin(lcp));
k<<=1;
}
return {p,lcp};
}
struct suffix_tree
{
struct edge
{
int from;
int to;
int next_vert;
int suffix_here;
};
struct vertex
{
vector<edge> go;
};
string str;
vector<vertex> data;
static bool comp(const edge &b,const char &a)
{
return 1;
}
void build(string &s)
{
// Получим суффиксный массив строки, а также массив lcp
pair<vector<int>,vector<int>> info=compute(s);
vector<int> p=info.first,lcp=info.second;
int n=s.size();
str=s;
// Будем хранить здесь стек рёбер, из которых мы ещё не вышли
vector<int> p_vert;
vector<int> p_edge;
vector<int> p_dist;
// Добавим первую строку в дерево
vertex v;
edge e;
e.from=p[0];
e.to=n;
e.next_vert=-1;
e.suffix_here=p[0];
v.go.push_back(e);
data.push_back(v);
p_vert.push_back(0);
p_edge.push_back(0);
p_dist.push_back(0);
for(int i=1;i<n;i++)
{
int c_lcp=lcp[i];
// Поднимаемся до lcp.
while(p_dist.back()>c_lcp)
{
// Найдём минимальный суффикс, покрывающий ребро для ответа на задачу. Опционально.
edge &E=data[p_vert.back()].go[p_edge.back()];
if(E.next_vert+1)
{
int m=data[E.next_vert].go.size();
for(int j=0;j<m;j++)
E.suffix_here=min(E.suffix_here,data[E.next_vert].go[j].suffix_here);
}
// Удалим ребро из стека. Больше мы в него не вернёмся
p_vert.pop_back();
p_edge.pop_back();
p_dist.pop_back();
}
vertex v;
edge e;
int c_v=p_vert.back();
int c_e=p_edge.back();
int At=data[c_v].go[c_e].from+c_lcp-p_dist.back(); // Индекс для разделения ребра
p_dist.push_back(c_lcp);
// Ребро, которое надо добавить
e.next_vert=-1;
e.suffix_here=p[i];
e.from=p[i]+c_lcp;
e.to=n;
// Либо добавляем ребро к вершине, либо разделяем текущее
if(At==data[c_v].go[c_e].from)
{
data[c_v].go.push_back(e);
p_vert.push_back(c_v);
p_edge.push_back(data[c_v].go.size()-1);
}
else
{
v.go.push_back(data[c_v].go[c_e]);
v.go.back().from=At;
v.go.push_back(e);
data.push_back(v);
data[c_v].go[c_e].next_vert=data.size()-1;
data[c_v].go[c_e].to=At;
p_vert.push_back(data.size()-1);
p_edge.push_back(1);
}
}
while(!p_dist.empty())
{
// Найдём минимальный суффикс, покрывающий ребро для ответа на задачу. Опционально.
edge &E=data[p_vert.back()].go[p_edge.back()];
if(E.next_vert+1)
{
int m=data[E.next_vert].go.size();
for(int j=0;j<m;j++)
E.suffix_here=min(E.suffix_here,data[E.next_vert].go[j].suffix_here);
}
// Удалим ребро из стека. Больше мы в него не вернёмся
p_vert.pop_back();
p_edge.pop_back();
p_dist.pop_back();
}
}
int search_str(string &s)
{
int n=s.size();
int cur_v=0;
int cur_e;
char t;
for(int i=0;i<n;)
{
if(cur_v==-1)break;
t=s[i];
int cur_e;
for(cur_e=0;cur_e<data[cur_v].go.size();cur_e++)
if(str[data[cur_v].go[cur_e].from]>=t)break;
for(int j=data[cur_v].go[cur_e].from;i<n && j<data[cur_v].go[cur_e].to;j++,i++)
if(str[j]!=s[i])
i=n+1;
if(i==n)
return data[cur_v].go[cur_e].suffix_here;
cur_v=data[cur_v].go[cur_e].next_vert;
}
return -1;
}
int print(int x)
{
if(x==-1)return 0;
int ans=0;
for(int i=0;i<data[x].go.size();i++)
ans+=data[x].go[i].to-data[x].go[i].from+print(data[x].go[i].next_vert)-(data[x].go[i].to==str.size());
return ans;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string a;
cin>>a;
a+='#';
suffix_tree sf;
sf.build(a);
cout<<sf.print(0)<<endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IGFscGg9MjU2OwoKY29uc3QgaW50IElORj0xZTk7CmNvbnN0IGludCBNUE9XPTE2Owpjb25zdCBpbnQgTj0xPDxNUE9XLTE7CmNvbnN0IGludCBOMj1OPDwxOwpzdHJ1Y3Qgc2dfdHJlZQp7CiAgICBpbnQgYXJyW04yXTsKCiAgICB2b2lkIGJ1aWxkKHZlY3RvcjxpbnQ+IHgsaW50IG4pCiAgICB7CiAgICAgICAgZmlsbChhcnIsYXJyK04yLElORik7CiAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICAgICAgYXJyW2krTl09eFtpXTsKICAgICAgICBmb3IoaW50IGk9Ti0xO2k+MDtpLS0pCiAgICAgICAgICAgIGFycltpXT1taW4oYXJyW2k8PDFdLGFyclsoaTw8MSkrMV0pOwogICAgfQoKICAgIGludCBnZXRfbWluKGludCBjLGludCBjbCxpbnQgY3IsaW50IGwsaW50IHIpCiAgICB7CiAgICAgICAgaWYobD09Y2wgJiYgcj09Y3IpCiAgICAgICAgICAgIHJldHVybiBhcnJbY107CiAgICAgICAgaWYobD5yKQogICAgICAgICAgICByZXR1cm4gSU5GOwogICAgICAgIGludCBjbT1jbCtjcj4+MTsKICAgICAgICByZXR1cm4gbWluKGdldF9taW4oYzw8MSxjbCxjbSxsLG1pbihyLGNtKSksZ2V0X21pbigoYzw8MSkrMSxjbSsxLGNyLG1heChsLGNtKzEpLHIpKTsKICAgIH0KCiAgICBpbnQgZ2V0X21pbihpbnQgbCxpbnQgcikKICAgIHsKICAgICAgICByZXR1cm4gZ2V0X21pbigxLDAsTi0xLGwscik7CiAgICB9Cn07CgpwYWlyPHZlY3RvcjxpbnQ+LHZlY3RvcjxpbnQ+PiBjb21wdXRlKHN0cmluZyAmcykKewogICAgaW50IG49cy5zaXplKCk7CiAgICBpbnQgbWF4bj1uK2FscGg7CgogICAgdmVjdG9yPGludD4gcChuKSxjKG4pLGNudChtYXhuLDApOwogICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICBjbnRbc1tpXV0rKzsKICAgIGZvcihpbnQgaT0xO2k8bWF4bjtpKyspCiAgICAgICAgY250W2ldKz1jbnRbaS0xXTsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgcFstLWNudFtzW2ldXV09aTsKICAgIGludCBjbD0wOwogICAgY1twWzBdXT1jbDsKICAgIGZvcihpbnQgaT0xO2k8bjtpKyspCiAgICB7CiAgICAgICAgaWYoc1twW2ldXSE9c1twW2ktMV1dKWNsKys7CiAgICAgICAgY1twW2ldXT1jbDsKICAgIH0KICAgIHZlY3RvcjxpbnQ+IGxjcChuLDApOwogICAgZm9yKGludCBpPTE7aTxuO2krKykKICAgICAgICBsY3BbaV09Y1twW2ldXT09Y1twW2ktMV1dOwogICAgdmVjdG9yPGludD4gcG4obiksY24obiksbGNwbihuKTsKICAgIHZlY3RvcjxpbnQ+IHJwb3MobiksbHBvcyhuKTsKICAgIHNnX3RyZWUgcm1xOwogICAgaW50IGs9MTsKICAgIHdoaWxlKGs8bikKICAgIHsKICAgICAgICBmaWxsKGJlZ2luKGNudCksZW5kKGNudCksMCk7CiAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICAgICAgcnBvc1tjW3BbaV1dXT1pOwogICAgICAgIGZvcihpbnQgaT1uLTE7aT49MDtpLS0pCiAgICAgICAgICAgIGxwb3NbY1twW2ldXV09aTsKICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgICAgIHsKICAgICAgICAgICAgcG5baV09cFtpXS1rOwogICAgICAgICAgICBpZihwbltpXTwwKXBuW2ldKz1uOwogICAgICAgIH0KICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgICAgICAgICBjbnRbY1tpXV0rKzsKICAgICAgICBmb3IoaW50IGk9MTtpPG1heG47aSsrKQogICAgICAgICAgICBjbnRbaV0rPWNudFtpLTFdOwogICAgICAgIGZvcihpbnQgaT1uLTE7aT49MDtpLS0pCiAgICAgICAgICAgIHBbLS1jbnRbY1twbltpXV1dXT1wbltpXTsKICAgICAgICBjbD0wOwogICAgICAgIGNuW3BbMF1dPTA7CiAgICAgICAgZm9yKGludCBpPTE7aTxuO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGludCBtMT0ocFtpXStrKSVuLG0yPShwW2ktMV0rayklbjsKICAgICAgICAgICAgaWYoY1twW2ldXSE9Y1twW2ktMV1dIHx8IGNbbTFdIT1jW20yXSljbCsrOwogICAgICAgICAgICBjbltwW2ldXT1jbDsKICAgICAgICB9CiAgICAgICAgcm1xLmJ1aWxkKGxjcCxuKTsKICAgICAgICBmb3IoaW50IGk9MTtpPG47aSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IGE9cFtpXSxiPXBbaS0xXTsKICAgICAgICAgICAgaWYoY1thXSE9Y1tiXSkKICAgICAgICAgICAgICAgIGxjcG5baV09bGNwW2xwb3NbY1thXV1dOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBhYT0oYStrKSVuLGJiPShiK2spJW47CiAgICAgICAgICAgICAgICBpZihjW2FhXT09Y1tiYl0pCiAgICAgICAgICAgICAgICAgICAgbGNwbltpXT1rPDwxOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGxjcG5baV09aytybXEuZ2V0X21pbihscG9zW2NbYmJdXSsxLHJwb3NbY1thYV1dKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBsY3BuW2ldPW1pbihuLGxjcG5baV0pOwogICAgICAgIH0KICAgICAgICBjb3B5KGJlZ2luKGNuKSxlbmQoY24pLGJlZ2luKGMpKTsKICAgICAgICBjb3B5KGJlZ2luKGxjcG4pLGVuZChsY3BuKSxiZWdpbihsY3ApKTsKICAgICAgICBrPDw9MTsKICAgIH0KICAgIHJldHVybiB7cCxsY3B9Owp9CgoKc3RydWN0IHN1ZmZpeF90cmVlCnsKICAgIHN0cnVjdCBlZGdlCiAgICB7CiAgICAgICAgaW50IGZyb207CiAgICAgICAgaW50IHRvOwogICAgICAgIGludCBuZXh0X3ZlcnQ7CiAgICAgICAgaW50IHN1ZmZpeF9oZXJlOwogICAgfTsKCiAgICBzdHJ1Y3QgdmVydGV4CiAgICB7CiAgICAgICAgdmVjdG9yPGVkZ2U+IGdvOwogICAgfTsKCiAgICBzdHJpbmcgc3RyOwogICAgdmVjdG9yPHZlcnRleD4gZGF0YTsKCiAgICBzdGF0aWMgYm9vbCBjb21wKGNvbnN0IGVkZ2UgJmIsY29uc3QgY2hhciAmYSkKICAgIHsKICAgICAgICByZXR1cm4gMTsKICAgIH0KCiAgICB2b2lkIGJ1aWxkKHN0cmluZyAmcykKICAgIHsKICAgICAgICAvLyDQn9C+0LvRg9GH0LjQvCDRgdGD0YTRhNC40LrRgdC90YvQuSDQvNCw0YHRgdC40LIg0YHRgtGA0L7QutC4LCDQsCDRgtCw0LrQttC1INC80LDRgdGB0LjQsiBsY3AKICAgICAgICBwYWlyPHZlY3RvcjxpbnQ+LHZlY3RvcjxpbnQ+PiBpbmZvPWNvbXB1dGUocyk7CiAgICAgICAgdmVjdG9yPGludD4gcD1pbmZvLmZpcnN0LGxjcD1pbmZvLnNlY29uZDsKCiAgICAgICAgaW50IG49cy5zaXplKCk7CiAgICAgICAgc3RyPXM7CgogICAgICAgIC8vINCR0YPQtNC10Lwg0YXRgNCw0L3QuNGC0Ywg0LfQtNC10YHRjCDRgdGC0LXQuiDRgNGR0LHQtdGALCDQuNC3INC60L7RgtC+0YDRi9GFINC80Ysg0LXRidGRINC90LUg0LLRi9GI0LvQuAogICAgICAgIHZlY3RvcjxpbnQ+IHBfdmVydDsKICAgICAgICB2ZWN0b3I8aW50PiBwX2VkZ2U7CiAgICAgICAgdmVjdG9yPGludD4gcF9kaXN0OwoKICAgICAgICAvLyDQlNC+0LHQsNCy0LjQvCDQv9C10YDQstGD0Y4g0YHRgtGA0L7QutGDINCyINC00LXRgNC10LLQvgogICAgICAgIHZlcnRleCB2OwogICAgICAgIGVkZ2UgZTsKICAgICAgICBlLmZyb209cFswXTsKICAgICAgICBlLnRvPW47CiAgICAgICAgZS5uZXh0X3ZlcnQ9LTE7CiAgICAgICAgZS5zdWZmaXhfaGVyZT1wWzBdOwogICAgICAgIHYuZ28ucHVzaF9iYWNrKGUpOwogICAgICAgIGRhdGEucHVzaF9iYWNrKHYpOwoKICAgICAgICBwX3ZlcnQucHVzaF9iYWNrKDApOwogICAgICAgIHBfZWRnZS5wdXNoX2JhY2soMCk7CiAgICAgICAgcF9kaXN0LnB1c2hfYmFjaygwKTsKCiAgICAgICAgZm9yKGludCBpPTE7aTxuO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGludCBjX2xjcD1sY3BbaV07CiAgICAgICAgICAgIC8vINCf0L7QtNC90LjQvNCw0LXQvNGB0Y8g0LTQviBsY3AuCiAgICAgICAgICAgIHdoaWxlKHBfZGlzdC5iYWNrKCk+Y19sY3ApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIC8vINCd0LDQudC00ZHQvCDQvNC40L3QuNC80LDQu9GM0L3Ri9C5INGB0YPRhNGE0LjQutGBLCDQv9C+0LrRgNGL0LLQsNGO0YnQuNC5INGA0LXQsdGA0L4g0LTQu9GPINC+0YLQstC10YLQsCDQvdCwINC30LDQtNCw0YfRgy4g0J7Qv9GG0LjQvtC90LDQu9GM0L3Qvi4KICAgICAgICAgICAgICAgIGVkZ2UgJkU9ZGF0YVtwX3ZlcnQuYmFjaygpXS5nb1twX2VkZ2UuYmFjaygpXTsKICAgICAgICAgICAgICAgIGlmKEUubmV4dF92ZXJ0KzEpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaW50IG09ZGF0YVtFLm5leHRfdmVydF0uZ28uc2l6ZSgpOwogICAgICAgICAgICAgICAgICAgIGZvcihpbnQgaj0wO2o8bTtqKyspCiAgICAgICAgICAgICAgICAgICAgICAgIEUuc3VmZml4X2hlcmU9bWluKEUuc3VmZml4X2hlcmUsZGF0YVtFLm5leHRfdmVydF0uZ29bal0uc3VmZml4X2hlcmUpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgLy8g0KPQtNCw0LvQuNC8INGA0LXQsdGA0L4g0LjQtyDRgdGC0LXQutCwLiDQkdC+0LvRjNGI0LUg0LzRiyDQsiDQvdC10LPQviDQvdC1INCy0LXRgNC90ZHQvNGB0Y8KICAgICAgICAgICAgICAgIHBfdmVydC5wb3BfYmFjaygpOwogICAgICAgICAgICAgICAgcF9lZGdlLnBvcF9iYWNrKCk7CiAgICAgICAgICAgICAgICBwX2Rpc3QucG9wX2JhY2soKTsKICAgICAgICAgICAgfQogICAgICAgICAgICB2ZXJ0ZXggdjsKICAgICAgICAgICAgZWRnZSBlOwogICAgICAgICAgICBpbnQgY192PXBfdmVydC5iYWNrKCk7CiAgICAgICAgICAgIGludCBjX2U9cF9lZGdlLmJhY2soKTsKICAgICAgICAgICAgaW50IEF0PWRhdGFbY192XS5nb1tjX2VdLmZyb20rY19sY3AtcF9kaXN0LmJhY2soKTsgLy8g0JjQvdC00LXQutGBINC00LvRjyDRgNCw0LfQtNC10LvQtdC90LjRjyDRgNC10LHRgNCwCgogICAgICAgICAgICBwX2Rpc3QucHVzaF9iYWNrKGNfbGNwKTsKCiAgICAgICAgICAgIC8vINCg0LXQsdGA0L4sINC60L7RgtC+0YDQvtC1INC90LDQtNC+INC00L7QsdCw0LLQuNGC0YwKICAgICAgICAgICAgZS5uZXh0X3ZlcnQ9LTE7CiAgICAgICAgICAgIGUuc3VmZml4X2hlcmU9cFtpXTsKICAgICAgICAgICAgZS5mcm9tPXBbaV0rY19sY3A7CiAgICAgICAgICAgIGUudG89bjsKCiAgICAgICAgICAgIC8vINCb0LjQsdC+INC00L7QsdCw0LLQu9GP0LXQvCDRgNC10LHRgNC+INC6INCy0LXRgNGI0LjQvdC1LCDQu9C40LHQviDRgNCw0LfQtNC10LvRj9C10Lwg0YLQtdC60YPRidC10LUKICAgICAgICAgICAgaWYoQXQ9PWRhdGFbY192XS5nb1tjX2VdLmZyb20pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGRhdGFbY192XS5nby5wdXNoX2JhY2soZSk7CiAgICAgICAgICAgICAgICBwX3ZlcnQucHVzaF9iYWNrKGNfdik7CiAgICAgICAgICAgICAgICBwX2VkZ2UucHVzaF9iYWNrKGRhdGFbY192XS5nby5zaXplKCktMSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB2LmdvLnB1c2hfYmFjayhkYXRhW2Nfdl0uZ29bY19lXSk7CiAgICAgICAgICAgICAgICB2LmdvLmJhY2soKS5mcm9tPUF0OwogICAgICAgICAgICAgICAgdi5nby5wdXNoX2JhY2soZSk7CiAgICAgICAgICAgICAgICBkYXRhLnB1c2hfYmFjayh2KTsKICAgICAgICAgICAgICAgIGRhdGFbY192XS5nb1tjX2VdLm5leHRfdmVydD1kYXRhLnNpemUoKS0xOwogICAgICAgICAgICAgICAgZGF0YVtjX3ZdLmdvW2NfZV0udG89QXQ7CiAgICAgICAgICAgICAgICBwX3ZlcnQucHVzaF9iYWNrKGRhdGEuc2l6ZSgpLTEpOwogICAgICAgICAgICAgICAgcF9lZGdlLnB1c2hfYmFjaygxKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgd2hpbGUoIXBfZGlzdC5lbXB0eSgpKQogICAgICAgIHsKICAgICAgICAgICAgLy8g0J3QsNC50LTRkdC8INC80LjQvdC40LzQsNC70YzQvdGL0Lkg0YHRg9GE0YTQuNC60YEsINC/0L7QutGA0YvQstCw0Y7RidC40Lkg0YDQtdCx0YDQviDQtNC70Y8g0L7RgtCy0LXRgtCwINC90LAg0LfQsNC00LDRh9GDLiDQntC/0YbQuNC+0L3QsNC70YzQvdC+LgogICAgICAgICAgICBlZGdlICZFPWRhdGFbcF92ZXJ0LmJhY2soKV0uZ29bcF9lZGdlLmJhY2soKV07CiAgICAgICAgICAgIGlmKEUubmV4dF92ZXJ0KzEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBtPWRhdGFbRS5uZXh0X3ZlcnRdLmdvLnNpemUoKTsKICAgICAgICAgICAgICAgIGZvcihpbnQgaj0wO2o8bTtqKyspCiAgICAgICAgICAgICAgICAgICAgRS5zdWZmaXhfaGVyZT1taW4oRS5zdWZmaXhfaGVyZSxkYXRhW0UubmV4dF92ZXJ0XS5nb1tqXS5zdWZmaXhfaGVyZSk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIC8vINCj0LTQsNC70LjQvCDRgNC10LHRgNC+INC40Lcg0YHRgtC10LrQsC4g0JHQvtC70YzRiNC1INC80Ysg0LIg0L3QtdCz0L4g0L3QtSDQstC10YDQvdGR0LzRgdGPCiAgICAgICAgICAgIHBfdmVydC5wb3BfYmFjaygpOwogICAgICAgICAgICBwX2VkZ2UucG9wX2JhY2soKTsKICAgICAgICAgICAgcF9kaXN0LnBvcF9iYWNrKCk7CiAgICAgICAgfQogICAgfQoKICAgIGludCBzZWFyY2hfc3RyKHN0cmluZyAmcykKICAgIHsKICAgICAgICBpbnQgbj1zLnNpemUoKTsKICAgICAgICBpbnQgY3VyX3Y9MDsKICAgICAgICBpbnQgY3VyX2U7CiAgICAgICAgY2hhciB0OwoKICAgICAgICBmb3IoaW50IGk9MDtpPG47KQogICAgICAgIHsKICAgICAgICAgICAgaWYoY3VyX3Y9PS0xKWJyZWFrOwogICAgICAgICAgICB0PXNbaV07CiAgICAgICAgICAgIGludCBjdXJfZTsKICAgICAgICAgICAgZm9yKGN1cl9lPTA7Y3VyX2U8ZGF0YVtjdXJfdl0uZ28uc2l6ZSgpO2N1cl9lKyspCiAgICAgICAgICAgICAgICBpZihzdHJbZGF0YVtjdXJfdl0uZ29bY3VyX2VdLmZyb21dPj10KWJyZWFrOwogICAgICAgICAgICBmb3IoaW50IGo9ZGF0YVtjdXJfdl0uZ29bY3VyX2VdLmZyb207aTxuICYmIGo8ZGF0YVtjdXJfdl0uZ29bY3VyX2VdLnRvO2orKyxpKyspCiAgICAgICAgICAgICAgICBpZihzdHJbal0hPXNbaV0pCiAgICAgICAgICAgICAgICAgICAgaT1uKzE7CiAgICAgICAgICAgIGlmKGk9PW4pCiAgICAgICAgICAgICAgICByZXR1cm4gZGF0YVtjdXJfdl0uZ29bY3VyX2VdLnN1ZmZpeF9oZXJlOwogICAgICAgICAgICBjdXJfdj1kYXRhW2N1cl92XS5nb1tjdXJfZV0ubmV4dF92ZXJ0OwogICAgICAgIH0KICAgICAgICByZXR1cm4gLTE7CiAgICB9CgogICAgaW50IHByaW50KGludCB4KQogICAgewogICAgICAgIGlmKHg9PS0xKXJldHVybiAwOwogICAgICAgIGludCBhbnM9MDsKICAgICAgICBmb3IoaW50IGk9MDtpPGRhdGFbeF0uZ28uc2l6ZSgpO2krKykKICAgICAgICAgICAgYW5zKz1kYXRhW3hdLmdvW2ldLnRvLWRhdGFbeF0uZ29baV0uZnJvbStwcmludChkYXRhW3hdLmdvW2ldLm5leHRfdmVydCktKGRhdGFbeF0uZ29baV0udG89PXN0ci5zaXplKCkpOwogICAgICAgIHJldHVybiBhbnM7CiAgICB9Cn07CgppbnQgbWFpbigpCnsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKICAgIHN0cmluZyBhOwogICAgY2luPj5hOwogICAgYSs9JyMnOwogICAgc3VmZml4X3RyZWUgc2Y7CiAgICBzZi5idWlsZChhKTsKICAgIGNvdXQ8PHNmLnByaW50KDApPDxlbmRsOwp9