#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vll vector<ll>
const int g = 3, mod = 998244353, p = 998244353;
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline void ADD(int & a, int b){
a += b;
if(a >= mod) a -= mod;
}
inline int powr(int a, ll b){
int x = 1 % mod;
while(b){
if(b & 1) x = mul(x, a);
a = mul(a, a);
b >>= 1;
}
return x;
}
inline int inv(int a){ return powr(a, mod - 2);}
const int MX = 15;
int W[1 << MX], invW[1 << MX]; // max polynomial input/output -> (1 << MX)
int maxn, MAXN;
void precompute_powers(){
int p2 = p - 1;
while(p2 % 2 == 0){
p2 >>= 1;
MAXN ++;
}
MAXN = min(MAXN, MX);
int g1 = powr(g, (p - 1) >> MAXN);
maxn = 1 << MAXN;
int st = 1;
for(int i = 0; i < maxn; i++){
W[i] = st;
st = mul(st, g1);
}
for(int i = 0; i < maxn; i++){
invW[i] = (i == 0) ? 1 : W[maxn - i];
}
}
void fft (vector<int> & a, bool invert) {
int n = (int) a.size();
for (int i=1, j=0; i<n; ++i) {
int bit = n >> 1;
for (; j>=bit; bit>>=1)
j -= bit;
j += bit;
if (i < j)
swap (a[i], a[j]);
}
for (int len=2; len<=n; len<<=1) {
for (int i=0; i<n; i+=len) {
int ind = 0,ADD = maxn/len;
for (int j=0; j<len/2; ++j) {
int u = a[i+j], v = mul(a[i+j+len/2], (invert?invW[ind]:W[ind]));
a[i+j] = add(u, v);
a[i+j+len/2] = sub(u, v);
ind += ADD;
}
}
}
if (invert){
int invn = inv(n);
for (int i=0; i<n; ++i) a[i] = mul(a[i], invn);
}
}
vi add(vi a, vi b){
vi ret(max(a.size(), b.size()));
for(int i = 0; i < ret.size(); i++){
ret[i] = add(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
}
return ret;
}
vi sub(vi a, vi b){
vi ret(max(a.size(), b.size()));
for(int i = 0; i < ret.size(); i++){
ret[i] = sub(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
}
return ret;
}
vi mul(vi a, vi b){
int sz = a.size() + b.size() - 1;
int k = 0;
while((1 << k) < sz) k++;
a.resize(1 << k); b.resize(1 << k);
fft(a, 0); fft(b, 0);
for(int i = 0; i < (1 << k); i++)
a[i] = mul(a[i], b[i]);
fft(a, 1);
a.resize(sz);
return a;
}
vi inverse(vi a, int sz){
assert(a[0] != 0);
vi x = {inv(a[0])};
while(x.size() < sz){
vi temp(a.begin(), a.begin() + min(a.size(), 2 * x.size()));
vi nx = mul(mul(x, x), temp);
x.resize(2 * x.size());
for(int i = 0; i < x.size(); i++)
x[i] = sub(add(x[i], x[i]), nx[i]);
}
x.resize(sz);
return x;
}
vi shorten(vi x, int k){
x.resize(min((int)x.size(), k));
return x;
}
vi truncate_end(vi v){
while(!v.empty() && v.back() == 0) v.pop_back();
if(v.empty()) v = {0};
return v;
}
void print(vi v){
cerr << "[";
for(int i = 0; i < v.size(); i++){
cerr << v[i];
if(i + 1 != v.size()) cerr <<" ";
else cerr << "]";
}
cerr << endl;
}
vi _inv;
// _inv = inverse(rev(g))
pair<vi, vi> divmod(vi f, vi g){
if(f.size() < g.size()) return {{0}, f};
int sz = f.size() - g.size() + 1;
reverse(f.begin(), f.end()); reverse(g.begin(), g.end());
vi inv2 = _inv;
inv2.resize(sz);
vi _p = f; _p.resize(sz);
vi q = mul(inv2, _p);
q.resize(sz);
reverse(q.begin(), q.end()); reverse(f.begin(), f.end()); reverse(g.begin(), g.end());
return {q, truncate_end(sub(f, mul(g, q)))};
}
const int N = 3005;
int st[N][N];
int beg;
struct tree{
int n;
vector<vector<int> > con;
tree(int n) : n(n), con(n + 1) {}
void add_edge(int a, int b){
con[a].push_back(b);
con[b].push_back(a);
}
// compute characteristic polynomial at a given value
int get(int x){
vector<bool> U(n + 1, 1);
vector<int> a(n + 1, x);
int d = 0;
function<void(int, int)> dfs = [&](int s, int p){
bool deleted = 0;
for(int v : con[s]) if(v != p){
dfs(v, s);
if(U[v] && a[v] == 0 && !deleted){
U[v] = U[s] = 0;
deleted = 1;
d++;
} else if(U[v] && !deleted){
a[s] = sub(a[s], inv(a[v]));
}
}
};
dfs(1, -1);
int ret = powr(mod - 1, d);
for(int i = 1; i <= n; i++) if(U[i]) ret = mul(ret, a[i]);
return ret;
}
// get characteristic polynomial
vector<int> getCharPoly(){
int sz = n + 1;
int k = 0;
while((1 << k) < sz) k++;
vector<int> eval(1 << k);
for(int i = 0; i < (1 << k); i++){
eval[i] = get(sub(mod, W[i << (MAXN - k)]));
}
fft(eval, 1);
while(!eval.empty() && eval.back() == 0) eval.pop_back();
int m = eval.size();
return eval;
}
// precompute for small values of k
void compute_st(){
st[0][beg] = 1;
for(int j = 1; j <= n; j++){
for(int i = 1; i <= n; i++){
for(int i2 : con[i]){
ADD(st[j][i], st[j - 1][i2]);
}
}
}
}
};
map<int, vi> cache;
vi char_poly;
vi get(int k){
if(cache.find(k) != cache.end()) return cache[k];
int store_k = k;
vi A = {1};
vi B = {0, 1};
for(; k; k >>= 1, B = divmod(mul(B, B), char_poly).second) if(k & 1){
A = divmod(mul(A, B), char_poly).second;
}
return cache[store_k] = A;
}
int main(){
srand(time(NULL));
cin.tie(0);
ios_base::sync_with_stdio(0);
precompute_powers();
int n = 1000;
cin >> n;
assert(n <= 3000);
tree T(n);
for(int i = 1; i < n; i++){
int x, y;
x = i + 1; y = rand() % i + 1;
cin >> x >> y;
assert(x >= 1 && x <= n && y >= 1 && y <= n && x != y);
T.add_edge(x, y);
}
char_poly = T.getCharPoly();
reverse(char_poly.begin(), char_poly.end());
_inv = inverse(char_poly, n + 10);
reverse(char_poly.begin(), char_poly.end());
int a, b, k;
a = rand() % n + 1, b = rand() % n + 1, k = n + 1 + rand() % n;
cin >> a >> k;
assert(a >= 1 && a <= n);
assert(k >= 0 && k <= 1e9);
beg = a;
T.compute_st();
if(k <= n){
for(int b = 1; b <= n; b++)
cout << st[k][b] << " ";
return 0;
}
vi poly = get(k);
poly.resize(n);
for(int b = 1; b <= n; b++){
int ret = 0;
for(int i = 0; i < n; i++) ret = add(ret, mul(poly[i], st[i][b]));
cout << ret << " ";
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgdmxsIHZlY3RvcjxsbD4KCmNvbnN0IGludCBnID0gMywgbW9kID0gOTk4MjQ0MzUzLCBwID0gOTk4MjQ0MzUzOwoKaW5saW5lIGludCBhZGQoaW50IHgsIGludCB5KXsgeCArPSB5OyBpZih4ID49IG1vZCkgeCAtPSBtb2Q7IHJldHVybiB4O30KaW5saW5lIGludCBzdWIoaW50IHgsIGludCB5KXsgeCAtPSB5OyBpZih4IDwgMCkgeCArPSBtb2Q7IHJldHVybiB4O30KaW5saW5lIGludCBtdWwoaW50IHgsIGludCB5KXsgcmV0dXJuICh4ICogMWxsICogeSkgJSBtb2Q7fQoKaW5saW5lIHZvaWQgQUREKGludCAmIGEsIGludCBiKXsKICAgIGEgKz0gYjsKICAgIGlmKGEgPj0gbW9kKSBhIC09IG1vZDsKfQoKaW5saW5lIGludCBwb3dyKGludCBhLCBsbCBiKXsKICAgIGludCB4ID0gMSAlIG1vZDsKICAgIHdoaWxlKGIpewogICAgICAgIGlmKGIgJiAxKSB4ID0gbXVsKHgsIGEpOwogICAgICAgIGEgPSBtdWwoYSwgYSk7CiAgICAgICAgYiA+Pj0gMTsKICAgIH0KICAgIHJldHVybiB4Owp9CmlubGluZSBpbnQgaW52KGludCBhKXsgcmV0dXJuIHBvd3IoYSwgbW9kIC0gMik7fQoKY29uc3QgaW50IE1YID0gMTU7CmludCBXWzEgPDwgTVhdLCBpbnZXWzEgPDwgTVhdOyAvLyBtYXggcG9seW5vbWlhbCBpbnB1dC9vdXRwdXQgLT4gKDEgPDwgTVgpCmludCBtYXhuLCBNQVhOOwoKdm9pZCBwcmVjb21wdXRlX3Bvd2VycygpewogICAgaW50IHAyID0gcCAtIDE7CiAgICB3aGlsZShwMiAlIDIgPT0gMCl7CiAgICAgICAgcDIgPj49IDE7CiAgICAgICAgTUFYTiArKzsKICAgIH0KICAgIE1BWE4gPSBtaW4oTUFYTiwgTVgpOwogICAgaW50IGcxID0gcG93cihnLCAocCAtIDEpID4+IE1BWE4pOwogICAgbWF4biA9IDEgPDwgTUFYTjsKICAgIGludCBzdCA9IDE7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbWF4bjsgaSsrKXsKICAgICAgICBXW2ldID0gc3Q7CiAgICAgICAgc3QgPSBtdWwoc3QsIGcxKTsKICAgIH0KICAgIGZvcihpbnQgaSA9IDA7IGkgPCBtYXhuOyBpKyspewogICAgICAgIGludldbaV0gPSAoaSA9PSAwKSA/IDEgOiBXW21heG4gLSBpXTsKICAgIH0KfQoKdm9pZCBmZnQgKHZlY3RvcjxpbnQ+ICYgYSwgYm9vbCBpbnZlcnQpIHsKICAgIGludCBuID0gKGludCkgYS5zaXplKCk7CgogICAgZm9yIChpbnQgaT0xLCBqPTA7IGk8bjsgKytpKSB7CiAgICAgICAgaW50IGJpdCA9IG4gPj4gMTsKICAgICAgICBmb3IgKDsgaj49Yml0OyBiaXQ+Pj0xKQogICAgICAgICAgICBqIC09IGJpdDsKICAgICAgICBqICs9IGJpdDsKICAgICAgICBpZiAoaSA8IGopCiAgICAgICAgICAgIHN3YXAgKGFbaV0sIGFbal0pOwogICAgfQoKICAgIGZvciAoaW50IGxlbj0yOyBsZW48PW47IGxlbjw8PTEpIHsKICAgICAgICBmb3IgKGludCBpPTA7IGk8bjsgaSs9bGVuKSB7CiAgICAgICAgICAgIGludCBpbmQgPSAwLEFERCA9IG1heG4vbGVuOwogICAgICAgICAgICBmb3IgKGludCBqPTA7IGo8bGVuLzI7ICsraikgewogICAgICAgICAgICAgICAgaW50IHUgPSBhW2kral0sICB2ID0gbXVsKGFbaStqK2xlbi8yXSwgKGludmVydD9pbnZXW2luZF06V1tpbmRdKSk7CiAgICAgICAgICAgICAgICBhW2kral0gPSBhZGQodSwgdik7CiAgICAgICAgICAgICAgICBhW2kraitsZW4vMl0gPSBzdWIodSwgdik7CiAgICAgICAgICAgICAgICBpbmQgKz0gQUREOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgaWYgKGludmVydCl7CiAgICAgICAgaW50IGludm4gPSBpbnYobik7CiAgICAgICAgZm9yIChpbnQgaT0wOyBpPG47ICsraSkgYVtpXSA9IG11bChhW2ldLCBpbnZuKTsKICAgIH0KfQoKdmkgYWRkKHZpIGEsIHZpIGIpewogICAgdmkgcmV0KG1heChhLnNpemUoKSwgYi5zaXplKCkpKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCByZXQuc2l6ZSgpOyBpKyspewogICAgICAgIHJldFtpXSA9IGFkZChpIDwgYS5zaXplKCkgPyBhW2ldIDogMCwgaSA8IGIuc2l6ZSgpID8gYltpXSA6IDApOwogICAgfQogICAgcmV0dXJuIHJldDsKfQoKdmkgc3ViKHZpIGEsIHZpIGIpeyAKICAgIHZpIHJldChtYXgoYS5zaXplKCksIGIuc2l6ZSgpKSk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgcmV0LnNpemUoKTsgaSsrKXsKICAgICAgICByZXRbaV0gPSBzdWIoaSA8IGEuc2l6ZSgpID8gYVtpXSA6IDAsIGkgPCBiLnNpemUoKSA/IGJbaV0gOiAwKTsKICAgIH0KICAgIHJldHVybiByZXQ7Cn0KCnZpIG11bCh2aSBhLCB2aSBiKXsKICAgIGludCBzeiA9IGEuc2l6ZSgpICsgYi5zaXplKCkgLSAxOwogICAgaW50IGsgPSAwOwogICAgd2hpbGUoKDEgPDwgaykgPCBzeikgaysrOwogICAgYS5yZXNpemUoMSA8PCBrKTsgYi5yZXNpemUoMSA8PCBrKTsKICAgIGZmdChhLCAwKTsgZmZ0KGIsIDApOwogICAgZm9yKGludCBpID0gMDsgaSA8ICgxIDw8IGspOyBpKyspCiAgICAgICAgYVtpXSA9IG11bChhW2ldLCBiW2ldKTsKICAgIGZmdChhLCAxKTsKICAgIGEucmVzaXplKHN6KTsKICAgIHJldHVybiBhOwp9Cgp2aSBpbnZlcnNlKHZpIGEsIGludCBzeil7CiAgICBhc3NlcnQoYVswXSAhPSAwKTsKICAgIHZpIHggPSB7aW52KGFbMF0pfTsKICAgIHdoaWxlKHguc2l6ZSgpIDwgc3opewogICAgICAgIHZpIHRlbXAoYS5iZWdpbigpLCBhLmJlZ2luKCkgKyBtaW4oYS5zaXplKCksIDIgKiB4LnNpemUoKSkpOwogICAgICAgIHZpIG54ID0gbXVsKG11bCh4LCB4KSwgdGVtcCk7CiAgICAgICAgeC5yZXNpemUoMiAqIHguc2l6ZSgpKTsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgeC5zaXplKCk7IGkrKykKICAgICAgICAgICAgeFtpXSA9IHN1YihhZGQoeFtpXSwgeFtpXSksIG54W2ldKTsKICAgIH0KICAgIHgucmVzaXplKHN6KTsKICAgIHJldHVybiB4Owp9Cgp2aSBzaG9ydGVuKHZpIHgsIGludCBrKXsKICAgIHgucmVzaXplKG1pbigoaW50KXguc2l6ZSgpLCBrKSk7CiAgICByZXR1cm4geDsKfQoKdmkgdHJ1bmNhdGVfZW5kKHZpIHYpewogICAgd2hpbGUoIXYuZW1wdHkoKSAmJiB2LmJhY2soKSA9PSAwKSB2LnBvcF9iYWNrKCk7CiAgICBpZih2LmVtcHR5KCkpIHYgPSB7MH07CiAgICByZXR1cm4gdjsKfQoKdm9pZCBwcmludCh2aSB2KXsKICAgIGNlcnIgPDwgIlsiOyAKICAgIGZvcihpbnQgaSA9IDA7IGkgPCB2LnNpemUoKTsgaSsrKXsKICAgICAgICBjZXJyIDw8IHZbaV07CiAgICAgICAgaWYoaSArIDEgIT0gdi5zaXplKCkpIGNlcnIgPDwiICI7CiAgICAgICAgZWxzZSBjZXJyIDw8ICJdIjsKICAgIH0KICAgIGNlcnIgPDwgZW5kbDsKfQoKdmkgX2ludjsKLy8gX2ludiA9IGludmVyc2UocmV2KGcpKQpwYWlyPHZpLCB2aT4gZGl2bW9kKHZpIGYsIHZpIGcpewogICAgaWYoZi5zaXplKCkgPCBnLnNpemUoKSkgcmV0dXJuIHt7MH0sIGZ9OwogICAgaW50IHN6ID0gZi5zaXplKCkgLSBnLnNpemUoKSArIDE7CiAgICByZXZlcnNlKGYuYmVnaW4oKSwgZi5lbmQoKSk7IHJldmVyc2UoZy5iZWdpbigpLCBnLmVuZCgpKTsKICAgIHZpIGludjIgPSBfaW52OyAKICAgIGludjIucmVzaXplKHN6KTsKICAgIHZpIF9wID0gZjsgX3AucmVzaXplKHN6KTsKICAgIHZpIHEgPSBtdWwoaW52MiwgX3ApOwogICAgcS5yZXNpemUoc3opOwogICAgcmV2ZXJzZShxLmJlZ2luKCksIHEuZW5kKCkpOyByZXZlcnNlKGYuYmVnaW4oKSwgZi5lbmQoKSk7IHJldmVyc2UoZy5iZWdpbigpLCBnLmVuZCgpKTsKICAgIHJldHVybiB7cSwgdHJ1bmNhdGVfZW5kKHN1YihmLCBtdWwoZywgcSkpKX07Cn0KCmNvbnN0IGludCBOID0gMzAwNTsKCmludCBzdFtOXVtOXTsKaW50IGJlZzsKc3RydWN0IHRyZWV7CiAgICBpbnQgbjsKICAgIHZlY3Rvcjx2ZWN0b3I8aW50PiA+IGNvbjsKICAgIHRyZWUoaW50IG4pIDogbihuKSwgY29uKG4gKyAxKSB7fQoKICAgIHZvaWQgYWRkX2VkZ2UoaW50IGEsIGludCBiKXsKICAgICAgICBjb25bYV0ucHVzaF9iYWNrKGIpOwogICAgICAgIGNvbltiXS5wdXNoX2JhY2soYSk7CiAgICB9CiAgICAvLyBjb21wdXRlIGNoYXJhY3RlcmlzdGljIHBvbHlub21pYWwgYXQgYSBnaXZlbiB2YWx1ZQogICAgaW50IGdldChpbnQgeCl7CiAgICAgICAgdmVjdG9yPGJvb2w+IFUobiArIDEsIDEpOwogICAgICAgIHZlY3RvcjxpbnQ+IGEobiArIDEsIHgpOwogICAgICAgIGludCBkID0gMDsKICAgICAgICBmdW5jdGlvbjx2b2lkKGludCwgaW50KT4gZGZzID0gWyZdKGludCBzLCBpbnQgcCl7CiAgICAgICAgICAgIGJvb2wgZGVsZXRlZCA9IDA7CiAgICAgICAgICAgIGZvcihpbnQgdiA6IGNvbltzXSkgaWYodiAhPSBwKXsKICAgICAgICAgICAgICAgIGRmcyh2LCBzKTsKICAgICAgICAgICAgICAgIGlmKFVbdl0gJiYgYVt2XSA9PSAwICYmICFkZWxldGVkKXsKICAgICAgICAgICAgICAgICAgICBVW3ZdID0gVVtzXSA9IDA7CiAgICAgICAgICAgICAgICAgICAgZGVsZXRlZCA9IDE7CiAgICAgICAgICAgICAgICAgICAgZCsrOwogICAgICAgICAgICAgICAgfSBlbHNlIGlmKFVbdl0gJiYgIWRlbGV0ZWQpewogICAgICAgICAgICAgICAgICAgIGFbc10gPSBzdWIoYVtzXSwgIGludihhW3ZdKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9OwogICAgICAgIGRmcygxLCAtMSk7CiAgICAgICAgaW50IHJldCA9IHBvd3IobW9kIC0gMSwgZCk7CiAgICAgICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspIGlmKFVbaV0pIHJldCA9IG11bChyZXQsIGFbaV0pOwogICAgICAgIHJldHVybiByZXQ7CiAgICB9CiAgICAvLyBnZXQgY2hhcmFjdGVyaXN0aWMgcG9seW5vbWlhbAogICAgdmVjdG9yPGludD4gZ2V0Q2hhclBvbHkoKXsKICAgICAgICBpbnQgc3ogPSBuICsgMTsKICAgICAgICBpbnQgayA9IDA7CiAgICAgICAgd2hpbGUoKDEgPDwgaykgPCBzeikgaysrOwogICAgICAgIHZlY3RvcjxpbnQ+IGV2YWwoMSA8PCBrKTsKCiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8ICgxIDw8IGspOyBpKyspewogICAgICAgICAgICBldmFsW2ldID0gZ2V0KHN1Yihtb2QsIFdbaSA8PCAoTUFYTiAtIGspXSkpOwogICAgICAgIH0KCiAgICAgICAgZmZ0KGV2YWwsIDEpOwogICAgICAgIHdoaWxlKCFldmFsLmVtcHR5KCkgJiYgZXZhbC5iYWNrKCkgPT0gMCkgZXZhbC5wb3BfYmFjaygpOwoKICAgICAgICBpbnQgbSA9IGV2YWwuc2l6ZSgpOwogICAgICAgIHJldHVybiBldmFsOwogICAgfQogICAgLy8gcHJlY29tcHV0ZSBmb3Igc21hbGwgdmFsdWVzIG9mIGsKICAgIHZvaWQgY29tcHV0ZV9zdCgpewogICAgICAgIHN0WzBdW2JlZ10gPSAxOwogICAgICAgIGZvcihpbnQgaiA9IDE7IGogPD0gbjsgaisrKXsKICAgICAgICAgICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspewogICAgICAgICAgICAgICAgICAgIGZvcihpbnQgaTIgOiBjb25baV0pewogICAgICAgICAgICAgICAgICAgICAgICBBREQoc3Rbal1baV0sIHN0W2ogLSAxXVtpMl0pOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfTsKCm1hcDxpbnQsIHZpPiBjYWNoZTsKdmkgY2hhcl9wb2x5OwoKdmkgZ2V0KGludCBrKXsKICAgIGlmKGNhY2hlLmZpbmQoaykgIT0gY2FjaGUuZW5kKCkpIHJldHVybiBjYWNoZVtrXTsKICAgIGludCBzdG9yZV9rID0gazsKICAgIHZpIEEgPSB7MX07CiAgICB2aSBCID0gezAsIDF9OwogICAgZm9yKDsgazsgayA+Pj0gMSwgQiA9IGRpdm1vZChtdWwoQiwgQiksIGNoYXJfcG9seSkuc2Vjb25kKSBpZihrICYgMSl7CiAgICAgICAgQSA9IGRpdm1vZChtdWwoQSwgQiksIGNoYXJfcG9seSkuc2Vjb25kOwogICAgfQogICAgcmV0dXJuIGNhY2hlW3N0b3JlX2tdID0gQTsKfQoKCmludCBtYWluKCl7CiAgICBzcmFuZCh0aW1lKE5VTEwpKTsKICAgIGNpbi50aWUoMCk7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgcHJlY29tcHV0ZV9wb3dlcnMoKTsKICAgIGludCBuID0gMTAwMDsKICAgIGNpbiA+PiBuOwogICAgYXNzZXJ0KG4gPD0gMzAwMCk7CiAgICB0cmVlIFQobik7CiAgICBmb3IoaW50IGkgPSAxOyBpIDwgbjsgaSsrKXsKICAgICAgICBpbnQgeCwgeTsKICAgICAgICB4ID0gaSArIDE7IHkgPSByYW5kKCkgJSBpICsgMTsKICAgICAgICBjaW4gPj4geCA+PiB5OwogICAgICAgIGFzc2VydCh4ID49IDEgJiYgeCA8PSBuICYmIHkgPj0gMSAmJiB5IDw9IG4gJiYgIHggIT0geSk7CiAgICAgICAgVC5hZGRfZWRnZSh4LCB5KTsKICAgIH0KICAgIGNoYXJfcG9seSA9IFQuZ2V0Q2hhclBvbHkoKTsKICAgIHJldmVyc2UoY2hhcl9wb2x5LmJlZ2luKCksIGNoYXJfcG9seS5lbmQoKSk7CiAgICBfaW52ID0gaW52ZXJzZShjaGFyX3BvbHksIG4gKyAxMCk7CiAgICByZXZlcnNlKGNoYXJfcG9seS5iZWdpbigpLCBjaGFyX3BvbHkuZW5kKCkpOwogICAgaW50IGEsIGIsIGs7CiAgICBhID0gcmFuZCgpICUgbiArIDEsIGIgPSByYW5kKCkgJSBuICsgMSwgayA9IG4gKyAxICsgcmFuZCgpICUgbjsKICAgIGNpbiA+PiBhID4+IGs7ICAKCiAgICBhc3NlcnQoYSA+PSAxICAmJiBhIDw9IG4pOwogICAgYXNzZXJ0KGsgPj0gMCAmJiBrIDw9IDFlOSk7CiAgICAKICAgIGJlZyA9IGE7CiAgICBULmNvbXB1dGVfc3QoKTsKICAgIGlmKGsgPD0gbil7IAogICAgICAgIGZvcihpbnQgYiA9IDE7IGIgPD0gbjsgYisrKQogICAgICAgICAgICBjb3V0IDw8IHN0W2tdW2JdIDw8ICIgIjsKICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICB2aSBwb2x5ID0gZ2V0KGspOwogICAgcG9seS5yZXNpemUobik7CiAgICBmb3IoaW50IGIgPSAxOyBiIDw9IG47IGIrKyl7CiAgICAgICAgaW50IHJldCA9IDA7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgcmV0ID0gYWRkKHJldCwgbXVsKHBvbHlbaV0sIHN0W2ldW2JdKSk7ICAKICAgICAgICBjb3V0IDw8IHJldCA8PCAiICI7CiAgICB9Cn0=