struct Node {
    Node *lc, *rc;
    int l, r;
    long long val;
    int tag;
    inline void clear() { val = tag = 0; }
    inline void cover(const int delta) { tag += delta, val += (long long)delta * (r - l + 1); }
    inline void pushDown() { if (tag) lc->cover(tag), rc->cover(tag), tag = 0; }
    inline void update(const int l, const int r, const int delta) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) cover(delta);
        else pushDown(), lc->update(l, r, delta), rc->update(l, r, delta), val = lc->val + rc->val;
    }
    inline long long query(const int l, const int r) {
        register long long ret = 0;
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return val;
        else return pushDown(), ret += lc->query(l, r), ret += rc->query(l, r), ret;
    }
} pool[(MAXN + 10) << 4], *root, *tail = pool;
inline void build(Node *&rt, const int l, const int r, int *a) {
    rt = tail++, rt->clear(), rt->l = l, rt->r = r;
    if (l == r) { rt->val = a[l]; return; }
    register int mid = l + r >> 1;
    build(rt->lc, l, mid, a), build(rt->rc, mid + 1, r, a);
    rt->val = rt->lc->val + rt->rc->val;
}

const int MAXN = 100000;
int phi[MAXN + 10], prime[MAXN + 10], mu[MAXN + 10], tot;
bool vis[MAXN + 10];
inline void init() {
    mu[1] = phi[1] = 1;
    for (register int i = 2; i <= MAXN; i++) {
        if (!vis[i]) prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
        for (register int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j], mu[i * prime[j]] = 0;
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1), mu[i * prime[j]] = -mu[i];
        }
    }
}

const int MAXN = 10010;
struct Node {
    int v, w;
    Node(int v, int w) : v(v), w(w) {}
};
vector<Node> edge[MAXN];
inline void addEdge(int u, int v, int w) {
    edge[u].push_back(Node(v, w));
    edge[v].push_back(Node(u, v));
}