#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;
template<typename M>
class LinkCutTree {
public:
using T = typename M::T;
using E = typename M::E;
struct node {
int sz, idx;
T val, sum;
E lazy;
node *left, *right, *par;
bool rev;
node(int idx) : sz(1), idx(idx), val(M::T0()), sum(M::T0()), lazy(M::E0()),
left(nullptr), right(nullptr), par(nullptr), rev(false) {}
node(T _val, int idx) : sz(1), idx(idx), val(_val), sum(_val), lazy(M::E0()),
left(nullptr), right(nullptr), par(nullptr), rev(false) {}
inline bool isRoot() const {
return (!par) || (par->left != this && par->right != this);
}
void push() {
if(lazy != M::E0()) {
val = M::g(val, lazy, 1), sum = M::g(sum, lazy, sz);
if(left) left->lazy = M::h(left->lazy, lazy);
if(right) right->lazy = M::h(right->lazy, lazy);
lazy = M::E0();
}
if(rev) {
swap(left, right);
sum = M::s(sum);
if(left) left->rev ^= true;
if(right) right->rev ^= true;
rev = false;
}
}
void eval() {
sz = 1, sum = val;
if(left) left->push(), sz += left->sz, sum = M::f(left->sum, sum);
if(right) right->push(), sz += right->sz, sum = M::f(sum, right->sum);
}
};
private:
void rotate(node *u, bool right) {
node *p = u->par, *g = p->par;
if(right) {
if((p->left = u->right)) u->right->par = p;
u->right = p, p->par = u;
} else {
if((p->right = u->left)) u->left->par = p;
u->left = p, p->par = u;
}
p->eval(), u->eval(), u->par = g;
if(!g) return;
if(g->left == p) g->left = u;
if(g->right == p) g->right = u;
g->eval();
}
// uをsplay木の根にする
void splay(node *u) {
while(!u->isRoot()) {
node *p = u->par, *gp = p->par;
if(p->isRoot()) { // zig
p->push(), u->push();
rotate(u, (u == p->left));
} else {
gp->push(), p->push(), u->push();
bool flag = (u == p->left);
if((u == p->left) == (p == gp->left)) { // zig-zig
rotate(p, flag), rotate(u, flag);
} else { // zig-zag
rotate(u, flag), rotate(u, !flag);
}
}
}
u->push();
}
// 頂点uから根へのパスをつなげる
node* expose(node *u) {
node *last = nullptr;
for(node *v = u; v; v = v->par) {
splay(v);
v->right = last;
v->eval();
last = v;
}
splay(u);
return last;
}
void evert(node *u) {
expose(u), u->rev = !(u->rev), u->push();
}
bool connected(node *u, node *v) {
expose(u), expose(v);
return u == v || u->par;
}
void link(node *u, node *v) {
evert(u), u->par = v;
}
void cut(node *u) { // uと親の辺を切る
expose(u), u->left->par = nullptr, u->left = nullptr, u->eval();
}
void cut(node *u, node *v) {
expose(u), expose(v);
if(u->isRoot()) u->par = nullptr;
else v->left->par = nullptr, v->left = nullptr, v->eval();
}
node* lca(node *u, node *v) {
expose(u);
return expose(v);
}
int depth(node *u) {
expose(u);
return u->sz - 1;
}
void toRoot_range(node *u, const E x) {
expose(u);
u->lazy = M::h(u->lazy, x), u->push();
}
void range(node *u, node *v, const E x) {
evert(u), expose(v);
v->lazy = M::h(v->lazy, x), v->push();
}
void toRoot_query(node *u) {
expose(u);
return u->sum;
}
T query(node *u, node *v) {
evert(u), expose(v);
return v->sum;
}
node* get_kth(node *u, node *v, int k) {
evert(v), expose(u);
while(u) {
push(u);
if(u->right && u->right->sz > k) u = u->right;
else {
if(u->right) k -= u->right->sz;
if(k == 0) return u;
k--;
u = u->left;
}
}
return nullptr;
}
public:
const int n;
node** arr;
LinkCutTree(const vector<T> &v) : n(v.size()) {
arr = new node*[n];
REP(i, n) arr[i] = new node(v[i], i);
}
~LinkCutTree(){
REP(i, n) delete arr[i];
delete[] arr;
}
bool connected(int id1, int id2) { return connected(arr[id1], arr[id2]); }
void link(int id1, int id2) { return link(arr[id1], arr[id2]); }
void cut(int id) { return cut(arr[id]); } // uと親の辺を切る
void cut(int id1, int id2) { return cut(arr[id1], arr[id2]); }
int lca(int id1, int id2) { return lca(arr[id1], arr[id2])->idx; }
void evert(int id) { return evert(arr[id]); }
int depth(int id) { return depth(arr[id]); }
void toRoot_range(int id, const E x) { return toRoot_range(arr[id], x); }
void range(int id1, int id2, const E x) { return range(arr[id1], arr[id2], x); }
T toRoot_query(int id) { return toRoot_query(arr[id]); }
T query(int id1, int id2) { return query(arr[id1], arr[id2]); }
int get_kth(int id1, int id2, int k) {
node *u = get_kth(arr[id1], arr[id2], k);
return !u ? -1 : u->idx;
}
};
struct monoid {
using T = ll;
using E = ll;
static T T0() { return -INF; }
static constexpr E E0() { return -INF; }
static T f(const T &x, const T &y) { return max(x, y); }
static T g(const T &x, const E &y, int sz) { return y; }
static E h(const E &x, const E &y) { return y; }
static T s(const T &x) { return x; }
};
void solve() {
ll n;
cin >> n;
vector<ll> a(n-1), b(n-1), c(n-1);
REP(i, n-1) {
cin >> a[i] >> b[i] >> c[i];
a[i]--, b[i]--;
}
vector<ll> init(2*n-1);
REP(i, n-1) init[n+i] = c[i];
LinkCutTree<monoid> lct(init);
REP(i, n-1) lct.link(a[i], n+i), lct.link(n+i, b[i]);
while(1) {
string s;
cin >> s;
if(s[0]=='D') break;
if(s[0]=='Q') {
ll u, v;
cin >> u >> v;
u--, v--;
cout << lct.query(u, v) << "\n";
} else {
ll u, v;
cin >> u >> v;
u--;
lct.range(n+u, n+u, v);
}
}
cout << flush;
}
int main(void) {
ll t;
cin >> t;
while(t--) solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwp1c2luZyBQSUkgPSBwYWlyPGxsLCBsbD47CiNkZWZpbmUgRk9SKGksIGEsIG4pIGZvciAobGwgaSA9IChsbClhOyBpIDwgKGxsKW47ICsraSkKI2RlZmluZSBSRVAoaSwgbikgRk9SKGksIDAsIG4pCiNkZWZpbmUgQUxMKHgpIHguYmVnaW4oKSwgeC5lbmQoKQp0ZW1wbGF0ZTx0eXBlbmFtZSBUPiB2b2lkIGNobWluKFQgJmEsIGNvbnN0IFQgJmIpIHsgYSA9IG1pbihhLCBiKTsgfQp0ZW1wbGF0ZTx0eXBlbmFtZSBUPiB2b2lkIGNobWF4KFQgJmEsIGNvbnN0IFQgJmIpIHsgYSA9IG1heChhLCBiKTsgfQpzdHJ1Y3QgRmFzdElPIHtGYXN0SU8oKSB7IGNpbi50aWUoMCk7IGlvczo6c3luY193aXRoX3N0ZGlvKDApOyB9fWZhc3Rpb2Zhc3RpbzsKI2lmZGVmIERFQlVHXyAKI2luY2x1ZGUgIi4uL3Byb2dyYW1fY29udGVzdF9saWJyYXJ5L21lbW8vZHVtcC5ocHAiCiNlbHNlCiNkZWZpbmUgZHVtcCguLi4pCiNlbmRpZgpjb25zdCBsbCBJTkYgPSAxTEw8PDYwOwoKdGVtcGxhdGU8dHlwZW5hbWUgTT4KY2xhc3MgTGlua0N1dFRyZWUgewpwdWJsaWM6CiAgICB1c2luZyBUID0gdHlwZW5hbWUgTTo6VDsKICAgIHVzaW5nIEUgPSB0eXBlbmFtZSBNOjpFOwoKICAgIHN0cnVjdCBub2RlIHsKICAgICAgICBpbnQgc3osIGlkeDsKICAgICAgICBUIHZhbCwgc3VtOwogICAgICAgIEUgbGF6eTsKICAgICAgICBub2RlICpsZWZ0LCAqcmlnaHQsICpwYXI7CiAgICAgICAgYm9vbCByZXY7CiAgICAgICAgbm9kZShpbnQgaWR4KSA6IHN6KDEpLCBpZHgoaWR4KSwgdmFsKE06OlQwKCkpLCBzdW0oTTo6VDAoKSksIGxhenkoTTo6RTAoKSksCiAgICAgICAgICAgIGxlZnQobnVsbHB0ciksIHJpZ2h0KG51bGxwdHIpLCBwYXIobnVsbHB0ciksIHJldihmYWxzZSkge30KICAgICAgICBub2RlKFQgX3ZhbCwgaW50IGlkeCkgOiBzeigxKSwgaWR4KGlkeCksIHZhbChfdmFsKSwgc3VtKF92YWwpLCBsYXp5KE06OkUwKCkpLAogICAgICAgICAgICBsZWZ0KG51bGxwdHIpLCByaWdodChudWxscHRyKSwgcGFyKG51bGxwdHIpLCByZXYoZmFsc2UpIHt9CiAgICAgICAgaW5saW5lIGJvb2wgaXNSb290KCkgY29uc3QgewogICAgICAgICAgICByZXR1cm4gKCFwYXIpIHx8IChwYXItPmxlZnQgIT0gdGhpcyAmJiBwYXItPnJpZ2h0ICE9IHRoaXMpOwogICAgICAgIH0KICAgICAgICB2b2lkIHB1c2goKSB7CiAgICAgICAgICAgIGlmKGxhenkgIT0gTTo6RTAoKSkgewogICAgICAgICAgICAgICAgdmFsID0gTTo6Zyh2YWwsIGxhenksIDEpLCBzdW0gPSBNOjpnKHN1bSwgbGF6eSwgc3opOwogICAgICAgICAgICAgICAgaWYobGVmdCkgbGVmdC0+bGF6eSA9IE06OmgobGVmdC0+bGF6eSwgbGF6eSk7CiAgICAgICAgICAgICAgICBpZihyaWdodCkgcmlnaHQtPmxhenkgPSBNOjpoKHJpZ2h0LT5sYXp5LCBsYXp5KTsKICAgICAgICAgICAgICAgIGxhenkgPSBNOjpFMCgpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKHJldikgewogICAgICAgICAgICAgICAgc3dhcChsZWZ0LCByaWdodCk7CiAgICAgICAgICAgICAgICBzdW0gPSBNOjpzKHN1bSk7CiAgICAgICAgICAgICAgICBpZihsZWZ0KSBsZWZ0LT5yZXYgXj0gdHJ1ZTsKICAgICAgICAgICAgICAgIGlmKHJpZ2h0KSByaWdodC0+cmV2IF49IHRydWU7CiAgICAgICAgICAgICAgICByZXYgPSBmYWxzZTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICB2b2lkIGV2YWwoKSB7CiAgICAgICAgICAgIHN6ID0gMSwgc3VtID0gdmFsOwogICAgICAgICAgICBpZihsZWZ0KSBsZWZ0LT5wdXNoKCksIHN6ICs9IGxlZnQtPnN6LCBzdW0gPSBNOjpmKGxlZnQtPnN1bSwgc3VtKTsKICAgICAgICAgICAgaWYocmlnaHQpIHJpZ2h0LT5wdXNoKCksIHN6ICs9IHJpZ2h0LT5zeiwgc3VtID0gTTo6ZihzdW0sIHJpZ2h0LT5zdW0pOwogICAgICAgIH0KICAgIH07CiAKcHJpdmF0ZToKICAgIHZvaWQgcm90YXRlKG5vZGUgKnUsIGJvb2wgcmlnaHQpIHsKICAgICAgICBub2RlICpwID0gdS0+cGFyLCAqZyA9IHAtPnBhcjsKICAgICAgICBpZihyaWdodCkgewogICAgICAgICAgICBpZigocC0+bGVmdCA9IHUtPnJpZ2h0KSkgdS0+cmlnaHQtPnBhciA9IHA7CiAgICAgICAgICAgIHUtPnJpZ2h0ID0gcCwgcC0+cGFyID0gdTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBpZigocC0+cmlnaHQgPSB1LT5sZWZ0KSkgdS0+bGVmdC0+cGFyID0gcDsKICAgICAgICAgICAgdS0+bGVmdCA9IHAsIHAtPnBhciA9IHU7CiAgICAgICAgfQogICAgICAgIHAtPmV2YWwoKSwgdS0+ZXZhbCgpLCB1LT5wYXIgPSBnOwogICAgICAgIGlmKCFnKSByZXR1cm47CiAgICAgICAgaWYoZy0+bGVmdCA9PSBwKSBnLT5sZWZ0ID0gdTsKICAgICAgICBpZihnLT5yaWdodCA9PSBwKSBnLT5yaWdodCA9IHU7CiAgICAgICAgZy0+ZXZhbCgpOwogICAgfQogICAgLy8gdeOCknNwbGF55pyo44Gu5qC544Gr44GZ44KLCiAgICB2b2lkIHNwbGF5KG5vZGUgKnUpIHsKICAgICAgICB3aGlsZSghdS0+aXNSb290KCkpIHsKICAgICAgICAgICAgbm9kZSAqcCA9IHUtPnBhciwgKmdwID0gcC0+cGFyOwogICAgICAgICAgICBpZihwLT5pc1Jvb3QoKSkgeyAvLyB6aWcKICAgICAgICAgICAgICAgIHAtPnB1c2goKSwgdS0+cHVzaCgpOwogICAgICAgICAgICAgICAgcm90YXRlKHUsICh1ID09IHAtPmxlZnQpKTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGdwLT5wdXNoKCksIHAtPnB1c2goKSwgdS0+cHVzaCgpOwogICAgICAgICAgICAgICAgYm9vbCBmbGFnID0gKHUgPT0gcC0+bGVmdCk7CiAgICAgICAgICAgICAgICBpZigodSA9PSBwLT5sZWZ0KSA9PSAocCA9PSBncC0+bGVmdCkpIHsgLy8gemlnLXppZwogICAgICAgICAgICAgICAgICAgIHJvdGF0ZShwLCBmbGFnKSwgcm90YXRlKHUsIGZsYWcpOwogICAgICAgICAgICAgICAgfSBlbHNlIHsgLy8gemlnLXphZwogICAgICAgICAgICAgICAgICAgIHJvdGF0ZSh1LCBmbGFnKSwgcm90YXRlKHUsICFmbGFnKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICB1LT5wdXNoKCk7CiAgICB9CiAgICAvLyDpoILngrl144GL44KJ5qC544G444Gu44OR44K544KS44Gk44Gq44GS44KLCiAgICBub2RlKiBleHBvc2Uobm9kZSAqdSkgewogICAgICAgIG5vZGUgKmxhc3QgPSBudWxscHRyOwogICAgICAgIGZvcihub2RlICp2ID0gdTsgdjsgdiA9IHYtPnBhcikgewogICAgICAgICAgICBzcGxheSh2KTsKICAgICAgICAgICAgdi0+cmlnaHQgPSBsYXN0OwogICAgICAgICAgICB2LT5ldmFsKCk7CiAgICAgICAgICAgIGxhc3QgPSB2OwogICAgICAgIH0KICAgICAgICBzcGxheSh1KTsKICAgICAgICByZXR1cm4gbGFzdDsKICAgIH0KICAgIHZvaWQgZXZlcnQobm9kZSAqdSkgewogICAgICAgIGV4cG9zZSh1KSwgdS0+cmV2ID0gISh1LT5yZXYpLCB1LT5wdXNoKCk7CiAgICB9CiAgICBib29sIGNvbm5lY3RlZChub2RlICp1LCBub2RlICp2KSB7CiAgICAgICAgZXhwb3NlKHUpLCBleHBvc2Uodik7CiAgICAgICAgcmV0dXJuIHUgPT0gdiB8fCB1LT5wYXI7CiAgICB9CiAgICB2b2lkIGxpbmsobm9kZSAqdSwgbm9kZSAqdikgewogICAgICAgIGV2ZXJ0KHUpLCB1LT5wYXIgPSB2OwogICAgfQogICAgdm9pZCBjdXQobm9kZSAqdSkgeyAvLyB144Go6Kaq44Gu6L6644KS5YiH44KLCiAgICAgICAgZXhwb3NlKHUpLCB1LT5sZWZ0LT5wYXIgPSBudWxscHRyLCB1LT5sZWZ0ID0gbnVsbHB0ciwgdS0+ZXZhbCgpOwogICAgfQogICAgdm9pZCBjdXQobm9kZSAqdSwgbm9kZSAqdikgewogICAgICAgIGV4cG9zZSh1KSwgZXhwb3NlKHYpOwogICAgICAgIGlmKHUtPmlzUm9vdCgpKSB1LT5wYXIgPSBudWxscHRyOwogICAgICAgIGVsc2Ugdi0+bGVmdC0+cGFyID0gbnVsbHB0ciwgdi0+bGVmdCA9IG51bGxwdHIsIHYtPmV2YWwoKTsKICAgIH0KICAgIG5vZGUqIGxjYShub2RlICp1LCBub2RlICp2KSB7CiAgICAgICAgZXhwb3NlKHUpOwogICAgICAgIHJldHVybiBleHBvc2Uodik7CiAgICB9CiAgICBpbnQgZGVwdGgobm9kZSAqdSkgewogICAgICAgIGV4cG9zZSh1KTsKICAgICAgICByZXR1cm4gdS0+c3ogLSAxOwogICAgfQogICAgdm9pZCB0b1Jvb3RfcmFuZ2Uobm9kZSAqdSwgY29uc3QgRSB4KSB7CiAgICAgICAgZXhwb3NlKHUpOwogICAgICAgIHUtPmxhenkgPSBNOjpoKHUtPmxhenksIHgpLCB1LT5wdXNoKCk7CiAgICB9CiAgICB2b2lkIHJhbmdlKG5vZGUgKnUsIG5vZGUgKnYsIGNvbnN0IEUgeCkgewogICAgICAgIGV2ZXJ0KHUpLCBleHBvc2Uodik7CiAgICAgICAgdi0+bGF6eSA9IE06Omgodi0+bGF6eSwgeCksIHYtPnB1c2goKTsKICAgIH0KICAgIHZvaWQgdG9Sb290X3F1ZXJ5KG5vZGUgKnUpIHsKICAgICAgICBleHBvc2UodSk7CiAgICAgICAgcmV0dXJuIHUtPnN1bTsKICAgIH0KICAgIFQgcXVlcnkobm9kZSAqdSwgbm9kZSAqdikgewogICAgICAgIGV2ZXJ0KHUpLCBleHBvc2Uodik7CiAgICAgICAgcmV0dXJuIHYtPnN1bTsKICAgIH0KICAgIG5vZGUqIGdldF9rdGgobm9kZSAqdSwgbm9kZSAqdiwgaW50IGspIHsKICAgICAgICBldmVydCh2KSwgZXhwb3NlKHUpOwogICAgICAgIHdoaWxlKHUpIHsKICAgICAgICAgICAgcHVzaCh1KTsKICAgICAgICAgICAgaWYodS0+cmlnaHQgJiYgdS0+cmlnaHQtPnN6ID4gaykgdSA9IHUtPnJpZ2h0OwogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIGlmKHUtPnJpZ2h0KSBrIC09IHUtPnJpZ2h0LT5zejsKICAgICAgICAgICAgICAgIGlmKGsgPT0gMCkgcmV0dXJuIHU7CiAgICAgICAgICAgICAgICBrLS07CiAgICAgICAgICAgICAgICB1ID0gdS0+bGVmdDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gbnVsbHB0cjsKICAgIH0KIApwdWJsaWM6CiAgICBjb25zdCBpbnQgbjsKICAgIG5vZGUqKiBhcnI7CiAgICBMaW5rQ3V0VHJlZShjb25zdCB2ZWN0b3I8VD4gJnYpIDogbih2LnNpemUoKSkgeyAKICAgICAgICBhcnIgPSBuZXcgbm9kZSpbbl07CiAgICAgICAgUkVQKGksIG4pIGFycltpXSA9IG5ldyBub2RlKHZbaV0sIGkpOwogICAgfQogICAgfkxpbmtDdXRUcmVlKCl7CiAgICAgICAgUkVQKGksIG4pIGRlbGV0ZSBhcnJbaV07CiAgICAgICAgZGVsZXRlW10gYXJyOwogICAgfQogICAgYm9vbCBjb25uZWN0ZWQoaW50IGlkMSwgaW50IGlkMikgeyByZXR1cm4gY29ubmVjdGVkKGFycltpZDFdLCBhcnJbaWQyXSk7IH0KICAgIHZvaWQgbGluayhpbnQgaWQxLCBpbnQgaWQyKSB7IHJldHVybiBsaW5rKGFycltpZDFdLCBhcnJbaWQyXSk7IH0KICAgIHZvaWQgY3V0KGludCBpZCkgeyByZXR1cm4gY3V0KGFycltpZF0pOyB9IC8vIHXjgajopqrjga7ovrrjgpLliIfjgosKICAgIHZvaWQgY3V0KGludCBpZDEsIGludCBpZDIpIHsgcmV0dXJuIGN1dChhcnJbaWQxXSwgYXJyW2lkMl0pOyB9CiAgICBpbnQgbGNhKGludCBpZDEsIGludCBpZDIpIHsgcmV0dXJuIGxjYShhcnJbaWQxXSwgYXJyW2lkMl0pLT5pZHg7IH0KICAgIHZvaWQgZXZlcnQoaW50IGlkKSB7IHJldHVybiBldmVydChhcnJbaWRdKTsgfQogICAgaW50IGRlcHRoKGludCBpZCkgeyByZXR1cm4gZGVwdGgoYXJyW2lkXSk7IH0KICAgIHZvaWQgdG9Sb290X3JhbmdlKGludCBpZCwgY29uc3QgRSB4KSB7IHJldHVybiB0b1Jvb3RfcmFuZ2UoYXJyW2lkXSwgeCk7IH0KICAgIHZvaWQgcmFuZ2UoaW50IGlkMSwgaW50IGlkMiwgY29uc3QgRSB4KSB7IHJldHVybiByYW5nZShhcnJbaWQxXSwgYXJyW2lkMl0sIHgpOyB9CiAgICBUIHRvUm9vdF9xdWVyeShpbnQgaWQpIHsgcmV0dXJuIHRvUm9vdF9xdWVyeShhcnJbaWRdKTsgfQogICAgVCBxdWVyeShpbnQgaWQxLCBpbnQgaWQyKSB7IHJldHVybiBxdWVyeShhcnJbaWQxXSwgYXJyW2lkMl0pOyB9CiAgICBpbnQgZ2V0X2t0aChpbnQgaWQxLCBpbnQgaWQyLCBpbnQgaykgewogICAgICAgIG5vZGUgKnUgPSBnZXRfa3RoKGFycltpZDFdLCBhcnJbaWQyXSwgayk7CiAgICAgICAgcmV0dXJuICF1ID8gLTEgOiB1LT5pZHg7CiAgICB9Cn07CgpzdHJ1Y3QgbW9ub2lkIHsKICAgIHVzaW5nIFQgPSBsbDsKICAgIHVzaW5nIEUgPSBsbDsKICAgIHN0YXRpYyBUIFQwKCkgeyByZXR1cm4gLUlORjsgfQogICAgc3RhdGljIGNvbnN0ZXhwciBFIEUwKCkgeyByZXR1cm4gLUlORjsgfQogICAgc3RhdGljIFQgZihjb25zdCBUICZ4LCBjb25zdCBUICZ5KSB7IHJldHVybiBtYXgoeCwgeSk7IH0KICAgIHN0YXRpYyBUIGcoY29uc3QgVCAmeCwgY29uc3QgRSAmeSwgaW50IHN6KSB7IHJldHVybiB5OyB9CiAgICBzdGF0aWMgRSBoKGNvbnN0IEUgJngsIGNvbnN0IEUgJnkpIHsgcmV0dXJuIHk7IH0KICAgIHN0YXRpYyBUIHMoY29uc3QgVCAmeCkgeyByZXR1cm4geDsgfQp9OwoKdm9pZCBzb2x2ZSgpIHsKICAgIGxsIG47CiAgICBjaW4gPj4gbjsKICAgIHZlY3RvcjxsbD4gYShuLTEpLCBiKG4tMSksIGMobi0xKTsKICAgIFJFUChpLCBuLTEpIHsKICAgICAgICBjaW4gPj4gYVtpXSA+PiBiW2ldID4+IGNbaV07CiAgICAgICAgYVtpXS0tLCBiW2ldLS07CiAgICB9CgogICAgdmVjdG9yPGxsPiBpbml0KDIqbi0xKTsKICAgIFJFUChpLCBuLTEpIGluaXRbbitpXSA9IGNbaV07CiAgICBMaW5rQ3V0VHJlZTxtb25vaWQ+IGxjdChpbml0KTsKICAgIFJFUChpLCBuLTEpIGxjdC5saW5rKGFbaV0sIG4raSksIGxjdC5saW5rKG4raSwgYltpXSk7CgogICAgd2hpbGUoMSkgewogICAgICAgIHN0cmluZyBzOwogICAgICAgIGNpbiA+PiBzOwogICAgICAgIGlmKHNbMF09PSdEJykgYnJlYWs7CiAgICAgICAgaWYoc1swXT09J1EnKSB7CiAgICAgICAgICAgIGxsIHUsIHY7CiAgICAgICAgICAgIGNpbiA+PiB1ID4+IHY7CiAgICAgICAgICAgIHUtLSwgdi0tOwogICAgICAgICAgICBjb3V0IDw8IGxjdC5xdWVyeSh1LCB2KSA8PCAiXG4iOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGxsIHUsIHY7CiAgICAgICAgICAgIGNpbiA+PiB1ID4+IHY7CiAgICAgICAgICAgIHUtLTsKICAgICAgICAgICAgbGN0LnJhbmdlKG4rdSwgbit1LCB2KTsKICAgICAgICB9CiAgICB9CiAgICBjb3V0IDw8IGZsdXNoOwp9CgppbnQgbWFpbih2b2lkKSB7CiAgICBsbCB0OwogICAgY2luID4+IHQ7CiAgICB3aGlsZSh0LS0pIHNvbHZlKCk7CgogICAgcmV0dXJuIDA7Cn0=