#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<db,db> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll half(ll x) { return fdiv(x,2); }
template<class T, class U> T fstTrue(T lo, T hi, U f) {
// note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
hi ++; assert(lo <= hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = half(lo+hi);
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U f) {
lo --; assert(lo <= hi); // assuming f is decreasing
while (lo < hi) { // find first index such that f is true
T mid = half(lo+hi+1);
f(mid) ? lo = mid : hi = mid-1;
}
return lo;
}
template<class T> void remDup(vector<T>& v) {
sort(all(v)); v.erase(unique(all(v)),end(v)); }
// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);
template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) {
#ifdef LOCAL
return b ? "true" : "false";
#else
return ts((int)b);
#endif
}
template<class A> str ts(complex<A> c) {
stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
str res = ""; F0R(i,SZ) res += char('0'+b[i]);
return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
#ifdef LOCAL
bool fst = 1; str res = "{";
for (const auto& x: v) {
if (!fst) res += ", ";
fst = 0; res += ts(x);
}
res += "}"; return res;
#else
bool fst = 1; str res = "";
for (const auto& x: v) {
if (!fst) res += " ";
fst = 0; res += ts(x);
}
return res;
#endif
}
template<class A, class B> str ts(pair<A,B> p) {
#ifdef LOCAL
return "("+ts(p.f)+", "+ts(p.s)+")";
#else
return ts(p.f)+" "+ts(p.s);
#endif
}
// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) {
pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) {
pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << ts(h); if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
<< __FUNCTION__ << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
#define dbg(...) 0
#define chk(...) 0
#endif
// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str s = "") {
unsyncIO();
// cin.exceptions(cin.failbit);
// throws exception when do smth illegal
// ex. try to read letter into int
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
#include "fun.h"
vi adj[MX];
int color[MX];
vpi vis;
void dfs(int a, int b, int d) {
vis.pb({d,a});
trav(t,adj[a]) if (t != b) dfs(t,a,d+1);
}
std::vector<int> createFunTour(int N, int Q) {
F0R(i,N) FOR(j,i+1,N) {
if (hoursRequired(i,j) == 1) {
adj[i].pb(j), adj[j].pb(i);
}
}
F0R(i,N) {
int maxSize = 0;
vector<vpi> tmp;
trav(t,adj[i]) {
vis.clear(); dfs(t,i,1);
ckmax(maxSize,sz(vis));
tmp.pb(vis);
}
if (2*maxSize > N) continue;
color[i] = -1;
F0R(_,sz(tmp)) trav(t,tmp[_]) color[t.s] = _;
trav(t,tmp) sort(rall(t));
vpi res{{0,i}};
int lef = N;
int col = -1, lst = -1;
while (1) {
lef --; if (lef == 0) break;
pi bes = {MOD,MOD};
if (lst == 1) {
F0R(_,sz(tmp)) if (_ != col) {
if (sz(tmp[_])) ckmin(bes,tmp[_].bk);
}
res.pb(bes); tmp[color[bes.s]].pop_back();
lst ^= 1;
} else if (lst == 0) {
F0R(_,sz(tmp)) if (_ == col) {
if (sz(tmp[_])) ckmin(bes,tmp[_].bk);
}
res.pb(bes); tmp[color[bes.s]].pop_back();
lst ^= 1;
} else {
maxSize = 0;
F0R(_,sz(tmp)) {
ckmax(maxSize,sz(tmp[_]));
if (sz(tmp[_]) && _ != color[res.bk.s]) ckmin(bes,tmp[_].bk);
}
if (2*maxSize > lef) {
trav(t,tmp) if (sz(t) == maxSize) {
bes = t.bk;
res.pb(bes);
col = color[bes.s];
tmp[color[bes.s]].pop_back();
}
lst = 1;
continue;
}
if (2*maxSize == lef) {
int big = 0; F0R(i,sz(tmp)) if (sz(tmp[i]) == maxSize) big = i;
pi x = tmp[big].bk, y = {MOD,MOD};
F0R(i,sz(tmp)) if (i != big && sz(tmp[i])) ckmin(y,tmp[i].bk);
pi one = res.bk, two = {-MOD,-MOD};
if (sz(res) > 1) two = res[sz(res)-2];
if (color[x.s] != color[res.bk.s] && x >= two && y >= one) {
res.pb(x); col = color[x.s]; lst = 1;
tmp[color[x.s]].pop_back();
continue;
}
if (color[y.s] != color[res.bk.s] && y >= two && x >= one) {
res.pb(y); col = color[x.s]; lst = 0;
tmp[color[y.s]].pop_back();
continue;
}
exit(5); // one of above two cases must hold
}
res.pb(bes); tmp[color[bes.s]].pop_back(); // just greedy
}
}
FOR(i,2,sz(res)) assert(res[i] >= res[i-2]);
FOR(i,1,sz(res)) assert(color[res[i].s] != color[res[i-1].s]);
reverse(all(res));
vi ans; trav(t,res) ans.pb(t.s);
return ans;
}
return {};
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7CnR5cGVkZWYgZG91YmxlIGRiOyAKdHlwZWRlZiBzdHJpbmcgc3RyOyAKCnR5cGVkZWYgcGFpcjxpbnQsaW50PiBwaTsKdHlwZWRlZiBwYWlyPGxsLGxsPiBwbDsgCnR5cGVkZWYgcGFpcjxkYixkYj4gcGQ7IAoKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsgCnR5cGVkZWYgdmVjdG9yPGJvb2w+IHZiOyAKdHlwZWRlZiB2ZWN0b3I8bGw+IHZsOyAKdHlwZWRlZiB2ZWN0b3I8ZGI+IHZkOyAKdHlwZWRlZiB2ZWN0b3I8c3RyPiB2czsgCnR5cGVkZWYgdmVjdG9yPHBpPiB2cGk7CnR5cGVkZWYgdmVjdG9yPHBsPiB2cGw7IAp0eXBlZGVmIHZlY3RvcjxwZD4gdnBkOyAKCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgZiBmaXJzdAojZGVmaW5lIHMgc2Vjb25kCiNkZWZpbmUgc3ooeCkgKGludCkoeCkuc2l6ZSgpCiNkZWZpbmUgYWxsKHgpIGJlZ2luKHgpLCBlbmQoeCkKI2RlZmluZSByYWxsKHgpICh4KS5yYmVnaW4oKSwgKHgpLnJlbmQoKSAKI2RlZmluZSBzb3IoeCkgc29ydChhbGwoeCkpIAojZGVmaW5lIHJzeiByZXNpemUKI2RlZmluZSBpbnMgaW5zZXJ0IAojZGVmaW5lIGZ0IGZyb250KCkgCiNkZWZpbmUgYmsgYmFjaygpCiNkZWZpbmUgcGYgcHVzaF9mcm9udCAKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBlYiBlbXBsYWNlX2JhY2sgCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQgCiNkZWZpbmUgdWIgdXBwZXJfYm91bmQgCgojZGVmaW5lIEZPUihpLGEsYikgZm9yIChpbnQgaSA9IChhKTsgaSA8IChiKTsgKytpKQojZGVmaW5lIEYwUihpLGEpIEZPUihpLDAsYSkKI2RlZmluZSBST0YoaSxhLGIpIGZvciAoaW50IGkgPSAoYiktMTsgaSA+PSAoYSk7IC0taSkKI2RlZmluZSBSMEYoaSxhKSBST0YoaSwwLGEpCiNkZWZpbmUgdHJhdihhLHgpIGZvciAoYXV0byYgYTogeCkKCmNvbnN0IGludCBNT0QgPSAxZTkrNzsgLy8gOTk4MjQ0MzUzOwpjb25zdCBpbnQgTVggPSAyZTUrNTsgCmNvbnN0IGxsIElORiA9IDFlMTg7IApjb25zdCBsZCBQSSA9IGFjb3MoKGxkKS0xKTsKY29uc3QgaW50IHhkWzRdID0gezEsMCwtMSwwfSwgeWRbNF0gPSB7MCwxLDAsLTF9OyAKbXQxOTkzNyBybmcoKHVpbnQzMl90KWNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7IAoKdGVtcGxhdGU8Y2xhc3MgVD4gYm9vbCBja21pbihUJiBhLCBjb25zdCBUJiBiKSB7IAoJcmV0dXJuIGIgPCBhID8gYSA9IGIsIDEgOiAwOyB9CnRlbXBsYXRlPGNsYXNzIFQ+IGJvb2wgY2ttYXgoVCYgYSwgY29uc3QgVCYgYikgeyAKCXJldHVybiBhIDwgYiA/IGEgPSBiLCAxIDogMDsgfSAKY29uc3RleHByIGludCBwY3QoaW50IHgpIHsgcmV0dXJuIF9fYnVpbHRpbl9wb3Bjb3VudCh4KTsgfSAKY29uc3RleHByIGludCBiaXRzKGludCB4KSB7IHJldHVybiAzMS1fX2J1aWx0aW5fY2x6KHgpOyB9IC8vIGZsb29yKGxvZzIoeCkpIApsbCBjZGl2KGxsIGEsIGxsIGIpIHsgcmV0dXJuIGEvYisoKGFeYik+MCYmYSViKTsgfSAvLyBkaXZpZGUgYSBieSBiIHJvdW5kZWQgdXAKbGwgZmRpdihsbCBhLCBsbCBiKSB7IHJldHVybiBhL2ItKChhXmIpPDAmJmElYik7IH0gLy8gZGl2aWRlIGEgYnkgYiByb3VuZGVkIGRvd24KbGwgaGFsZihsbCB4KSB7IHJldHVybiBmZGl2KHgsMik7IH0KCnRlbXBsYXRlPGNsYXNzIFQsIGNsYXNzIFU+IFQgZnN0VHJ1ZShUIGxvLCBUIGhpLCBVIGYpIHsgCgkvLyBub3RlOiBpZiAobG8raGkpLzIgaXMgdXNlZCBpbnN0ZWFkIG9mIGhhbGYobG8raGkpIHRoZW4gdGhpcyB3aWxsIGxvb3AgaW5maW5pdGVseSB3aGVuIGxvPWhpCgloaSArKzsgYXNzZXJ0KGxvIDw9IGhpKTsgLy8gYXNzdW1pbmcgZiBpcyBpbmNyZWFzaW5nCgl3aGlsZSAobG8gPCBoaSkgeyAvLyBmaW5kIGZpcnN0IGluZGV4IHN1Y2ggdGhhdCBmIGlzIHRydWUgCgkJVCBtaWQgPSBoYWxmKGxvK2hpKTsKCQlmKG1pZCkgPyBoaSA9IG1pZCA6IGxvID0gbWlkKzE7IAoJfSAKCXJldHVybiBsbzsKfQp0ZW1wbGF0ZTxjbGFzcyBULCBjbGFzcyBVPiBUIGxzdFRydWUoVCBsbywgVCBoaSwgVSBmKSB7CglsbyAtLTsgYXNzZXJ0KGxvIDw9IGhpKTsgLy8gYXNzdW1pbmcgZiBpcyBkZWNyZWFzaW5nCgl3aGlsZSAobG8gPCBoaSkgeyAvLyBmaW5kIGZpcnN0IGluZGV4IHN1Y2ggdGhhdCBmIGlzIHRydWUgCgkJVCBtaWQgPSBoYWxmKGxvK2hpKzEpOwoJCWYobWlkKSA/IGxvID0gbWlkIDogaGkgPSBtaWQtMTsKCX0gCglyZXR1cm4gbG87Cn0KdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCByZW1EdXAodmVjdG9yPFQ+JiB2KSB7IAoJc29ydChhbGwodikpOyB2LmVyYXNlKHVuaXF1ZShhbGwodikpLGVuZCh2KSk7IH0KCi8vIElOUFVUCnRlbXBsYXRlPGNsYXNzIEE+IHZvaWQgcmUoY29tcGxleDxBPiYgYyk7CnRlbXBsYXRlPGNsYXNzIEEsIGNsYXNzIEI+IHZvaWQgcmUocGFpcjxBLEI+JiBwKTsKdGVtcGxhdGU8Y2xhc3MgQT4gdm9pZCByZSh2ZWN0b3I8QT4mIHYpOwp0ZW1wbGF0ZTxjbGFzcyBBLCBzaXplX3QgU1o+IHZvaWQgcmUoYXJyYXk8QSxTWj4mIGEpOwoKdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCByZShUJiB4KSB7IGNpbiA+PiB4OyB9CnZvaWQgcmUoZGImIGQpIHsgc3RyIHQ7IHJlKHQpOyBkID0gc3RvZCh0KTsgfQp2b2lkIHJlKGxkJiBkKSB7IHN0ciB0OyByZSh0KTsgZCA9IHN0b2xkKHQpOyB9CnRlbXBsYXRlPGNsYXNzIEgsIGNsYXNzLi4uIFQ+IHZvaWQgcmUoSCYgaCwgVCYuLi4gdCkgeyByZShoKTsgcmUodC4uLik7IH0KCnRlbXBsYXRlPGNsYXNzIEE+IHZvaWQgcmUoY29tcGxleDxBPiYgYykgeyBBIGEsYjsgcmUoYSxiKTsgYyA9IHthLGJ9OyB9CnRlbXBsYXRlPGNsYXNzIEEsIGNsYXNzIEI+IHZvaWQgcmUocGFpcjxBLEI+JiBwKSB7IHJlKHAuZixwLnMpOyB9CnRlbXBsYXRlPGNsYXNzIEE+IHZvaWQgcmUodmVjdG9yPEE+JiB4KSB7IHRyYXYoYSx4KSByZShhKTsgfQp0ZW1wbGF0ZTxjbGFzcyBBLCBzaXplX3QgU1o+IHZvaWQgcmUoYXJyYXk8QSxTWj4mIHgpIHsgdHJhdihhLHgpIHJlKGEpOyB9CgovLyBUT19TVFJJTkcKI2RlZmluZSB0cyB0b19zdHJpbmcKc3RyIHRzKGNoYXIgYykgeyByZXR1cm4gc3RyKDEsYyk7IH0Kc3RyIHRzKGNvbnN0IGNoYXIqIHMpIHsgcmV0dXJuIChzdHIpczsgfQpzdHIgdHMoc3RyIHMpIHsgcmV0dXJuIHM7IH0Kc3RyIHRzKGJvb2wgYikgeyAKCSNpZmRlZiBMT0NBTAoJCXJldHVybiBiID8gInRydWUiIDogImZhbHNlIjsgCgkjZWxzZSAKCQlyZXR1cm4gdHMoKGludCliKTsKCSNlbmRpZgp9CnRlbXBsYXRlPGNsYXNzIEE+IHN0ciB0cyhjb21wbGV4PEE+IGMpIHsgCglzdHJpbmdzdHJlYW0gc3M7IHNzIDw8IGM7IHJldHVybiBzcy5zdHIoKTsgfQpzdHIgdHModmVjdG9yPGJvb2w+IHYpIHsKCXN0ciByZXMgPSAieyI7IEYwUihpLHN6KHYpKSByZXMgKz0gY2hhcignMCcrdltpXSk7CglyZXMgKz0gIn0iOyByZXR1cm4gcmVzOyB9CnRlbXBsYXRlPHNpemVfdCBTWj4gc3RyIHRzKGJpdHNldDxTWj4gYikgewoJc3RyIHJlcyA9ICIiOyBGMFIoaSxTWikgcmVzICs9IGNoYXIoJzAnK2JbaV0pOwoJcmV0dXJuIHJlczsgfQp0ZW1wbGF0ZTxjbGFzcyBBLCBjbGFzcyBCPiBzdHIgdHMocGFpcjxBLEI+IHApOwp0ZW1wbGF0ZTxjbGFzcyBUPiBzdHIgdHMoVCB2KSB7IC8vIGNvbnRhaW5lcnMgd2l0aCBiZWdpbigpLCBlbmQoKQoJI2lmZGVmIExPQ0FMCgkJYm9vbCBmc3QgPSAxOyBzdHIgcmVzID0gInsiOwoJCWZvciAoY29uc3QgYXV0byYgeDogdikgewoJCQlpZiAoIWZzdCkgcmVzICs9ICIsICI7CgkJCWZzdCA9IDA7IHJlcyArPSB0cyh4KTsKCQl9CgkJcmVzICs9ICJ9IjsgcmV0dXJuIHJlczsKCSNlbHNlCgkJYm9vbCBmc3QgPSAxOyBzdHIgcmVzID0gIiI7CgkJZm9yIChjb25zdCBhdXRvJiB4OiB2KSB7CgkJCWlmICghZnN0KSByZXMgKz0gIiAiOwoJCQlmc3QgPSAwOyByZXMgKz0gdHMoeCk7CgkJfQoJCXJldHVybiByZXM7CgoJI2VuZGlmCn0KdGVtcGxhdGU8Y2xhc3MgQSwgY2xhc3MgQj4gc3RyIHRzKHBhaXI8QSxCPiBwKSB7CgkjaWZkZWYgTE9DQUwKCQlyZXR1cm4gIigiK3RzKHAuZikrIiwgIit0cyhwLnMpKyIpIjsgCgkjZWxzZQoJCXJldHVybiB0cyhwLmYpKyIgIit0cyhwLnMpOwoJI2VuZGlmCn0KCi8vIE9VVFBVVAp0ZW1wbGF0ZTxjbGFzcyBBPiB2b2lkIHByKEEgeCkgeyBjb3V0IDw8IHRzKHgpOyB9CnRlbXBsYXRlPGNsYXNzIEgsIGNsYXNzLi4uIFQ+IHZvaWQgcHIoY29uc3QgSCYgaCwgY29uc3QgVCYuLi4gdCkgeyAKCXByKGgpOyBwcih0Li4uKTsgfQp2b2lkIHBzKCkgeyBwcigiXG4iKTsgfSAvLyBwcmludCB3LyBzcGFjZXMKdGVtcGxhdGU8Y2xhc3MgSCwgY2xhc3MuLi4gVD4gdm9pZCBwcyhjb25zdCBIJiBoLCBjb25zdCBUJi4uLiB0KSB7IAoJcHIoaCk7IGlmIChzaXplb2YuLi4odCkpIHByKCIgIik7IHBzKHQuLi4pOyB9CgovLyBERUJVRwp2b2lkIERCRygpIHsgY2VyciA8PCAiXSIgPDwgZW5kbDsgfQp0ZW1wbGF0ZTxjbGFzcyBILCBjbGFzcy4uLiBUPiB2b2lkIERCRyhIIGgsIFQuLi4gdCkgewoJY2VyciA8PCB0cyhoKTsgaWYgKHNpemVvZi4uLih0KSkgY2VyciA8PCAiLCAiOwoJREJHKHQuLi4pOyB9CiNpZmRlZiBMT0NBTCAvLyBjb21waWxlIHdpdGggLURMT0NBTCwgY2hrIC0+IGZha2UgYXNzZXJ0CgkjZGVmaW5lIGRiZyguLi4pIGNlcnIgPDwgIkxpbmUoIiA8PCBfX0xJTkVfXyA8PCAiKSAtPiBbIiA8PCAjX19WQV9BUkdTX18gPDwgIl06IFsiLCBEQkcoX19WQV9BUkdTX18pCgkjZGVmaW5lIGNoayguLi4pIGlmICghKF9fVkFfQVJHU19fKSkgY2VyciA8PCAiTGluZSgiIDw8IF9fTElORV9fIDw8ICIpIC0+IGZ1bmN0aW9uKCIgXAoJCSA8PCBfX0ZVTkNUSU9OX18gIDw8ICIpIC0+IENISyBGQUlMRUQ6ICgiIDw8ICNfX1ZBX0FSR1NfXyA8PCAiKSIgPDwgIlxuIiwgZXhpdCgwKTsKI2Vsc2UKCSNkZWZpbmUgZGJnKC4uLikgMAoJI2RlZmluZSBjaGsoLi4uKSAwCiNlbmRpZgoKLy8gRklMRSBJL08Kdm9pZCBzZXRJbihzdHIgcykgeyBmcmVvcGVuKHMuY19zdHIoKSwiciIsc3RkaW4pOyB9CnZvaWQgc2V0T3V0KHN0ciBzKSB7IGZyZW9wZW4ocy5jX3N0cigpLCJ3IixzdGRvdXQpOyB9CnZvaWQgdW5zeW5jSU8oKSB7IGNpbi50aWUoMCktPnN5bmNfd2l0aF9zdGRpbygwKTsgfQp2b2lkIHNldElPKHN0ciBzID0gIiIpIHsKCXVuc3luY0lPKCk7CgkvLyBjaW4uZXhjZXB0aW9ucyhjaW4uZmFpbGJpdCk7IAoJLy8gdGhyb3dzIGV4Y2VwdGlvbiB3aGVuIGRvIHNtdGggaWxsZWdhbAoJLy8gZXguIHRyeSB0byByZWFkIGxldHRlciBpbnRvIGludAoJaWYgKHN6KHMpKSB7IHNldEluKHMrIi5pbiIpLCBzZXRPdXQocysiLm91dCIpOyB9IC8vIGZvciBVU0FDTwp9CgoKI2luY2x1ZGUgImZ1bi5oIgoKdmkgYWRqW01YXTsKaW50IGNvbG9yW01YXTsKdnBpIHZpczsKCnZvaWQgZGZzKGludCBhLCBpbnQgYiwgaW50IGQpIHsKCXZpcy5wYih7ZCxhfSk7Cgl0cmF2KHQsYWRqW2FdKSBpZiAodCAhPSBiKSBkZnModCxhLGQrMSk7Cn0KCnN0ZDo6dmVjdG9yPGludD4gY3JlYXRlRnVuVG91cihpbnQgTiwgaW50IFEpIHsKCUYwUihpLE4pIEZPUihqLGkrMSxOKSB7CgkJaWYgKGhvdXJzUmVxdWlyZWQoaSxqKSA9PSAxKSB7CgkJCWFkaltpXS5wYihqKSwgYWRqW2pdLnBiKGkpOwoJCX0KCX0KCUYwUihpLE4pIHsKCQlpbnQgbWF4U2l6ZSA9IDA7CgkJdmVjdG9yPHZwaT4gdG1wOwoJCXRyYXYodCxhZGpbaV0pIHsKCQkJdmlzLmNsZWFyKCk7IGRmcyh0LGksMSk7CgkJCWNrbWF4KG1heFNpemUsc3oodmlzKSk7CgkJCXRtcC5wYih2aXMpOwoJCX0KCQlpZiAoMiptYXhTaXplID4gTikgY29udGludWU7CgkJY29sb3JbaV0gPSAtMTsKCQlGMFIoXyxzeih0bXApKSB0cmF2KHQsdG1wW19dKSBjb2xvclt0LnNdID0gXzsKCQl0cmF2KHQsdG1wKSBzb3J0KHJhbGwodCkpOwoJCXZwaSByZXN7ezAsaX19OwoJCWludCBsZWYgPSBOOwoJCWludCBjb2wgPSAtMSwgbHN0ID0gLTE7CgkJd2hpbGUgKDEpIHsKCQkJbGVmIC0tOyBpZiAobGVmID09IDApIGJyZWFrOwoJCQlwaSBiZXMgPSB7TU9ELE1PRH07CgkJCWlmIChsc3QgPT0gMSkgewoJCQkJRjBSKF8sc3oodG1wKSkgaWYgKF8gIT0gY29sKSB7CgkJCQkJaWYgKHN6KHRtcFtfXSkpIGNrbWluKGJlcyx0bXBbX10uYmspOwoJCQkJfQoJCQkJcmVzLnBiKGJlcyk7IHRtcFtjb2xvcltiZXMuc11dLnBvcF9iYWNrKCk7CgkJCQlsc3QgXj0gMTsKCQkJfSBlbHNlIGlmIChsc3QgPT0gMCkgewoJCQkJRjBSKF8sc3oodG1wKSkgaWYgKF8gPT0gY29sKSB7CgkJCQkJaWYgKHN6KHRtcFtfXSkpIGNrbWluKGJlcyx0bXBbX10uYmspOwoJCQkJfQoJCQkJcmVzLnBiKGJlcyk7IHRtcFtjb2xvcltiZXMuc11dLnBvcF9iYWNrKCk7CgkJCQlsc3QgXj0gMTsKCQkJfSBlbHNlIHsKCQkJCW1heFNpemUgPSAwOwoJCQkJRjBSKF8sc3oodG1wKSkgewoJCQkJCWNrbWF4KG1heFNpemUsc3oodG1wW19dKSk7CgkJCQkJaWYgKHN6KHRtcFtfXSkgJiYgXyAhPSBjb2xvcltyZXMuYmsuc10pIGNrbWluKGJlcyx0bXBbX10uYmspOwoJCQkJfQoJCQkJaWYgKDIqbWF4U2l6ZSA+IGxlZikgeyAKCQkJCQl0cmF2KHQsdG1wKSBpZiAoc3oodCkgPT0gbWF4U2l6ZSkgewoJCQkJCQliZXMgPSB0LmJrOwoJCQkJCQlyZXMucGIoYmVzKTsKCQkJCQkJY29sID0gY29sb3JbYmVzLnNdOwoJCQkJCQl0bXBbY29sb3JbYmVzLnNdXS5wb3BfYmFjaygpOwoJCQkJCX0KCQkJCQlsc3QgPSAxOwoJCQkJCWNvbnRpbnVlOwoJCQkJfSAKCQkJCWlmICgyKm1heFNpemUgPT0gbGVmKSB7CgkJCQkJaW50IGJpZyA9IDA7IEYwUihpLHN6KHRtcCkpIGlmIChzeih0bXBbaV0pID09IG1heFNpemUpIGJpZyA9IGk7CgkJCQkJcGkgeCA9IHRtcFtiaWddLmJrLCB5ID0ge01PRCxNT0R9OwoJCQkJCUYwUihpLHN6KHRtcCkpIGlmIChpICE9IGJpZyAmJiBzeih0bXBbaV0pKSBja21pbih5LHRtcFtpXS5iayk7CgkJCQkJcGkgb25lID0gcmVzLmJrLCB0d28gPSB7LU1PRCwtTU9EfTsKCQkJCQlpZiAoc3oocmVzKSA+IDEpIHR3byA9IHJlc1tzeihyZXMpLTJdOwoJCQkJCWlmIChjb2xvclt4LnNdICE9IGNvbG9yW3Jlcy5iay5zXSAmJiB4ID49IHR3byAmJiB5ID49IG9uZSkgewoJCQkJCQlyZXMucGIoeCk7IGNvbCA9IGNvbG9yW3guc107IGxzdCA9IDE7CgkJCQkJCXRtcFtjb2xvclt4LnNdXS5wb3BfYmFjaygpOwoJCQkJCQljb250aW51ZTsKCQkJCQl9CgkJCQkJaWYgKGNvbG9yW3kuc10gIT0gY29sb3JbcmVzLmJrLnNdICYmIHkgPj0gdHdvICYmIHggPj0gb25lKSB7CgkJCQkJCXJlcy5wYih5KTsgY29sID0gY29sb3JbeC5zXTsgbHN0ID0gMDsKCQkJCQkJdG1wW2NvbG9yW3kuc11dLnBvcF9iYWNrKCk7CgkJCQkJCWNvbnRpbnVlOwoJCQkJCX0KCQkJCQlleGl0KDUpOyAvLyBvbmUgb2YgYWJvdmUgdHdvIGNhc2VzIG11c3QgaG9sZAoJCQkJfQoJCQkJcmVzLnBiKGJlcyk7IHRtcFtjb2xvcltiZXMuc11dLnBvcF9iYWNrKCk7IC8vIGp1c3QgZ3JlZWR5CgkJCX0KCQl9CgkJRk9SKGksMixzeihyZXMpKSBhc3NlcnQocmVzW2ldID49IHJlc1tpLTJdKTsKCQlGT1IoaSwxLHN6KHJlcykpIGFzc2VydChjb2xvcltyZXNbaV0uc10gIT0gY29sb3JbcmVzW2ktMV0uc10pOwoJCXJldmVyc2UoYWxsKHJlcykpOwoJCXZpIGFuczsgdHJhdih0LHJlcykgYW5zLnBiKHQucyk7CgkJcmV0dXJuIGFuczsKCX0KCXJldHVybiB7fTsKfQ==