#include <bits/stdc++.h>
using namespace std;
#define int long long
#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))
#define Int __int128
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;
template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <class T>
void remove_duplicate(vector<T> &ve) {
sort (ve.begin(), ve.end());
ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
return rng() % r;
}
const int N = 2e5 + 5, LG = 19;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
int n, m, len = 0;
int heavy[N], head[N], par[N], dep[N], pos[N];
vector<int> adj[N];
struct Node {
int le, ri;
int lazy1, lazy2;
ll sum;
Node(int _le = 0, int _ri = 0, int _lazy1 = 0, int _lazy2 = 0, ll _sum = 0) {
le = _le, ri = _ri, lazy1 = _lazy1, lazy2 = _lazy2, sum = _sum;
}
} nodes[N * LG];
int numNode, root = 0;
vector<int> version;
struct PersistentIT {
ll f(int n) {
return 1ll * n * (n + 1) / 2;
}
ll f(int l, int r) {
return f(r) - f(l - 1);
}
void refine(int id) {
int le = nodes[id].le, ri = nodes[id].ri;
nodes[id].sum = nodes[le].sum + nodes[ri].sum;
nodes[id].lazy1 = nodes[id].lazy2 = 0;
}
void push(int id, int l, int r) {
int mid = l + r >> 1, le = nodes[id].le, ri = nodes[id].ri;
nodes[le].sum += 1ll * (mid - l + 1) * nodes[id].lazy1;
nodes[le].sum += 1ll * f(l, mid) * nodes[id].lazy2;
nodes[le].lazy1 += nodes[id].lazy1, nodes[le].lazy2 += nodes[id].lazy2;
nodes[ri].sum += 1ll * (r - mid) * nodes[id].lazy1;
nodes[ri].sum += 1ll * f(mid + 1, r) * nodes[id].lazy2;
nodes[ri].lazy1 += nodes[id].lazy1, nodes[ri].lazy2 += nodes[id].lazy2;
nodes[id].lazy1 = nodes[id].lazy2 = 0;
}
int update(int u, int v, int A, int B, int l, int r, int oldId) {
if (l > v || r < u) return oldId;
int id = ++numNode;
if (l == r) {
nodes[id] = nodes[oldId];
nodes[id].sum += 1ll * (0ll + A - 1ll * u * B) * (r - l + 1);
nodes[id].sum += 1ll * f(l, r) * B;
nodes[id].lazy1 += 0ll + A - 1ll * u * B, nodes[id].lazy2 += B;
return id;
}
push(id, l, r); int mid = l + r >> 1;
nodes[id].le = update(u, v, A, B, l, mid, nodes[oldId].le);
nodes[id].ri = update(u, v, A, B, mid + 1, r, nodes[oldId].ri);
refine(id); return id;
}
ll get(int u, int v, int l, int r, int id) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) return nodes[id].sum;
push(id, l, r); int mid = l + r >> 1;
return get(u, v, l, mid, nodes[id].le) + get(u, v, mid + 1, r, nodes[id].ri);
}
} mytree;
int dfs(int u, int fa) {
int ma = -1, sz = 1; heavy[u] = -1;
for (auto v : adj[u]) {
if (v == fa) continue;
par[v] = u, dep[v] = dep[u] + 1;
int tmp = dfs(v, u); sz += tmp;
if (maximize(ma, tmp)) heavy[u] = v;
}
return sz;
}
void hld(int u, int uhead) {
head[u] = uhead, pos[u] = ++len;
if (heavy[u] != -1) hld(heavy[u], uhead);
for (auto v : adj[u])
if (v != heavy[u] && v != par[u]) hld(v, v);
}
int lca(int u, int v) {
for (; head[u] != head[v]; v = par[head[v]]) {
if (dep[head[u]] > dep[head[v]]) swap(u, v);
}
if (dep[u] > dep[v]) swap(u, v);
return u;
}
void update(int u, int v, int A, int B, int start) {
int cur = start - (start > 0);
for (; head[u] != head[v]; v = par[head[v]]) {
if (dep[head[u]] > dep[head[v]]) swap(u, v);
if (start != 0) {
root = mytree.update(pos[head[v]], pos[v], A + cur * B, B, 1, len, root);
}
else {
root = mytree.update(pos[head[v]], pos[v], A + cur * B + (pos[v] - pos[head[v]]) * B, -B, 1, len, root);
}
cur += pos[v] - pos[head[v]] + 1;
}
if (dep[u] > dep[v]) swap(u, v);
if (start != 0) {
root = mytree.update(pos[u], pos[v], A + cur * B, B, 1, len, root);
}
else {
root = mytree.update(pos[u], pos[v], A + cur * B + (pos[v] - pos[u]) * B, -B, 1, len, root);
}
}
void update(int u, int v, int A, int B) {
int p = lca(u, v);
update(u, p, A, B, 0);
update(v, p, A, B, dep[u] - dep[p] + 1);
update(p, p, -A, 0, dep[u] - dep[p] + 1);
version.emplace_back(root);
}
ll query(int u, int v) {
ll ans = 0;
for (; head[u] != head[v]; v = par[head[v]]) {
if (dep[head[u]] > dep[head[v]]) swap(u, v);
ans += mytree.get(pos[head[v]], pos[v], 1, len, root);
}
if (dep[u] > dep[v]) swap(u, v);
ans += mytree.get(pos[u], pos[v], 1, len, root);
return ans;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
adj[u].emplace_back(v), adj[v].emplace_back(u);
}
dfs(1, -1), hld(1, 1);
version.emplace_back(root = numNode);
ll lastans = 0;
for (int i = 1; i <= m; ++i) {
char type; cin >> type;
if (type == 'l') {
int q; cin >> q;
q = (0ll + q + lastans) % version.size();
root = version[q];
}
else {
int u, v; cin >> u >> v;
u = (0ll + u + lastans) % n + 1, v = (0ll + v + lastans) % n + 1;
if (type == 'c') {
int A, B; cin >> A >> B;
update(u, v, A, B);
// cout << "Sum = " << mytree.get(1, n, 1, n, root) << '\n';
// for (int x = 1; x <= n; ++x)
// cout << mytree.get(x, x, 1, n, root) << ' ';
// cout << '\n';
}
else cout << (lastans = query(u, v)) << '\n';
}
}
cerr << '\n'; return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGludCBsb25nIGxvbmcKCiNkZWZpbmUgcG9wY291bnQobikgKF9fYnVpbHRpbl9wb3Bjb3VudGxsKChuKSkpCiNkZWZpbmUgY2x6KG4pIChfX2J1aWx0aW5fY2x6bGwoKG4pKSkKI2RlZmluZSBjdHoobikgKF9fYnVpbHRpbl9jdHpsbCgobikpKQojZGVmaW5lIGxnKG4pICg2MyAtIF9fYnVpbHRpbl9jbHpsbCgobikpKQojZGVmaW5lIEJJVChuLCBpKSAoKChuKSA+PiAoaSkpICYgMWxsKQojZGVmaW5lIE1BU0soaSkgKDFsbCA8PCAoaSkpCiNkZWZpbmUgRkxJUChuLCBpKSAoKG4pIF4gKDFsbCA8PCAoaSkpKQojZGVmaW5lIE9OKG4sIGkpICgobikgfCBNQVNLKGkpKQojZGVmaW5lIE9GRihuLCBpKSAoKG4pICYgfk1BU0soaSkpCgojZGVmaW5lIEludCBfX2ludDEyOAojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxvbmcgbG9uZywgbG9uZyBsb25nPiBwbGw7CnR5cGVkZWYgcGFpcjxsb25nIGxvbmcsIGludD4gcGxpOwp0eXBlZGVmIHBhaXI8aW50LCBsb25nIGxvbmc+IHBpbDsKdHlwZWRlZiB2ZWN0b3I8cGFpcjxpbnQsIGludD4+IHZpaTsKdHlwZWRlZiB2ZWN0b3I8cGFpcjxsb25nIGxvbmcsIGxvbmcgbG9uZz4+IHZsbDsKdHlwZWRlZiB2ZWN0b3I8cGFpcjxsb25nIGxvbmcsIGludD4+IHZsaTsKdHlwZWRlZiB2ZWN0b3I8cGFpcjxpbnQsIGxvbmcgbG9uZz4+IHZpbDsKCnRlbXBsYXRlIDxjbGFzcyBUMSwgY2xhc3MgVDI+CmJvb2wgbWF4aW1pemUoVDEgJngsIFQyIHkpIHsKICAgIGlmICh4IDwgeSkgewogICAgICAgIHggPSB5OwogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgcmV0dXJuIGZhbHNlOwp9CnRlbXBsYXRlIDxjbGFzcyBUMSwgY2xhc3MgVDI+CmJvb2wgbWluaW1pemUoVDEgJngsIFQyIHkpIHsKICAgIGlmICh4ID4geSkgewogICAgICAgIHggPSB5OwogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgcmV0dXJuIGZhbHNlOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4Kdm9pZCByZW1vdmVfZHVwbGljYXRlKHZlY3RvcjxUPiAmdmUpIHsKICAgIHNvcnQgKHZlLmJlZ2luKCksIHZlLmVuZCgpKTsKICAgIHZlLnJlc2l6ZSh1bmlxdWUodmUuYmVnaW4oKSwgdmUuZW5kKCkpIC0gdmUuYmVnaW4oKSk7Cn0KCm10MTk5Mzcgcm5nKGNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CnRlbXBsYXRlIDxjbGFzcyBUPiBUIHJhbmRvbShUIGwsIFQgcikgewogICAgcmV0dXJuIHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxUPihsLCByKShybmcpOwp9CnRlbXBsYXRlIDxjbGFzcyBUPiBUIHJhbmRvbShUIHIpIHsKICAgIHJldHVybiBybmcoKSAlIHI7Cn0KCmNvbnN0IGludCBOID0gMmU1ICsgNSwgTEcgPSAxOTsKY29uc3QgaW50IE1PRCA9IDFlOSArIDc7CmNvbnN0IGludCBpbmYgPSAxZTk7CmNvbnN0IGxsIElORiA9IDFlMTg7CgppbnQgbiwgbSwgbGVuID0gMDsKaW50IGhlYXZ5W05dLCBoZWFkW05dLCBwYXJbTl0sIGRlcFtOXSwgcG9zW05dOwp2ZWN0b3I8aW50PiBhZGpbTl07CgpzdHJ1Y3QgTm9kZSB7CiAgICBpbnQgbGUsIHJpOwogICAgaW50IGxhenkxLCBsYXp5MjsKICAgIGxsIHN1bTsKCiAgICBOb2RlKGludCBfbGUgPSAwLCBpbnQgX3JpID0gMCwgaW50IF9sYXp5MSA9IDAsIGludCBfbGF6eTIgPSAwLCBsbCBfc3VtID0gMCkgewogICAgICAgIGxlID0gX2xlLCByaSA9IF9yaSwgbGF6eTEgPSBfbGF6eTEsIGxhenkyID0gX2xhenkyLCBzdW0gPSBfc3VtOwogICAgfQp9IG5vZGVzW04gKiBMR107CmludCBudW1Ob2RlLCByb290ID0gMDsKdmVjdG9yPGludD4gdmVyc2lvbjsKCnN0cnVjdCBQZXJzaXN0ZW50SVQgewogICAgbGwgZihpbnQgbikgewogICAgICAgIHJldHVybiAxbGwgKiBuICogKG4gKyAxKSAvIDI7CiAgICB9CgogICAgbGwgZihpbnQgbCwgaW50IHIpIHsKICAgICAgICByZXR1cm4gZihyKSAtIGYobCAtIDEpOwogICAgfQoKICAgIHZvaWQgcmVmaW5lKGludCBpZCkgewogICAgICAgIGludCBsZSA9IG5vZGVzW2lkXS5sZSwgcmkgPSBub2Rlc1tpZF0ucmk7CiAgICAgICAgbm9kZXNbaWRdLnN1bSA9IG5vZGVzW2xlXS5zdW0gKyBub2Rlc1tyaV0uc3VtOwogICAgICAgIG5vZGVzW2lkXS5sYXp5MSA9IG5vZGVzW2lkXS5sYXp5MiA9IDA7CiAgICB9CgogICAgdm9pZCBwdXNoKGludCBpZCwgaW50IGwsIGludCByKSB7CiAgICAgICAgaW50IG1pZCA9IGwgKyByID4+IDEsIGxlID0gbm9kZXNbaWRdLmxlLCByaSA9IG5vZGVzW2lkXS5yaTsKCiAgICAgICAgbm9kZXNbbGVdLnN1bSArPSAxbGwgKiAobWlkIC0gbCArIDEpICogbm9kZXNbaWRdLmxhenkxOwogICAgICAgIG5vZGVzW2xlXS5zdW0gKz0gMWxsICogZihsLCBtaWQpICogbm9kZXNbaWRdLmxhenkyOwogICAgICAgIG5vZGVzW2xlXS5sYXp5MSArPSBub2Rlc1tpZF0ubGF6eTEsIG5vZGVzW2xlXS5sYXp5MiArPSBub2Rlc1tpZF0ubGF6eTI7CgogICAgICAgIG5vZGVzW3JpXS5zdW0gKz0gMWxsICogKHIgLSBtaWQpICogbm9kZXNbaWRdLmxhenkxOwogICAgICAgIG5vZGVzW3JpXS5zdW0gKz0gMWxsICogZihtaWQgKyAxLCByKSAqIG5vZGVzW2lkXS5sYXp5MjsKICAgICAgICBub2Rlc1tyaV0ubGF6eTEgKz0gbm9kZXNbaWRdLmxhenkxLCBub2Rlc1tyaV0ubGF6eTIgKz0gbm9kZXNbaWRdLmxhenkyOwoKICAgICAgICBub2Rlc1tpZF0ubGF6eTEgPSBub2Rlc1tpZF0ubGF6eTIgPSAwOwogICAgfQoKICAgIGludCB1cGRhdGUoaW50IHUsIGludCB2LCBpbnQgQSwgaW50IEIsIGludCBsLCBpbnQgciwgaW50IG9sZElkKSB7CiAgICAgICAgaWYgKGwgPiB2IHx8IHIgPCB1KSByZXR1cm4gb2xkSWQ7CgogICAgICAgIGludCBpZCA9ICsrbnVtTm9kZTsKICAgICAgICBpZiAobCA9PSByKSB7CiAgICAgICAgICAgIG5vZGVzW2lkXSA9IG5vZGVzW29sZElkXTsKICAgICAgICAgICAgbm9kZXNbaWRdLnN1bSArPSAxbGwgKiAoMGxsICsgQSAtIDFsbCAqIHUgKiBCKSAqIChyIC0gbCArIDEpOwogICAgICAgICAgICBub2Rlc1tpZF0uc3VtICs9IDFsbCAqIGYobCwgcikgKiBCOwogICAgICAgICAgICBub2Rlc1tpZF0ubGF6eTEgKz0gMGxsICsgQSAtIDFsbCAqIHUgKiBCLCBub2Rlc1tpZF0ubGF6eTIgKz0gQjsKICAgICAgICAgICAgcmV0dXJuIGlkOwogICAgICAgIH0KCiAgICAgICAgcHVzaChpZCwgbCwgcik7IGludCBtaWQgPSBsICsgciA+PiAxOwogICAgICAgIG5vZGVzW2lkXS5sZSA9IHVwZGF0ZSh1LCB2LCBBLCBCLCBsLCBtaWQsIG5vZGVzW29sZElkXS5sZSk7CiAgICAgICAgbm9kZXNbaWRdLnJpID0gdXBkYXRlKHUsIHYsIEEsIEIsIG1pZCArIDEsIHIsIG5vZGVzW29sZElkXS5yaSk7CgogICAgICAgIHJlZmluZShpZCk7IHJldHVybiBpZDsKICAgIH0KCiAgICBsbCBnZXQoaW50IHUsIGludCB2LCBpbnQgbCwgaW50IHIsIGludCBpZCkgewogICAgICAgIGlmIChsID4gdiB8fCByIDwgdSkgcmV0dXJuIDA7CiAgICAgICAgaWYgKHUgPD0gbCAmJiByIDw9IHYpIHJldHVybiBub2Rlc1tpZF0uc3VtOwogICAgICAgIHB1c2goaWQsIGwsIHIpOyBpbnQgbWlkID0gbCArIHIgPj4gMTsKICAgICAgICByZXR1cm4gZ2V0KHUsIHYsIGwsIG1pZCwgbm9kZXNbaWRdLmxlKSArIGdldCh1LCB2LCBtaWQgKyAxLCByLCBub2Rlc1tpZF0ucmkpOwogICAgfQp9IG15dHJlZTsKCmludCBkZnMoaW50IHUsIGludCBmYSkgewogICAgaW50IG1hID0gLTEsIHN6ID0gMTsgaGVhdnlbdV0gPSAtMTsKICAgIGZvciAoYXV0byB2IDogYWRqW3VdKSB7CiAgICAgICAgaWYgKHYgPT0gZmEpIGNvbnRpbnVlOwogICAgICAgIHBhclt2XSA9IHUsIGRlcFt2XSA9IGRlcFt1XSArIDE7CiAgICAgICAgaW50IHRtcCA9IGRmcyh2LCB1KTsgc3ogKz0gdG1wOwogICAgICAgIGlmIChtYXhpbWl6ZShtYSwgdG1wKSkgaGVhdnlbdV0gPSB2OwogICAgfQogICAgcmV0dXJuIHN6Owp9Cgp2b2lkIGhsZChpbnQgdSwgaW50IHVoZWFkKSB7CiAgICBoZWFkW3VdID0gdWhlYWQsIHBvc1t1XSA9ICsrbGVuOwogICAgaWYgKGhlYXZ5W3VdICE9IC0xKSBobGQoaGVhdnlbdV0sIHVoZWFkKTsKICAgIGZvciAoYXV0byB2IDogYWRqW3VdKQogICAgICAgIGlmICh2ICE9IGhlYXZ5W3VdICYmIHYgIT0gcGFyW3VdKSBobGQodiwgdik7Cn0KCmludCBsY2EoaW50IHUsIGludCB2KSB7CiAgICBmb3IgKDsgaGVhZFt1XSAhPSBoZWFkW3ZdOyB2ID0gcGFyW2hlYWRbdl1dKSB7CiAgICAgICAgaWYgKGRlcFtoZWFkW3VdXSA+IGRlcFtoZWFkW3ZdXSkgc3dhcCh1LCB2KTsKICAgIH0KICAgIGlmIChkZXBbdV0gPiBkZXBbdl0pIHN3YXAodSwgdik7CiAgICByZXR1cm4gdTsKfQoKdm9pZCB1cGRhdGUoaW50IHUsIGludCB2LCBpbnQgQSwgaW50IEIsIGludCBzdGFydCkgewogICAgaW50IGN1ciA9IHN0YXJ0IC0gKHN0YXJ0ID4gMCk7CiAgICBmb3IgKDsgaGVhZFt1XSAhPSBoZWFkW3ZdOyB2ID0gcGFyW2hlYWRbdl1dKSB7CiAgICAgICAgaWYgKGRlcFtoZWFkW3VdXSA+IGRlcFtoZWFkW3ZdXSkgc3dhcCh1LCB2KTsKICAgICAgICBpZiAoc3RhcnQgIT0gMCkgewogICAgICAgICAgICByb290ID0gbXl0cmVlLnVwZGF0ZShwb3NbaGVhZFt2XV0sIHBvc1t2XSwgQSArIGN1ciAqIEIsIEIsIDEsIGxlbiwgcm9vdCk7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICByb290ID0gbXl0cmVlLnVwZGF0ZShwb3NbaGVhZFt2XV0sIHBvc1t2XSwgQSArIGN1ciAqIEIgKyAocG9zW3ZdIC0gcG9zW2hlYWRbdl1dKSAqIEIsIC1CLCAxLCBsZW4sIHJvb3QpOwogICAgICAgIH0KICAgICAgICBjdXIgKz0gcG9zW3ZdIC0gcG9zW2hlYWRbdl1dICsgMTsKICAgIH0KICAgIGlmIChkZXBbdV0gPiBkZXBbdl0pIHN3YXAodSwgdik7CiAgICBpZiAoc3RhcnQgIT0gMCkgewogICAgICAgIHJvb3QgPSBteXRyZWUudXBkYXRlKHBvc1t1XSwgcG9zW3ZdLCBBICsgY3VyICogQiwgQiwgMSwgbGVuLCByb290KTsKICAgIH0KICAgIGVsc2UgewogICAgICAgIHJvb3QgPSBteXRyZWUudXBkYXRlKHBvc1t1XSwgcG9zW3ZdLCBBICsgY3VyICogQiArIChwb3Nbdl0gLSBwb3NbdV0pICogQiwgLUIsIDEsIGxlbiwgcm9vdCk7CiAgICB9Cn0KCnZvaWQgdXBkYXRlKGludCB1LCBpbnQgdiwgaW50IEEsIGludCBCKSB7CiAgICBpbnQgcCA9IGxjYSh1LCB2KTsKICAgIHVwZGF0ZSh1LCBwLCBBLCBCLCAwKTsKICAgIHVwZGF0ZSh2LCBwLCBBLCBCLCBkZXBbdV0gLSBkZXBbcF0gKyAxKTsKICAgIHVwZGF0ZShwLCBwLCAtQSwgMCwgZGVwW3VdIC0gZGVwW3BdICsgMSk7CiAgICB2ZXJzaW9uLmVtcGxhY2VfYmFjayhyb290KTsKfQoKbGwgcXVlcnkoaW50IHUsIGludCB2KSB7CiAgICBsbCBhbnMgPSAwOwogICAgZm9yICg7IGhlYWRbdV0gIT0gaGVhZFt2XTsgdiA9IHBhcltoZWFkW3ZdXSkgewogICAgICAgIGlmIChkZXBbaGVhZFt1XV0gPiBkZXBbaGVhZFt2XV0pIHN3YXAodSwgdik7CiAgICAgICAgYW5zICs9IG15dHJlZS5nZXQocG9zW2hlYWRbdl1dLCBwb3Nbdl0sIDEsIGxlbiwgcm9vdCk7CiAgICB9CiAgICBpZiAoZGVwW3VdID4gZGVwW3ZdKSBzd2FwKHUsIHYpOwogICAgYW5zICs9IG15dHJlZS5nZXQocG9zW3VdLCBwb3Nbdl0sIDEsIGxlbiwgcm9vdCk7CiAgICByZXR1cm4gYW5zOwp9CgpzaWduZWQgbWFpbigpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKE5VTEwpOyBjb3V0LnRpZShOVUxMKTsKCiAgICBjaW4gPj4gbiA+PiBtOwoKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgbjsgKytpKSB7CiAgICAgICAgaW50IHUsIHY7IGNpbiA+PiB1ID4+IHY7CiAgICAgICAgYWRqW3VdLmVtcGxhY2VfYmFjayh2KSwgYWRqW3ZdLmVtcGxhY2VfYmFjayh1KTsKICAgIH0KCiAgICBkZnMoMSwgLTEpLCBobGQoMSwgMSk7CgogICAgdmVyc2lvbi5lbXBsYWNlX2JhY2socm9vdCA9IG51bU5vZGUpOwogICAgbGwgbGFzdGFucyA9IDA7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBtOyArK2kpIHsKICAgICAgICBjaGFyIHR5cGU7IGNpbiA+PiB0eXBlOwogICAgICAgIGlmICh0eXBlID09ICdsJykgewogICAgICAgICAgICBpbnQgcTsgY2luID4+IHE7CiAgICAgICAgICAgIHEgPSAoMGxsICsgcSArIGxhc3RhbnMpICUgdmVyc2lvbi5zaXplKCk7CiAgICAgICAgICAgIHJvb3QgPSB2ZXJzaW9uW3FdOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAgICAgaW50IHUsIHY7IGNpbiA+PiB1ID4+IHY7CiAgICAgICAgICAgIHUgPSAoMGxsICsgdSArIGxhc3RhbnMpICUgbiArIDEsIHYgPSAoMGxsICsgdiArIGxhc3RhbnMpICUgbiArIDE7CiAgICAgICAgICAgIGlmICh0eXBlID09ICdjJykgewogICAgICAgICAgICAgICAgaW50IEEsIEI7IGNpbiA+PiBBID4+IEI7CiAgICAgICAgICAgICAgICB1cGRhdGUodSwgdiwgQSwgQik7CiAgICAgICAgICAgICAgICAvLyBjb3V0IDw8ICJTdW0gPSAiIDw8IG15dHJlZS5nZXQoMSwgbiwgMSwgbiwgcm9vdCkgPDwgJ1xuJzsKICAgICAgICAgICAgICAgIC8vIGZvciAoaW50IHggPSAxOyB4IDw9IG47ICsreCkKICAgICAgICAgICAgICAgIC8vICAgICBjb3V0IDw8IG15dHJlZS5nZXQoeCwgeCwgMSwgbiwgcm9vdCkgPDwgJyAnOwogICAgICAgICAgICAgICAgLy8gY291dCA8PCAnXG4nOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgY291dCA8PCAobGFzdGFucyA9IHF1ZXJ5KHUsIHYpKSA8PCAnXG4nOwogICAgICAgIH0KICAgIH0KICAgIGNlcnIgPDwgJ1xuJzsgcmV0dXJuIDA7Cn0=