int jmp[20][MAXN], dep[MAXN];

// add child to parent
void addchild(int p, int v) {
    jmp[0][v] = p;
    dep[v] = dep[p] + 1;
}

// prepare jumps
void build() {
    for (int i = 1; i < 20; i++) for(int j = 0; j < MAXN; j++) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}

// kth ancestor of i
int kth(int i, int k) {
    for(int x = 19; x >= 0; x--) if (k & (1<<x)) i = jmp[x][i];
    return i;
}

// LCA of a, b
int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    a = kth(a, dep[a] - dep[b]);
    if(a == b) return a;
    for(int x = 19; x >= 0; x--) if(jmp[x][a] != jmp[x][b]) a = jmp[x][a], b = jmp[x][b];
    return jmp[0][a];
}

// REQUIRES binpow
ll modinv(ll x, ll MOD) {
    return binpow(x, MOD - 2, MOD);
}

class DSU {
  public:
    vector<int> parents;
    vector<int> sizes;
    DSU(int size) : parents(size), sizes(size, 1) {
        for (int i = 0; i < size; i++) { parents[i] = i; }
    }

    /** @return the "representative" node in x's component */
    int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

    /** @return whether the merge changed connectivity */
    bool unite(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if (x_root == y_root) { return false; }

        if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
        sizes[x_root] += sizes[y_root];
        parents[y_root] = x_root;
        return true;
    }

    /** @return whether x and y are in the same connected component */
    bool connected(int x, int y) { return find(x) == find(y); }
};

template <class T>
class Segtree {
private:
    int N;  // array size
    vector<T> t;

    T combine(T a, T b) {
        return a + b;
    }

public:
    Segtree(int size) : N(size), t(2 * size, T()) {}

    void build() {  // Build the tree
        for (int i = N - 1; i > 0; i--) 
            t[i] = combine(t[i<<1], t[i<<1|1]);
    }

    void modify(int p, T value) {  // Set value at position p
        for (t[p += N] = value; p > 1; p >>= 1) 
            t[p >> 1] = combine(t[p], t[p^1]);
    }

    T query(int l, int r) {  // Query on interval [l, r)
        T res = T();
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = combine(res, t[l++]);
            if (r&1) res = combine(res, t[--r]);
        }
        return res;
    }
};

template <class T, class K>
class LazySegtree {
private:
    int N;  // array size
    int h;
    vector<T> t;
    vector<K> d;

    T combine(T a, T b) {
        return a + b;
    }

    // k is the length of the segment
    T calc(T a, T b, K d, int k) {
        return max(a, b) + d;
    }

    // Update d[p]
    // k is the length of segment
    void apply(int p, K value, int k) {
        // Update t[p] as if it was already affected by d[p]
        t[p] += value;
        if (p < N) d[p] += value;
    }

public:
    LazySegtree(int size) : N(size), h(sizeof(int) * 8 - __builtin_clz(N)), t(2 * size, T()), d(size) {}

    void build(int l, int r) {
        int k = 2;
        for (l += N, r += N-1; l > 1; k <<= 1) {
            l >>= 1, r >>= 1;
            for (int i = r; i >= l; --i) t[i] = calc(t[i<<1], t[i<<1|1], d[i], k);
        }
    }

    void push(int l, int r) {
        int s = h, k = 1 << (h-1);
        for (l += N, r += N-1; s > 0; --s, k >>= 1) for (int i = l >> s; i <= r >> s; ++i) if (d[i] != 0) {
            apply(i<<1, d[i], k);
            apply(i<<1|1, d[i], k);
            d[i] = 0;
        }
    }

    void modify(int l, int r, K value) {
        if (value == 0) return;
        push(l, l + 1);
        push(r - 1, r);
        int l0 = l, r0 = r, k = 1;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1, k <<= 1) {
            if (l&1) apply(l++, value, k);
            if (r&1) apply(--r, value, k);
        }
        build(l0, l0 + 1);
        build(r0 - 1, r0);
    }

    T query(int l, int r) {
        push(l, l + 1);
        push(r - 1, r);
        T res = 0;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = calc(res, t[l++], 0, -1);
            if (r&1) res = calc(res, t[--r], 0, -1);
        }
        return res;
    }
};

// Can replace with any other function as long as any f[i] intersects with any other f[j] at most once
struct line {
    ll a, b;

    ll calc(ll x) { return a*x + b; }
    ld intersect(line two) { return (ld) (two.b - b) / (a - two.a); };
};

deque<line> hull;
vector<int> ints(MAXN + 1);
// iota(ints.begin(), ints.end(), 0);

