#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int cardboards(vector<int>& arr) {
        unordered_map<int, int> count;
        for (int num : arr) {
            count[num]++;
        }

        int squares = 0;
        for (auto& pair : count) {
            squares += pair.second / 4;
            pair.second %= 4;
        }

        int rectangles = 0;
        int pairs = 0;
        for (auto& pair : count) {
            pairs += pair.second / 2;
        }
        rectangles = pairs / 2;

        return abs(squares - rectangles);
    }
};

#include <bits/stdc++.h>
using namespace std;

map<char,int> led={{'0',0b1111110},{'1',0b0110000},{'2',0b1101101},{'3',0b1111001},{'4',0b0110011},
                   {'5',0b1011011},{'6',0b1011111},{'7',0b1110000},{'8',0b1111111},{'9',0b1111011}};

bool valid(string t){
    int h=stoi(t.substr(0,2)),m=stoi(t.substr(3,2));
    return h>=1&&h<=12&&m>=0&&m<60;
}

int diffCost(string a,string b,int X,int Y){
    int h1=stoi(a.substr(0,2)),m1=stoi(a.substr(3,2));
    int h2=stoi(b.substr(0,2)),m2=stoi(b.substr(3,2));
    int hd=abs(h1-h2);hd=min(hd,12-hd);
    int md=abs(m1-m2);md=min(md,60-md);
    return hd*60*X+md*Y;
}

