#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
#define int ll
#warning :(( long longul vostru gen e so nenecesar
#define sz(x) ((int)(x).size())
using pii = pair<int, int>;
using tii = tuple<int, int, int>;

const int nmax = 15e4 + 5;

bool isinfected[nmax];
int wheninfected[nmax];
int rez[nmax];

struct LineSolver {
	int time;
	set<tuple<int, int, int>> infected[2][2];
	set<tuple<int, int, int>> notinfected[2][2];
	
	struct Event {
		int time;
		int infected, pozi, wheni, diri;
		int non, pozn, whenn, dirn;
		Event(int a, int b, int c, int d, int e, int f, int g, int h, int i): time(a), infected(b), pozi(c), wheni(d), diri(e), non(f), pozn(g), whenn(h), dirn(i) {;}
		bool operator < (const Event& x) const { return time > x.time; }
	};
	
	priority_queue<Event> events;
	
	#warning daca S = F nu prea se poate intampla ceva rau, adica nu are cui sa ii dea, nu? (dupa ce se infecteaza el, nu?)
	void update_time(int his_time) {
		while(!events.empty()) {
			auto [ctime, infect, pozi, wheni, diri, non, pozn, whenn, dirn] = events.top();
			// cerr << ctime << ' ' << infect << ' ' << non << '\n';
			if(ctime > his_time) break;
			events.pop();
			// cerr << ctime << ' ' << infect << ' ' << non << '\n';
			if(diri == -1) {
				// cerr << ctime << ' ' << infect << ' ' << non << '\n';
				erasePlayer(non, pozn, whenn, isinfected[non], dirn);
				if(isinfected[non]) rez[non] = ctime - wheninfected[non];
				continue;
			}
			else {
				if(isinfected[infect] != 1 || isinfected[non] != 0) continue;
				int mult = (diri == 0? 1 : -1);
				if(infected[abs(wheni + pozi) % 2][diri].count(tii{pozi + wheni * mult, infect, wheni}) == 0) continue;
				mult = (dirn == 0? 1 : -1);
				if(notinfected[abs(whenn + pozn) % 2][dirn].count(tii{pozn + whenn * mult, non, whenn}) == 0) continue;
				erasePlayer(non, pozn, whenn, 0, dirn);
				
				isinfected[non] = 1;
				wheninfected[non] = ctime;
				
				insertPlayer(non, pozn, whenn, 1, dirn);
			}
		}
		time = his_time;
	}
	
	#warning where NUU e convertit deja
	void considerPlayer(int who, int where, int when, int type, int dir) {
		// daca ceri tip care merge in fata inseamna de regula ca ai timpul mai mare ca el deci trebuie sa iti scazi coord ca sa fi pe ac plan ca el
		// daca ceri tip care merge in spate trebuie sa te compari cu el in directiain care merge (i.e. +timpul tau)
		int mult = (dir == 0? 1 : -1);
		where -= when * mult; // deci daca mergi in spate ceri in data si cel din fata merge pe diag principala
		int parity = abs(where) % 2;

		set<tuple<int, int, int>>::iterator it;
		auto target = &infected;
		if(type == 1)
			target = &notinfected;
			
		if(dir == 0) {
			it = (*target)[parity][!dir].lower_bound(tii{where, -1, -1});
			if(it == (*target)[parity][!dir].begin()) return;
			it = prev(it);
		}
		else {
			it = (*target)[parity][!dir].lower_bound(tii{where + 1, -1, -1});
			if(it == (*target)[parity][!dir].end()) return;
		}
		
		auto [his_where, his_who, his_when] = *it;
		
		Event E = Event(when + abs((where + mult * when) - ((his_where + mult * his_when) + (dir == 0? 1 : -1) * (when - his_when))) / 2, 
										his_who, his_where + mult * his_when, his_when, !dir,
										who, where + mult * when, when, dir);
		if(type == 1) {
			swap(E.infected, E.non);
			swap(E.pozi, E.pozn);
			swap(E.diri, E.dirn);
			swap(E.wheni, E.whenn);
		}
		
		events.emplace(E);
	}
	void insertPlayer(int who, int where, int when, int type, int dir) {
		considerPlayer(who, where, when, type, dir);
		int mult = (dir == 0? 1 : -1), parity = abs(where + when) % 2;
		if(type == 0) notinfected[parity][dir].emplace(where + when * mult, who, when);
		if(type == 1) infected[parity][dir].emplace(where + when * mult, who, when);
		return;
	}
	
	void erasePlayer(int who, int where, int when, int type, int dir) {
		int mult = (dir == 0? 1 : -1);
		where += mult * when; // ??
		int parity = abs(where) % 2;
		
		if(type == 0) notinfected[parity][dir].erase(tii{where, who, when});
		if(type == 1) infected[parity][dir].erase(tii{where, who, when});
		
		where -= 2 * mult * when;
		
		auto target = &infected;
		if(type == 1)
			target = &notinfected;
		set<tuple<int, int, int>>::iterator it;
		if(dir == 0) {
			it = (*target)[parity][!dir].lower_bound(tii{where, -1, -1});
			if(it == (*target)[parity][!dir].begin()) return;
			it = prev(it);
		}
		else {
			it = (*target)[parity][!dir].lower_bound(tii{where + 1, -1, -1});
			if(it == (*target)[parity][!dir].end()) return;
		}
		
		auto [his_where, his_who, his_when] = *it;
		his_where += mult * when; 
		considerPlayer(his_who, his_where, his_when, !type, !dir);
	}
	
	
	void insert(int who, int start, int finish, int his_time) {
		update_time(his_time);
		int type = isinfected[who];
		insertPlayer(who, start, his_time, type, (start < finish));
		if(start == finish)
			insertPlayer(who, start, his_time, type, 1);
		
		events.emplace(Event{his_time + abs(finish - start) + 1,
									-1, -1, -1, -1, 
									who, start, his_time, (start <= finish)});
								
		if(start == finish)
			events.emplace(Event{his_time + abs(finish - start) + 1,
									-1, -1, -1, -1, 
									who, start, his_time, 1});
	}
};

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> I
) {
	int M = sz(D);
	for(int i = 0; i < M; i++) {
		isinfected[i] = I[i];
		if(I[i]) wheninfected[i] = D[i];
	}
		
	vector<int> idx(M);
	iota(all(idx), 0);
	LineSolver line;
	sort(all(idx), [&](int a, int b) {
		return D[a] < D[b];
	});
	
	for(auto i : idx) {
		line.insert(i, S[i], T[i], D[i]);
	}
	line.update_time(1e18 + 5);
	
	vector<int> result;
	for(int i = 0; i < M; i++) {
		result.emplace_back(rez[i]);
	}
	return result;
}

	