// Find which f to use for some value of x
auto cmp = [&hull](int idx, ll x) { return hull[idx].intersect(hull[idx + 1]) < x; };
// int idx = *lower_bound(ints.begin(), ints.begin() + hull.size() - 1, x, cmp);

template <class T, int V>
class HeavyLight {
    int parent[V], heavy[V], depth[V];
    int root[V], treePos[V], subtree[V];
    Segtree<T> tree;

    template <class G>
    int dfs(const G& graph, int v) {
        int size = 1, maxSubtree = 0;
        for (int u : graph[v]) if (u != parent[v]) {
            parent[u] = v;
            depth[u] = depth[v] + 1;
            int subtree = dfs(graph, u);
            if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree;
            size += subtree;
        }
        subtree[v] = size;
        return size;
    }

    template <class G>
    void dfs2(const G& graph, int v, int& i) {
        treePos[v] = i++;
        if (heavy[v] != -1) dfs2(graph, heavy[v], i);
        for (int u : graph[v]) if (u != parent[v] && u != heavy[v]) dfs2(graph, u, i);
    }

    template <class BinaryOperation>
    void processPath(int u, int v, BinaryOperation op) {
        for (; root[u] != root[v]; v = parent[root[v]]) {
            if (depth[root[u]] > depth[root[v]]) swap(u, v);
            op(treePos[root[v]], treePos[v] + 1);
        }
        if (depth[u] > depth[v]) swap(u, v); op(treePos[u], treePos[v] + 1);
    }

public:
    template <class G>
    // Pass in adjacency list vector<vector<int>>
    HeavyLight(const G& graph) : tree(graph.size()) {
        int n = graph.size();
        fill_n(heavy, n, -1);
        parent[0] = -1;
        depth[0] = 0;
        dfs(graph, 0);
        for (int i = 0, currentPos = 0; i < n; ++i)
            if (parent[i] == -1 || heavy[parent[i]] != i)
                for (int j = i; j != -1; j = heavy[j])
                    root[j] = i;

        int k = 0;
        dfs2(graph, 0, k);
        }

    void set(int v, const T& value) {
        tree.modify(treePos[v], value);
    }

    // Need lazy segtree for this one
    void modifyPath(int u, int v, const T& value) {
        processPath(u, v, [this, &value](int l, int r) { tree.modify(l, r, value); });
    }

    T queryPath(int u, int v) {
        T res = T();
        processPath(u, v, [this, &res](int l, int r) { 
            // Combine
            res = combine(res, tree.query(l, r));
        });
        return res;
    }

    void modifySubtree(int v, const T& value) {
        tree.modify(treePos[v], treePos[v] + subtree[v], value);
    }

    void querySubtree(int v, const T& value) {
        return tree.query(treePos[v], treePos[v] + subtree[v]);
    }
};

// https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html#implementation
// only has edges from one side of bipartite graph to other
vector<vector<int>> kuhngraph;
// the matching vertex for each vertex on the other side of the graph
// if matching vertex won't be -1
vector<int> mt;
// only for side 1
vector<bool> used;

bool try_kuhn(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int to : g[v]) {
        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

// if N vertices on left side and M on right side
mt.assign(M, -1);
for (int v = 0; v < N; v++) {
    used.assign(N, false);
    try_kuhn(v);
}

for (int i = 0; i < M; i++) if (mt[i] != -1) {/* i on right side matches with mt[i] on left side */}

ll binpow(ll a, ll b, ll MOD) {
    a %= MOD;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

template <class T, int... Ns> struct BIT {
    T val = 0;
    void upd(T v) { val += v; }
    T query() { return val; }
};

template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
    BIT<T, Ns...> bit[N + 1];
    template <typename... Args> void upd(int pos, Args... args) {
        for (; pos <= N; pos += (pos & -pos)) bit[pos].upd(args...);
    }
    template <typename... Args> T sum(int r, Args... args) {
        T res = 0;
        for (; r; r -= (r & -r)) res += bit[r].query(args...);
        return res;
    }
    template <typename... Args> T query(int l, int r, Args... args) {
        return sum(r, args...) - sum(l - 1, args...);
    }
};
// Do like BIT<int, 1024, 1024> bit;

ll mobius[MOBIUSMAX];

void calcmobius() {
    mobius[1] = -1;
    mobius[0] = 0;
    for (int i = 2; i < MOBIUSMAX; i++) mobius[i] = 0;

    for (int i = 1; i < MOBIUSMAX; i++) {
        if (mobius[i]) {
            mobius[i] = -mobius[i];
            for (int j = 2 * i; j < MOBIUSMAX; j += i) { mobius[j] += mobius[i]; }
        }
    }
}