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

#define ff first
#define sc second
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(),(x).end()

const int maxN = 2 * 1e5;

vector<ll> d;
vector<bool> f;
vector<int> g[maxN], s, t;
int n, m, par[maxN][20], dep[maxN], in[maxN], out[maxN], tim;
void dfs(int v, int p) {
    in[v] = ++tim;
    par[v][0] = p; dep[v] = dep[p] + 1;
    for (int u : g[v]) {
        if (u == p) continue;
        dfs(u, v);
    }

    out[v] = ++tim;
}

bool is_anc(int x, int y) {
    return (in[x] <= in[y] && out[x] >= out[y]);
}
int lca(int x, int y) {
    if (is_anc(x, y)) return x;
    if (is_anc(y, x)) return y;
    for (int j = 19; j >= 0; j--) {
        if (!is_anc(par[x][j], y)) x = par[x][j];
    } return par[x][0];
}
std::vector<int> solve(
    std::vector<std::pair<int, int>> r,
    std::vector<long long> _d,
    std::vector<int> _s,
    std::vector<int> _t,
    std::vector<bool> _f
) {

    for (auto i : r) {
        g[i.ff].pb(i.sc);
        g[i.sc].pb(i.ff);
    }

    d = _d; s = _s; t = _t; f = _f;
    n = (int)r.size() + 1; m = (int)d.size();

    bool has[n]{};
    for (int i = 0; i < m; i++) {
        if (f[i]) has[s[i]] = 1;
    }

    for (int i = 0; i < m; i++) {
        if (has[s[i]]) f[i] = 1;
    }

    vector<int> seg[n];
    vector<pii> v[n][2]; vector<int> ans(m, -1);
    for (int i = 0; i < m; i++) {
        if (f[i]) ans[i] = 0;
        if (s[i] <= t[i]) {
            v[s[i]][s[i] % 2].pb({i, 0});
            v[t[i] + 1][s[i] % 2].pb({i, 1});
        } else {
            seg[s[i]].pb(i);
        }
    }


    set<pii> inf[2], good[2];
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < 2; k++) {
            for (pii j : v[i][k]) {
                if (j.sc == 0) {
                    if (f[j.ff] == 0) good[k].insert({s[j.ff], j.ff});
                    else inf[k].insert({s[j.ff], j.ff});
                } else {
                    good[k].erase({s[j.ff], j.ff});
                    inf[k].erase({s[j.ff], j.ff});
                }
            }
        }

        for (int j : seg[i]) {
            if (ans[j] == -1 && inf[i % 2].size() > 0) {
                pii cur = *inf[i % 2].rbegin();
                int pos = (cur.ff + s[j]) / 2;
                ans[j] = s[j] - pos;
            }

            if (ans[j] == -1) continue;
            int pos = s[j] - ans[j];
            int mn = s[j] - 2 * (s[j] - t[j]);
            auto it = good[i % 2].lower_bound({mn, -1});
            vector<pii> ers;
            for ( ; it != good[i % 2].end(); it++) {
                pii cur = *it;
                if (cur.ff > pos) break;
                f[cur.sc] = 1; ans[cur.sc] = (cur.ff + s[j]) / 2 - cur.ff;
                inf[i % 2].insert(cur); ers.pb(cur);
            }

            for (pii j : ers) good[i % 2].erase(j);
        }
    }

    for (int i = 0; i < m; i++) {
        if (ans[i] == -1) ans[i] = 0;
        else ans[i] = abs(s[i] - t[i]) + 1 - ans[i];
    }
    return ans;
}


// signed main() {
//     int n, m;

//     std::cin >> n;
//     std::cin >> m;

//     std::vector<std::pair<int, int>> edges = {};
//     std::vector<long long> day;
//     std::vector<int> start;
//     std::vector<int> target;
//     std::vector<bool> infected;

//     for (int i = 0; i < n - 1; i++) {
//         int u, v;
//         std::cin >> u >> v;
//         edges.emplace_back(u, v);
//     }

//     for (int i = 0; i < m; i++) {
//         long long _d, _s, _t, _i;
//         std::cin >> _d >> _s >> _t >> _i;
//         day.push_back(_d);
//         start.push_back(_s);
//         target.push_back(_t);
//         infected.push_back(_i);
//     }

//     const auto ans = solve(edges, day, start, target, infected);
//     for (const auto it : ans) {
//         std::cout << it << std::endl;
//     }

//     return 0;
// }
