#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(v) v.begin(),v.end()
const int N = 1e5+7;
ll time_in = 0; ll idx = 0; ll n,m,q;
vll value(N),color(N),left_range_(N),right_range_(N),parent(N,0),depth(N,0),subtree_size(N,0),heavy(N,0);
vll head(N,0),lt(N,0),pos(N,0),pos_out(N,0);
void dfs(int node,int par,vll adj[],int dep){
parent[node] = par;
depth[node] = dep;
for(auto x: adj[node]){
if(x != par){
dfs(x,node,adj,dep+1);
subtree_size[node] += subtree_size[x];
if(subtree_size[x] > subtree_size[heavy[node]]){
heavy[node] = x;
}
}
}
subtree_size[node]++;
}
ll lca(ll x,ll y){
while(head[x] != head[y]){
if(depth[head[x]] < depth[head[y]]) swap(x,y);
x = parent[head[x]];
}
if(depth[x] < depth[y]) swap(x,y);
return y;
}
void dfsHLD(int node,vll adj[], ll chain){
head[node] = chain;
lt[idx] = value[node];
pos[node] = idx++;
if(heavy[node] != 0){
dfsHLD(heavy[node],adj,chain);
}
for(auto x: adj[node]){
if(x != parent[node] and x != heavy[node]){
dfsHLD(x,adj,x);
}
}
pos_out[node] = idx;
}
vpll arr;
vll lazyarr;
void merge(ll ind, ll left, ll right)
{
arr[ind]=arr[left];
arr[ind].first+=arr[right].first;
arr[ind].second+=arr[right].second;
}
void update_lazy(ll ind, ll lo, ll hi)
{
if (lazyarr[ind]==0) return;
ll upd=lazyarr[ind];
lazyarr[ind]=0;
if (upd==1)
arr[ind].first+=arr[ind].second, arr[ind].second=0;
else
arr[ind].second+=arr[ind].first, arr[ind].first=0;
if (lo!=hi)
lazyarr[2*ind+1]=upd, lazyarr[2*ind+2]=upd;
}
void build(ll ind, ll lo, ll hi, vll &v)
{
if (lo==hi)
{
if (v[lo]>=0) arr[ind].first=v[lo], arr[ind].second=0;
else arr[ind].first=0, arr[ind].second=-v[lo];
return;
}
ll mid=(hi+lo)/2;
build(2*ind+1,lo,mid,v);
build(2*ind+2,mid+1,hi,v);
merge(ind,2*ind+1,2*ind+2);
}
void update(ll ind, ll lo, ll hi, ll l, ll r, ll d)
{
// check for update
update_lazy(ind,lo,hi);
if (lo>r || hi<l) return;
else if (lo>=l && hi<=r)
{
if (d==1)
arr[ind].first+=arr[ind].second, arr[ind].second=0;
else
arr[ind].second+=arr[ind].first, arr[ind].first=0;
if (lo!=hi)
lazyarr[2*ind+1]=d, lazyarr[2*ind+2]=d;
}
else
{
ll mid=(hi+lo)/2;
update(2*ind+1,lo,mid,l,r,d);
update(2*ind+2,mid+1,hi,l,r,d);
merge(ind,2*ind+1,2*ind+2);
}
}
ll query(ll ind, ll lo, ll hi, ll l, ll r)
{
// check for update
update_lazy(ind,lo,hi);
if (lo>r || hi<l) return 0;
else if (lo>=l && hi<=r) return arr[ind].first-arr[ind].second;
ll mid=(hi+lo)/2;
ll left=query(2*ind+1,lo,mid,l,r);
ll right=query(2*ind+2,mid+1,hi,l,r);
ll ans=left+right;
return ans;
}
vpll brr; // { count 0, count 1}
vll lazy;
// 0 -> no update_color
// 1 -> force 0
// 2 -> force 1
void merge_color(ll ind, ll left, ll right)
{
brr[ind]=brr[left];
brr[ind].first+=brr[right].first;
brr[ind].second+=brr[right].second;
}
void update_lazy_color(ll ind, ll lo, ll hi)
{
if (lazy[ind]==0) return;
ll elem=hi-lo+1;
ll upd=lazy[ind];
if (lazy[ind]==1) brr[ind]={elem,0};
else brr[ind]={0,elem};
lazy[ind]=0;
if (lo!=hi) lazy[2*ind+1]=upd, lazy[2*ind+2]=upd;
}
void build_color(ll ind, ll lo, ll hi, vll &v)
{
if (lo==hi)
{
if (v[lo]==0) brr[ind]={1,0};
else brr[ind]={0,1};
return;
}
ll mid=(hi+lo)/2;
build_color(2*ind+1,lo,mid,v);
build_color(2*ind+2,mid+1,hi,v);
merge_color(ind,2*ind+1,2*ind+2);
}
void update_color(ll ind, ll lo, ll hi, ll l, ll r, ll x)
{
// check update_color in lazy
update_lazy_color(ind,lo,hi);
if (lo>r || hi<l) return;
else if (lo>=l && hi<=r)
{
ll elem=hi-lo+1;
if (x==1) brr[ind]={elem,0};
else brr[ind]={0,elem};
if (lo!=hi) lazy[2*ind+1]=x, lazy[2*ind+2]=x;
}
else
{
ll mid=(hi+lo)/2;
update_color(2*ind+1,lo,mid,l,r,x);
update_color(2*ind+2,mid+1,hi,l,r,x);
merge_color(ind,2*ind+1,2*ind+2);
}
}
ll query_color(ll ind, ll lo, ll hi, ll l, ll r)
{
// check update_color in lazy
update_lazy_color(ind,lo,hi);
if (lo>r || hi<l) return 0;
else if (lo>=l && hi<=r) return brr[ind].second;
ll mid=(hi+lo)/2;
ll left=query_color(2*ind+1,lo,mid,l,r);
ll right=query_color(2*ind+2,mid+1,hi,l,r);
ll ans=left+right;
return ans;
}
ll get_the_value_color(int x,int y){
ll sum = 0;
while(head[x] != head[y]){
if(depth[head[x]] < depth[head[y]]) swap(x,y);
ll value = query_color(0,0,n-1,pos[head[x]], pos[x]);
sum += value;
x = parent[head[x]];
}
if(depth[x] < depth[y]) swap(x,y);
ll value = query_color(0,0,n-1,pos[y],pos[x]);
if(pos[x] >= pos[y]) sum += value;
return sum;
}
void update_the_color(int x,int y,int color){
while(head[x] != head[y]){
if(depth[head[x]] < depth[head[y]]) swap(x,y);
update_color(0,0,n-1,pos[head[x]],pos[x],color);
x = parent[head[x]];
}
if(depth[x] < depth[y]) swap(x,y);
if(pos[x] >= pos[y] )update_color(0,0,n-1,pos[y],pos[x],color);
}
void update_the_value(int x,int y,int sign){
while(head[x] != head[y]){
if(depth[head[x]] < depth[head[y]]) swap(x,y);
update(0,0,n-1,pos[head[x]],pos[x],sign);
x = parent[head[x]];
}
if(depth[x] < depth[y]) swap(x,y);
if(pos[x] >= pos[y] )update(0,0,n-1,pos[y],pos[x],sign);
}
ll get_the_value(int x,int y){
ll sum = 0;
while(head[x] != head[y]){
if(depth[head[x]] < depth[head[y]]) swap(x,y);
ll value = query(0,0,n-1,pos[head[x]],pos[x]);
sum += value;
x = parent[head[x]];
}
if(depth[x] < depth[y]) swap(x,y);
ll value = query(0,0,n-1,pos[y],pos[x]);
if(pos[x] >= pos[y]) sum += value;
return sum;
}
template<typename Node, typename Update>
struct SegTree {
vector<Node> tree;
vector<ll> arr; // type may change
int n;
int s;
SegTree(int a_len, vector<ll> &a) { // change if type updated
arr = a;
n = a_len;
s = 1;
while(s < 2 * n){
s = s << 1;
}
tree.resize(s); fill(all(tree), Node());
build(0, n - 1, 1);
}
void build(int start, int end, int index) // Never change this
{
if (start == end) {
tree[index] = Node(arr[start]);
return;
}
int mid = (start + end) / 2;
build(start, mid, 2 * index);
build(mid + 1, end, 2 * index + 1);
tree[index].merge(tree[2 * index], tree[2 * index + 1]);
}
void update(int start, int end, int index, int query_index, Update &u) // Never Change this
{
if (start == end) {
u.apply(tree[index]);
return;
}
int mid = (start + end) / 2;
if (mid >= query_index)
update(start, mid, 2 * index, query_index, u);
else
update(mid + 1, end, 2 * index + 1, query_index, u);
tree[index].merge(tree[2 * index], tree[2 * index + 1]);
}
Node query(int start, int end, int index, int left, int right) { // Never change this
if (start > right || end < left)
return Node();
if (start >= left && end <= right)
return tree[index];
int mid = (start + end) / 2;
Node l, r, ans;
l = query(start, mid, 2 * index, left, right);
r = query(mid + 1, end, 2 * index + 1, left, right);
ans.merge(l, r);
return ans;
}
void make_update(int index, ll val) { // pass in as many parameters as required
Update new_update = Update(val); // may change
update(0, n - 1, 1, index, new_update);
}
Node make_query(int left, int right) {
return query(0, n - 1, 1, left, right);
}
};
// all positive
struct Node1 {
ll val; // may change
Node1() { // Identity element
val = 0; // may change
}
Node1(ll p1) { // Actual Node
val = p1; // may change
}
void merge(Node1 &l, Node1 &r) { // Merge two child nodes
val = l.val + r.val; // may change
}
};
struct Update1 {
ll val; // may change
Update1(ll p1) { // Actual Update
val = p1; // may change
}
void apply(Node1 &a) { // apply update to given node
a.val = val; // may change
}
};
void solve() {
cin>>n>>q;
assert(n >= 1 and n <= 100000);
assert(q >= 1 and q <= 100000);
color.resize(n + 1); value.resize(n + 1);
for(int i = 0; i< n; i++) color[i] = 0;
arr.clear(); lazyarr.clear(); arr.resize(4*n+1); lazyarr.resize(4*n+1,0);
brr.clear(); lazy.clear(); brr.resize(4*n+1); lazy.resize(4*n+1,0);
vector<ll> adj[n + 1];
for(int i = 0; i< n-1; i++){
ll x,y; cin>>x>>y;
assert(x >= 1 and x <= n); assert(y >= 1 and y <= n);
adj[x].push_back(y);
adj[y].pb(x);
}
for(int i = 1; i<= n; i++) cin>>value[i];
parent.resize(n + 1); depth.resize(n + 1); subtree_size.resize(n + 1); heavy.resize(n + 1); head.resize(n + 1);
lt.resize(n + 1); pos.resize(n + 1); pos_out.resize(n + 1);
dfs(1,0,adj,0); // main dfs calling
dfsHLD(1,adj,1); // hld dfs calling
auto lt1 = lt; // decomposed array after HLD
build(0,0,n-1,lt); // segment tree for the mix of black and white node values
build_color(0,0,n-1,color); // segment tree for saving the color white and black nodes
SegTree<Node1,Update1> sg = SegTree<Node1,Update1> (n,lt1); // segment tree storing all the original values
//all nodes are considered positive means all nodes are black first
update(0,0,n-1,0,n-1,-1); // coloring all the node white first
for(int i = 0; i < q; i++){
int qType; cin>>qType;
assert(qType >= 1 and qType <= 3);
if(qType == 1){
ll x,y ;cin>>x>>y;
assert(x >= 1 and x <= n);
assert(y >= 1 and y <= n);
ll lca_node = lca(x,y);
ll path_dist = abs(depth[lca_node] - depth[x]) + abs(depth[lca_node] - depth[y]) + 1;
ll black_nodes = get_the_value_color(x,y);
ll white_nodes = path_dist - black_nodes;
if(black_nodes > white_nodes){
update_the_color(x,y,2);
update_the_value(x,y,1);
}else if(black_nodes < white_nodes){
update_the_color(x,y,1);
update_the_value(x,y,-1);
}
}else if(qType == 2){
ll x; cin>>x;
assert(x >= 1 and x <= n);
update_color(0,0,n-1,pos[x], pos_out[x] - 1,2); // changing the color of the subtree
update(0,0,n-1,pos[x], pos_out[x] - 1,1); // change the subtree with positive values means black nodes
}else{
ll a,b ;cin>>a>>b;
assert(a >= 1 and a <= n);
assert(b >= 1 and b <= n);
ll x,y; x = a; y = b;
ll total_value = 0;
while(head[x] != head[y]){
if(depth[head[x]] < depth[head[y]]) swap(x,y);
total_value += sg.make_query(pos[head[x]],pos[x]).val;
x = parent[head[x]];
}
if(depth[x] < depth[y]) swap(x,y);
if(pos[x] >= pos[y]) total_value += sg.make_query(pos[y],pos[x]).val;
// total_value --> getting the original values considered all nodes are black
ll path_value = get_the_value(a,b); // getting the values where both positive and negative values are there
ll black_value = (total_value + path_value) / 2;
ll white_value = (total_value - path_value) / 2;
cout<<max(white_value,black_value)<<endl;
}
}
}
int main()
{
IOS;
#ifndef ONLINE_JUDGE
freopen("error.txt", "w", stderr);
#endif
int test = 1;
// cin >> test;
for (int i = 1; i <= test; i++) {
// cout << "Case " << i << ": "<<endl;
solve();
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgSU9TICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKTsgY291dC50aWUoTlVMTCk7CiNkZWZpbmUgbGwgICAgICAgICAgICAgICBsb25nIGxvbmcKI2RlZmluZSBwYiAgICAgICAgICAgICAgIHB1c2hfYmFjawojZGVmaW5lIHZsbCAgICAgICAgICAgICAgdmVjdG9yPGxsPgojZGVmaW5lIHBsbCAgICAgICAgICAgICAgcGFpcjxsbCxsbD4KI2RlZmluZSB2cGxsICAgICAgICAgICAgIHZlY3RvcjxwbGw+CiNkZWZpbmUgYWxsKHYpIHYuYmVnaW4oKSx2LmVuZCgpCgoKY29uc3QgaW50IE4gPSAxZTUrNzsKbGwgdGltZV9pbiA9IDA7IGxsIGlkeCA9IDA7IGxsIG4sbSxxOyAKdmxsIHZhbHVlKE4pLGNvbG9yKE4pLGxlZnRfcmFuZ2VfKE4pLHJpZ2h0X3JhbmdlXyhOKSxwYXJlbnQoTiwwKSxkZXB0aChOLDApLHN1YnRyZWVfc2l6ZShOLDApLGhlYXZ5KE4sMCk7ICAgCnZsbCBoZWFkKE4sMCksbHQoTiwwKSxwb3MoTiwwKSxwb3Nfb3V0KE4sMCk7Cgp2b2lkIGRmcyhpbnQgbm9kZSxpbnQgcGFyLHZsbCBhZGpbXSxpbnQgZGVwKXsKICAgIHBhcmVudFtub2RlXSA9IHBhcjsKICAgIGRlcHRoW25vZGVdID0gZGVwOwogICAgZm9yKGF1dG8geDogYWRqW25vZGVdKXsKICAgICAgICBpZih4ICE9IHBhcil7CiAgICAgICAgICAgIGRmcyh4LG5vZGUsYWRqLGRlcCsxKTsKICAgICAgICAgICAgc3VidHJlZV9zaXplW25vZGVdICs9IHN1YnRyZWVfc2l6ZVt4XTsgCiAgICAgICAgICAgIGlmKHN1YnRyZWVfc2l6ZVt4XSA+ICBzdWJ0cmVlX3NpemVbaGVhdnlbbm9kZV1dKXsKICAgICAgICAgICAgICAgIGhlYXZ5W25vZGVdID0geDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHN1YnRyZWVfc2l6ZVtub2RlXSsrOwp9IAoKbGwgbGNhKGxsIHgsbGwgeSl7ICAgCiAgICAgICAgd2hpbGUoaGVhZFt4XSAhPSBoZWFkW3ldKXsKICAgICAgICAgICAgaWYoZGVwdGhbaGVhZFt4XV0gPCBkZXB0aFtoZWFkW3ldXSkgc3dhcCh4LHkpOwogICAgICAgICAgICB4ID0gcGFyZW50W2hlYWRbeF1dOwogICAgICAgIH0KICAgICAgICBpZihkZXB0aFt4XSA8IGRlcHRoW3ldKSBzd2FwKHgseSk7CiAgICByZXR1cm4geTsKfQp2b2lkIGRmc0hMRChpbnQgbm9kZSx2bGwgYWRqW10sIGxsIGNoYWluKXsKICAgIGhlYWRbbm9kZV0gPSBjaGFpbjsKICAgIGx0W2lkeF0gPSB2YWx1ZVtub2RlXTsKICAgIHBvc1tub2RlXSA9IGlkeCsrOwogICAgaWYoaGVhdnlbbm9kZV0gIT0gMCl7CiAgICAgICAgZGZzSExEKGhlYXZ5W25vZGVdLGFkaixjaGFpbik7CiAgICB9CiAgICBmb3IoYXV0byB4OiBhZGpbbm9kZV0pewogICAgICAgIGlmKHggIT0gcGFyZW50W25vZGVdIGFuZCB4ICE9IGhlYXZ5W25vZGVdKXsKICAgICAgICAgICAgICAgIGRmc0hMRCh4LGFkaix4KTsKICAgICAgICB9CiAgICB9IAogICAgcG9zX291dFtub2RlXSA9IGlkeDsKfQoKCgp2cGxsIGFycjsKdmxsIGxhenlhcnI7Cgp2b2lkIG1lcmdlKGxsIGluZCwgbGwgbGVmdCwgbGwgcmlnaHQpCnsKICAgIGFycltpbmRdPWFycltsZWZ0XTsKICAgIGFycltpbmRdLmZpcnN0Kz1hcnJbcmlnaHRdLmZpcnN0OwogICAgYXJyW2luZF0uc2Vjb25kKz1hcnJbcmlnaHRdLnNlY29uZDsKfQoKdm9pZCB1cGRhdGVfbGF6eShsbCBpbmQsIGxsIGxvLCBsbCBoaSkKewogICAgaWYgKGxhenlhcnJbaW5kXT09MCkgcmV0dXJuOwogICAgbGwgdXBkPWxhenlhcnJbaW5kXTsKICAgIGxhenlhcnJbaW5kXT0wOwogICAgaWYgKHVwZD09MSkKICAgICAgICBhcnJbaW5kXS5maXJzdCs9YXJyW2luZF0uc2Vjb25kLCBhcnJbaW5kXS5zZWNvbmQ9MDsKICAgIGVsc2UKICAgICAgICBhcnJbaW5kXS5zZWNvbmQrPWFycltpbmRdLmZpcnN0LCBhcnJbaW5kXS5maXJzdD0wOwogICAgaWYgKGxvIT1oaSkKICAgICAgICBsYXp5YXJyWzIqaW5kKzFdPXVwZCwgbGF6eWFyclsyKmluZCsyXT11cGQ7Cn0KCnZvaWQgYnVpbGQobGwgaW5kLCBsbCBsbywgbGwgaGksIHZsbCAmdikKewogICAgaWYgKGxvPT1oaSkKICAgIHsKICAgICAgICBpZiAodltsb10+PTApIGFycltpbmRdLmZpcnN0PXZbbG9dLCBhcnJbaW5kXS5zZWNvbmQ9MDsKICAgICAgICBlbHNlIGFycltpbmRdLmZpcnN0PTAsIGFycltpbmRdLnNlY29uZD0tdltsb107CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgbGwgbWlkPShoaStsbykvMjsKICAgIGJ1aWxkKDIqaW5kKzEsbG8sbWlkLHYpOwogICAgYnVpbGQoMippbmQrMixtaWQrMSxoaSx2KTsKICAgIG1lcmdlKGluZCwyKmluZCsxLDIqaW5kKzIpOwp9Cgp2b2lkIHVwZGF0ZShsbCBpbmQsIGxsIGxvLCBsbCBoaSwgbGwgbCwgbGwgciwgbGwgZCkKewogICAgLy8gY2hlY2sgZm9yIHVwZGF0ZQogICAgdXBkYXRlX2xhenkoaW5kLGxvLGhpKTsKICAgIGlmIChsbz5yIHx8IGhpPGwpIHJldHVybjsKICAgIGVsc2UgaWYgKGxvPj1sICYmIGhpPD1yKQogICAgewogICAgICAgIGlmIChkPT0xKQogICAgICAgICAgICBhcnJbaW5kXS5maXJzdCs9YXJyW2luZF0uc2Vjb25kLCBhcnJbaW5kXS5zZWNvbmQ9MDsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGFycltpbmRdLnNlY29uZCs9YXJyW2luZF0uZmlyc3QsIGFycltpbmRdLmZpcnN0PTA7CiAgICAgICAgaWYgKGxvIT1oaSkKICAgICAgICAgICAgbGF6eWFyclsyKmluZCsxXT1kLCBsYXp5YXJyWzIqaW5kKzJdPWQ7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgbGwgbWlkPShoaStsbykvMjsKICAgICAgICB1cGRhdGUoMippbmQrMSxsbyxtaWQsbCxyLGQpOwogICAgICAgIHVwZGF0ZSgyKmluZCsyLG1pZCsxLGhpLGwscixkKTsKICAgICAgICBtZXJnZShpbmQsMippbmQrMSwyKmluZCsyKTsKICAgIH0KfQoKbGwgcXVlcnkobGwgaW5kLCBsbCBsbywgbGwgaGksIGxsIGwsIGxsIHIpCnsKICAgIC8vIGNoZWNrIGZvciB1cGRhdGUKICAgIHVwZGF0ZV9sYXp5KGluZCxsbyxoaSk7CiAgICBpZiAobG8+ciB8fCBoaTxsKSByZXR1cm4gMDsKICAgIGVsc2UgaWYgKGxvPj1sICYmIGhpPD1yKSByZXR1cm4gYXJyW2luZF0uZmlyc3QtYXJyW2luZF0uc2Vjb25kOwogICAgbGwgbWlkPShoaStsbykvMjsKICAgIGxsIGxlZnQ9cXVlcnkoMippbmQrMSxsbyxtaWQsbCxyKTsKICAgIGxsIHJpZ2h0PXF1ZXJ5KDIqaW5kKzIsbWlkKzEsaGksbCxyKTsKICAgIGxsIGFucz1sZWZ0K3JpZ2h0OwogICAgcmV0dXJuIGFuczsKfQoKdnBsbCBicnI7ICAvLyB7IGNvdW50IDAsIGNvdW50IDF9CnZsbCBsYXp5OwovLyAwIC0+IG5vIHVwZGF0ZV9jb2xvcgovLyAxIC0+IGZvcmNlIDAKLy8gMiAtPiBmb3JjZSAxCgp2b2lkIG1lcmdlX2NvbG9yKGxsIGluZCwgbGwgbGVmdCwgbGwgcmlnaHQpCnsKICAgIGJycltpbmRdPWJycltsZWZ0XTsKICAgIGJycltpbmRdLmZpcnN0Kz1icnJbcmlnaHRdLmZpcnN0OwogICAgYnJyW2luZF0uc2Vjb25kKz1icnJbcmlnaHRdLnNlY29uZDsKfQoKdm9pZCB1cGRhdGVfbGF6eV9jb2xvcihsbCBpbmQsIGxsIGxvLCBsbCBoaSkKewogICAgaWYgKGxhenlbaW5kXT09MCkgcmV0dXJuOwogICAgbGwgZWxlbT1oaS1sbysxOwogICAgbGwgdXBkPWxhenlbaW5kXTsKICAgIGlmIChsYXp5W2luZF09PTEpIGJycltpbmRdPXtlbGVtLDB9OwogICAgZWxzZSBicnJbaW5kXT17MCxlbGVtfTsKICAgIGxhenlbaW5kXT0wOwogICAgaWYgKGxvIT1oaSkgbGF6eVsyKmluZCsxXT11cGQsIGxhenlbMippbmQrMl09dXBkOwp9Cgp2b2lkIGJ1aWxkX2NvbG9yKGxsIGluZCwgbGwgbG8sIGxsIGhpLCB2bGwgJnYpCnsKICAgIGlmIChsbz09aGkpCiAgICB7CiAgICAgICAgaWYgKHZbbG9dPT0wKSBicnJbaW5kXT17MSwwfTsKICAgICAgICBlbHNlIGJycltpbmRdPXswLDF9OwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGxsIG1pZD0oaGkrbG8pLzI7CiAgICBidWlsZF9jb2xvcigyKmluZCsxLGxvLG1pZCx2KTsKICAgIGJ1aWxkX2NvbG9yKDIqaW5kKzIsbWlkKzEsaGksdik7CiAgICBtZXJnZV9jb2xvcihpbmQsMippbmQrMSwyKmluZCsyKTsKfQoKdm9pZCB1cGRhdGVfY29sb3IobGwgaW5kLCBsbCBsbywgbGwgaGksIGxsIGwsIGxsIHIsIGxsIHgpCnsKICAgIC8vIGNoZWNrIHVwZGF0ZV9jb2xvciBpbiBsYXp5CiAgICB1cGRhdGVfbGF6eV9jb2xvcihpbmQsbG8saGkpOwogICAgaWYgKGxvPnIgfHwgaGk8bCkgcmV0dXJuOwogICAgZWxzZSBpZiAobG8+PWwgJiYgaGk8PXIpCiAgICB7CiAgICAgICAgbGwgZWxlbT1oaS1sbysxOwogICAgICAgIGlmICh4PT0xKSBicnJbaW5kXT17ZWxlbSwwfTsKICAgICAgICBlbHNlIGJycltpbmRdPXswLGVsZW19OwogICAgICAgIGlmIChsbyE9aGkpIGxhenlbMippbmQrMV09eCwgbGF6eVsyKmluZCsyXT14OwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGxsIG1pZD0oaGkrbG8pLzI7CiAgICAgICAgdXBkYXRlX2NvbG9yKDIqaW5kKzEsbG8sbWlkLGwscix4KTsKICAgICAgICB1cGRhdGVfY29sb3IoMippbmQrMixtaWQrMSxoaSxsLHIseCk7CiAgICAgICAgbWVyZ2VfY29sb3IoaW5kLDIqaW5kKzEsMippbmQrMik7CiAgICB9Cn0KCmxsIHF1ZXJ5X2NvbG9yKGxsIGluZCwgbGwgbG8sIGxsIGhpLCBsbCBsLCBsbCByKQp7CiAgICAvLyBjaGVjayB1cGRhdGVfY29sb3IgaW4gbGF6eQogICAgdXBkYXRlX2xhenlfY29sb3IoaW5kLGxvLGhpKTsKICAgIGlmIChsbz5yIHx8IGhpPGwpIHJldHVybiAwOwogICAgZWxzZSBpZiAobG8+PWwgJiYgaGk8PXIpIHJldHVybiBicnJbaW5kXS5zZWNvbmQ7CiAgICBsbCBtaWQ9KGhpK2xvKS8yOwogICAgbGwgbGVmdD1xdWVyeV9jb2xvcigyKmluZCsxLGxvLG1pZCxsLHIpOwogICAgbGwgcmlnaHQ9cXVlcnlfY29sb3IoMippbmQrMixtaWQrMSxoaSxsLHIpOwogICAgbGwgYW5zPWxlZnQrcmlnaHQ7CiAgICByZXR1cm4gYW5zOwp9CgoKbGwgZ2V0X3RoZV92YWx1ZV9jb2xvcihpbnQgeCxpbnQgeSl7CiAgICBsbCBzdW0gPSAwOwogICAgd2hpbGUoaGVhZFt4XSAhPSBoZWFkW3ldKXsKICAgICAgICBpZihkZXB0aFtoZWFkW3hdXSA8IGRlcHRoW2hlYWRbeV1dKSBzd2FwKHgseSk7CiAgICAgICAgbGwgdmFsdWUgPSBxdWVyeV9jb2xvcigwLDAsbi0xLHBvc1toZWFkW3hdXSwgcG9zW3hdKTsKICAgICAgICBzdW0gKz0gdmFsdWU7CiAgICAgICAgeCA9IHBhcmVudFtoZWFkW3hdXTsKICAgIH0gICAgCiAgICBpZihkZXB0aFt4XSA8IGRlcHRoW3ldKSBzd2FwKHgseSk7CiAgICBsbCB2YWx1ZSA9IHF1ZXJ5X2NvbG9yKDAsMCxuLTEscG9zW3ldLHBvc1t4XSk7CiAgICBpZihwb3NbeF0gPj0gcG9zW3ldKSBzdW0gKz0gdmFsdWU7CiAgICByZXR1cm4gc3VtOwp9CgoKdm9pZCB1cGRhdGVfdGhlX2NvbG9yKGludCB4LGludCB5LGludCBjb2xvcil7CiAgICB3aGlsZShoZWFkW3hdICE9IGhlYWRbeV0pewogICAgICAgIGlmKGRlcHRoW2hlYWRbeF1dIDwgZGVwdGhbaGVhZFt5XV0pIHN3YXAoeCx5KTsKICAgICAgICB1cGRhdGVfY29sb3IoMCwwLG4tMSxwb3NbaGVhZFt4XV0scG9zW3hdLGNvbG9yKTsKICAgICAgICB4ID0gcGFyZW50W2hlYWRbeF1dOwogICAgfSAgICAKICAgIGlmKGRlcHRoW3hdIDwgZGVwdGhbeV0pIHN3YXAoeCx5KTsKICAgIGlmKHBvc1t4XSA+PSBwb3NbeV0gKXVwZGF0ZV9jb2xvcigwLDAsbi0xLHBvc1t5XSxwb3NbeF0sY29sb3IpOwp9Cgp2b2lkIHVwZGF0ZV90aGVfdmFsdWUoaW50IHgsaW50IHksaW50IHNpZ24pewogICAgd2hpbGUoaGVhZFt4XSAhPSBoZWFkW3ldKXsKICAgICAgICBpZihkZXB0aFtoZWFkW3hdXSA8IGRlcHRoW2hlYWRbeV1dKSBzd2FwKHgseSk7CiAgICAgICAgdXBkYXRlKDAsMCxuLTEscG9zW2hlYWRbeF1dLHBvc1t4XSxzaWduKTsKICAgICAgICB4ID0gcGFyZW50W2hlYWRbeF1dOwogICAgfSAgICAKICAgIGlmKGRlcHRoW3hdIDwgZGVwdGhbeV0pIHN3YXAoeCx5KTsKICAgIGlmKHBvc1t4XSA+PSBwb3NbeV0gKXVwZGF0ZSgwLDAsbi0xLHBvc1t5XSxwb3NbeF0sc2lnbik7Cn0KCgpsbCBnZXRfdGhlX3ZhbHVlKGludCB4LGludCB5KXsKICAgICBsbCBzdW0gPSAwOwogICAgd2hpbGUoaGVhZFt4XSAhPSBoZWFkW3ldKXsKICAgICAgICBpZihkZXB0aFtoZWFkW3hdXSA8IGRlcHRoW2hlYWRbeV1dKSBzd2FwKHgseSk7CiAgICAgICAgbGwgdmFsdWUgPSAgcXVlcnkoMCwwLG4tMSxwb3NbaGVhZFt4XV0scG9zW3hdKTsKICAgICAgICBzdW0gKz0gdmFsdWU7CiAgICAgICAgeCA9IHBhcmVudFtoZWFkW3hdXTsKICAgIH0gICAgCiAgICBpZihkZXB0aFt4XSA8IGRlcHRoW3ldKSBzd2FwKHgseSk7CiAgICBsbCB2YWx1ZSA9IHF1ZXJ5KDAsMCxuLTEscG9zW3ldLHBvc1t4XSk7CiAgICBpZihwb3NbeF0gPj0gcG9zW3ldKSBzdW0gKz0gdmFsdWU7CiAgICByZXR1cm4gc3VtOwp9Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBOb2RlLCB0eXBlbmFtZSBVcGRhdGU+CnN0cnVjdCBTZWdUcmVlIHsKICAgIHZlY3RvcjxOb2RlPiB0cmVlOwogICAgdmVjdG9yPGxsPiBhcnI7IC8vIHR5cGUgbWF5IGNoYW5nZQogICAgaW50IG47CiAgICBpbnQgczsKICAgIFNlZ1RyZWUoaW50IGFfbGVuLCB2ZWN0b3I8bGw+ICZhKSB7IC8vIGNoYW5nZSBpZiB0eXBlIHVwZGF0ZWQKICAgICAgICBhcnIgPSBhOwogICAgICAgIG4gPSBhX2xlbjsKICAgICAgICBzID0gMTsKICAgICAgICB3aGlsZShzIDwgMiAqIG4pewogICAgICAgICAgICBzID0gcyA8PCAxOwogICAgICAgIH0KICAgICAgICB0cmVlLnJlc2l6ZShzKTsgZmlsbChhbGwodHJlZSksIE5vZGUoKSk7CiAgICAgICAgYnVpbGQoMCwgbiAtIDEsIDEpOwogICAgfQogICAgdm9pZCBidWlsZChpbnQgc3RhcnQsIGludCBlbmQsIGludCBpbmRleCkgIC8vIE5ldmVyIGNoYW5nZSB0aGlzCiAgICB7CiAgICAgICAgaWYgKHN0YXJ0ID09IGVuZCkgICB7CiAgICAgICAgICAgIHRyZWVbaW5kZXhdID0gTm9kZShhcnJbc3RhcnRdKTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBpbnQgbWlkID0gKHN0YXJ0ICsgZW5kKSAvIDI7CiAgICAgICAgYnVpbGQoc3RhcnQsIG1pZCwgMiAqIGluZGV4KTsKICAgICAgICBidWlsZChtaWQgKyAxLCBlbmQsIDIgKiBpbmRleCArIDEpOwogICAgICAgIHRyZWVbaW5kZXhdLm1lcmdlKHRyZWVbMiAqIGluZGV4XSwgdHJlZVsyICogaW5kZXggKyAxXSk7CiAgICB9CiAgICB2b2lkIHVwZGF0ZShpbnQgc3RhcnQsIGludCBlbmQsIGludCBpbmRleCwgaW50IHF1ZXJ5X2luZGV4LCBVcGRhdGUgJnUpICAvLyBOZXZlciBDaGFuZ2UgdGhpcwogICAgewogICAgICAgIGlmIChzdGFydCA9PSBlbmQpIHsKICAgICAgICAgICAgdS5hcHBseSh0cmVlW2luZGV4XSk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IG1pZCA9IChzdGFydCArIGVuZCkgLyAyOwogICAgICAgIGlmIChtaWQgPj0gcXVlcnlfaW5kZXgpCiAgICAgICAgICAgIHVwZGF0ZShzdGFydCwgbWlkLCAyICogaW5kZXgsIHF1ZXJ5X2luZGV4LCB1KTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIHVwZGF0ZShtaWQgKyAxLCBlbmQsIDIgKiBpbmRleCArIDEsIHF1ZXJ5X2luZGV4LCB1KTsKICAgICAgICB0cmVlW2luZGV4XS5tZXJnZSh0cmVlWzIgKiBpbmRleF0sIHRyZWVbMiAqIGluZGV4ICsgMV0pOwogICAgfQogICAgTm9kZSBxdWVyeShpbnQgc3RhcnQsIGludCBlbmQsIGludCBpbmRleCwgaW50IGxlZnQsIGludCByaWdodCkgeyAvLyBOZXZlciBjaGFuZ2UgdGhpcwogICAgICAgIGlmIChzdGFydCA+IHJpZ2h0IHx8IGVuZCA8IGxlZnQpCiAgICAgICAgICAgIHJldHVybiBOb2RlKCk7CiAgICAgICAgaWYgKHN0YXJ0ID49IGxlZnQgJiYgZW5kIDw9IHJpZ2h0KQogICAgICAgICAgICByZXR1cm4gdHJlZVtpbmRleF07CiAgICAgICAgaW50IG1pZCA9IChzdGFydCArIGVuZCkgLyAyOwogICAgICAgIE5vZGUgbCwgciwgYW5zOwogICAgICAgIGwgPSBxdWVyeShzdGFydCwgbWlkLCAyICogaW5kZXgsIGxlZnQsIHJpZ2h0KTsKICAgICAgICByID0gcXVlcnkobWlkICsgMSwgZW5kLCAyICogaW5kZXggKyAxLCBsZWZ0LCByaWdodCk7CiAgICAgICAgYW5zLm1lcmdlKGwsIHIpOwogICAgICAgIHJldHVybiBhbnM7CiAgICB9CiAgICB2b2lkIG1ha2VfdXBkYXRlKGludCBpbmRleCwgbGwgdmFsKSB7ICAvLyBwYXNzIGluIGFzIG1hbnkgcGFyYW1ldGVycyBhcyByZXF1aXJlZAogICAgICAgIFVwZGF0ZSBuZXdfdXBkYXRlID0gVXBkYXRlKHZhbCk7IC8vIG1heSBjaGFuZ2UKICAgICAgICB1cGRhdGUoMCwgbiAtIDEsIDEsIGluZGV4LCBuZXdfdXBkYXRlKTsKICAgIH0KICAgIE5vZGUgbWFrZV9xdWVyeShpbnQgbGVmdCwgaW50IHJpZ2h0KSB7CiAgICAgICAgcmV0dXJuIHF1ZXJ5KDAsIG4gLSAxLCAxLCBsZWZ0LCByaWdodCk7CiAgICB9Cn07CgovLyBhbGwgcG9zaXRpdmUKCgpzdHJ1Y3QgTm9kZTEgewogICAgbGwgdmFsOyAvLyBtYXkgY2hhbmdlCiAgICBOb2RlMSgpIHsgLy8gSWRlbnRpdHkgZWxlbWVudAogICAgICAgIHZhbCA9IDA7ICAgIC8vIG1heSBjaGFuZ2UKICAgIH0KICAgIE5vZGUxKGxsIHAxKSB7ICAvLyBBY3R1YWwgTm9kZQogICAgICAgIHZhbCA9IHAxOyAvLyBtYXkgY2hhbmdlCiAgICB9CiAgICB2b2lkIG1lcmdlKE5vZGUxICZsLCBOb2RlMSAmcikgeyAvLyBNZXJnZSB0d28gY2hpbGQgbm9kZXMKICAgICAgICB2YWwgPSBsLnZhbCArIHIudmFsOyAgLy8gbWF5IGNoYW5nZQogICAgfQp9OwoKc3RydWN0IFVwZGF0ZTEgewogICAgbGwgdmFsOyAvLyBtYXkgY2hhbmdlCiAgICBVcGRhdGUxKGxsIHAxKSB7IC8vIEFjdHVhbCBVcGRhdGUKICAgICAgICB2YWwgPSBwMTsgLy8gbWF5IGNoYW5nZQogICAgfQogICAgdm9pZCBhcHBseShOb2RlMSAmYSkgeyAvLyBhcHBseSB1cGRhdGUgdG8gZ2l2ZW4gbm9kZQogICAgICAgIGEudmFsID0gdmFsOyAvLyBtYXkgY2hhbmdlCiAgICB9Cn07CgoKdm9pZCBzb2x2ZSgpIHsKICAgY2luPj5uPj5xOwogICAgYXNzZXJ0KG4gPj0gMSBhbmQgbiA8PSAxMDAwMDApOwogICAgYXNzZXJ0KHEgPj0gMSBhbmQgcSA8PSAxMDAwMDApOwogICAgY29sb3IucmVzaXplKG4gKyAxKTsgdmFsdWUucmVzaXplKG4gKyAxKTsgCiAgICBmb3IoaW50IGkgPSAwOyBpPCBuOyBpKyspIGNvbG9yW2ldID0gMDsKICAgIGFyci5jbGVhcigpOyBsYXp5YXJyLmNsZWFyKCk7IGFyci5yZXNpemUoNCpuKzEpOyBsYXp5YXJyLnJlc2l6ZSg0Km4rMSwwKTsKICAgIGJyci5jbGVhcigpOyBsYXp5LmNsZWFyKCk7IGJyci5yZXNpemUoNCpuKzEpOyBsYXp5LnJlc2l6ZSg0Km4rMSwwKTsKICAgIHZlY3RvcjxsbD4gYWRqW24gKyAxXTsKICAgIGZvcihpbnQgaSA9IDA7IGk8IG4tMTsgaSsrKXsKICAgICAgICBsbCB4LHk7IGNpbj4+eD4+eTsKICAgICAgICBhc3NlcnQoeCA+PSAxIGFuZCB4IDw9IG4pOyBhc3NlcnQoeSA+PSAxIGFuZCB5IDw9IG4pOwogICAgICAgIGFkalt4XS5wdXNoX2JhY2soeSk7CiAgICAgICAgYWRqW3ldLnBiKHgpOwogICAgfQogICAgZm9yKGludCBpID0gMTsgaTw9IG47IGkrKykgY2luPj52YWx1ZVtpXTsKICAgIHBhcmVudC5yZXNpemUobiArIDEpOyAgZGVwdGgucmVzaXplKG4gKyAxKTsgc3VidHJlZV9zaXplLnJlc2l6ZShuICsgMSk7IGhlYXZ5LnJlc2l6ZShuICsgMSk7IGhlYWQucmVzaXplKG4gKyAxKTsKICAgIGx0LnJlc2l6ZShuICsgMSk7IHBvcy5yZXNpemUobiArIDEpOyBwb3Nfb3V0LnJlc2l6ZShuICsgMSk7IAogICAgZGZzKDEsMCxhZGosMCk7IC8vIG1haW4gZGZzIGNhbGxpbmcKICAgIGRmc0hMRCgxLGFkaiwxKTsgLy8gaGxkIGRmcyBjYWxsaW5nCiAgICBhdXRvIGx0MSA9IGx0OyAvLyBkZWNvbXBvc2VkIGFycmF5IGFmdGVyIEhMRAogICAgYnVpbGQoMCwwLG4tMSxsdCk7IC8vIHNlZ21lbnQgdHJlZSBmb3IgdGhlIG1peCBvZiBibGFjayBhbmQgd2hpdGUgbm9kZSB2YWx1ZXMKICAgIGJ1aWxkX2NvbG9yKDAsMCxuLTEsY29sb3IpOyAvLyBzZWdtZW50IHRyZWUgZm9yIHNhdmluZyB0aGUgY29sb3Igd2hpdGUgYW5kIGJsYWNrIG5vZGVzCiAgICBTZWdUcmVlPE5vZGUxLFVwZGF0ZTE+IHNnID0gU2VnVHJlZTxOb2RlMSxVcGRhdGUxPiAobixsdDEpOyAvLyBzZWdtZW50IHRyZWUgc3RvcmluZyBhbGwgdGhlIG9yaWdpbmFsIHZhbHVlcwogICAgLy9hbGwgbm9kZXMgYXJlIGNvbnNpZGVyZWQgcG9zaXRpdmUgbWVhbnMgYWxsIG5vZGVzIGFyZSBibGFjayBmaXJzdAogICAgdXBkYXRlKDAsMCxuLTEsMCxuLTEsLTEpOyAvLyBjb2xvcmluZyBhbGwgdGhlIG5vZGUgd2hpdGUgZmlyc3QKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspewogICAgICAgIGludCBxVHlwZTsgY2luPj5xVHlwZTsKICAgICAgICBhc3NlcnQocVR5cGUgPj0gMSBhbmQgcVR5cGUgPD0gMyk7CiAgICAgICAgaWYocVR5cGUgPT0gMSl7CiAgICAgICAgICAgIGxsIHgseSA7Y2luPj54Pj55OwogICAgICAgICAgICBhc3NlcnQoeCA+PSAxIGFuZCB4IDw9IG4pOwogICAgICAgICAgICBhc3NlcnQoeSA+PSAxIGFuZCB5IDw9IG4pOwogICAgICAgICAgICBsbCBsY2Ffbm9kZSA9IGxjYSh4LHkpOwogICAgICAgICAgICBsbCBwYXRoX2Rpc3QgPSBhYnMoZGVwdGhbbGNhX25vZGVdIC0gZGVwdGhbeF0pICsgYWJzKGRlcHRoW2xjYV9ub2RlXSAtIGRlcHRoW3ldKSArIDE7CiAgICAgICAgICAgIGxsIGJsYWNrX25vZGVzID0gZ2V0X3RoZV92YWx1ZV9jb2xvcih4LHkpOwogICAgICAgICAgICBsbCB3aGl0ZV9ub2RlcyA9IHBhdGhfZGlzdCAtIGJsYWNrX25vZGVzOwogICAgICAgICAgICBpZihibGFja19ub2RlcyA+IHdoaXRlX25vZGVzKXsKICAgICAgICAgICAgICAgIHVwZGF0ZV90aGVfY29sb3IoeCx5LDIpOwogICAgICAgICAgICAgICAgdXBkYXRlX3RoZV92YWx1ZSh4LHksMSk7CiAgICAgICAgICAgIH1lbHNlIGlmKGJsYWNrX25vZGVzIDwgd2hpdGVfbm9kZXMpewogICAgICAgICAgICAgICAgdXBkYXRlX3RoZV9jb2xvcih4LHksMSk7CiAgICAgICAgICAgICAgICB1cGRhdGVfdGhlX3ZhbHVlKHgseSwtMSk7CiAgICAgICAgICAgIH0KICAgICAgICB9ZWxzZSBpZihxVHlwZSA9PSAyKXsKICAgICAgICAgICAgICAgIGxsIHg7IGNpbj4+eDsKICAgICAgICAgICAgICAgIGFzc2VydCh4ID49IDEgYW5kIHggPD0gbik7CiAgICAgICAgICAgICAgICB1cGRhdGVfY29sb3IoMCwwLG4tMSxwb3NbeF0sIHBvc19vdXRbeF0gLSAxLDIpOyAvLyBjaGFuZ2luZyB0aGUgY29sb3Igb2YgdGhlIHN1YnRyZWUKICAgICAgICAgICAgICAgIHVwZGF0ZSgwLDAsbi0xLHBvc1t4XSwgcG9zX291dFt4XSAtIDEsMSk7IC8vIGNoYW5nZSB0aGUgc3VidHJlZSB3aXRoIHBvc2l0aXZlIHZhbHVlcyBtZWFucyBibGFjayBub2RlcwogICAgICAgIH1lbHNlewogICAgICAgICAgICAgICAgbGwgYSxiIDtjaW4+PmE+PmI7CiAgICAgICAgICAgICAgICBhc3NlcnQoYSA+PSAxIGFuZCBhIDw9IG4pOwogICAgICAgICAgICAgICAgYXNzZXJ0KGIgPj0gMSBhbmQgYiA8PSBuKTsKICAgICAgICAgICAgICAgIGxsIHgseTsgeCA9IGE7IHkgPSBiOwogICAgICAgICAgICAgICAgbGwgdG90YWxfdmFsdWUgPSAwOwogICAgICAgICAgICAgICAgd2hpbGUoaGVhZFt4XSAhPSBoZWFkW3ldKXsKICAgICAgICAgICAgICAgICAgICBpZihkZXB0aFtoZWFkW3hdXSA8IGRlcHRoW2hlYWRbeV1dKSBzd2FwKHgseSk7CiAgICAgICAgICAgICAgICAgICAgdG90YWxfdmFsdWUgKz0gc2cubWFrZV9xdWVyeShwb3NbaGVhZFt4XV0scG9zW3hdKS52YWw7CiAgICAgICAgICAgICAgICAgICAgeCA9IHBhcmVudFtoZWFkW3hdXTsKICAgICAgICAgICAgICAgIH0gICAgCiAgICAgICAgICAgICAgICBpZihkZXB0aFt4XSA8IGRlcHRoW3ldKSBzd2FwKHgseSk7CiAgICAgICAgICAgICAgICBpZihwb3NbeF0gPj0gcG9zW3ldKSB0b3RhbF92YWx1ZSArPSBzZy5tYWtlX3F1ZXJ5KHBvc1t5XSxwb3NbeF0pLnZhbDsKICAgICAgICAgICAgICAgIC8vIHRvdGFsX3ZhbHVlIC0tPiBnZXR0aW5nIHRoZSBvcmlnaW5hbCB2YWx1ZXMgY29uc2lkZXJlZCBhbGwgbm9kZXMgYXJlIGJsYWNrCiAgICAgICAgICAgICAgICBsbCBwYXRoX3ZhbHVlID0gZ2V0X3RoZV92YWx1ZShhLGIpOyAvLyBnZXR0aW5nIHRoZSB2YWx1ZXMgd2hlcmUgYm90aCBwb3NpdGl2ZSBhbmQgbmVnYXRpdmUgdmFsdWVzIGFyZSB0aGVyZQogICAgICAgICAgICAgICAgbGwgYmxhY2tfdmFsdWUgPSAodG90YWxfdmFsdWUgKyBwYXRoX3ZhbHVlKSAvIDI7CiAgICAgICAgICAgICAgICBsbCB3aGl0ZV92YWx1ZSA9ICh0b3RhbF92YWx1ZSAtIHBhdGhfdmFsdWUpIC8gMjsKICAgICAgICAgICAgICAgIGNvdXQ8PG1heCh3aGl0ZV92YWx1ZSxibGFja192YWx1ZSk8PGVuZGw7CiAgICAgICAgfSAgICAgICAgCiAgICB9Cn0KIAppbnQgbWFpbigpCiB7CiAgICAgSU9TOwogCiAjaWZuZGVmIE9OTElORV9KVURHRQogICAgIGZyZW9wZW4oImVycm9yLnR4dCIsICJ3Iiwgc3RkZXJyKTsKICNlbmRpZgogICAgIGludCB0ZXN0ID0gMTsKICAgICAvLyBjaW4gPj4gdGVzdDsKICAgICBmb3IgKGludCBpID0gMTsgaSA8PSB0ZXN0OyBpKyspIHsKICAgICAgICAgLy8gY291dCA8PCAiQ2FzZSAiIDw8IGkgPDwgIjogIjw8ZW5kbDsKICAgICAgICBzb2x2ZSgpOwogICAgIH0KICAgICByZXR1cm4gMDsKIH0K