#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define int long long
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).begin(); ++i)
#define ALL(x) (x).begin(), (x).begin()
#define SZ(x) ((int)(x).size())
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define left ____left
#define hash ____hash
#define exchange dupa
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;
template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
const int N = 2e5 + 5;
VPII slo[N];
int dp[N][4]; // dp[v][c] - najwiekszy zysk jaki mozna uzyskac w poddrzewie v majac niedokonczona sciezke w dol o dlugosci c
int vis[N];
const int kInf = 1e12;
int from_to[4][4];
typedef array<int, 4> A;
set<PII> exchange[4][4];
set<PII> merged02[4][4];
void Dfs(int v) {
vis[v] = 1;
vector<A> sons;
for (auto e : slo[v]) {
int nei = e.st;
int cost = e.nd;
if (vis[nei]) { continue; }
Dfs(nei);
A son;
REP (c, 4) {
son[c] = cost + dp[nei][(c + 3) % 4];
}
maxi(son[0], dp[nei][0]);
sons.PB(son);
}
A B;
REP (tr, 4) {
B[tr] = -kInf / 2;
}
REP (artificial, 4) {
int best = -kInf;
sons.PB(B);
sons.back()[artificial] = 0;
//debug(v, artificial, sons);
REP (x, 4) {
REP (y, 4) {
exchange[x][y].clear();
merged02[x][y].clear();
}
}
int score = 0;
int parity = 0;
VI where(SZ(sons), -1);
function<void(int)> Del = [&](int who) {
int ind = where[who];
where[who] = -1;
auto& vec = sons[who];
score -= vec[ind];
if (ind == 2) { parity ^= 1; }
int i2 = ind;
if (ind == 2) { i2 = 0; }
REP (to, 4) {
if (to == ind) { continue; }
assert(exchange[ind][to].erase({vec[ind] - vec[to], who}));
int t2 = to;
if (to == 2) { t2 = 0; }
merged02[i2][t2].erase({vec[ind] - vec[to], who});
}
};
function<void(int, int)> Add = [&](int who, int ind) {
auto& vec = sons[who];
score += vec[ind];
assert(where[who] == -1);
where[who] = ind;
if (ind == 2) { parity ^= 1; }
int i2 = ind;
if (ind == 2) { i2 = 0; }
REP (to, 4) {
if (to == ind) { continue; }
exchange[ind][to].insert({vec[ind] - vec[to], who});
int t2 = to;
if (to == 2) { t2 = 0; }
merged02[i2][t2].insert({vec[ind] - vec[to], who});
}
};
function<void(int, int)> Move = [&](int who, int to) {
Del(who);
Add(who, to);
};
function<void()> UpdTable = [&]() {
REP (from, 4) {
REP (to, 4) {
if (from == to) { continue; }
if (exchange[from][to].empty()) {
from_to[from][to] = -kInf;
} else {
from_to[from][to] = -exchange[from][to].begin()->st;
}
}
}
};
REP (i, SZ(sons)) {
auto& vec = sons[i];
if (vec[0] > vec[2]) {
Add(i, 0);
} else {
Add(i, 2);
}
}
FOR (k, 0, SZ(sons) / 2) {
UpdTable();
if (parity == 0) {
maxi(best, score);
//debug(k, score);
} else {
int cand = -kInf;
maxi(cand, from_to[0][2]);
maxi(cand, from_to[2][0]);
maxi(cand, from_to[0][3] + from_to[3][1] + from_to[1][2]);
maxi(cand, from_to[0][1] + from_to[1][2]);
maxi(cand, from_to[2][1] + from_to[1][0]);
maxi(cand, from_to[2][1] + from_to[1][3] + from_to[3][0]);
maxi(cand, from_to[0][1] + from_to[1][3] + from_to[3][2]);
maxi(cand, from_to[2][3] + from_to[3][1] + from_to[1][0]);
maxi(cand, from_to[0][3] + from_to[3][2]);
maxi(cand, from_to[2][3] + from_to[3][0]);
maxi(best, cand + score);
assert(cand <= 0);
}
if (k == SZ(sons) / 2) { break; }
assert(SZ(merged02[0][1]) == SZ(sons) - 2 * k);
int c1 = -kInf;
int c11 = -kInf;
int c12 = -kInf;
PII best_to_1 = *merged02[0][1].begin();
PII best_to_3 = *merged02[0][3].begin();
if (best_to_1.nd != best_to_3.nd) {
c1 = -best_to_1.st - best_to_3.st;
} else {
c11 = -best_to_1.st - next(merged02[0][3].begin())->st;
c12 = -next(merged02[0][1].begin())->st - best_to_3.st;
}
int c2 = -kInf, c3 = -kInf;
if (k > 0) {
c2 = -merged02[0][1].begin()->st - next(merged02[0][1].begin())->st - merged02[1][3].begin()->st; // 1->3, 02->1, 02->1
c3 = -merged02[0][3].begin()->st - next(merged02[0][3].begin())->st - merged02[3][1].begin()->st; // 3->1, 02->3, 02->3
}
int M = max({c1, c11, c12, c2, c3});
if (c1 == M) {
Move(best_to_1.nd, 1);
Move(best_to_3.nd, 3);
} else if (c11 == M) {
Move(next(merged02[0][3].begin())->nd, 3);
Move(best_to_1.nd, 1);
} else if (c12 == M) {
Move(next(merged02[0][1].begin())->nd, 1);
Move(best_to_3.nd, 3);
} else if (c2 == M) {
Move(merged02[1][3].begin()->nd, 3);
Move(next(merged02[0][1].begin())->nd, 1);
Move(merged02[0][1].begin()->nd, 1);
} else {
assert(c3 == M);
Move(merged02[3][1].begin()->nd, 1);
Move(next(merged02[0][3].begin())->nd, 3);
Move(merged02[0][3].begin()->nd, 3);
}
}
dp[v][(4 - artificial) % 4] = best;
sons.pop_back();
}
//debug(v);
// REP (i, 4) {
// cerr<<dp[v][i]<<" ";
// }
// cerr<<endl;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
cin.tie(0);
//double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
//#define TEST
int n;
#ifdef TEST
n = 2e5;
int R = 1000000;
#else
cin>>n;
#endif
RE (i, n - 1) {
int a, b, c;
#ifndef TEST
cin>>a>>b>>c;
#else
a = i + 1;
b = 1 + rand() % i;
c = -R + rand() % (2 * R);
#endif
slo[a].PB({b, c});
slo[b].PB({a, c});
}
Dfs(1);
cout<<dp[1][0]<<endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIHN0IGZpcnN0CiNkZWZpbmUgbmQgc2Vjb25kCiNkZWZpbmUgcmQgdGhpcmQKI2RlZmluZSBGT1IoaSwgYSwgYikgZm9yKGludCBpID0oYSk7IGkgPD0oYik7ICsraSkKI2RlZmluZSBSRShpLCBuKSBGT1IoaSwgMSwgbikKI2RlZmluZSBGT1JEKGksIGEsIGIpIGZvcihpbnQgaSA9IChhKTsgaSA+PSAoYik7IC0taSkKI2RlZmluZSBSRVAoaSwgbikgZm9yKGludCBpID0gMDtpIDwobik7ICsraSkKI2RlZmluZSBWQVIodiwgaSkgX190eXBlb2YoaSkgdj0oaSkKI2RlZmluZSBGT1JFKGksIGMpIGZvcihWQVIoaSwgKGMpLmJlZ2luKCkpOyBpICE9IChjKS5iZWdpbigpOyArK2kpCiNkZWZpbmUgQUxMKHgpICh4KS5iZWdpbigpLCAoeCkuYmVnaW4oKQojZGVmaW5lIFNaKHgpICgoaW50KSh4KS5zaXplKCkpCiNkZWZpbmUgX19idWlsdGluX2N0eiBfX2J1aWx0aW5fY3R6bGwKI2RlZmluZSBfX2J1aWx0aW5fY2x6IF9fYnVpbHRpbl9jbHpsbAojZGVmaW5lIF9fYnVpbHRpbl9wb3Bjb3VudCBfX2J1aWx0aW5fcG9wY291bnRsbAp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0ZW1wbGF0ZTx0eXBlbmFtZSBUSD4gdm9pZCBfZGJnKGNvbnN0IGNoYXIqIHNkYmcsIFRIIGgpIHsgY2Vycjw8c2RiZzw8Ij0iPDxoPDwiXG4iOyB9CnRlbXBsYXRlPHR5cGVuYW1lIFRILCB0eXBlbmFtZS4uLiBUQT4gdm9pZCBfZGJnKGNvbnN0IGNoYXIqIHNkYmcsIFRIIGgsIFRBLi4uIHQpIHsKICB3aGlsZSgqc2RiZyAhPSAnLCcpIHsgY2Vycjw8KnNkYmcrKzsgfSBjZXJyPDwiPSI8PGg8PCIsIjsgX2RiZyhzZGJnKzEsIHQuLi4pOwp9CiNpZmRlZiBMT0NBTAojZGVmaW5lIGRlYnVnKC4uLikgX2RiZygjX19WQV9BUkdTX18sIF9fVkFfQVJHU19fKQojZGVmaW5lIGRlYnVndih4KSB7e2NlcnIgPDwjeCA8PCIgPSAiOyBGT1JFKGl0dCwgKHgpKSBjZXJyIDw8Kml0dCA8PCIsICI7IGNlcnIgPDwiXG4iOyB9fQojZWxzZQojZGVmaW5lIGRlYnVnKC4uLikgKF9fVkFfQVJHU19fKQojZGVmaW5lIGRlYnVndih4KQojZGVmaW5lIGNlcnIgaWYoMCljb3V0CiNlbmRpZgojZGVmaW5lIGxlZnQgX19fX2xlZnQKI2RlZmluZSBoYXNoIF9fX19oYXNoCiNkZWZpbmUgZXhjaGFuZ2UgZHVwYQp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBsb25nIGRvdWJsZSBMRDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBQSUk7CnR5cGVkZWYgcGFpcjxsbCwgbGw+IFBMTDsKdHlwZWRlZiB2ZWN0b3I8aW50PiBWSTsKdHlwZWRlZiB2ZWN0b3I8Vkk+IFZWSTsKdHlwZWRlZiB2ZWN0b3I8bGw+IFZMTDsKdHlwZWRlZiB2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiBWUElJOwp0eXBlZGVmIHZlY3RvcjxwYWlyPGxsLCBsbD4gPiBWUExMOwoKdGVtcGxhdGU8Y2xhc3MgQz4gdm9pZCBtaW5pKEMmYTQsIEMgYjQpe2E0PW1pbihhNCwgYjQpOyB9CnRlbXBsYXRlPGNsYXNzIEM+IHZvaWQgbWF4aShDJmE0LCBDIGI0KXthND1tYXgoYTQsIGI0KTsgfQp0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDI+Cm9zdHJlYW0mIG9wZXJhdG9yPDwgKG9zdHJlYW0gJm91dCwgcGFpcjxUMSwgVDI+IHBhaXIpIHsgcmV0dXJuIG91dCA8PCAiKCIgPDwgcGFpci5maXJzdCA8PCAiLCAiIDw8IHBhaXIuc2Vjb25kIDw8ICIpIjt9CnRlbXBsYXRlPGNsYXNzIEEsIGNsYXNzIEIsIGNsYXNzIEM+IHN0cnVjdCBUcmlwbGUgeyBBIGZpcnN0OyBCIHNlY29uZDsgQyB0aGlyZDsKICBib29sIG9wZXJhdG9yPChjb25zdCBUcmlwbGUmIHQpIGNvbnN0IHsgaWYgKHN0ICE9IHQuc3QpIHJldHVybiBzdCA8IHQuc3Q7IGlmIChuZCAhPSB0Lm5kKSByZXR1cm4gbmQgPCB0Lm5kOyByZXR1cm4gcmQgPCB0LnJkOyB9IH07CnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgUmVzaXplVmVjKFQmLCB2ZWN0b3I8aW50Pikge30KdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBSZXNpemVWZWModmVjdG9yPFQ+JiB2ZWMsIHZlY3RvcjxpbnQ+IHN6KSB7CiAgdmVjLnJlc2l6ZShzelswXSk7IHN6LmVyYXNlKHN6LmJlZ2luKCkpOyBpZiAoc3ouZW1wdHkoKSkgeyByZXR1cm47IH0KICBmb3IgKFQmIHYgOiB2ZWMpIHsgUmVzaXplVmVjKHYsIHN6KTsgfQp9CnR5cGVkZWYgVHJpcGxlPGludCwgaW50LCBpbnQ+IFRJSUk7CnRlbXBsYXRlPGNsYXNzIEEsIGNsYXNzIEIsIGNsYXNzIEM+Cm9zdHJlYW0mIG9wZXJhdG9yPDwgKG9zdHJlYW0gJm91dCwgVHJpcGxlPEEsIEIsIEM+IHQpIHsgcmV0dXJuIG91dCA8PCAiKCIgPDwgdC5zdCA8PCAiLCAiIDw8IHQubmQgPDwgIiwgIiA8PCB0LnJkIDw8ICIpIjsgfQp0ZW1wbGF0ZTxjbGFzcyBUPiBvc3RyZWFtJiBvcGVyYXRvcjw8KG9zdHJlYW0mIG91dCwgdmVjdG9yPFQ+IHZlYykgeyBvdXQ8PCIoIjsgZm9yIChhdXRvJiB2OiB2ZWMpIG91dDw8djw8IiwgIjsgcmV0dXJuIG91dDw8IikiOyB9CnRlbXBsYXRlPGNsYXNzIFQ+IG9zdHJlYW0mIG9wZXJhdG9yPDwob3N0cmVhbSYgb3V0LCBzZXQ8VD4gdmVjKSB7IG91dDw8IigiOyBmb3IgKGF1dG8mIHY6IHZlYykgb3V0PDx2PDwiLCAiOyByZXR1cm4gb3V0PDwiKSI7IH0KdGVtcGxhdGU8Y2xhc3MgTCwgY2xhc3MgUj4gb3N0cmVhbSYgb3BlcmF0b3I8PChvc3RyZWFtJiBvdXQsIG1hcDxMLCBSPiB2ZWMpIHsgb3V0PDwiKCI7IGZvciAoYXV0byYgdjogdmVjKSBvdXQ8PHY8PCIsICI7IHJldHVybiBvdXQ8PCIpIjsgfQoKY29uc3QgaW50IE4gPSAyZTUgKyA1OwpWUElJIHNsb1tOXTsKaW50IGRwW05dWzRdOyAvLyBkcFt2XVtjXSAtIG5handpZWtzenkgenlzayBqYWtpIG1vem5hIHV6eXNrYWMgdyBwb2Rkcnpld2llIHYgbWFqYWMgbmllZG9rb25jem9uYSBzY2llemtlIHcgZG9sIG8gZGx1Z29zY2kgYwppbnQgdmlzW05dOwpjb25zdCBpbnQga0luZiA9IDFlMTI7CmludCBmcm9tX3RvWzRdWzRdOwp0eXBlZGVmIGFycmF5PGludCwgND4gQTsKc2V0PFBJST4gZXhjaGFuZ2VbNF1bNF07CnNldDxQSUk+IG1lcmdlZDAyWzRdWzRdOwp2b2lkIERmcyhpbnQgdikgewogIHZpc1t2XSA9IDE7CiAgdmVjdG9yPEE+IHNvbnM7CiAgZm9yIChhdXRvIGUgOiBzbG9bdl0pIHsKICAgIGludCBuZWkgPSBlLnN0OwogICAgaW50IGNvc3QgPSBlLm5kOwogICAgaWYgKHZpc1tuZWldKSB7IGNvbnRpbnVlOyB9CiAgICBEZnMobmVpKTsKICAgIEEgc29uOwogICAgUkVQIChjLCA0KSB7CiAgICAgIHNvbltjXSA9IGNvc3QgKyBkcFtuZWldWyhjICsgMykgJSA0XTsKICAgIH0KICAgIG1heGkoc29uWzBdLCBkcFtuZWldWzBdKTsKICAgIHNvbnMuUEIoc29uKTsKICB9CiAgQSBCOwogIFJFUCAodHIsIDQpIHsKICAgIEJbdHJdID0gLWtJbmYgLyAyOwogIH0KICBSRVAgKGFydGlmaWNpYWwsIDQpIHsKICAgIGludCBiZXN0ID0gLWtJbmY7CiAgICBzb25zLlBCKEIpOwogICAgc29ucy5iYWNrKClbYXJ0aWZpY2lhbF0gPSAwOwogICAgLy9kZWJ1Zyh2LCBhcnRpZmljaWFsLCBzb25zKTsKICAgIFJFUCAoeCwgNCkgewogICAgICBSRVAgKHksIDQpIHsKICAgICAgICBleGNoYW5nZVt4XVt5XS5jbGVhcigpOwogICAgICAgIG1lcmdlZDAyW3hdW3ldLmNsZWFyKCk7CiAgICAgIH0KICAgIH0KICAgIGludCBzY29yZSA9IDA7CiAgICBpbnQgcGFyaXR5ID0gMDsKICAgIFZJIHdoZXJlKFNaKHNvbnMpLCAtMSk7CiAgICBmdW5jdGlvbjx2b2lkKGludCk+IERlbCA9IFsmXShpbnQgd2hvKSB7CiAgICAgIGludCBpbmQgPSB3aGVyZVt3aG9dOwogICAgICB3aGVyZVt3aG9dID0gLTE7CiAgICAgIGF1dG8mIHZlYyA9IHNvbnNbd2hvXTsKICAgICAgc2NvcmUgLT0gdmVjW2luZF07CiAgICAgIGlmIChpbmQgPT0gMikgeyBwYXJpdHkgXj0gMTsgfQogICAgICBpbnQgaTIgPSBpbmQ7CiAgICAgIGlmIChpbmQgPT0gMikgeyBpMiA9IDA7IH0KICAgICAgUkVQICh0bywgNCkgewogICAgICAgIGlmICh0byA9PSBpbmQpIHsgY29udGludWU7IH0KICAgICAgICBhc3NlcnQoZXhjaGFuZ2VbaW5kXVt0b10uZXJhc2Uoe3ZlY1tpbmRdIC0gdmVjW3RvXSwgd2hvfSkpOwogICAgICAgIGludCB0MiA9IHRvOwogICAgICAgIGlmICh0byA9PSAyKSB7IHQyID0gMDsgfQogICAgICAgIG1lcmdlZDAyW2kyXVt0Ml0uZXJhc2Uoe3ZlY1tpbmRdIC0gdmVjW3RvXSwgd2hvfSk7CiAgICAgIH0KICAgIH07CiAgICBmdW5jdGlvbjx2b2lkKGludCwgaW50KT4gQWRkID0gWyZdKGludCB3aG8sIGludCBpbmQpIHsKICAgICAgYXV0byYgdmVjID0gc29uc1t3aG9dOwogICAgICBzY29yZSArPSB2ZWNbaW5kXTsKICAgICAgYXNzZXJ0KHdoZXJlW3dob10gPT0gLTEpOwogICAgICB3aGVyZVt3aG9dID0gaW5kOwogICAgICBpZiAoaW5kID09IDIpIHsgcGFyaXR5IF49IDE7IH0KICAgICAgaW50IGkyID0gaW5kOwogICAgICBpZiAoaW5kID09IDIpIHsgaTIgPSAwOyB9CiAgICAgIFJFUCAodG8sIDQpIHsKICAgICAgICBpZiAodG8gPT0gaW5kKSB7IGNvbnRpbnVlOyB9CiAgICAgICAgZXhjaGFuZ2VbaW5kXVt0b10uaW5zZXJ0KHt2ZWNbaW5kXSAtIHZlY1t0b10sIHdob30pOwogICAgICAgIGludCB0MiA9IHRvOwogICAgICAgIGlmICh0byA9PSAyKSB7IHQyID0gMDsgfQogICAgICAgIG1lcmdlZDAyW2kyXVt0Ml0uaW5zZXJ0KHt2ZWNbaW5kXSAtIHZlY1t0b10sIHdob30pOwogICAgICB9CiAgICB9OwogICAgZnVuY3Rpb248dm9pZChpbnQsIGludCk+IE1vdmUgPSBbJl0oaW50IHdobywgaW50IHRvKSB7CiAgICAgIERlbCh3aG8pOwogICAgICBBZGQod2hvLCB0byk7CiAgICB9OwogICAgZnVuY3Rpb248dm9pZCgpPiBVcGRUYWJsZSA9IFsmXSgpIHsKICAgICAgUkVQIChmcm9tLCA0KSB7CiAgICAgICAgUkVQICh0bywgNCkgewogICAgICAgICAgaWYgKGZyb20gPT0gdG8pIHsgY29udGludWU7IH0KICAgICAgICAgIGlmIChleGNoYW5nZVtmcm9tXVt0b10uZW1wdHkoKSkgewogICAgICAgICAgICBmcm9tX3RvW2Zyb21dW3RvXSA9IC1rSW5mOwogICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgZnJvbV90b1tmcm9tXVt0b10gPSAtZXhjaGFuZ2VbZnJvbV1bdG9dLmJlZ2luKCktPnN0OwogICAgICAgICAgfQogICAgICAgIH0KICAgICAgfQogICAgfTsKICAgIFJFUCAoaSwgU1ooc29ucykpIHsKICAgICAgYXV0byYgdmVjID0gc29uc1tpXTsKICAgICAgaWYgKHZlY1swXSA+IHZlY1syXSkgewogICAgICAgIEFkZChpLCAwKTsKICAgICAgfSBlbHNlIHsKICAgICAgICBBZGQoaSwgMik7CiAgICAgIH0KICAgIH0KICAgIEZPUiAoaywgMCwgU1ooc29ucykgLyAyKSB7CiAgICAgIFVwZFRhYmxlKCk7CiAgICAgIGlmIChwYXJpdHkgPT0gMCkgewogICAgICAgIG1heGkoYmVzdCwgc2NvcmUpOwogICAgICAgIC8vZGVidWcoaywgc2NvcmUpOwogICAgICB9IGVsc2UgewogICAgICAgIGludCBjYW5kID0gLWtJbmY7CiAgICAgICAgbWF4aShjYW5kLCBmcm9tX3RvWzBdWzJdKTsKICAgICAgICBtYXhpKGNhbmQsIGZyb21fdG9bMl1bMF0pOwogICAgICAgIG1heGkoY2FuZCwgZnJvbV90b1swXVszXSArIGZyb21fdG9bM11bMV0gKyBmcm9tX3RvWzFdWzJdKTsKICAgICAgICBtYXhpKGNhbmQsIGZyb21fdG9bMF1bMV0gKyBmcm9tX3RvWzFdWzJdKTsKICAgICAgICBtYXhpKGNhbmQsIGZyb21fdG9bMl1bMV0gKyBmcm9tX3RvWzFdWzBdKTsKICAgICAgICBtYXhpKGNhbmQsIGZyb21fdG9bMl1bMV0gKyBmcm9tX3RvWzFdWzNdICsgZnJvbV90b1szXVswXSk7CiAgICAgICAgbWF4aShjYW5kLCBmcm9tX3RvWzBdWzFdICsgZnJvbV90b1sxXVszXSArIGZyb21fdG9bM11bMl0pOwogICAgICAgIG1heGkoY2FuZCwgZnJvbV90b1syXVszXSArIGZyb21fdG9bM11bMV0gKyBmcm9tX3RvWzFdWzBdKTsKICAgICAgICBtYXhpKGNhbmQsIGZyb21fdG9bMF1bM10gKyBmcm9tX3RvWzNdWzJdKTsKICAgICAgICBtYXhpKGNhbmQsIGZyb21fdG9bMl1bM10gKyBmcm9tX3RvWzNdWzBdKTsKICAgICAgICBtYXhpKGJlc3QsIGNhbmQgKyBzY29yZSk7CiAgICAgICAgYXNzZXJ0KGNhbmQgPD0gMCk7CiAgICAgIH0KICAgICAgaWYgKGsgPT0gU1ooc29ucykgLyAyKSB7IGJyZWFrOyB9CiAgICAgIGFzc2VydChTWihtZXJnZWQwMlswXVsxXSkgPT0gU1ooc29ucykgLSAyICogayk7CiAgICAgIGludCBjMSA9IC1rSW5mOwogICAgICBpbnQgYzExID0gLWtJbmY7CiAgICAgIGludCBjMTIgPSAta0luZjsKICAgICAgUElJIGJlc3RfdG9fMSA9ICptZXJnZWQwMlswXVsxXS5iZWdpbigpOwogICAgICBQSUkgYmVzdF90b18zID0gKm1lcmdlZDAyWzBdWzNdLmJlZ2luKCk7CiAgICAgIGlmIChiZXN0X3RvXzEubmQgIT0gYmVzdF90b18zLm5kKSB7CiAgICAgICAgYzEgPSAtYmVzdF90b18xLnN0IC0gYmVzdF90b18zLnN0OwogICAgICB9IGVsc2UgewogICAgICAgIGMxMSA9IC1iZXN0X3RvXzEuc3QgLSBuZXh0KG1lcmdlZDAyWzBdWzNdLmJlZ2luKCkpLT5zdDsKICAgICAgICBjMTIgPSAtbmV4dChtZXJnZWQwMlswXVsxXS5iZWdpbigpKS0+c3QgLSBiZXN0X3RvXzMuc3Q7CiAgICAgIH0KICAgICAgaW50IGMyID0gLWtJbmYsIGMzID0gLWtJbmY7CiAgICAgIGlmIChrID4gMCkgewogICAgICAgIGMyID0gLW1lcmdlZDAyWzBdWzFdLmJlZ2luKCktPnN0IC0gbmV4dChtZXJnZWQwMlswXVsxXS5iZWdpbigpKS0+c3QgLSBtZXJnZWQwMlsxXVszXS5iZWdpbigpLT5zdDsgLy8gMS0+MywgMDItPjEsIDAyLT4xCiAgICAgICAgYzMgPSAtbWVyZ2VkMDJbMF1bM10uYmVnaW4oKS0+c3QgLSBuZXh0KG1lcmdlZDAyWzBdWzNdLmJlZ2luKCkpLT5zdCAtIG1lcmdlZDAyWzNdWzFdLmJlZ2luKCktPnN0OyAvLyAzLT4xLCAwMi0+MywgMDItPjMKICAgICAgfQogICAgICBpbnQgTSA9IG1heCh7YzEsIGMxMSwgYzEyLCBjMiwgYzN9KTsKICAgICAgaWYgKGMxID09IE0pIHsKICAgICAgICBNb3ZlKGJlc3RfdG9fMS5uZCwgMSk7CiAgICAgICAgTW92ZShiZXN0X3RvXzMubmQsIDMpOwogICAgICB9IGVsc2UgaWYgKGMxMSA9PSBNKSB7CiAgICAgICAgTW92ZShuZXh0KG1lcmdlZDAyWzBdWzNdLmJlZ2luKCkpLT5uZCwgMyk7CiAgICAgICAgTW92ZShiZXN0X3RvXzEubmQsIDEpOwogICAgICB9IGVsc2UgaWYgKGMxMiA9PSBNKSB7CiAgICAgICAgTW92ZShuZXh0KG1lcmdlZDAyWzBdWzFdLmJlZ2luKCkpLT5uZCwgMSk7CiAgICAgICAgTW92ZShiZXN0X3RvXzMubmQsIDMpOwogICAgICB9IGVsc2UgaWYgKGMyID09IE0pIHsKICAgICAgICBNb3ZlKG1lcmdlZDAyWzFdWzNdLmJlZ2luKCktPm5kLCAzKTsKICAgICAgICBNb3ZlKG5leHQobWVyZ2VkMDJbMF1bMV0uYmVnaW4oKSktPm5kLCAxKTsKICAgICAgICBNb3ZlKG1lcmdlZDAyWzBdWzFdLmJlZ2luKCktPm5kLCAxKTsKICAgICAgfSBlbHNlIHsKICAgICAgICBhc3NlcnQoYzMgPT0gTSk7CiAgICAgICAgTW92ZShtZXJnZWQwMlszXVsxXS5iZWdpbigpLT5uZCwgMSk7CiAgICAgICAgTW92ZShuZXh0KG1lcmdlZDAyWzBdWzNdLmJlZ2luKCkpLT5uZCwgMyk7CiAgICAgICAgTW92ZShtZXJnZWQwMlswXVszXS5iZWdpbigpLT5uZCwgMyk7CiAgICAgIH0KICAgIH0KICAgIGRwW3ZdWyg0IC0gYXJ0aWZpY2lhbCkgJSA0XSA9IGJlc3Q7CiAgICBzb25zLnBvcF9iYWNrKCk7CiAgfQogIC8vZGVidWcodik7Ci8vICAgUkVQIChpLCA0KSB7Ci8vICAgICBjZXJyPDxkcFt2XVtpXTw8IiAiOwovLyAgIH0KLy8gICBjZXJyPDxlbmRsOwp9CmludDMyX3QgbWFpbigpIHsKCiAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICBjb3V0IDw8IGZpeGVkIDw8IHNldHByZWNpc2lvbigxMCk7CiAgY2VyciA8PCBmaXhlZCA8PCBzZXRwcmVjaXNpb24oMTApOwogIGNpbi50aWUoMCk7CiAgLy9kb3VibGUgYmVnX2Nsb2NrID0gMS4wICogY2xvY2soKSAvIENMT0NLU19QRVJfU0VDOwovLyNkZWZpbmUgVEVTVAogIGludCBuOwojaWZkZWYgVEVTVAogIG4gPSAyZTU7CiAgaW50IFIgPSAxMDAwMDAwOwojZWxzZQogIGNpbj4+bjsKI2VuZGlmCiAgUkUgKGksIG4gLSAxKSB7CiAgICBpbnQgYSwgYiwgYzsKI2lmbmRlZiBURVNUCiAgICBjaW4+PmE+PmI+PmM7CiNlbHNlCiAgICBhID0gaSArIDE7CiAgICBiID0gMSArIHJhbmQoKSAlIGk7CiAgICBjID0gLVIgKyByYW5kKCkgJSAoMiAqIFIpOwojZW5kaWYKICAgIHNsb1thXS5QQih7YiwgY30pOwogICAgc2xvW2JdLlBCKHthLCBjfSk7CiAgfQogIERmcygxKTsKICBjb3V0PDxkcFsxXVswXTw8ZW5kbDsKICAKCiAgCiAgCiAgCiAgcmV0dXJuIDA7Cn0K