#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=