/*=================================*\
| |
| Md. Shahidul Islam |
| CSE, BRUR |
| Rangpur, Bangladesh |
| mail: shahidul.cse.brur@gmail.com |
| FB : fb.com/shahidul.brur |
| Blog: shahidul-brur.blogspot.com |
\*=================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsinged long long
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define vii vector<pair<int, int> >
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define all(a) a.begin(), a.end()
#define F(i, a, b) for(int i=a;i<=b;i++)
#define rep(i, k) for(int i=0;i<k;i++)
#define rep1(i, k) for(int i=1;i<=k;i++)
#define FORR(i, b, a) for(int i=b;i>=a;i--)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
#define pi acos(-1.0)
#define eps 1e-6
#define mem(a, b) memset(a, b, sizeof(a))
#define mod 1000000007
#define N 10005
#define inf 1e9
#define LN 14
vii tree[N];
vi edgeCost[N];
int chainHead[N], chainIndex[N], par[N][LN+5], depth[N], subSize[N], arrPos[N];
int endNode[N], chainNo, pos;
int costArr[N], segTree[N*4];
void initialize(int n)
{
for(int i=0;i<=n;i++)
{
tree[i].clear();
edgeCost[i].clear();
chainHead[i] = -1;
for(int j=0;j<LN;j++)
{
par[i][j] = -1;
}
}
}
void dfs(int node, int parent, int d)
{
depth[node] = d;
subSize[node] = 1;
par[node][0] = parent;
int siz = tree[node].sz;
for(int i=0;i<siz;i++)
{
int next = tree[node][i].ff;
int ind = tree[node][i].ss;
if(next!=parent)
{
endNode[ind] = next;
dfs(next, node, d+1);
subSize[node]+=subSize[next];
}
}
}
void initLCA(int n)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<LN;j++)
{
int pre = par[i][j-1];
if(pre!=-1)
par[i][j] = par[pre][j-1];
}
}
}
void HLD(int node, int cost, int parent)
{
if(chainHead[chainNo]==-1)
chainHead[chainNo] = node;
pos++;
chainIndex[node] = chainNo;
costArr[pos] = cost;
arrPos[node] = pos;
int siz = tree[node].sz;
int heavyNode = -1;
int heavyCost = 0;
for(int i=0;i<siz;i++)
{
int next = tree[node][i].ff;
if(next==parent)
continue;
if(heavyNode==-1 || subSize[next]>subSize[heavyNode])
{
heavyNode = next;
heavyCost = edgeCost[node][i];
}
}
if(heavyNode!=-1)
HLD(heavyNode, heavyCost, node);
for(int i=0;i<siz;i++)
{
int next = tree[node][i].ff;
if(next!=parent && next!=heavyNode)
{
chainNo++;
HLD(next, edgeCost[node][i], node);
}
}
}
void buildSegTree(int node, int b, int e)
{
if(b==e)
{
segTree[node] = costArr[b];
return;
}
int mid = (b+e)>>1;
int l = node<<1;
int r = l+1;
buildSegTree(l, b, mid);
buildSegTree(r, mid+1, e);
segTree[node] = max(segTree[l], segTree[r]);
}
int querySegTree(int node, int b, int e, int l, int r)
{
if(l>e || r<b)
return 0;
if(b>=l && e<=r)
return segTree[node];
int mid = (b+e)>>1;
int left = node<<1;
int right = left+1;
int q1 = querySegTree(left, b, mid, l, r);
int q2 = querySegTree(right, mid+1, e, l, r);
return max(q1, q2);
}
void updateSegTree(int node, int b, int e, int p, int val)
{
if(b==e)
{
segTree[node] = val;
return;
}
int mid = (b+e)>>1;
int l = node<<1;
int r = l+1;
if(p<=mid)
updateSegTree(l, b, mid, p, val);
else updateSegTree(r, mid+1, e, p, val);
segTree[node] = max(segTree[l], segTree[r]);
}
int LCA(int u, int v)
{
if(depth[u]<depth[v])
swap(u, v);
for(int i = LN-1;i>=0;i--)
{
if(depth[u] - (1<<i)>=depth[v])
u = par[u][i];
}
if(u==v)
return u;
for(int i = LN-1;i>=0;i--)
{
if(par[u][i]!=-1 && par[u][i]!=par[v][i])
{
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
int queryUp(int u, int v)
{
if(u==v)
return 0;
int lchain, rchain = chainIndex[v];
int ans = -1;
while(1)
{
lchain = chainIndex[u];
if(lchain==rchain)
{
if(u==v)
break;
int cur = querySegTree(1, 1, pos, arrPos[v]+1, arrPos[u]);
ans = max(cur, ans);
break;
}
int cur = querySegTree(1, 1, pos, arrPos[chainHead[lchain]], arrPos[u]);
ans = max(ans, cur);
u = chainHead[lchain];
u = par[u][0];
}
return ans;
}
int queryPath(int u, int v)
{
int lca = LCA(u, v);
int a = queryUp(u, lca);
int b = queryUp(v, lca);
return max(a, b);
}
void update(int idx, int val)
{
int node = endNode[idx];
updateSegTree(1, 1, pos, arrPos[node], val);
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//ios_base::sync_with_stdio(false); cin.tie(NULL);
int t, n, u, v;
int cost;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
initialize(n);
for(int i=1;i<n;i++)
{
scanf("%d %d", &u, &v);
scanf("%d", &cost);
tree[u].pb(pii(v, i));
tree[v].pb(pii(u, i));
edgeCost[u].pb(cost);
edgeCost[v].pb(cost);
}
dfs(1, 0, 0);
initLCA(n);
pos = -1;
chainNo = 1;
HLD(1, 0, -1);
buildSegTree(1, 1, pos);
char cmd[14];
scanf("%s", cmd);
while(cmd[0]!='D')
{
if(cmd[0]=='Q')
{
scanf("%d %d", &u, &v);
printf("%d\n", queryPath(u, v));
}
else
{
int edge;
int val;
scanf("%d", &edge);
scanf("%d", &val);
update(edge, val);
}
scanf("%s", cmd);
}
}
return 0;
}
Lyo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0qXAp8ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB8CnwgICAgICBNZC4gU2hhaGlkdWwgSXNsYW0gICAgICAgICAgIHwKfCAgICAgICAgIENTRSwgQlJVUiAgICAgICAgICAgICAgICAgfAp8ICAgICAgUmFuZ3B1ciwgQmFuZ2xhZGVzaCAgICAgICAgICB8CnwgbWFpbDogc2hhaGlkdWwuY3NlLmJydXJAZ21haWwuY29tIHwKfCBGQiAgOiBmYi5jb20vc2hhaGlkdWwuYnJ1ciAgICAgICAgfAp8IEJsb2c6IHNoYWhpZHVsLWJydXIuYmxvZ3Nwb3QuY29tICB8ClwqPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ki8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsICAgICAgIGxvbmcgbG9uZwojZGVmaW5lIHVsbCAgICAgIHVuc2luZ2VkIGxvbmcgbG9uZwojZGVmaW5lIHZpICAgICAgIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdmxsICAgICAgdmVjdG9yPGxsPgojZGVmaW5lIHBpaSAgICAgIHBhaXI8aW50LCBpbnQ+CiNkZWZpbmUgdmlpICAgICAgdmVjdG9yPHBhaXI8aW50LCBpbnQ+ID4KI2RlZmluZSB2cyAgICAgICB2ZWN0b3I8c3RyaW5nPgoKI2RlZmluZSBwYiAgICAgICAgICAgICAgcHVzaF9iYWNrCiNkZWZpbmUgbXAgICAgICAgICAgICAgIG1ha2VfcGFpcgojZGVmaW5lIGZmICAgICAgICAgICAgICBmaXJzdAojZGVmaW5lIHNzICAgICAgICAgICAgICBzZWNvbmQKI2RlZmluZSBzeiAgICAgICAgICAgICAgc2l6ZSgpCiNkZWZpbmUgYWxsKGEpICAgICAgICAgIGEuYmVnaW4oKSwgYS5lbmQoKQojZGVmaW5lIEYoaSwgYSwgYikgICAgICBmb3IoaW50IGk9YTtpPD1iO2krKykKI2RlZmluZSByZXAoaSwgaykgICAgICAgZm9yKGludCBpPTA7aTxrO2krKykKI2RlZmluZSByZXAxKGksIGspICAgICAgZm9yKGludCBpPTE7aTw9aztpKyspCiNkZWZpbmUgRk9SUihpLCBiLCBhKSAgIGZvcihpbnQgaT1iO2k+PWE7aS0tKQojZGVmaW5lIEZPUihpLCBhLCBiKSAgICBmb3IoaW50IGk9YTtpPD1iO2krKykKI2RlZmluZSBwaSAgICAgICAgICAgICAgYWNvcygtMS4wKQojZGVmaW5lIGVwcyAgICAgICAgICAgICAxZS02CiNkZWZpbmUgbWVtKGEsIGIpICAgICAgIG1lbXNldChhLCBiLCBzaXplb2YoYSkpCiNkZWZpbmUgbW9kICAgICAgICAgICAgIDEwMDAwMDAwMDcKI2RlZmluZSBOICAgICAgICAgICAgICAgMTAwMDUKI2RlZmluZSBpbmYgICAgICAgICAgICAgMWU5CiNkZWZpbmUgTE4gICAgICAgICAgICAgIDE0CnZpaSB0cmVlW05dOwp2aSBlZGdlQ29zdFtOXTsKaW50IGNoYWluSGVhZFtOXSwgY2hhaW5JbmRleFtOXSwgcGFyW05dW0xOKzVdLCBkZXB0aFtOXSwgc3ViU2l6ZVtOXSwgYXJyUG9zW05dOwppbnQgZW5kTm9kZVtOXSwgY2hhaW5ObywgcG9zOwppbnQgY29zdEFycltOXSwgc2VnVHJlZVtOKjRdOwoKdm9pZCBpbml0aWFsaXplKGludCBuKQp7CiAgICBmb3IoaW50IGk9MDtpPD1uO2krKykKICAgIHsKICAgICAgICB0cmVlW2ldLmNsZWFyKCk7CiAgICAgICAgZWRnZUNvc3RbaV0uY2xlYXIoKTsKICAgICAgICBjaGFpbkhlYWRbaV0gPSAtMTsKICAgICAgICBmb3IoaW50IGo9MDtqPExOO2orKykKICAgICAgICB7CiAgICAgICAgICAgIHBhcltpXVtqXSA9IC0xOwogICAgICAgIH0KICAgIH0KfQp2b2lkIGRmcyhpbnQgbm9kZSwgaW50IHBhcmVudCwgaW50IGQpCnsKICAgIGRlcHRoW25vZGVdID0gZDsKICAgIHN1YlNpemVbbm9kZV0gPSAxOwogICAgcGFyW25vZGVdWzBdID0gcGFyZW50OwogICAgaW50IHNpeiA9IHRyZWVbbm9kZV0uc3o7CiAgICBmb3IoaW50IGk9MDtpPHNpejtpKyspCiAgICB7CiAgICAgICAgaW50IG5leHQgPSB0cmVlW25vZGVdW2ldLmZmOwogICAgICAgIGludCBpbmQgPSB0cmVlW25vZGVdW2ldLnNzOwogICAgICAgIGlmKG5leHQhPXBhcmVudCkKICAgICAgICB7CiAgICAgICAgICAgIGVuZE5vZGVbaW5kXSA9IG5leHQ7CiAgICAgICAgICAgIGRmcyhuZXh0LCBub2RlLCBkKzEpOwogICAgICAgICAgICBzdWJTaXplW25vZGVdKz1zdWJTaXplW25leHRdOwogICAgICAgIH0KICAgIH0KfQp2b2lkIGluaXRMQ0EoaW50IG4pCnsKICAgIGZvcihpbnQgaT0xO2k8PW47aSsrKQogICAgewogICAgICAgIGZvcihpbnQgaj0xO2o8TE47aisrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHByZSA9IHBhcltpXVtqLTFdOwogICAgICAgICAgICBpZihwcmUhPS0xKQogICAgICAgICAgICAgICAgcGFyW2ldW2pdID0gcGFyW3ByZV1bai0xXTsKICAgICAgICB9CiAgICB9Cn0Kdm9pZCBITEQoaW50IG5vZGUsIGludCBjb3N0LCBpbnQgcGFyZW50KQp7CiAgICBpZihjaGFpbkhlYWRbY2hhaW5Ob109PS0xKQogICAgICAgIGNoYWluSGVhZFtjaGFpbk5vXSA9IG5vZGU7CiAgICAKICAgIHBvcysrOwogICAgY2hhaW5JbmRleFtub2RlXSA9IGNoYWluTm87CiAgICBjb3N0QXJyW3Bvc10gPSBjb3N0OwogICAgYXJyUG9zW25vZGVdID0gcG9zOwogICAgCiAgICBpbnQgc2l6ID0gdHJlZVtub2RlXS5zejsKICAgIGludCBoZWF2eU5vZGUgPSAtMTsKICAgIGludCBoZWF2eUNvc3QgPSAwOwogICAgCiAgICBmb3IoaW50IGk9MDtpPHNpejtpKyspCiAgICB7CiAgICAgICAgaW50IG5leHQgPSB0cmVlW25vZGVdW2ldLmZmOwogICAgICAgIGlmKG5leHQ9PXBhcmVudCkKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgaWYoaGVhdnlOb2RlPT0tMSB8fCBzdWJTaXplW25leHRdPnN1YlNpemVbaGVhdnlOb2RlXSkKICAgICAgICB7CiAgICAgICAgICAgIGhlYXZ5Tm9kZSA9IG5leHQ7CiAgICAgICAgICAgIGhlYXZ5Q29zdCA9IGVkZ2VDb3N0W25vZGVdW2ldOwogICAgICAgIH0KICAgIH0KICAgIAogICAgaWYoaGVhdnlOb2RlIT0tMSkKICAgICAgICBITEQoaGVhdnlOb2RlLCBoZWF2eUNvc3QsIG5vZGUpOwogICAgCiAgICBmb3IoaW50IGk9MDtpPHNpejtpKyspCiAgICB7CiAgICAgICAgaW50IG5leHQgPSB0cmVlW25vZGVdW2ldLmZmOwogICAgICAgIGlmKG5leHQhPXBhcmVudCAmJiBuZXh0IT1oZWF2eU5vZGUpCiAgICAgICAgewogICAgICAgICAgICBjaGFpbk5vKys7CiAgICAgICAgICAgIEhMRChuZXh0LCBlZGdlQ29zdFtub2RlXVtpXSwgbm9kZSk7CiAgICAgICAgfQogICAgfQp9CnZvaWQgYnVpbGRTZWdUcmVlKGludCBub2RlLCBpbnQgYiwgaW50IGUpCnsKICAgIGlmKGI9PWUpCiAgICB7CiAgICAgICAgc2VnVHJlZVtub2RlXSA9IGNvc3RBcnJbYl07CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IG1pZCA9IChiK2UpPj4xOwogICAgaW50IGwgPSBub2RlPDwxOwogICAgaW50IHIgPSBsKzE7CiAgICBidWlsZFNlZ1RyZWUobCwgYiwgbWlkKTsKICAgIGJ1aWxkU2VnVHJlZShyLCBtaWQrMSwgZSk7CiAgICBzZWdUcmVlW25vZGVdID0gbWF4KHNlZ1RyZWVbbF0sIHNlZ1RyZWVbcl0pOwp9CmludCBxdWVyeVNlZ1RyZWUoaW50IG5vZGUsIGludCBiLCBpbnQgZSwgaW50IGwsIGludCByKQp7CiAgICBpZihsPmUgfHwgcjxiKQogICAgICAgIHJldHVybiAwOwogICAgaWYoYj49bCAmJiBlPD1yKQogICAgICAgIHJldHVybiBzZWdUcmVlW25vZGVdOwogICAgaW50IG1pZCA9IChiK2UpPj4xOwogICAgaW50IGxlZnQgPSBub2RlPDwxOwogICAgaW50IHJpZ2h0ID0gbGVmdCsxOwogICAgaW50IHExID0gcXVlcnlTZWdUcmVlKGxlZnQsIGIsIG1pZCwgbCwgcik7CiAgICBpbnQgcTIgPSBxdWVyeVNlZ1RyZWUocmlnaHQsIG1pZCsxLCBlLCBsLCByKTsKICAgIHJldHVybiBtYXgocTEsIHEyKTsKfQp2b2lkIHVwZGF0ZVNlZ1RyZWUoaW50IG5vZGUsIGludCBiLCBpbnQgZSwgaW50IHAsIGludCB2YWwpCnsKICAgIGlmKGI9PWUpCiAgICB7CiAgICAgICAgc2VnVHJlZVtub2RlXSA9IHZhbDsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbWlkID0gKGIrZSk+PjE7CiAgICBpbnQgbCA9IG5vZGU8PDE7CiAgICBpbnQgciA9IGwrMTsKICAgIGlmKHA8PW1pZCkKICAgICAgICB1cGRhdGVTZWdUcmVlKGwsIGIsIG1pZCwgcCwgdmFsKTsKICAgIGVsc2UgdXBkYXRlU2VnVHJlZShyLCBtaWQrMSwgZSwgcCwgdmFsKTsKICAgIHNlZ1RyZWVbbm9kZV0gPSBtYXgoc2VnVHJlZVtsXSwgc2VnVHJlZVtyXSk7Cn0KaW50IExDQShpbnQgdSwgaW50IHYpCnsKICAgIGlmKGRlcHRoW3VdPGRlcHRoW3ZdKQogICAgICAgIHN3YXAodSwgdik7CiAgICBmb3IoaW50IGkgPSBMTi0xO2k+PTA7aS0tKQogICAgewogICAgICAgIGlmKGRlcHRoW3VdIC0gKDE8PGkpPj1kZXB0aFt2XSkKICAgICAgICAgICAgdSA9IHBhclt1XVtpXTsKICAgIH0KICAgIAogICAgaWYodT09dikKICAgICAgICByZXR1cm4gdTsKICAgIGZvcihpbnQgaSA9IExOLTE7aT49MDtpLS0pCiAgICB7CiAgICAgICAgaWYocGFyW3VdW2ldIT0tMSAmJiBwYXJbdV1baV0hPXBhclt2XVtpXSkKICAgICAgICB7CiAgICAgICAgICAgIHUgPSBwYXJbdV1baV07CiAgICAgICAgICAgIHYgPSBwYXJbdl1baV07CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHBhclt1XVswXTsKfQppbnQgcXVlcnlVcChpbnQgdSwgaW50IHYpCnsKICAgIGlmKHU9PXYpCiAgICAgICAgcmV0dXJuIDA7CiAgICBpbnQgbGNoYWluLCByY2hhaW4gPSBjaGFpbkluZGV4W3ZdOwogICAgaW50IGFucyA9IC0xOwogICAgd2hpbGUoMSkKICAgIHsKICAgICAgICBsY2hhaW4gPSBjaGFpbkluZGV4W3VdOwogICAgICAgIGlmKGxjaGFpbj09cmNoYWluKQogICAgICAgIHsKICAgICAgICAgICAgaWYodT09dikKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICBpbnQgY3VyID0gcXVlcnlTZWdUcmVlKDEsIDEsIHBvcywgYXJyUG9zW3ZdKzEsIGFyclBvc1t1XSk7CiAgICAgICAgICAgIGFucyA9IG1heChjdXIsIGFucyk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICBpbnQgY3VyID0gcXVlcnlTZWdUcmVlKDEsIDEsIHBvcywgYXJyUG9zW2NoYWluSGVhZFtsY2hhaW5dXSwgYXJyUG9zW3VdKTsKICAgICAgICBhbnMgPSBtYXgoYW5zLCBjdXIpOwogICAgICAgIHUgPSBjaGFpbkhlYWRbbGNoYWluXTsKICAgICAgICB1ID0gcGFyW3VdWzBdOwogICAgfQogICAgcmV0dXJuIGFuczsKfQppbnQgcXVlcnlQYXRoKGludCB1LCBpbnQgdikKewogICAgCiAgICBpbnQgbGNhID0gTENBKHUsIHYpOwogICAgCiAgICBpbnQgYSA9IHF1ZXJ5VXAodSwgbGNhKTsKICAgIGludCBiID0gcXVlcnlVcCh2LCBsY2EpOwogICAgcmV0dXJuIG1heChhLCBiKTsKfQp2b2lkIHVwZGF0ZShpbnQgaWR4LCBpbnQgdmFsKQp7CiAgICBpbnQgbm9kZSA9IGVuZE5vZGVbaWR4XTsKICAgIHVwZGF0ZVNlZ1RyZWUoMSwgMSwgcG9zLCBhcnJQb3Nbbm9kZV0sIHZhbCk7Cn0KaW50IG1haW4oKQp7CiAgICAvL2ZyZW9wZW4oImluLnR4dCIsICJyIiwgc3RkaW4pOwogICAgLy9mcmVvcGVuKCJvdXQudHh0IiwgInciLCBzdGRvdXQpOwogICAgLy9pb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKTsKICAgIGludCB0LCBuLCB1LCB2OwogICAgaW50IGNvc3Q7CiAgICBzY2FuZigiJWQiLCAmdCk7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgc2NhbmYoIiVkIiwgJm4pOwogICAgICAgIGluaXRpYWxpemUobik7CiAgICAgICAgZm9yKGludCBpPTE7aTxuO2krKykKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlZCAlZCIsICZ1LCAmdik7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZjb3N0KTsKICAgICAgICAgICAgdHJlZVt1XS5wYihwaWkodiwgaSkpOwogICAgICAgICAgICB0cmVlW3ZdLnBiKHBpaSh1LCBpKSk7CiAgICAgICAgICAgIAogICAgICAgICAgICBlZGdlQ29zdFt1XS5wYihjb3N0KTsKICAgICAgICAgICAgZWRnZUNvc3Rbdl0ucGIoY29zdCk7CiAgICAgICAgfQogICAgICAgIGRmcygxLCAwLCAwKTsKICAgICAgICAKICAgICAgICBpbml0TENBKG4pOwogICAgICAgIAogICAgICAgIHBvcyA9IC0xOwogICAgICAgIGNoYWluTm8gPSAxOwogICAgICAgIEhMRCgxLCAwLCAtMSk7CiAgICAgICAgCiAgICAgICAgYnVpbGRTZWdUcmVlKDEsIDEsIHBvcyk7CiAgICAgICAgY2hhciBjbWRbMTRdOwogICAgICAgIHNjYW5mKCIlcyIsIGNtZCk7CiAgICAgICAgd2hpbGUoY21kWzBdIT0nRCcpCiAgICAgICAgewogICAgICAgICAgICBpZihjbWRbMF09PSdRJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc2NhbmYoIiVkICVkIiwgJnUsICZ2KTsKICAgICAgICAgICAgICAgIHByaW50ZigiJWRcbiIsIHF1ZXJ5UGF0aCh1LCB2KSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgZWRnZTsKICAgICAgICAgICAgICAgIGludCB2YWw7CiAgICAgICAgICAgICAgICBzY2FuZigiJWQiLCAmZWRnZSk7CiAgICAgICAgICAgICAgICBzY2FuZigiJWQiLCAmdmFsKTsKICAgICAgICAgICAgICAgIHVwZGF0ZShlZGdlLCB2YWwpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHNjYW5mKCIlcyIsIGNtZCk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0K