Problem: Alice and Bob are going to celebrate Christmas by playing a game with a tree of presents. The tree has n nodes (numbered 1 to n, with some node r as its root). There are a_i presents are hanging from the i-th node.

Before beginning the game, a special integer k is chosen. The game proceeds as follows:

  * Alice begins the game, with moves alternating each turn;
  * in any move, the current player may choose some node (for example, i) which has depth at least k. Then, the player picks some positive number of presents hanging from that node, let's call it m (1 ≤ m ≤ a_i);
  * the player then places these m presents on the k-th ancestor (let's call it j) of the i-th node (the k-th ancestor of vertex i is a vertex j such that i is a descendant of j, and the difference between the depth of j and the depth of i is exactly k). Now, the number of presents of the i-th node (a_i) is decreased by m, and, correspondingly, a_j is increased by m;
  * Alice and Bob both play optimally. The player unable to make a move loses the game.



For each possible root of the tree, find who among Alice or Bob wins the game.

Note: The depth of a node i in a tree with root r is defined as the number of edges on the simple path from node r to node i. The depth of root r itself is zero.

Input

The first line contains two space-separated integers n and k (3 ≤ n ≤ 10^5, 1 ≤ k ≤ 20).

The next n-1 lines each contain two integers x and y (1 ≤ x, y ≤ n, x ≠ y), denoting an undirected edge between the two nodes x and y. These edges form a tree of n nodes.

The next line contains n space-separated integers denoting the array a (0 ≤ a_i ≤ 10^9).

Output

Output n integers, where the i-th integer is 1 if Alice wins the game when the tree is rooted at node i, or 0 otherwise.

Example

Input


5 1
1 2
1 3
5 2
4 3
0 3 2 4 4


Output


1 0 0 1 1 

Note

Let us calculate the answer for sample input with root node as 1 and as 2.

Root node 1

Alice always wins in this case. One possible gameplay between Alice and Bob is:

  * Alice moves one present from node 4 to node 3. 
  * Bob moves four presents from node 5 to node 2. 
  * Alice moves four presents from node 2 to node 1. 
  * Bob moves three presents from node 2 to node 1. 
  * Alice moves three presents from node 3 to node 1. 
  * Bob moves three presents from node 4 to node 3. 
  * Alice moves three presents from node 3 to node 1. 



Bob is now unable to make a move and hence loses.

Root node 2

Bob always wins in this case. One such gameplay is:

  * Alice moves four presents from node 4 to node 3. 
  * Bob moves four presents from node 5 to node 2. 
  * Alice moves six presents from node 3 to node 1. 
  * Bob moves six presents from node 1 to node 2. 



Alice is now unable to make a move and hence loses.

Solution (in CPP):

Solution:
#include <functional>
#include <type_traits>
#include <bits/stdc++.h>

// #define ASC
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#define int long long
//
#define all(X) (X).begin(), (X).end()
#define reset(X) memset(X, 0, sizeof(X))

#define pb push_back
#define endl '\n'
#define fi first
#define se second


using namespace std;

bool flag_last_endl;

// const int mod = 1e9 + 9;
const int mod = 1e9 + 7;
// const int mod=998'244'353;


// const int &MOD = mod;

const int INF = 4e18 + 10;
// const int INF=2e9+10;


#define readv(x, n)   \
    vector<int> x(n); \
    for (auto &i : x) \
        cin >> i;

#define rep(i, x,y) for(int i = x;i<y;i++)




// template<typename ...>
// using to_void = void; // maps everything to void, used in non-evaluated contexts

// template<typename T, typename = void>
// struct is_container : std::false_type
// {};

// template<typename T>
// struct is_container<T,
//         to_void<decltype(std::declval<T>().begin()),
//                 decltype(std::declval<T>().end()),
//                 typename T::value_type
//         >> : std::true_type // will  be enabled for iterable objects
// {};

// template<typename T>
// void flush(const T &data, typename std::enable_if<std::is_fundamental<T>::value>::type* = nullptr)
// {

//     cout<<data<<" ";
// }

// template<typename T>
// void flush(const T &data,
//     typename std::enable_if<!std::is_fundamental<T>::value>::type* = nullptr,
//     typename std::enable_if<!is_container<T>::value>::type* = nullptr)
// {
//     cerr<<"Make sure << is overloaded"<<endl;
//     cout<<data<<" ";
// }

// template<typename T>
// void flush(const T &data, typename std::enable_if<is_container<T>::value>::type* = nullptr)
// {
//     for(auto it=begin(data);it!=end(data);++it)
//     {
//         flush(*it);
//     }

//     // Need to get rid of this endl // Somebody help pls
//     cout<<endl;
// }

std::ostream& operator << (std::ostream& stream, const std::string& str)
    {
    stream << str.c_str();
    return stream;
    }

std::wostream& operator << (std::wostream& stream, const std::wstring& str)
    {
    stream << str.c_str();
    return stream;
    }

template <template <typename... Args> class ContainerT, typename... Args>
std::ostream& operator << (std::ostream& stream, const ContainerT <Args...> & container)
    {
    for (auto&& elem : container){

         cout<<" ";
         stream << elem;


       }
    stream<<endl;
    return stream;
    }

template <template <typename T, size_t N, typename... Args> class ContainerT, typename T, size_t N, typename... Args>
std::ostream& operator << (std::ostream& stream, const ContainerT <T, N, Args...> & container)
    {
    for (auto&& elem : container){

        cout<<" ";
         stream << elem;


       }
    stream<<endl;
    return stream;
    }

template<typename T1, typename T2>
std::ostream& operator << (std::ostream& stream, const std::pair <T1, T2> & val)
    {
    stream << val.first << " " << val.second ;
    stream<<endl;
    return stream;
    }


template <typename T>
    using v = vector<T>;

template <typename T>
    using vv = vector<vector<T>>;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int>> vvi; typedef vector<vector<double>> vvd;


typedef pair<int, int> pii;

template <typename T1, typename T2>
bool sort_by_sec(pair<T1, T2> a, pair<T1, T2> b)
{
    return make_pair(a.se, a.fi) < make_pair(b.se, b.fi);
}



int multiply(int a, int b, int in_mod) { return (int)(1LL * a * b % in_mod); }
int mult_identity(int a) { return 1; }

template<typename T>
array<T, 2> multiply(const array<T, 2> &a, const array<T, 2> &b, int mod);
template<typename T>
array<T, 2> mult_identity(array<T, 2> a) { return {1}; }

const double PI = acosl(-1);





template<typename T>
T power(T a, int b, int in_mod)
{

    T prod = mult_identity(a);
    T mult = a ;
    // int mult = a % in_mod;
    while (b != 0)
    {
        if (b % 2)
        {
            prod = multiply(prod, mult, in_mod);
        }
        mult = multiply(mult, mult, in_mod);
        b /= 2;
    }
    return prod;
}
int mod_inv(int q, int in_mod)
{

    return power(q, in_mod - 2, in_mod);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define stp cout << fixed << setprecision(15);


// -----------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//--------------Lubba_________________________________Lubba--------------------
//------------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
// -----------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//--------------Lubba_________________________________Lubba--------------------
//------------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
// -----------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//--------------Lubba_________________________________Lubba--------------------
// ------------------------------|||||||||||||----------------------------------



const int maxn =1e5 + 100;
vi adj[maxn];


vvi table;

vi a;
int k;

vi cycle_shift(vi t, bool flag)
{
    if(flag)
    {
        t.insert(t.end(), t[0]);
        t.erase(t.begin());
    }
    else
    {
        t.insert(t.begin(), t.back());
        t.erase(t.end() - 1);

    }
    return t;
}
void dfs(int root, int parent, int depth)
{

    if(a[root])
        table[root][0]^=a[root];

    for(auto i:adj[root])
    {
        if(i!=parent)
        {
            dfs(i,root, depth+1);

            vi ll = cycle_shift(table[i], false);
            for(int l= 0;l<2*k;l++)
                table[root][l]^= ll[l];

        }
    }
}

vi ans;
void reroot(int root, int parent)
{
    for(int i = k;i<2*k;i++)
        ans[root]^=table[root][i];
    ans[root] = (ans[root]>0);

    for(auto i:adj[root])
    {
        if(i!=parent)
        {

            vi back_root  = table[root];
            vi back_i  = table[i];

            vi kl = cycle_shift(table[i], false);

            for(int l= 0;l<2*k;l++)
                table[root][l] ^= kl[l];


            table[root] = cycle_shift(table[root], false);


            for(int l= 0;l<2*k;l++)
                table[i][l] ^= table[root][l];




            reroot(i,root);

            swap(back_root, table[root]);
            swap(back_i, table[i]);

        }
    }
}
void solve()
{
    int n;
    cin>>n>>k;

    for(int i= 0;i<n-1;i++)
    {
        int x, y;
        cin>>x>>y;

        x--;
        y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    a.resize(n);
    for(int i= 0;i<n;i++)
    {
        cin>>a[i];
    }

    ans.resize(n);
    table.resize(maxn);
    for(auto &i:table)
        i.resize(2*k);

    dfs(0, 0, 0);

    reroot(0,0);
    cout<<ans<<endl;

}





// -----------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//--------------Lubba_________________________________Lubba--------------------
//------------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
// -----------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//--------------Lubba_________________________________Lubba--------------------
//------------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
// -----------------------------|||||||||||||----------------------------------
//--------------Lubba_________________________________Lubba--------------------
//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//--------------Lubba_________________________________Lubba--------------------
//------------------------------|||||||||||||----------------------------------



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);
#ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen("INPUT.txt", "r", stdin);
        freopen("OUTPUT.txt", "w", stdout);
    }
#else
    #ifdef ASC
    if (fopen("codes.in", "r"))
    {
        freopen("codes.in", "r", stdin);
        freopen("codes.out", "w", stdout);
    }

    #endif

#endif
    auto clk = clock();
    // -------------------------------------Code starts here---------------------------------------------------------------------

    signed t = 1;
    // cin >> t;
//
    for (signed test = 1; test <= t; test++)
    {
        // cout<<"Case #"<<test<<": ";
        // cout<<endl;

        solve();
    }

    // -------------------------------------Code ends here------------------------------------------------------------------

    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "\nTime: " << ((double)clk) / CLOCKS_PER_SEC << "\n";
    return 0;
}