#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

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> infected)
{
    ll N = R.size() + 1;
    ll M = D.size();
    v infectionDay(M, -1);
    for (ll parity = 0; parity < 2; parity++)
    {
        map<ll, vtri> upLines;
        map<ll, vtri> rightLines;
        v constantThing(M);
        vp changingThing(M);
        v relevants;
        for (ll i = 0; i < M; i++)
        {
            if ((D[i] + S[i]) % 2 != parity) continue;
            relevants.pb(i);
            p start = p(S[i] + D[i], D[i] - S[i]);
            ll length = abs(T[i] - S[i]);
            p end = p(D[i] + T[i] + length, D[i] - T[i] + length);
            if (S[i] < T[i])
            {
                rightLines[start.s].eb(i, p(start.f, end.f));
                constantThing[i] = start.s;
                changingThing[i] = p(start.f, end.f);
            }
            else
            {
                upLines[start.f].eb(i, p(start.s, end.s));
                constantThing[i] = start.f;
                changingThing[i] = p(start.s, end.s);
            }
            if (infected[i]) infectionDay[i] = D[i];
        }
        for (auto x : upLines)
        {
            auto vals = x.s;
            vtri events;
            for (auto x : vals)
            {
                events.eb(x.s.f, p(1 + !infected[x.f], x.f));
                events.eb(x.s.s, p(3, x.f));
            }
            sort(all(events));
            ll infectedCnt = 0;
            for (auto x : events)
            {
                if (x.s.s != 3)
                {
                    if (infectedCnt > 0 && !infected[x.s.s])
                    {
                        infected[x.s.s] = true;
                        infectionDay[x.s.s] = D[x.s.s];
                    }
                    else if (infected[x.s.s]) infectedCnt++;
                }
                else
                {
                    if (infected[x.s.s]) infectedCnt--;
                }
            }
        }
        for (auto x : rightLines)
        {
            auto vals = x.s;
            vtri events;
            for (auto x : vals)
            {
                events.eb(x.s.f, p(1 + !infected[x.f], x.f));
                events.eb(x.s.s, p(3, x.f));
            }
            sort(all(events));
            ll infectedCnt = 0;
            for (auto x : events)
            {
                if (x.s.s != 3)
                {
                    if (infectedCnt > 0 && !infected[x.s.s])
                    {
                        infected[x.s.s] = true;
                        infectionDay[x.s.s] = D[x.s.s];
                    }
                    else if (infected[x.s.s]) infectedCnt++;
                }
                else
                {
                    if (infected[x.s.s]) infectedCnt--;
                }
            }
        }
        vtri allEvents;
        for (auto x : upLines)
        {
            for (auto y : x.s)
            {
                allEvents.eb(y.s.f, p(1, y.f));
                allEvents.eb(y.s.s, p(3, y.f));
            }
        }
        for (auto x : rightLines)
        {
            for (auto y : x.s)
            {
                allEvents.eb(x.f, p(2, y.f));
            }
        }
        sort(all(allEvents));
        map<ll, set<ll>> infectedUps;
        map<ll, set<ll>> uninfectedUps;
        for (auto evt : allEvents)
        {
            ll i = evt.s.s;
            ll y = evt.f;
            if (evt.s.f == 1)
            {
                if (infected[i]) infectedUps[constantThing[i]].insert(i);
                else
                {
                    uninfectedUps[constantThing[i]].insert(i);
                }
            }
            else if (evt.s.f == 2)
            {
                ll infectingStart = -1;
                if (infected[i])
                {
                    infectingStart = changingThing[i].f;
                }
                else
                {
                    // check if getting infected
                    auto ptr = infectedUps.lower_bound(changingThing[i].f);
                    if (ptr != infectedUps.end())
                    {
                        auto val = (*ptr);
                        if (val.f <= changingThing[i].s)
                        {
                            infected[i] = true; 
                            infectionDay[i] = (val.f + y) / 2;
                            infectingStart = infectionDay[i];
                        }
                    }
                }
                if (infectingStart != -1)
                {
                    while (true)
                    {
                        auto ptr = uninfectedUps.lower_bound(infectingStart);
                        if (ptr != uninfectedUps.end())
                        {
                            ll time = (*ptr).f;
                            if (time > changingThing[i].s) break;
                            set<ll> vals = (*ptr).s;
                            uninfectedUps.erase(ptr);
                            for (auto x : vals)
                            {
                                infectedUps[time].insert(x);
                                infected[x] = true;
                                infectionDay[x] = (time + y) / 2;
                            }
                        }
                        else break;
                    }
                }
            }
            else
            {
                if (infected[i])
                {
                    infectedUps[constantThing[i]].erase(i);
                    if (infectedUps[constantThing[i]].empty()) infectedUps.erase(constantThing[i]);
                }
                else
                {
                    uninfectedUps[constantThing[i]].erase(i);
                    if (uninfectedUps[constantThing[i]].empty()) uninfectedUps.erase(constantThing[i]);
                }
            }
        }
    }
    vector<int> res(M);
    for (ll i = 0; i < M; i++)
    {
        ll lastDay = D[i] + abs(T[i] - S[i]);
        if (infectionDay[i] == -1) res[i] = 0;
        else res[i] = lastDay - infectionDay[i] + 1;
    }
    return res;
}

/*
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;
}
/**/