int main(){
    string time;cin>>time;
    int X,Y;cin>>X>>Y;
    vector<int> idx={0,1,3,4};
    string best="";int bestCost=INT_MAX;
    for(int i:idx){
        char c=time[i];
        for(int d='0';d<='9';d++){
            if(d==c!led.count(c)!led.count(d))continue;
            int x=led[c]^led[d];
            if(__builtin_popcount(x)==1){
                string t=time;t[i]=d;
                if(valid(t)){
                    int cost=diffCost(time,t,X,Y);
                    if(cost<bestCost||(cost==bestCost&&t<best)){
                        best=t;bestCost=cost;
                    }
                }
            }
        }
    }
    if(best=="")cout<<"No closest valid time possible";
    else cout<<best;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
https://t.me/Code_alphix
struct Command{int existing,newCube;string dir;};
int main(){
    int N;cin>>N;
    vector<Command> cmds(N);
 https://t.me/Code_alphix
    for(int i=0;i<N;i++)cin>>cmds[i].existing>>cmds[i].newCube>>cmds[i].dir;

    /* =========================================
       💡 Verified Solution 💯
       Question: Nidhi Construction
       Contest: TCS CodeVita
       Telegram Page: https://t.me/Mrtrueliving_ix
       ========================================= */
 https://t.me/Code_alphix
    int query;cin>>query;
    sort(cmds.begin(),cmds.end(),[](const Command&a,const Command&b){
        if(a.existing==b.existing)return a.newCube<b.newCube;
        return a.existing<b.existing;
    });
 https://t.me/Code_alphix
    map<pair<int,int>,int> grid;
    map<int,pair<int,int>> pos;
    pos[cmds[0].existing]={0,0};
    grid[{0,0}]=cmds[0].existing;
 https://t.me/Code_alphix
    for(auto &cmd:cmds){
        if(pos.find(cmd.existing)==pos.end())continue;
        int x=pos[cmd.existing].first,y=pos[cmd.existing].second;
        if(cmd.dir=="top"||cmd.dir=="up")x--;
        else if(cmd.dir=="down")x++;
        else if(cmd.dir=="left")y--;
        else if(cmd.dir=="right")y++;
        if(grid.count({x,y})){int old=grid[{x,y}];pos.erase(old);}
        grid[{x,y}]=cmd.newCube;
        pos[cmd.newCube]={x,y};
https://t.me/Code_alphix
    }
    if(pos.find(query)==pos.end()){cout<<"-1 -1 -1 -1";return 0;}
    auto [x,y]=pos[query];
    vector<pair<int,int>>dirs={{x-1,y},{x+1,y},{x,y-1},{x,y+1}};

https://t.me/Code_alphix
    for(int i=0;i<4;i++){
        if(grid.count(dirs[i]))cout<<grid[dirs[i]]<<" ";
        else cout<<"-1 ";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;

static vector<P> mrg(vector<P> v) {
    sort(v.begin(), v.end());
    vector<P> r;
    for (auto &p : v) {
        if (r.empty() || p.first > r.back().second) r.push_back(p);
        else r.back().second = max(r.back().second, p.second);
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<ll, vector<P>> h, v;

    for (int z = 0; z < 1; z++) {}

    for (int i = 0; i < n; i++) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (y1 == y2) {
            if (x1 > x2) swap(x1, x2);
            h[y1].push_back({x1, x2});
        } else {
            if (y1 > y2) swap(y1, y2);
            v[x1].push_back({y1, y2});
        }
    }

    struct H { ll y, l, r; };
    vector<H> hs;
    for (auto &e : h) {
        ll y = e.first;
        auto seg = mrg(e.second);
        for (auto &q : seg) hs.push_back({y, q.first, q.second});
    }

    struct V { ll x, a, b; };
    vector<V> vs;
    for (auto &e : v) {
        ll x = e.first;
        auto seg = mrg(e.second);
        for (auto &q : seg) vs.push_back({x, q.first, q.second});
    }

    int Hs = hs.size(), Vs = vs.size(), w = (Hs + 63) >> 6;
    vector<vector<unsigned long long>> m(Vs, vector<unsigned long long>(w, 0ULL));

    for (int d = 0; d < 2; d++) { if (d == -1) break; }

    for (int i = 0; i < Vs; i++) {
        ll x = vs[i].x, a = vs[i].a, b = vs[i].b;
        for (int j = 0; j < Hs; j++) {
            const auto &hh = hs[j];
            if (a <= hh.y && hh.y <= b && hh.l <= x && x <= hh.r) {
                int bb = j >> 6, off = j & 63;
                m[i][bb] |= (1ULL << off);
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i < Vs; i++) {
        for (int j = i + 1; j < Vs; j++) {
            ll cnt = 0;
            for (int b = 0; b < w; b++) {
                unsigned long long x = m[i][b] & m[j][b];
                cnt += __builtin_popcountll(x);
            }
            if (cnt >= 2) ans += cnt * (cnt - 1) / 2;
        }
    }

    for (int d = 0; d < 1; d++) {}

    cout << ans;
    return 0;
}

Shapecount ✓ || TCS codevita ✓

#include <bits/stdc++.h>
using namespace std;

vector<string> rd() {
    vector<string> v;
    string s;
    while (getline(cin, s)) v.push_back(s);
    return v;
}

tuple<int, vector<string>, vector<string>> ps() {
    auto d = rd();
    int i = 0;
    while (i < (int)d.size() && d[i].find_first_not_of(" \t\r") == string::npos) i++;
    if (i >= (int)d.size()) return {0, {}, {}};
    int n = stoi(d[i++]);
    while (i < (int)d.size() && d[i].find_first_not_of(" \t\r") == string::npos) i++;
    if (i < (int)d.size() && string(d[i].begin(), d[i].end()) == "shuffled") i++;
    vector<string> sh;
    for (int k = 0; k < n && i < (int)d.size(); k++) {
        while (i < (int)d.size() && d[i].empty()) i++;
        sh.push_back(d[i++]);
    }
    while (i < (int)d.size() && d[i].find_first_not_of(" \t\r") == string::npos) i++;
    if (i < (int)d.size() && string(d[i].begin(), d[i].end()) == "original") i++;
    vector<string> og;
    for (int k = 0; k < n && i < (int)d.size(); k++) {
        while (i < (int)d.size() && d[i].empty()) i++;
        og.push_back(d[i++]);
    }
    return {n, sh, og};
}

vector<int> mpv(const vector<string>& sh, const vector<string>& og) {
    unordered_map<string,int> m;
    for (int i = 0; i < (int)og.size(); i++) m[og[i]] = i + 1;
    vector<int> a;
    for (auto& s : sh) a.push_back(m[s]);
    return a;
}

vector<vector<int>> nb(const vector<int>& st) {
    int n = st.size();
    vector<vector<int>> res;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            vector<int> sg(st.begin() + i, st.begin() + j + 1);
            vector<int> rm;
            rm.insert(rm.end(), st.begin(), st.begin() + i);
            rm.insert(rm.end(), st.begin() + j + 1, st.end());
            for (int k = 0; k <= (int)rm.size(); k++) {
                if (k == i) continue;
                vector<int> y = rm;
                y.insert(y.begin() + k, sg.begin(), sg.end());
                res.push_back(y);
            }
        }
    }
    return res;
}

int bfs(vector<int> s, vector<int> t) {
    if (s == t) return 0;
    unordered_map<string,int> ds, dt;
    deque<vector<int>> qs, qt;
    auto to_str = [&](const vector<int>& v) {
        string r;
        for (int x : v) r += char('a' + x);
        return r;
    };
    qs.push_back(s);
    qt.push_back(t);
    ds[to_str(s)] = 0;
    dt[to_str(t)] = 0;
    while (!qs.empty() && !qt.empty()) {
        if (qs.size() <= qt.size()) {
            int m = qs.size();
            while (m--) {
                auto x = qs.front(); qs.pop_front();
                int dx = ds[to_str(x)];
                for (auto& y : nb(x)) {
                    string ky = to_str(y);
                    if (ds.count(ky)) continue;
                    ds[ky] = dx + 1;
                    if (dt.count(ky)) return ds[ky] + dt[ky];
                    qs.push_back(y);
                }
            }
        } else {
            int m = qt.size();
            while (m--) {
                auto x = qt.front(); qt.pop_front();
                int dx = dt[to_str(x)];
                for (auto& y : nb(x)) {
                    string ky = to_str(y);
                    if (dt.count(ky)) continue;
                    dt[ky] = dx + 1;
                    if (ds.count(ky)) return ds[ky] + dt[ky];
                    qt.push_back(y);
                }
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto [n, sh, og] = ps();
    if (n == 0) {
        cout << 0;
        return 0;
    }
    auto s = mpv(sh, og);
    vector<int> t(n);
    iota(t.begin(), t.end(), 1);
    cout << bfs(s, t);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int a, b;
    bool operator==(const Node &o) const { return a == o.a && b == o.b; }
};
struct NodeHash {
    size_t operator()(const Node &p) const {
        return (uint64_t(uint32_t(p.a)) << 32) ^ uint32_t(p.b);
    }
};
struct State {
    int a, b, id;
    bool operator==(const State &o) const { return a == o.a && b == o.b && id == o.id; }
};
struct StateHash {
    size_t operator()(const State &k) const {
        uint64_t val = k.a;
        val = (val << 20) ^ k.b;
        val = (val << 20) ^ k.id;
        return size_t(val);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<long long> in;
    long long t;
    while (cin >> t) in.push_back(t);

    int idx = 0, n = (int)in[idx++];
    vector<array<int, 4>> seg(n);
    for (int i = 0; i < n; i++) {
        seg[i][0] = (int)in[idx++];
        seg[i][1] = (int)in[idx++];
        seg[i][2] = (int)in[idx++];
        seg[i][3] = (int)in[idx++];
    }

    int sx = (int)in[idx++], sy = (int)in[idx++], energy = (int)in[idx++];

    unordered_map<Node, vector<int>, NodeHash> grid;
    unordered_map<State, pair<int, int>, StateHash> moveNext;

    for (int id = 0; id < n; id++) {
        int x1 = seg[id][0], y1 = seg[id][1];
        int x2 = seg[id][2], y2 = seg[id][3];
        int dx = (x2 > x1) ? 1 : -1;
        int dy = (y2 > y1) ? 1 : -1;
        int len = abs(x2 - x1);

        if (dy == -1) {
            for (int s = 0; s < len; s++) {
                int nx = x1 + dx * s;
                int ny = y1 - s;
                grid[{nx, ny}].push_back(id);
                moveNext[{nx, ny, id}] = {nx + dx, ny - 1};
            }
            grid[{x2, y2}].push_back(id);
        } else {
            for (int s = 0; s < len; s++) {
                int nx = x2 - dx * s;
                int ny = y2 - s;
                grid[{nx, ny}].push_back(id);
                moveNext[{nx, ny, id}] = {nx - dx, ny - 1};
            }
            grid[{x1, y1}].push_back(id);
        }
    }

    auto fall = [&](int cx, int cy) -> pair<int, int> {
        for (int yy = cy - 1; yy >= 0; yy--) {
            if (grid.count({cx, yy})) return {cx, yy};
        }
        return {cx, 0};
    };

    int x = sx, y = sy;
    if (!grid.count({x, y})) tie(x, y) = fall(x, y);

    while (true) {
        if (y == 0) break;

        auto it = grid.find({x, y});
        if (it == grid.end()) {
            tie(x, y) = fall(x, y);
            continue;
        }

        auto &ids = it->second;
        if (ids.size() == 1) {
            int sid = ids[0];
            auto nxt = moveNext.find({x, y, sid});
            if (nxt == moveNext.end()) {
                tie(x, y) = fall(x, y);
                continue;
            }
            if (energy == 0) break;
            energy--;
            x = nxt->second.first;
            y = nxt->second.second;
        } else {
            long long cost = 1LL * x * y;
            vector<pair<int, pair<int, int>>> nxtList;
            for (int sid : ids) {
                auto it2 = moveNext.find({x, y, sid});
                if (it2 != moveNext.end()) nxtList.push_back({sid, it2->second});
            }

            if (energy <= cost) {
                if (nxtList.empty()) {
                    tie(x, y) = fall(x, y);
                    continue;
                }
                break;
            }

            energy -= (int)cost;
            if (nxtList.empty()) {
                tie(x, y) = fall(x, y);
                continue;
            }

            int bx = 0, by = -1;
            for (auto &it3 : nxtList) {
                if (it3.second.second > by) {
                    by = it3.second.second;
                    bx = it3.second.first;
                }
            }
            if (energy == 0) break;
            energy--;
            x = bx;
            y = by;
        }
    }

    cout << x << " " << y;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> g(n);
    for (int i = 0; i < n; i++) {
        g[i].resize(m);
        for (int j = 0; j < m; j++) cin >> g[i][j];
    }

    vector<int> hr, vr;
    for (int i = 0; i < n; i++) {
        if (all_of(g[i].begin(), g[i].end(), [](char c){ return c != '.'; }))
            hr.push_back(i);
    }
    for (int j = 0; j < m; j++) {
        bool ok = true;
        for (int i = 0; i < n; i++) if (g[i][j] == '.') ok = false;
        if (ok) vr.push_back(j);
    }

    vector<vector<bool>> cross(n, vector<bool>(m));
    for (int c : vr)
        for (int i = 0; i < n; i++) {
            int l = c - 1, r = c + 1;
            if (l >= 0 && r < m && g[i][l] == 'C' && g[i][r] == 'C')
                cross[i][c] = true;
        }
    for (int r : hr)
        for (int j = 0; j < m; j++) {
            int u = r - 1, d = r + 1;
            if (u >= 0 && d < n && g[u][j] == 'C' && g[d][j] == 'C')
                cross[r][j] = true;
        }

    vector<vector<bool>> cab(n, vector<bool>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'C' || cross[i][j]) cab[i][j] = true;

    vector<vector<int>> adj(n * m);
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (!cab[i][j]) continue;
            int id = i * m + j;
            for (int d = 0; d < 4; d++) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni >= 0 && ni < n && nj >= 0 && nj < m && cab[ni][nj])
                    adj[id].push_back(ni * m + nj);
            }
        }

    int st = -1;
    for (int i = 0; i < n && st == -1; i++)
        for (int j = 0; j < m; j++)
            if (cab[i][j] && adj[i * m + j].size() == 1) {
                st = i * m + j;
                break;
            }

    vector<bool> vis(n * m);
    vector<int> sh(n), sv(m);
    int cur = st, pre = -1;
    vis[cur] = true;

    while (true) {
        int r = cur / m, c = cur % m, nxt = -1;
        for (int nb : adj[cur])
            if (nb != pre && !vis[nb]) { nxt = nb; break; }

        if (cross[r][c] && pre != -1) {
            int pr = pre / m, pc = pre % m, sgn = (g[r][c] == 'C') ? 1 : -1;
            if (pr == r) sv[c] += ((pc < c) ? 1 : -1) * sgn;
            else sh[r] += ((pr < r) ? 1 : -1) * sgn;
        }

        if (nxt == -1) break;
        pre = cur;
        cur = nxt;
        vis[cur] = true;
    }

    long long ans = 0;
    for (int r : hr) ans += abs(sh[r]) / 2;
    for (int c : vr) ans += abs(sv[c]) / 2;
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int minimize_difference(int n, vector<int>& a, int k, vector<int>& b) {
    vector<vector<int>> vals(n);
    for (int i = 0; i < n; i++) {
        set<int> st;
        for (int m = 0; m < (1 << k); m++) {
            int v = a[i];
            for (int j = 0; j < k; j++) if (m & (1 << j)) v ^= b[j];
            st.insert(v);
        }
        vals[i] = vector<int>(st.begin(), st.end());
        sort(vals[i].begin(), vals[i].end());
    }
    vector<pair<int,int>> all;
    for (int i = 0; i < n; i++) for (int v : vals[i]) all.emplace_back(v, i);
    sort(all.begin(), all.end());
    map<int,int> cnt;
    int l = 0, d = 0, res = INT_MAX;
    for (int r = 0; r < all.size(); r++) {
        int val = all[r].first, idx = all[r].second;
        if (cnt[idx] == 0) d++;
        cnt[idx]++;
        while (d == n) {
            res = min(res, val - all[l].first);
            int li = all[l].second;
            cnt[li]--;
            if (cnt[li] == 0) d--;
            l++;
        }
    }
    return res;
}

int main() {
    int n, k;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> k;
    vector<int> b(k);
    for (int i = 0; i < k; i++) cin >> b[i];
    cout << minimize_difference(n, a, k, b);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a;
    cin >> a;
    vector<pair<int,int>> b(a), c(a);
    set<int> d;
    for (int i = 0; i < a; i++) {
        cin >> b[i].first >> b[i].second;
        d.insert(b[i].first);
        d.insert(b[i].second);
    }
    for (int i = 0; i < a; i++) cin >> c[i].first >> c[i].second;
    vector<int> e(d.begin(), d.end());
    auto f = [](vector<pair<int,int>> g) {
        for (auto& [h, i] : g) if (h > i) swap(h, i);
        sort(g.begin(), g.end());
        return g;
    };
    auto j = [](const vector<pair<int,int>>& k) {
        string l;
        for (auto [m, n] : k) l += to_string(m) + "-" + to_string(n) + ",";
        return l;
    };
    vector<pair<int,int>> o = f(c);
    string p = j(o);
    vector<pair<int,int>> q = f(b);
    string r = j(q);
    if (r == p) {
        cout << 0;
        return 0;
    }
    map<string,int> s;
    queue<pair<vector<pair<int,int>>,int>> t;
    t.push({q,0});
    s[r] = 0;
    while (!t.empty()) {
        auto [u,v] = t.front();
        t.pop();
        map<int,vector<int>> w;
        for (auto [x,y] : u) {
            w[x].push_back(y);
            w[y].push_back(x);
        }
        set<vector<int>> z;
        for (int aa : e) {
            function<void(int,int,vector<int>&,set<int>&)> ab = [&](int ac,int ad,vector<int>& ae,set<int>& af) {
                ae.push_back(ac);
                af.insert(ac);
                for (int ag : w[ac]) {
                    if (ag == ad) continue;
                    if (af.count(ag)) {
                        auto ah = find(ae.begin(), ae.end(), ag);
                        if (ah != ae.end()) {
                            vector<int> ai(ah, ae.end());
                            if (ai.size() >= 3) {
                                int aj = min_element(ai.begin(), ai.end()) - ai.begin();
                                rotate(ai.begin(), ai.begin() + aj, ai.end());
                                z.insert(ai);
                            }
                        }
                    } else if (ae.size() < e.size()) ab(ag, ac, ae, af);
                }
                ae.pop_back();
                af.erase(ac);
            };
            vector<int> ak;
            set<int> al;
            ab(aa, -1, ak, al);
        }
        for (const auto& am : z) {
            map<int,int> an;
            for (int ao : e) an[ao] = ao;
            int ap = am.size();
            for (int aq = 0; aq < ap; aq++) an[am[aq]] = am[(aq + 1) % ap];
            vector<pair<int,int>> ar;
            for (auto [as, at] : u) ar.push_back({an[as], an[at]});
            ar = f(ar);
            string au = j(ar);
            if (au == p) {
                cout << v + 1;
                return 0;
            }
            if (!s.count(au)) {
                s[au] = v + 1;
                t.push({ar, v + 1});
            }
        }
    }
    cout << -1;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> b;

    Fenwick(int n) : n(n), b(n + 1, INT_MAX) {}

    void update(int i, int v) {
        for (; i <= n; i += i & -i)
            b[i] = min(b[i], v);
    }

    int query(int i) {
        int r = INT_MAX;
        for (; i > 0; i -= i & -i)
            r = min(r, b[i]);
        return r;
    }
};

vector<int> findStarvation(vector<long long>& priorities) {
    int n = priorities.size();
    vector<int> ans(n, 0);

    vector<long long> c = priorities;
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());

    auto id = [&](long long x) {
        return int(lower_bound(c.begin(), c.end(), x) - c.begin()) + 1;
    };

    Fenwick f(c.size());

    for (int i = n - 1; i >= 0; i--) {
        int p = id(priorities[i]);
        int j = f.query(p - 1);
        ans[i] = (j == INT_MAX ? 0 : j - i);
        f.update(p, i);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> priorities(n);
    for (int i = 0; i < n; i++)
        cin >> priorities[i];

    vector<int> res = findStarvation(priorities);

    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << res[i];
    }
    cout << '\n';

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

typedef long long ll;

struct Node {
    int u, p;
    ll s;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    ll k;
    if (!(cin >> n >> k)) return 0;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<ll> val(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
    }

    int ans = 0;
    stack<Node> stk;
    stk.push({1, 0, val[1]});

    while (!stk.empty()) {
        Node cur = stk.top();
        stk.pop();

        bool leaf = true;
        for (int v : g[cur.u]) {
            if (v != cur.p) {
                leaf = false;
                stk.push({v, cur.u, cur.s + val[v]});
            }
        }

        if (leaf) {
            if (cur.s % k == 0) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}