# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <string>
# include <vector>
using namespace std;
int get_point_mn(int x);
int get_last(int l, int r, int ll, int rr, int x, int y);
long long get_sum(int l, int r, int ll, int rr, int x, int y);
const int N = 250005;
struct NODE {
int mn, cnt_mn;
int qmn;
long long sum, qsum;
bool ob;
NODE () {
mn = cnt_mn = sum = qsum = 0;
ob = false;
}
} t[3 * N];
int ans_query7;
int n, m, sz, group, timer, sz_pred;
string bin_ed;
int vert_cnt[3 * N];
int max_tout[3 * N];
int qob[N];
int tin[N], tout[N], poc[N];
vector<pair<int, int> > v[N];
pair<int, int> ed[N];
int depth[N], first_pos[N], poc2[N + N], pred[19][N + N], max_step[N + N];
int pw[30];
bool comp[N];
void dfs(int x, int y) {
tin[x] = ++timer;
depth[x] = depth[y] + 1;
poc[timer] = x;
poc2[++sz_pred] = x;
first_pos[x] = sz_pred;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i].first;
if (to != y) {
dfs(to, x);
poc2[++sz_pred] = x;
}
}
tout[x] = timer;
return;
}
void build_sparse_table() {
for (int i = 2; i <= sz_pred; ++i)
max_step[i] = max_step[(i >> 1)] + 1;
for (int i = 1; i <= sz_pred; ++i) {
pred[0][i] = poc2[i];
}
for (int i = 0; i <= 25; ++i)
pw[i] = (1 << i);
for (int it = 1; it <= max_step[sz_pred]; ++it) {
for (int j = 1; j <= sz_pred - pw[it] + 1; ++j) {
pred[it][j] = pred[it - 1][j];
if (depth[pred[it][j]] > depth[pred[it - 1][j + pw[it - 1]]]) pred[it][j] = pred[it - 1][j + pw[it - 1]];
}
}
return;
}
int get_lca(int x, int y) {
x = first_pos[x];
y = first_pos[y];
if (x > y) swap(x, y);
int len = max_step[y - x + 1];
int xx = pred[len][x];
int yy = pred[len][y - pw[len] + 1];
if (depth[xx] <= depth[yy]) return xx;
return yy;
}
int get_number_of_edges(int x, int y, int xx, int yy) {
int z = get_lca(x, y);
if (tout[x] >= tout[y]) return yy - xx;
return xx + yy - (get_point_mn(tin[z]) << 1);
}
/////////////////////// Segment Tree for Components
void tree_update_vertex(int x, int y) {
x += sz - 1;
vert_cnt[x] = y;
x >>= 1;
while (x) {
vert_cnt[x] = vert_cnt[x + x] + vert_cnt[x + x + 1];
x >>= 1;
}
return;
}
int get_last_vertex(int l, int r, int ll, int rr, int x) {
if (l > r || ll > r || l > rr || ll > rr || !vert_cnt[x]) return 0;
if (l == r) return l;
int mid = (l + r) >> 1;
int res = get_last_vertex(mid + 1, r, ll, rr, x + x + 1);
if (res) return res;
return get_last_vertex(l, mid, ll, rr, x + x);
}
int get_first_vertex(int l, int r, int ll, int rr, int x) {
if (l > r || ll > r || l > rr || ll > rr || !vert_cnt[x]) return 0;
if (l == r) return l;
int mid = (l + r) >> 1;
int res = get_first_vertex(l, mid, ll, rr, x + x);
if (res) return res;
return get_first_vertex(mid + 1, r, ll, rr, x + x + 1);
}
int FIR = 1e9, SEC = -1e9;
void update_component(int x) {
comp[x] ^= 1;
tree_update_vertex(tin[x], comp[x]);
int xx = get_last_vertex(1, sz, 1, tin[x] - 1, 1);
int xx1, xx2, xx3;
xx1 = xx2 = xx3 = -1;
if (xx) {
xx1 = get_point_mn(tin[poc[xx]]), xx3 = get_point_mn(tin[x]);
if (comp[x]) ans_query7 += get_number_of_edges(poc[xx], x, xx1, xx3);
else ans_query7 -= get_number_of_edges(poc[xx], x, xx1, xx3);
}
int yy = get_first_vertex(1, sz, tin[x] + 1, n, 1);
if (yy) {
xx2 = get_point_mn(tin[poc[yy]]);
if (xx3 == -1) xx3 = get_point_mn(tin[x]);
if (comp[x]) ans_query7 += get_number_of_edges(x, poc[yy], xx3, xx2);
else ans_query7 -= get_number_of_edges(x, poc[yy], xx3, xx2);
}
if (comp[x] == 1) {
if (tin[x] < FIR) FIR = tin[x];
if (tin[x] > SEC) SEC = tin[x];
} else {
if (FIR == SEC) FIR = 1e9, SEC = -1e9;
else if (FIR == tin[x]) FIR = yy;
else if (SEC == tin[x]) SEC = xx;
}
if (xx && yy) {
xx = poc[xx];
yy = poc[yy];
if (xx1 == -1) xx1 = get_point_mn(tin[xx]);
if (xx2 == -1) xx2 = get_point_mn(tin[yy]);
if (comp[x]) ans_query7 -= get_number_of_edges(xx, yy, xx1, xx2);
else ans_query7 += get_number_of_edges(xx, yy, xx1, xx2);
}
return;
}
bool is_there_somebody(int x, bool y) {
if (!y) {
x = get_last(1, sz, 1, tin[x], 1, tout[x]);
if (!x) x = 1;
x = poc[x];
}
return (bool)(get_sum(1, sz, tin[x], tout[x], 1, get_point_mn(tin[x])) > 0);
}
/////////////////////// Closest blocked edge
void update_edge(int x, int y) {
x += sz - 1;
max_tout[x] = y;
x >>= 1;
while (x) {
max_tout[x] = max_tout[x + x];
if (max_tout[x + x + 1] > max_tout[x]) max_tout[x] = max_tout[x + x + 1];
x >>= 1;
}
return;
}
int get_last(int l, int r, int ll, int rr, int x, int y) {
if (l > r || ll > r || l > rr || ll > rr || max_tout[x] < y) return 0;
if (l == r) return l;
int mid = (l + r) >> 1;
int res = get_last(mid + 1, r, ll, rr, x + x + 1, y);
if (res) return res;
return get_last(l, mid, ll, rr, x + x, y);
}
////////////////////// Segment Tree for Queries
////////// Update NODE
void push(int x) {
int xx = t[x].mn;
if (t[x].qmn) {
int z = t[x].qmn;
t[x].qmn = 0;
t[x + x].mn += z;
t[x + x + 1].mn += z;
t[x + x].qmn += z;
t[x + x + 1].qmn += z;
}
if (t[x].ob) {
t[x].ob = false;
if (t[x + x].mn == xx) {
t[x + x].sum = t[x + x].qsum = 0;
t[x + x].ob = true;
}
if (t[x + x + 1].mn == xx) {
t[x + x + 1].sum = t[x + x + 1].qsum = 0;
t[x + x + 1].ob = true;
}
}
if (t[x].qsum) {
long long z = t[x].qsum;
t[x].qsum = 0;
if (t[x + x].mn == xx) {
t[x + x].sum += (t[x + x].cnt_mn * z);
t[x + x].qsum += z;
}
if (t[x + x + 1].mn == xx) {
t[x + x + 1].sum += (t[x + x + 1].cnt_mn * z);
t[x + x + 1].qsum += z;
}
}
return;
}
void update_NODE(int x) {
t[x].mn = t[x + x].mn;
t[x].cnt_mn = t[x + x].cnt_mn;
t[x].sum = t[x + x].sum;
if (t[x + x + 1].mn < t[x].mn) {
t[x].mn = t[x + x + 1].mn;
t[x].cnt_mn = t[x + x + 1].cnt_mn;
t[x].sum = t[x + x + 1].sum;
} else if (t[x + x + 1].mn == t[x].mn) {
t[x].cnt_mn += t[x + x + 1].cnt_mn;
t[x].sum += t[x + x + 1].sum;
}
return;
}
/////////////////////
void update_cnt(int l, int r, int ll, int rr, int x, int y) {
if (l > r || ll > r || l > rr || ll > rr) return;
if (l >= ll && r <= rr) {
t[x].mn += y;
t[x].qmn += y;
return;
}
int mid = (l + r) >> 1;
push(x);
update_cnt(l, mid, ll, rr, x + x, y);
update_cnt(mid + 1, r, ll, rr, x + x + 1, y);
update_NODE(x);
return;
}
int global_pos1;
void update_sum_point(int l, int r, int ll, int x, long long y) {
if (l == r) {
global_pos1 = t[x].mn;
t[x].sum += y;
return;
}
int mid = (l + r) >> 1;
push(x);
if (ll <= mid) update_sum_point(l, mid, ll, x + x, y);
else update_sum_point(mid + 1, r, ll, x + x + 1, y);
if (t[x].mn == global_pos1) t[x].sum += y;
return;
}
void update_sum(int l, int r, int ll, int rr, int x, int y, int z) {
if (l > r || ll > r || l > rr || ll > rr || t[x].mn > z) return;
if (l >= ll && r <= rr) {
if (t[x].mn != z) return;
t[x].sum += (t[x].cnt_mn * 1ll * y);
t[x].qsum += y;
return;
}
int mid = (l + r) >> 1;
push(x);
update_sum(l, mid, ll, rr, x + x, y, z);
update_sum(mid + 1, r, ll, rr, x + x + 1, y, z);
update_NODE(x);
return;
}
void clr_node(int l, int r, int ll, int rr, int x, int y) {
if (l > r || ll > r || l > rr || ll > rr || t[x].mn > y) return;
if (l >= ll && r <= rr) {
if (t[x].mn != y) return;
t[x].ob = true;
t[x].sum = t[x].qsum = 0;
return;
}
int mid = (l + r) >> 1;
push(x);
clr_node(l, mid, ll, rr, x + x, y);
clr_node(mid + 1, r, ll, rr, x + x + 1, y);
update_NODE(x);
return;
}
///////////////////////////// Answer Queries
long long get_point(int l, int r, int ll, int x) {
int mid;
while (l != r) {
mid = (l + r) >> 1;
push(x);
if (ll <= mid) x <<= 1, r = mid;
else x = x + x + 1, l = mid + 1;
}
return t[x].sum;
}
int get_point_mn(int x) {
x += sz - 1;
int res = t[x].mn;
x >>= 1;
while (x) {
res += t[x].qmn;
x >>= 1;
}
return res;
}
long long get_sum(int l, int r, int ll, int rr, int x, int y) {
if (l > r || ll > r || l > rr || ll > rr || t[x].mn > y) return 0;
if (l >= ll && r <= rr) {
if (t[x].mn != y) return 0;
return t[x].sum;
}
int mid = (l + r) >> 1;
push(x);
return get_sum(l, mid, ll, rr, x + x, y) + get_sum(mid + 1, r, ll, rr, x + x + 1, y);
}
long long query_4(int x) {
return get_point(1, sz, tin[x], 1);
}
long long query_5(int x) {
x = get_last(1, sz, 1, tin[x], 1, tout[x]);
if (!x) x = 1;
x = poc[x];
int y = get_point_mn(tin[x]);
return get_sum(1, sz, tin[x], tout[x], 1, y);
}
int query_7() {
int x, y;
x = FIR;
if (x != 1e9) {
y = SEC;
x = poc[x];
y = poc[y];
return ((ans_query7 + get_number_of_edges(x, y, get_point_mn(tin[x]), get_point_mn(tin[y]))) >> 1);
}
return 0;
}
///////////////////////////////// Modify Queries
void query_1(int r) {
int x = ed[r].second;
int xx = ed[r].first;
xx = get_last(1, sz, 1, tin[xx], 1, tout[xx]);
if (!xx) xx = 1;
xx = poc[xx];
if (get_first_vertex(1, sz, tin[x], tout[x], 1)) {
if (FIR < tin[x]) {
if (bin_ed[r] == '0') ++ans_query7;
else --ans_query7;
}
if (SEC > tout[x]) {
if (bin_ed[r] == '0') ++ans_query7;
else --ans_query7;
}
}
if (bin_ed[r] == '1') {
update_edge(tin[x], 0);
update_cnt(1, sz, tin[x], tout[x], 1, -1);
bin_ed[r] = '0';
} else {
update_edge(tin[x], tout[x]);
update_cnt(1, sz, tin[x], tout[x], 1, 1);
bin_ed[r] = '1';
}
if (bin_ed[r] == '0') {
if (comp[x]) {
update_component(x);
if (!comp[xx]) update_component(xx);
}
} else if (comp[xx]) {
if (is_there_somebody(x, 1)) {
update_component(x);
if (!is_there_somebody(xx, 1)) update_component(xx);
}
}
return;
}
void query_2(int x, int z) {
x = get_last(1, sz, 1, tin[x], 1, tout[x]);
if (!x) x = 1;
x = poc[x];
if (!comp[x]) update_component(x);
int y = get_point_mn(tin[x]);
update_sum(1, sz, tin[x], tout[x], 1, z, y);
return;
}
void query_6(int x) {
x = get_last(1, sz, 1, tin[x], 1, tout[x]);
if (!x) x = 1;
x = poc[x];
if (comp[x]) update_component(x);
int y = get_point_mn(tin[x]);
clr_node(1, sz, tin[x], tout[x], 1, y);
return;
}
void query_3(int x) {
int y = x;
x = get_last(1, sz, 1, tin[x], 1, tout[x]);
if (!x) x = 1;
x = poc[x];
long long xx = query_5(x);
clr_node(1, sz, tin[x], tout[x], 1, get_point_mn(tin[x]));
update_sum_point(1, sz, tin[y], 1, xx);
return;
}
bool dfs_init(int x, int y, bool edge) {
bool is_there = false;
if (t[sz + tin[x] - 1].sum) is_there = true;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i].first;
if (to == y) continue;
if (bin_ed[v[x][i].second] == '1') {
dfs_init(to, x, 1);
} else {
if (dfs_init(to, x, 0)) is_there = true;
}
}
if (edge && is_there) {
comp[x] = 1;
vert_cnt[sz + tin[x] - 1] = 1;
}
return is_there;
}
bool dfs_init2(int x, int y) {
bool is_there = false;
if (t[sz + tin[x] - 1].sum) is_there = true;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i].first;
if (to == y) continue;
if (bin_ed[v[x][i].second] == '1') {
if (dfs_init2(to, x)) {
is_there = true;
++ans_query7;
}
} else if (dfs_init2(to, x)) is_there = true;
}
return is_there;
}
void dfs_init3(int x, int y, int _d, int l) {
if (x == l) ans_query7 -= _d;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i].first;
if (to != y) dfs_init3(to, x, _d + (bin_ed[v[x][i].second] - '0'), l);
}
return;
}
///////////////////////////////
void init(int N, vector<int> v, vector<int> u, vector<int> b, vector<int> a, int GROUP) {
n = N;
int x, y;
for (int i = 1; i < n; ++i) {
x = v[i - 1];
y = u[i - 1];
ed[i] = {x, y};
::v[x].push_back({y, i});
::v[y].push_back({x, i});
}
bin_ed = "#";
for (int i = 0; i < b.size(); ++i)
bin_ed += char(b[i] + '0');
dfs(1, 0);
build_sparse_table();
for (int i = 1; i < n; ++i) {
x = ed[i].first;
y = ed[i].second;
if (tin[y] < tin[x]) swap(ed[i].first, ed[i].second);
}
sz = 1;
while (sz < n) sz += sz;
for (int i = 1; i <= n; ++i)
t[sz + i - 1].cnt_mn = 1;
for (int i = sz - 1; i > 0; --i)
t[i].cnt_mn = t[i + i].cnt_mn + t[i + i + 1].cnt_mn;
int rr;
for (int i = 1; i < n; ++i)
if (bin_ed[i] == '1') {
rr = ed[i].second;
max_tout[tin[rr] + sz - 1] = tout[rr];
qob[tin[rr]]++;
qob[tout[rr] + 1]--;
}
for (int i = 1; i <= n; ++i) {
qob[i] += qob[i - 1];
t[sz + tin[i] - 1].sum += a[i - 1];
t[sz + i - 1].mn = qob[i];
}
for (int i = sz - 1; i > 0; --i) {
max_tout[i] = max_tout[i + i];
if (max_tout[i + i + 1] > max_tout[i]) max_tout[i] = max_tout[i + i + 1];
update_NODE(i);
}
dfs_init(1, 0, true);
for (int i = sz - 1; i > 0; --i)
vert_cnt[i] = vert_cnt[i + i] + vert_cnt[i + i + 1];
/// ������¿������¾����¯�¿�½����¯�¿�½������¸����¯�¿�½������°����¯�¿�½����¯�¿�½ ������¾����¯�¿�½������²������µ����¯�¿�½
int pos = 0;
for (int i = 1; i <= n; ++i)
if (comp[i]) {
pos = i;
break;
}
if (pos) {
dfs_init2(pos, 0);
ans_query7 *= 2;
int fir = -1;
int last = -1;
for (int i = 1; i <= n; ++i)
if (comp[poc[i]]) {
if (fir == -1) fir = i;
last = i;
}
FIR = fir;
SEC = last;
fir = poc[fir];
last = poc[last];
dfs_init3(fir, 0, 0, last);
}
return;
}
int main(int argc, const char * argv[]) {
// ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int x, y;
cin >> group;
cin >> n >> m;
vector<int> vv, uu;
for (int i = 1; i < n; ++i) {
cin >> x >> y;
vv.push_back(x);
uu.push_back(y);
}
cin >> bin_ed;
vector<int> b, a;
for (int i = 0; i < (int)bin_ed.size(); ++i)
b.push_back(bin_ed[i] - '0');
for (int i = 1; i <= n; ++i) {
cin >> x;
a.push_back(x);
}
init(n, vv, uu, b, a, group);
int tp;
for (int it = 1; it <= m; ++it) {
cin >> tp;
if (tp == 1) {
cin >> x;
query_1(x);
} else if (tp == 2) {
cin >> x >> y;
query_2(x, y);
} else if (tp == 3) {
cin >> x;
query_3(x);
} else if (tp == 4) {
cin >> x;
cout << query_4(x) << '\n';
} else if (tp == 5) {
cin >> x;
cout << query_5(x) << '\n';
} else if (tp == 6) {
cin >> x;
query_6(x);
} else {
cout << query_7() << '\n';
}
}
return 0;
}
////
IyBpbmNsdWRlIDxpb3N0cmVhbT4KIyBpbmNsdWRlIDxjbWF0aD4KIyBpbmNsdWRlIDxhbGdvcml0aG0+CiMgaW5jbHVkZSA8c3RkaW8uaD4KIyBpbmNsdWRlIDxzdHJpbmc+CiMgaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgZ2V0X3BvaW50X21uKGludCB4KTsKaW50IGdldF9sYXN0KGludCBsLCBpbnQgciwgaW50IGxsLCBpbnQgcnIsIGludCB4LCBpbnQgeSk7CmxvbmcgbG9uZyBnZXRfc3VtKGludCBsLCBpbnQgciwgaW50IGxsLCBpbnQgcnIsIGludCB4LCBpbnQgeSk7CiAKY29uc3QgaW50IE4gPSAyNTAwMDU7CiAKIApzdHJ1Y3QgTk9ERSB7CiAgICBpbnQgbW4sIGNudF9tbjsKICAgIGludCBxbW47CiAgICBsb25nIGxvbmcgc3VtLCBxc3VtOwogICAgYm9vbCBvYjsKICAgIE5PREUgKCkgewogICAgICAgIG1uID0gY250X21uID0gc3VtID0gcXN1bSA9IDA7CiAgICAgICAgb2IgPSBmYWxzZTsKICAgIH0KICAgIAp9IHRbMyAqIE5dOwogCmludCBhbnNfcXVlcnk3OwppbnQgbiwgbSwgc3osIGdyb3VwLCB0aW1lciwgc3pfcHJlZDsKc3RyaW5nIGJpbl9lZDsKaW50IHZlcnRfY250WzMgKiBOXTsKaW50IG1heF90b3V0WzMgKiBOXTsKaW50IHFvYltOXTsKaW50IHRpbltOXSwgdG91dFtOXSwgcG9jW05dOwp2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiB2W05dOwpwYWlyPGludCwgaW50PiBlZFtOXTsKaW50IGRlcHRoW05dLCBmaXJzdF9wb3NbTl0sIHBvYzJbTiArIE5dLCBwcmVkWzE5XVtOICsgTl0sIG1heF9zdGVwW04gKyBOXTsKaW50IHB3WzMwXTsKYm9vbCBjb21wW05dOwogCnZvaWQgZGZzKGludCB4LCBpbnQgeSkgewogICAgdGluW3hdID0gKyt0aW1lcjsKICAgIGRlcHRoW3hdID0gZGVwdGhbeV0gKyAxOwogICAgcG9jW3RpbWVyXSA9IHg7CiAgICBwb2MyWysrc3pfcHJlZF0gPSB4OwogICAgZmlyc3RfcG9zW3hdID0gc3pfcHJlZDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgdlt4XS5zaXplKCk7ICsraSkgewogICAgICAgIGludCB0byA9IHZbeF1baV0uZmlyc3Q7CiAgICAgICAgaWYgKHRvICE9IHkpIHsKICAgICAgICAgICAgZGZzKHRvLCB4KTsKICAgICAgICAgICAgcG9jMlsrK3N6X3ByZWRdID0geDsKICAgICAgICB9CiAgICB9CiAgICB0b3V0W3hdID0gdGltZXI7CiAgICByZXR1cm47Cn0KIAp2b2lkIGJ1aWxkX3NwYXJzZV90YWJsZSgpIHsKICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IHN6X3ByZWQ7ICsraSkKICAgICAgICBtYXhfc3RlcFtpXSA9IG1heF9zdGVwWyhpID4+IDEpXSArIDE7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBzel9wcmVkOyArK2kpIHsKICAgICAgICBwcmVkWzBdW2ldID0gcG9jMltpXTsKICAgIH0KICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IDI1OyArK2kpCiAgICAgICAgcHdbaV0gPSAoMSA8PCBpKTsKICAgIGZvciAoaW50IGl0ID0gMTsgaXQgPD0gbWF4X3N0ZXBbc3pfcHJlZF07ICsraXQpIHsKICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBzel9wcmVkIC0gcHdbaXRdICsgMTsgKytqKSB7CiAgICAgICAgICAgIHByZWRbaXRdW2pdID0gcHJlZFtpdCAtIDFdW2pdOwogICAgICAgICAgICBpZiAoZGVwdGhbcHJlZFtpdF1bal1dID4gZGVwdGhbcHJlZFtpdCAtIDFdW2ogKyBwd1tpdCAtIDFdXV0pIHByZWRbaXRdW2pdID0gcHJlZFtpdCAtIDFdW2ogKyBwd1tpdCAtIDFdXTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm47Cn0KIAppbnQgZ2V0X2xjYShpbnQgeCwgaW50IHkpIHsKICAgIHggPSBmaXJzdF9wb3NbeF07CiAgICB5ID0gZmlyc3RfcG9zW3ldOwogICAgaWYgKHggPiB5KSBzd2FwKHgsIHkpOwogICAgaW50IGxlbiA9IG1heF9zdGVwW3kgLSB4ICsgMV07CiAgICBpbnQgeHggPSBwcmVkW2xlbl1beF07CiAgICBpbnQgeXkgPSBwcmVkW2xlbl1beSAtIHB3W2xlbl0gKyAxXTsKICAgIGlmIChkZXB0aFt4eF0gPD0gZGVwdGhbeXldKSByZXR1cm4geHg7CiAgICByZXR1cm4geXk7Cn0KIAppbnQgZ2V0X251bWJlcl9vZl9lZGdlcyhpbnQgeCwgaW50IHksIGludCB4eCwgaW50IHl5KSB7CiAgICBpbnQgeiA9IGdldF9sY2EoeCwgeSk7CiAgICBpZiAodG91dFt4XSA+PSB0b3V0W3ldKSByZXR1cm4geXkgLSB4eDsKICAgIHJldHVybiB4eCArIHl5IC0gKGdldF9wb2ludF9tbih0aW5bel0pIDw8IDEpOwp9CiAKLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8gICAgICAgICAgICAgICAgIFNlZ21lbnQgVHJlZSBmb3IgQ29tcG9uZW50cwogCnZvaWQgdHJlZV91cGRhdGVfdmVydGV4KGludCB4LCBpbnQgeSkgewogICAgeCArPSBzeiAtIDE7CiAgICB2ZXJ0X2NudFt4XSA9IHk7CiAgICB4ID4+PSAxOwogICAgd2hpbGUgKHgpIHsKICAgICAgICB2ZXJ0X2NudFt4XSA9IHZlcnRfY250W3ggKyB4XSArIHZlcnRfY250W3ggKyB4ICsgMV07CiAgICAgICAgeCA+Pj0gMTsKICAgIH0KICAgIHJldHVybjsKfQogCmludCBnZXRfbGFzdF92ZXJ0ZXgoaW50IGwsIGludCByLCBpbnQgbGwsIGludCByciwgaW50IHgpIHsKICAgIGlmIChsID4gciB8fCBsbCA+IHIgfHwgbCA+IHJyIHx8IGxsID4gcnIgfHwgIXZlcnRfY250W3hdKSByZXR1cm4gMDsKICAgIGlmIChsID09IHIpIHJldHVybiBsOwogICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgIGludCByZXMgPSBnZXRfbGFzdF92ZXJ0ZXgobWlkICsgMSwgciwgbGwsIHJyLCB4ICsgeCArIDEpOwogICAgaWYgKHJlcykgcmV0dXJuIHJlczsKICAgIHJldHVybiBnZXRfbGFzdF92ZXJ0ZXgobCwgbWlkLCBsbCwgcnIsIHggKyB4KTsKfQogCmludCBnZXRfZmlyc3RfdmVydGV4KGludCBsLCBpbnQgciwgaW50IGxsLCBpbnQgcnIsIGludCB4KSB7CiAgICBpZiAobCA+IHIgfHwgbGwgPiByIHx8IGwgPiByciB8fCBsbCA+IHJyIHx8ICF2ZXJ0X2NudFt4XSkgcmV0dXJuIDA7CiAgICBpZiAobCA9PSByKSByZXR1cm4gbDsKICAgIGludCBtaWQgPSAobCArIHIpID4+IDE7CiAgICBpbnQgcmVzID0gZ2V0X2ZpcnN0X3ZlcnRleChsLCBtaWQsIGxsLCByciwgeCArIHgpOwogICAgaWYgKHJlcykgcmV0dXJuIHJlczsKICAgIHJldHVybiBnZXRfZmlyc3RfdmVydGV4KG1pZCArIDEsIHIsIGxsLCByciwgeCArIHggKyAxKTsKfQogCmludCBGSVIgPSAxZTksIFNFQyA9IC0xZTk7CiAKdm9pZCB1cGRhdGVfY29tcG9uZW50KGludCB4KSB7CiAgICBjb21wW3hdIF49IDE7CiAgICB0cmVlX3VwZGF0ZV92ZXJ0ZXgodGluW3hdLCBjb21wW3hdKTsKICAgIGludCB4eCA9IGdldF9sYXN0X3ZlcnRleCgxLCBzeiwgMSwgdGluW3hdIC0gMSwgMSk7CiAgICBpbnQgeHgxLCB4eDIsIHh4MzsKICAgIHh4MSA9IHh4MiA9IHh4MyA9IC0xOwogICAgaWYgKHh4KSB7CiAgICAgICAgeHgxID0gZ2V0X3BvaW50X21uKHRpbltwb2NbeHhdXSksIHh4MyA9IGdldF9wb2ludF9tbih0aW5beF0pOwogICAgICAgIGlmIChjb21wW3hdKSBhbnNfcXVlcnk3ICs9IGdldF9udW1iZXJfb2ZfZWRnZXMocG9jW3h4XSwgeCwgeHgxLCB4eDMpOwogICAgICAgIGVsc2UgYW5zX3F1ZXJ5NyAtPSBnZXRfbnVtYmVyX29mX2VkZ2VzKHBvY1t4eF0sIHgsIHh4MSwgeHgzKTsKICAgIH0KICAgIGludCB5eSA9IGdldF9maXJzdF92ZXJ0ZXgoMSwgc3osIHRpblt4XSArIDEsIG4sIDEpOwogICAgaWYgKHl5KSB7CiAgICAgICAgeHgyID0gZ2V0X3BvaW50X21uKHRpbltwb2NbeXldXSk7CiAgICAgICAgaWYgKHh4MyA9PSAtMSkgeHgzID0gZ2V0X3BvaW50X21uKHRpblt4XSk7CiAgICAgICAgaWYgKGNvbXBbeF0pIGFuc19xdWVyeTcgKz0gZ2V0X251bWJlcl9vZl9lZGdlcyh4LCBwb2NbeXldLCB4eDMsIHh4Mik7CiAgICAgICAgZWxzZSBhbnNfcXVlcnk3IC09IGdldF9udW1iZXJfb2ZfZWRnZXMoeCwgcG9jW3l5XSwgeHgzLCB4eDIpOwogICAgfQogICAgaWYgKGNvbXBbeF0gPT0gMSkgewogICAgICAgIGlmICh0aW5beF0gPCBGSVIpIEZJUiA9IHRpblt4XTsKICAgICAgICBpZiAodGluW3hdID4gU0VDKSBTRUMgPSB0aW5beF07CiAgICB9IGVsc2UgewogICAgICAgIGlmIChGSVIgPT0gU0VDKSBGSVIgPSAxZTksIFNFQyA9IC0xZTk7CiAgICAgICAgZWxzZSBpZiAoRklSID09IHRpblt4XSkgRklSID0geXk7CiAgICAgICAgZWxzZSBpZiAoU0VDID09IHRpblt4XSkgU0VDID0geHg7CiAgICB9CiAgICBpZiAoeHggJiYgeXkpIHsKICAgICAgICB4eCA9IHBvY1t4eF07CiAgICAgICAgeXkgPSBwb2NbeXldOwogICAgICAgIGlmICh4eDEgPT0gLTEpIHh4MSA9IGdldF9wb2ludF9tbih0aW5beHhdKTsKICAgICAgICBpZiAoeHgyID09IC0xKSB4eDIgPSBnZXRfcG9pbnRfbW4odGluW3l5XSk7CiAgICAgICAgaWYgKGNvbXBbeF0pIGFuc19xdWVyeTcgLT0gZ2V0X251bWJlcl9vZl9lZGdlcyh4eCwgeXksIHh4MSwgeHgyKTsKICAgICAgICBlbHNlIGFuc19xdWVyeTcgKz0gZ2V0X251bWJlcl9vZl9lZGdlcyh4eCwgeXksIHh4MSwgeHgyKTsKICAgIH0KICAgIHJldHVybjsKfQogCmJvb2wgaXNfdGhlcmVfc29tZWJvZHkoaW50IHgsIGJvb2wgeSkgewogICAgaWYgKCF5KSB7CiAgICAgICAgeCA9IGdldF9sYXN0KDEsIHN6LCAxLCB0aW5beF0sIDEsIHRvdXRbeF0pOwogICAgICAgIGlmICgheCkgeCA9IDE7CiAgICAgICAgeCA9IHBvY1t4XTsKICAgIH0KICAgIHJldHVybiAoYm9vbCkoZ2V0X3N1bSgxLCBzeiwgdGluW3hdLCB0b3V0W3hdLCAxLCBnZXRfcG9pbnRfbW4odGluW3hdKSkgPiAwKTsKfQogCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vICAgICAgICAgICAgICAgICBDbG9zZXN0IGJsb2NrZWQgZWRnZQogCnZvaWQgdXBkYXRlX2VkZ2UoaW50IHgsIGludCB5KSB7CiAgICB4ICs9IHN6IC0gMTsKICAgIG1heF90b3V0W3hdID0geTsKICAgIHggPj49IDE7CiAgICB3aGlsZSAoeCkgewogICAgICAgIG1heF90b3V0W3hdID0gbWF4X3RvdXRbeCArIHhdOwogICAgICAgIGlmIChtYXhfdG91dFt4ICsgeCArIDFdID4gbWF4X3RvdXRbeF0pIG1heF90b3V0W3hdID0gbWF4X3RvdXRbeCArIHggKyAxXTsKICAgICAgICB4ID4+PSAxOwogICAgfQogICAgcmV0dXJuOwp9CiAKaW50IGdldF9sYXN0KGludCBsLCBpbnQgciwgaW50IGxsLCBpbnQgcnIsIGludCB4LCBpbnQgeSkgewogICAgaWYgKGwgPiByIHx8IGxsID4gciB8fCBsID4gcnIgfHwgbGwgPiByciB8fCBtYXhfdG91dFt4XSA8IHkpIHJldHVybiAwOwogICAgaWYgKGwgPT0gcikgcmV0dXJuIGw7CiAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxOwogICAgaW50IHJlcyA9IGdldF9sYXN0KG1pZCArIDEsIHIsIGxsLCByciwgeCArIHggKyAxLCB5KTsKICAgIGlmIChyZXMpIHJldHVybiByZXM7CiAgICByZXR1cm4gZ2V0X2xhc3QobCwgbWlkLCBsbCwgcnIsIHggKyB4LCB5KTsKfQogCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8gICAgICAgICAgICAgICAgICBTZWdtZW50IFRyZWUgZm9yIFF1ZXJpZXMKIAovLy8vLy8vLy8vICAgICAgICAgICAgICAgICAgVXBkYXRlIE5PREUKIAp2b2lkIHB1c2goaW50IHgpIHsKICAgIGludCB4eCA9IHRbeF0ubW47CiAgICBpZiAodFt4XS5xbW4pIHsKICAgICAgICBpbnQgeiA9IHRbeF0ucW1uOwogICAgICAgIHRbeF0ucW1uID0gMDsKICAgICAgICB0W3ggKyB4XS5tbiArPSB6OwogICAgICAgIHRbeCArIHggKyAxXS5tbiArPSB6OwogICAgICAgIHRbeCArIHhdLnFtbiArPSB6OwogICAgICAgIHRbeCArIHggKyAxXS5xbW4gKz0gejsKICAgIH0KICAgIGlmICh0W3hdLm9iKSB7CiAgICAgICAgdFt4XS5vYiA9IGZhbHNlOwogICAgICAgIGlmICh0W3ggKyB4XS5tbiA9PSB4eCkgewogICAgICAgICAgICB0W3ggKyB4XS5zdW0gPSB0W3ggKyB4XS5xc3VtID0gMDsKICAgICAgICAgICAgdFt4ICsgeF0ub2IgPSB0cnVlOwogICAgICAgIH0KICAgICAgICBpZiAodFt4ICsgeCArIDFdLm1uID09IHh4KSB7CiAgICAgICAgICAgIHRbeCArIHggKyAxXS5zdW0gPSB0W3ggKyB4ICsgMV0ucXN1bSA9IDA7CiAgICAgICAgICAgIHRbeCArIHggKyAxXS5vYiA9IHRydWU7CiAgICAgICAgfQogICAgfQogICAgaWYgKHRbeF0ucXN1bSkgewogICAgICAgIGxvbmcgbG9uZyB6ID0gdFt4XS5xc3VtOwogICAgICAgIHRbeF0ucXN1bSA9IDA7CiAgICAgICAgaWYgKHRbeCArIHhdLm1uID09IHh4KSB7CiAgICAgICAgICAgIHRbeCArIHhdLnN1bSArPSAodFt4ICsgeF0uY250X21uICogeik7CiAgICAgICAgICAgIHRbeCArIHhdLnFzdW0gKz0gejsKICAgICAgICB9CiAgICAgICAgaWYgKHRbeCArIHggKyAxXS5tbiA9PSB4eCkgewogICAgICAgICAgICB0W3ggKyB4ICsgMV0uc3VtICs9ICh0W3ggKyB4ICsgMV0uY250X21uICogeik7CiAgICAgICAgICAgIHRbeCArIHggKyAxXS5xc3VtICs9IHo7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuOwp9CiAKdm9pZCB1cGRhdGVfTk9ERShpbnQgeCkgewogICAgdFt4XS5tbiA9IHRbeCArIHhdLm1uOwogICAgdFt4XS5jbnRfbW4gPSB0W3ggKyB4XS5jbnRfbW47CiAgICB0W3hdLnN1bSA9IHRbeCArIHhdLnN1bTsKICAgIGlmICh0W3ggKyB4ICsgMV0ubW4gPCB0W3hdLm1uKSB7CiAgICAgICAgdFt4XS5tbiA9IHRbeCArIHggKyAxXS5tbjsKICAgICAgICB0W3hdLmNudF9tbiA9IHRbeCArIHggKyAxXS5jbnRfbW47CiAgICAgICAgdFt4XS5zdW0gPSB0W3ggKyB4ICsgMV0uc3VtOwogICAgfSBlbHNlIGlmICh0W3ggKyB4ICsgMV0ubW4gPT0gdFt4XS5tbikgewogICAgICAgIHRbeF0uY250X21uICs9IHRbeCArIHggKyAxXS5jbnRfbW47CiAgICAgICAgdFt4XS5zdW0gKz0gdFt4ICsgeCArIDFdLnN1bTsKICAgIH0KICAgIHJldHVybjsKfQogCi8vLy8vLy8vLy8vLy8vLy8vLy8vLwogCnZvaWQgdXBkYXRlX2NudChpbnQgbCwgaW50IHIsIGludCBsbCwgaW50IHJyLCBpbnQgeCwgaW50IHkpIHsKICAgIGlmIChsID4gciB8fCBsbCA+IHIgfHwgbCA+IHJyIHx8IGxsID4gcnIpIHJldHVybjsKICAgIGlmIChsID49IGxsICYmIHIgPD0gcnIpIHsKICAgICAgICB0W3hdLm1uICs9IHk7CiAgICAgICAgdFt4XS5xbW4gKz0geTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxOwogICAgcHVzaCh4KTsKICAgIHVwZGF0ZV9jbnQobCwgbWlkLCBsbCwgcnIsIHggKyB4LCB5KTsKICAgIHVwZGF0ZV9jbnQobWlkICsgMSwgciwgbGwsIHJyLCB4ICsgeCArIDEsIHkpOwogICAgdXBkYXRlX05PREUoeCk7CiAgICByZXR1cm47Cn0KIAppbnQgZ2xvYmFsX3BvczE7CiAKdm9pZCB1cGRhdGVfc3VtX3BvaW50KGludCBsLCBpbnQgciwgaW50IGxsLCBpbnQgeCwgbG9uZyBsb25nIHkpIHsKICAgIGlmIChsID09IHIpIHsKICAgICAgICBnbG9iYWxfcG9zMSA9IHRbeF0ubW47CiAgICAgICAgdFt4XS5zdW0gKz0geTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxOwogICAgcHVzaCh4KTsKICAgIGlmIChsbCA8PSBtaWQpIHVwZGF0ZV9zdW1fcG9pbnQobCwgbWlkLCBsbCwgeCArIHgsIHkpOwogICAgZWxzZSB1cGRhdGVfc3VtX3BvaW50KG1pZCArIDEsIHIsIGxsLCB4ICsgeCArIDEsIHkpOwogICAgaWYgKHRbeF0ubW4gPT0gZ2xvYmFsX3BvczEpIHRbeF0uc3VtICs9IHk7CiAgICByZXR1cm47Cn0KIAp2b2lkIHVwZGF0ZV9zdW0oaW50IGwsIGludCByLCBpbnQgbGwsIGludCByciwgaW50IHgsIGludCB5LCBpbnQgeikgewogICAgaWYgKGwgPiByIHx8IGxsID4gciB8fCBsID4gcnIgfHwgbGwgPiByciB8fCB0W3hdLm1uID4geikgcmV0dXJuOwogICAgaWYgKGwgPj0gbGwgJiYgciA8PSBycikgewogICAgICAgIGlmICh0W3hdLm1uICE9IHopIHJldHVybjsKICAgICAgICB0W3hdLnN1bSArPSAodFt4XS5jbnRfbW4gKiAxbGwgKiB5KTsKICAgICAgICB0W3hdLnFzdW0gKz0geTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxOwogICAgcHVzaCh4KTsKICAgIHVwZGF0ZV9zdW0obCwgbWlkLCBsbCwgcnIsIHggKyB4LCB5LCB6KTsKICAgIHVwZGF0ZV9zdW0obWlkICsgMSwgciwgbGwsIHJyLCB4ICsgeCArIDEsIHksIHopOwogICAgdXBkYXRlX05PREUoeCk7CiAgICByZXR1cm47Cn0KIAp2b2lkIGNscl9ub2RlKGludCBsLCBpbnQgciwgaW50IGxsLCBpbnQgcnIsIGludCB4LCBpbnQgeSkgewogICAgaWYgKGwgPiByIHx8IGxsID4gciB8fCBsID4gcnIgfHwgbGwgPiByciB8fCB0W3hdLm1uID4geSkgcmV0dXJuOwogICAgaWYgKGwgPj0gbGwgJiYgciA8PSBycikgewogICAgICAgIGlmICh0W3hdLm1uICE9IHkpIHJldHVybjsKICAgICAgICB0W3hdLm9iID0gdHJ1ZTsKICAgICAgICB0W3hdLnN1bSA9IHRbeF0ucXN1bSA9IDA7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgIHB1c2goeCk7CiAgICBjbHJfbm9kZShsLCBtaWQsIGxsLCByciwgeCArIHgsIHkpOwogICAgY2xyX25vZGUobWlkICsgMSwgciwgbGwsIHJyLCB4ICsgeCArIDEsIHkpOwogICAgdXBkYXRlX05PREUoeCk7CiAgICByZXR1cm47Cn0KIAovLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLyAgICAgICAgICAgICAgICAgICBBbnN3ZXIgUXVlcmllcwogCmxvbmcgbG9uZyBnZXRfcG9pbnQoaW50IGwsIGludCByLCBpbnQgbGwsIGludCB4KSB7CiAgICBpbnQgbWlkOwogICAgd2hpbGUgKGwgIT0gcikgewogICAgICAgIG1pZCA9IChsICsgcikgPj4gMTsKICAgICAgICBwdXNoKHgpOwogICAgICAgIGlmIChsbCA8PSBtaWQpIHggPDw9IDEsIHIgPSBtaWQ7CiAgICAgICAgZWxzZSB4ID0geCArIHggKyAxLCBsID0gbWlkICsgMTsKICAgIH0KICAgIHJldHVybiB0W3hdLnN1bTsKfQogCmludCBnZXRfcG9pbnRfbW4oaW50IHgpIHsKICAgIHggKz0gc3ogLSAxOwogICAgaW50IHJlcyA9IHRbeF0ubW47CiAgICB4ID4+PSAxOwogICAgd2hpbGUgKHgpIHsKICAgICAgICByZXMgKz0gdFt4XS5xbW47CiAgICAgICAgeCA+Pj0gMTsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KIAogCmxvbmcgbG9uZyBnZXRfc3VtKGludCBsLCBpbnQgciwgaW50IGxsLCBpbnQgcnIsIGludCB4LCBpbnQgeSkgewogICAgaWYgKGwgPiByIHx8IGxsID4gciB8fCBsID4gcnIgfHwgbGwgPiByciB8fCB0W3hdLm1uID4geSkgcmV0dXJuIDA7CiAgICBpZiAobCA+PSBsbCAmJiByIDw9IHJyKSB7CiAgICAgICAgaWYgKHRbeF0ubW4gIT0geSkgcmV0dXJuIDA7CiAgICAgICAgcmV0dXJuIHRbeF0uc3VtOwogICAgfQogICAgaW50IG1pZCA9IChsICsgcikgPj4gMTsKICAgIHB1c2goeCk7CiAgICByZXR1cm4gZ2V0X3N1bShsLCBtaWQsIGxsLCByciwgeCArIHgsIHkpICsgZ2V0X3N1bShtaWQgKyAxLCByLCBsbCwgcnIsIHggKyB4ICsgMSwgeSk7Cn0KIApsb25nIGxvbmcgcXVlcnlfNChpbnQgeCkgewogICAgcmV0dXJuIGdldF9wb2ludCgxLCBzeiwgdGluW3hdLCAxKTsKfQogCmxvbmcgbG9uZyBxdWVyeV81KGludCB4KSB7CiAgICB4ID0gZ2V0X2xhc3QoMSwgc3osIDEsIHRpblt4XSwgMSwgdG91dFt4XSk7CiAgICBpZiAoIXgpIHggPSAxOwogICAgeCA9IHBvY1t4XTsKICAgIGludCB5ID0gZ2V0X3BvaW50X21uKHRpblt4XSk7CiAgICByZXR1cm4gZ2V0X3N1bSgxLCBzeiwgdGluW3hdLCB0b3V0W3hdLCAxLCB5KTsKfQogCmludCBxdWVyeV83KCkgewogICAgaW50IHgsIHk7CiAgICB4ID0gRklSOwogICAgaWYgKHggIT0gMWU5KSB7CiAgICAgICAgeSA9IFNFQzsKICAgICAgICB4ID0gcG9jW3hdOwogICAgICAgIHkgPSBwb2NbeV07CiAgICAgICAgcmV0dXJuICgoYW5zX3F1ZXJ5NyArIGdldF9udW1iZXJfb2ZfZWRnZXMoeCwgeSwgZ2V0X3BvaW50X21uKHRpblt4XSksIGdldF9wb2ludF9tbih0aW5beV0pKSkgPj4gMSk7CiAgICB9CiAgICByZXR1cm4gMDsKfQogCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLyAgICAgICAgICAgICAgICAgICBNb2RpZnkgIFF1ZXJpZXMKIAogCnZvaWQgcXVlcnlfMShpbnQgcikgewogICAgaW50IHggPSBlZFtyXS5zZWNvbmQ7CiAgICBpbnQgeHggPSBlZFtyXS5maXJzdDsKICAgIHh4ID0gZ2V0X2xhc3QoMSwgc3osIDEsIHRpblt4eF0sIDEsIHRvdXRbeHhdKTsKICAgIGlmICgheHgpIHh4ID0gMTsKICAgIHh4ID0gcG9jW3h4XTsKICAgIAogICAgaWYgKGdldF9maXJzdF92ZXJ0ZXgoMSwgc3osIHRpblt4XSwgdG91dFt4XSwgMSkpIHsKICAgICAgICBpZiAoRklSIDwgdGluW3hdKSB7CiAgICAgICAgICAgIGlmIChiaW5fZWRbcl0gPT0gJzAnKSArK2Fuc19xdWVyeTc7CiAgICAgICAgICAgIGVsc2UgLS1hbnNfcXVlcnk3OwogICAgICAgIH0KICAgICAgICBpZiAoU0VDID4gdG91dFt4XSkgewogICAgICAgICAgICBpZiAoYmluX2VkW3JdID09ICcwJykgKythbnNfcXVlcnk3OwogICAgICAgICAgICBlbHNlIC0tYW5zX3F1ZXJ5NzsKICAgICAgICB9CiAgICB9CiAgICAKICAgIGlmIChiaW5fZWRbcl0gPT0gJzEnKSB7CiAgICAgICAgdXBkYXRlX2VkZ2UodGluW3hdLCAwKTsKICAgICAgICB1cGRhdGVfY250KDEsIHN6LCB0aW5beF0sIHRvdXRbeF0sIDEsIC0xKTsKICAgICAgICBiaW5fZWRbcl0gPSAnMCc7CiAgICB9IGVsc2UgewogICAgICAgIHVwZGF0ZV9lZGdlKHRpblt4XSwgdG91dFt4XSk7CiAgICAgICAgdXBkYXRlX2NudCgxLCBzeiwgdGluW3hdLCB0b3V0W3hdLCAxLCAxKTsKICAgICAgICBiaW5fZWRbcl0gPSAnMSc7CiAgICB9CiAgICAKICAgIGlmIChiaW5fZWRbcl0gPT0gJzAnKSB7CiAgICAgICAgaWYgKGNvbXBbeF0pIHsKICAgICAgICAgICAgdXBkYXRlX2NvbXBvbmVudCh4KTsKICAgICAgICAgICAgaWYgKCFjb21wW3h4XSkgdXBkYXRlX2NvbXBvbmVudCh4eCk7CiAgICAgICAgfQogICAgfSBlbHNlIGlmIChjb21wW3h4XSkgewogICAgICAgIGlmIChpc190aGVyZV9zb21lYm9keSh4LCAxKSkgewogICAgICAgICAgICB1cGRhdGVfY29tcG9uZW50KHgpOwogICAgICAgICAgICBpZiAoIWlzX3RoZXJlX3NvbWVib2R5KHh4LCAxKSkgdXBkYXRlX2NvbXBvbmVudCh4eCk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuOwp9CiAKdm9pZCBxdWVyeV8yKGludCB4LCBpbnQgeikgewogICAgeCA9IGdldF9sYXN0KDEsIHN6LCAxLCB0aW5beF0sIDEsIHRvdXRbeF0pOwogICAgaWYgKCF4KSB4ID0gMTsKICAgIHggPSBwb2NbeF07CiAgICBpZiAoIWNvbXBbeF0pIHVwZGF0ZV9jb21wb25lbnQoeCk7CiAgICBpbnQgeSA9IGdldF9wb2ludF9tbih0aW5beF0pOwogICAgdXBkYXRlX3N1bSgxLCBzeiwgdGluW3hdLCB0b3V0W3hdLCAxLCB6LCB5KTsKICAgIHJldHVybjsKfQogCnZvaWQgcXVlcnlfNihpbnQgeCkgewogICAgeCA9IGdldF9sYXN0KDEsIHN6LCAxLCB0aW5beF0sIDEsIHRvdXRbeF0pOwogICAgaWYgKCF4KSB4ID0gMTsKICAgIHggPSBwb2NbeF07CiAgICBpZiAoY29tcFt4XSkgdXBkYXRlX2NvbXBvbmVudCh4KTsKICAgIGludCB5ID0gZ2V0X3BvaW50X21uKHRpblt4XSk7CiAgICBjbHJfbm9kZSgxLCBzeiwgdGluW3hdLCB0b3V0W3hdLCAxLCB5KTsKICAgIHJldHVybjsKfQogCnZvaWQgcXVlcnlfMyhpbnQgeCkgewogICAgaW50IHkgPSB4OwogICAgeCA9IGdldF9sYXN0KDEsIHN6LCAxLCB0aW5beF0sIDEsIHRvdXRbeF0pOwogICAgaWYgKCF4KSB4ID0gMTsKICAgIHggPSBwb2NbeF07CiAgICBsb25nIGxvbmcgeHggPSBxdWVyeV81KHgpOwogICAgY2xyX25vZGUoMSwgc3osIHRpblt4XSwgdG91dFt4XSwgMSwgZ2V0X3BvaW50X21uKHRpblt4XSkpOwogICAgdXBkYXRlX3N1bV9wb2ludCgxLCBzeiwgdGluW3ldLCAxLCB4eCk7CiAgICByZXR1cm47Cn0KIApib29sIGRmc19pbml0KGludCB4LCBpbnQgeSwgYm9vbCBlZGdlKSB7CiAgICBib29sIGlzX3RoZXJlID0gZmFsc2U7CiAgICBpZiAodFtzeiArIHRpblt4XSAtIDFdLnN1bSkgaXNfdGhlcmUgPSB0cnVlOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCB2W3hdLnNpemUoKTsgKytpKSB7CiAgICAgICAgaW50IHRvID0gdlt4XVtpXS5maXJzdDsKICAgICAgICBpZiAodG8gPT0geSkgY29udGludWU7CiAgICAgICAgaWYgKGJpbl9lZFt2W3hdW2ldLnNlY29uZF0gPT0gJzEnKSB7CiAgICAgICAgICAgIGRmc19pbml0KHRvLCB4LCAxKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBpZiAoZGZzX2luaXQodG8sIHgsIDApKSBpc190aGVyZSA9IHRydWU7CiAgICAgICAgfQogICAgfQogICAgaWYgKGVkZ2UgJiYgaXNfdGhlcmUpIHsKICAgICAgICBjb21wW3hdID0gMTsKICAgICAgICB2ZXJ0X2NudFtzeiArIHRpblt4XSAtIDFdID0gMTsKICAgIH0KICAgIHJldHVybiBpc190aGVyZTsKfQogCmJvb2wgZGZzX2luaXQyKGludCB4LCBpbnQgeSkgewogICAgYm9vbCBpc190aGVyZSA9IGZhbHNlOwogICAgaWYgKHRbc3ogKyB0aW5beF0gLSAxXS5zdW0pIGlzX3RoZXJlID0gdHJ1ZTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgdlt4XS5zaXplKCk7ICsraSkgewogICAgICAgIGludCB0byA9IHZbeF1baV0uZmlyc3Q7CiAgICAgICAgaWYgKHRvID09IHkpIGNvbnRpbnVlOwogICAgICAgIGlmIChiaW5fZWRbdlt4XVtpXS5zZWNvbmRdID09ICcxJykgewogICAgICAgICAgICBpZiAoZGZzX2luaXQyKHRvLCB4KSkgewogICAgICAgICAgICAgICAgaXNfdGhlcmUgPSB0cnVlOwogICAgICAgICAgICAgICAgKythbnNfcXVlcnk3OwogICAgICAgICAgICB9CiAgICAgICAgfSBlbHNlIGlmIChkZnNfaW5pdDIodG8sIHgpKSBpc190aGVyZSA9IHRydWU7CiAgICB9CiAgICByZXR1cm4gaXNfdGhlcmU7Cn0KIAp2b2lkIGRmc19pbml0MyhpbnQgeCwgaW50IHksIGludCBfZCwgaW50IGwpIHsKICAgIGlmICh4ID09IGwpIGFuc19xdWVyeTcgLT0gX2Q7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHZbeF0uc2l6ZSgpOyArK2kpIHsKICAgICAgICBpbnQgdG8gPSB2W3hdW2ldLmZpcnN0OwogICAgICAgIGlmICh0byAhPSB5KSBkZnNfaW5pdDModG8sIHgsIF9kICsgKGJpbl9lZFt2W3hdW2ldLnNlY29uZF0gLSAnMCcpLCBsKTsKICAgIH0KICAgIHJldHVybjsKfQogCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KIAogCiAKdm9pZCBpbml0KGludCBOLCB2ZWN0b3I8aW50PiB2LCB2ZWN0b3I8aW50PiB1LCB2ZWN0b3I8aW50PiBiLCB2ZWN0b3I8aW50PiBhLCBpbnQgR1JPVVApIHsKICAgIG4gPSBOOwogICAgaW50IHgsIHk7CiAgICBmb3IgKGludCBpID0gMTsgaSA8IG47ICsraSkgewogICAgICAgIHggPSB2W2kgLSAxXTsKICAgICAgICB5ID0gdVtpIC0gMV07CiAgICAgICAgZWRbaV0gPSB7eCwgeX07CiAgICAgICAgOjp2W3hdLnB1c2hfYmFjayh7eSwgaX0pOwogICAgICAgIDo6dlt5XS5wdXNoX2JhY2soe3gsIGl9KTsKICAgIH0KICAgIGJpbl9lZCA9ICIjIjsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYi5zaXplKCk7ICsraSkKICAgICAgICBiaW5fZWQgKz0gY2hhcihiW2ldICsgJzAnKTsKICAgIGRmcygxLCAwKTsKICAgIGJ1aWxkX3NwYXJzZV90YWJsZSgpOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPCBuOyArK2kpIHsKICAgICAgICB4ID0gZWRbaV0uZmlyc3Q7CiAgICAgICAgeSA9IGVkW2ldLnNlY29uZDsKICAgICAgICBpZiAodGluW3ldIDwgdGluW3hdKSBzd2FwKGVkW2ldLmZpcnN0LCBlZFtpXS5zZWNvbmQpOwogICAgfQogICAgc3ogPSAxOwogICAgd2hpbGUgKHN6IDwgbikgc3ogKz0gc3o7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpCiAgICAgICAgdFtzeiArIGkgLSAxXS5jbnRfbW4gPSAxOwogICAgZm9yIChpbnQgaSA9IHN6IC0gMTsgaSA+IDA7IC0taSkKICAgICAgICB0W2ldLmNudF9tbiA9IHRbaSArIGldLmNudF9tbiArIHRbaSArIGkgKyAxXS5jbnRfbW47CiAgICAKICAgIGludCBycjsKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgbjsgKytpKQogICAgICAgIGlmIChiaW5fZWRbaV0gPT0gJzEnKSB7CiAgICAgICAgICAgIHJyID0gZWRbaV0uc2Vjb25kOwogICAgICAgICAgICBtYXhfdG91dFt0aW5bcnJdICsgc3ogLSAxXSA9IHRvdXRbcnJdOwogICAgICAgICAgICBxb2JbdGluW3JyXV0rKzsKICAgICAgICAgICAgcW9iW3RvdXRbcnJdICsgMV0tLTsKICAgICAgICB9CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgICAgICBxb2JbaV0gKz0gcW9iW2kgLSAxXTsKICAgICAgICB0W3N6ICsgdGluW2ldIC0gMV0uc3VtICs9IGFbaSAtIDFdOwogICAgICAgIHRbc3ogKyBpIC0gMV0ubW4gPSBxb2JbaV07CiAgICB9CiAgICBmb3IgKGludCBpID0gc3ogLSAxOyBpID4gMDsgLS1pKSB7CiAgICAgICAgbWF4X3RvdXRbaV0gPSBtYXhfdG91dFtpICsgaV07CiAgICAgICAgaWYgKG1heF90b3V0W2kgKyBpICsgMV0gPiBtYXhfdG91dFtpXSkgbWF4X3RvdXRbaV0gPSBtYXhfdG91dFtpICsgaSArIDFdOwogICAgICAgIHVwZGF0ZV9OT0RFKGkpOwogICAgfQogICAgCiAgICBkZnNfaW5pdCgxLCAwLCB0cnVlKTsKICAgIGZvciAoaW50IGkgPSBzeiAtIDE7IGkgPiAwOyAtLWkpCiAgICAgICAgdmVydF9jbnRbaV0gPSB2ZXJ0X2NudFtpICsgaV0gKyB2ZXJ0X2NudFtpICsgaSArIDFdOwogICAgLy8vIMOD77+9w6/Cv8K9w4PCr8OCwr/DgsK9w4Pvv73Dr8K/wr3Dg++/vcOCwr/Dg++/vcOvwr/CvcODwq/DgsK/w4LCvcOD77+9w6/Cv8K9w4Pvv73DgsK+w4Pvv73Dr8K/wr3Dg8Kvw4LCv8OCwr3Dg++/vcOCwq/Dg++/vcOCwr/Dg++/vcOCwr3Dg++/vcOvwr/CvcODwq/DgsK/w4LCvcOD77+9w4LCr8OD77+9w4LCv8OD77+9w4LCvcOD77+9w6/Cv8K9w4PCr8OCwr/DgsK9w4Pvv73Dr8K/wr3Dg++/vcOCwrjDg++/vcOvwr/CvcODwq/DgsK/w4LCvcOD77+9w4LCr8OD77+9w4LCv8OD77+9w4LCvcOD77+9w6/Cv8K9w4PCr8OCwr/DgsK9w4Pvv73Dr8K/wr3Dg++/vcOCwrDDg++/vcOvwr/CvcODwq/DgsK/w4LCvcOD77+9w4LCr8OD77+9w4LCv8OD77+9w4LCvcOD77+9w6/Cv8K9w4PCr8OCwr/DgsK9w4Pvv73DgsKvw4Pvv73DgsK/w4Pvv73DgsK9IMOD77+9w6/Cv8K9w4PCr8OCwr/DgsK9w4Pvv73Dr8K/wr3Dg++/vcOCwr7Dg++/vcOvwr/CvcODwq/DgsK/w4LCvcOD77+9w4LCr8OD77+9w4LCv8OD77+9w4LCvcOD77+9w6/Cv8K9w4PCr8OCwr/DgsK9w4Pvv73Dr8K/wr3Dg++/vcOCwrLDg++/vcOvwr/CvcODwq/DgsK/w4LCvcOD77+9w6/Cv8K9w4Pvv73DgsK1w4Pvv73Dr8K/wr3Dg8Kvw4LCv8OCwr3Dg++/vcOCwq/Dg++/vcOCwr/Dg++/vcOCwr0KICAgIGludCBwb3MgPSAwOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKQogICAgICAgIGlmIChjb21wW2ldKSB7CiAgICAgICAgICAgIHBvcyA9IGk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIGlmIChwb3MpIHsKICAgICAgICBkZnNfaW5pdDIocG9zLCAwKTsKICAgICAgICBhbnNfcXVlcnk3ICo9IDI7CiAgICAgICAgaW50IGZpciA9IC0xOwogICAgICAgIGludCBsYXN0ID0gLTE7CiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKQogICAgICAgICAgICBpZiAoY29tcFtwb2NbaV1dKSB7CiAgICAgICAgICAgICAgICBpZiAoZmlyID09IC0xKSBmaXIgPSBpOwogICAgICAgICAgICAgICAgbGFzdCA9IGk7CiAgICAgICAgICAgIH0KICAgICAgICBGSVIgPSBmaXI7CiAgICAgICAgU0VDID0gbGFzdDsKICAgICAgICBmaXIgPSBwb2NbZmlyXTsKICAgICAgICBsYXN0ID0gcG9jW2xhc3RdOwogICAgICAgIGRmc19pbml0MyhmaXIsIDAsIDAsIGxhc3QpOwogICAgfQogICAgcmV0dXJuOwp9CiAKIAppbnQgbWFpbihpbnQgYXJnYywgY29uc3QgY2hhciAqIGFyZ3ZbXSkgewogICAgLy8gICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgaW50IHgsIHk7CiAgICBjaW4gPj4gZ3JvdXA7CiAgICBjaW4gPj4gbiA+PiBtOwogICAgdmVjdG9yPGludD4gdnYsIHV1OwogICAgZm9yIChpbnQgaSA9IDE7IGkgPCBuOyArK2kpIHsKICAgICAgICBjaW4gPj4geCA+PiB5OwogICAgICAgIHZ2LnB1c2hfYmFjayh4KTsKICAgICAgICB1dS5wdXNoX2JhY2soeSk7CiAgICB9CiAgICBjaW4gPj4gYmluX2VkOwogICAgdmVjdG9yPGludD4gYiwgYTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgKGludCliaW5fZWQuc2l6ZSgpOyArK2kpCiAgICAgICAgYi5wdXNoX2JhY2soYmluX2VkW2ldIC0gJzAnKTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgewogICAgICAgIGNpbiA+PiB4OwogICAgICAgIGEucHVzaF9iYWNrKHgpOwogICAgfQogICAgaW5pdChuLCB2diwgdXUsIGIsIGEsIGdyb3VwKTsKICAgIGludCB0cDsKICAgIGZvciAoaW50IGl0ID0gMTsgaXQgPD0gbTsgKytpdCkgewogICAgICAgIGNpbiA+PiB0cDsKICAgICAgICBpZiAodHAgPT0gMSkgewogICAgICAgICAgICBjaW4gPj4geDsKICAgICAgICAgICAgcXVlcnlfMSh4KTsKICAgICAgICB9IGVsc2UgaWYgKHRwID09IDIpIHsKICAgICAgICAgICAgY2luID4+IHggPj4geTsKICAgICAgICAgICAgcXVlcnlfMih4LCB5KTsKICAgICAgICB9IGVsc2UgaWYgKHRwID09IDMpIHsKICAgICAgICAgICAgY2luID4+IHg7CiAgICAgICAgICAgIHF1ZXJ5XzMoeCk7CiAgICAgICAgfSBlbHNlIGlmICh0cCA9PSA0KSB7CiAgICAgICAgICAgIGNpbiA+PiB4OwogICAgICAgICAgICBjb3V0IDw8IHF1ZXJ5XzQoeCkgPDwgJ1xuJzsKICAgICAgICB9IGVsc2UgaWYgKHRwID09IDUpIHsKICAgICAgICAgICAgY2luID4+IHg7CiAgICAgICAgICAgIGNvdXQgPDwgcXVlcnlfNSh4KSA8PCAnXG4nOwogICAgICAgIH0gZWxzZSBpZiAodHAgPT0gNikgewogICAgICAgICAgICBjaW4gPj4geDsKICAgICAgICAgICAgcXVlcnlfNih4KTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBjb3V0IDw8IHF1ZXJ5XzcoKSA8PCAnXG4nOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9CiAKLy8vLwog