#include "infection.h"

#include <iostream>

#include <algorithm>
#include <cassert>

#include <vector>
#include <tuple>
#include <set>
#include <map>

template<class T> using vec = std::vector<T>;
using ll = long long;

constexpr ll INF = 1e18 + 67676;
constexpr int INF_INT = 1e9;
constexpr int NIL = -1;

template<class T>
ll peek( const T& container ) {
  if( container.empty() ) return +INF;
  return container.begin()->first;
}

// chestii vin din stanga, chestii vin din dreapta
// insert, erase, next_col type shiii

struct Ciocanitorul {
  static constexpr bool TYPE_LEFT = false;
  static constexpr bool TYPE_RIGHT = true;

  int n;
  vec<ll> penis;
  vec<bool> type;
  ll time;

  std::set<std::pair<ll, std::pair<int, int>>> col_t;
  std::set<std::pair<ll, int>> left, right;

  Ciocanitorul( int n ):
    n(n), penis(n), type(n)
  {}

  // Tl - Xl, Tr + Xr
  ll meet_t( ll val_left, ll val_right ) const { return (val_left + val_right) / 2; }
  std::pair<ll, std::pair<int, int>> meet( int L, int R ) {
    assert( type[L] == TYPE_LEFT );
    assert( type[R] == TYPE_RIGHT );
    return { meet_t( penis[L], penis[R] ), { L, R } };
  }

  int match_left( int idx ) {
    // R - T >= T - L --> R >= 2T - L
    auto it = right.lower_bound({ 2 * time - penis[idx], -INF_INT });
    if( it == right.end() ) return NIL;
    return it->second;
  }

  int match_right( int idx ) {
    // R - T >= T - L --> L >= 2T - R
    auto it = left.lower_bound({ 2 * time - penis[idx], -INF_INT });
    if( it == left.end() ) return NIL;
    return it->second;
  }

  void insert_left( ll op_t, int idx, ll val ) {
    // assert( op_t <= peek_next() );
    time = op_t;

    penis[idx] = val;
    type[idx] = TYPE_LEFT;

    int oth = match_left( idx );
    if( oth == NIL ) { left.emplace( val, idx ); return; }

    int before = match_right( oth );
    left.emplace( val, idx );
    int after = match_right( oth );
    
    if( before == after ) return;
    assert( after == idx );

    if( before != NIL )
      col_t.erase( meet( before, oth ) );

    col_t.insert( meet( idx, oth ) );
  }

  void erase_left( ll op_t, int idx ) {
    // assert( op_t <= peek_next() );
    time = op_t;

    ll val = penis[idx];
    
    int oth = match_left( idx );
    if( oth == NIL ) { left.erase({ val, idx }); return; }

    int before = match_right( oth );
    left.erase({ val, idx });
    int after = match_right( oth );
    if( before == after ) return;

    col_t.erase( meet( idx, oth ) );
    if( after != NIL )
      col_t.insert( meet( after, oth ) );
  }

  void insert_right( ll op_t, int idx, ll val ) {
    // assert( op_t <= peek_next() );
    time = op_t;

    penis[idx] = val;
    type[idx] = TYPE_RIGHT;

    int oth = match_right( idx );
    if( oth == NIL ) { right.emplace( val, idx ); return; }

    int before = match_left( oth );
    right.emplace( val, idx );
    int after = match_left( oth );
    
    if( before == after ) return;
    assert( after == idx );

    if( before != NIL )
      col_t.erase( meet( oth, before ) );

    col_t.insert( meet( oth, idx ) );
  }

  void erase_right( ll op_t, int idx ) {
    // assert( op_t <= peek_next() );
    time = op_t;
    
    ll val = penis[idx];
    
    int oth = match_right( idx );
    if( oth == NIL ) { right.erase({ val, idx }); return; }

    int before = match_left( oth );
    right.erase({ val, idx });
    int after = match_left( oth );
    if( before == after ) return;

    col_t.erase( meet( oth, idx ) );
    if( after != NIL )
      col_t.insert( meet( oth, after ) );
  }

  ll peek_next() const { return peek( col_t ); }
  std::pair<int, int> next_col() {
    assert( !col_t.empty() );
    return col_t.begin()->second;
  }
};

// container de segmente
// - insert (la idx) (t, src, dest, 0/1)
// - pop_next -> (idx, t_inf)

// pentru lant doar insert, dupa pop
// pentru heavy sunt interclasate

// implementare
// tii separat alea infectate de alea clean
// tii mereu cand timpul la urmatoarea coliziune (l2r vs r2l)
// celelalte suprapuneri le faci cand apar gen

struct Testiculatorul {
  struct Info {
    ll start;
    int src, dest;
    ll inf_t;
  };

  int n;
  vec<Info> sex;
  
  Ciocanitorul col_AB, col_BA;
  std::set<std::pair<ll, int>> A_l2r, A_r2l, B_l2r, B_r2l;
  std::set<std::pair<ll, int>> start, stop;

  Testiculatorul( int n ):
    n(n), sex(n), col_AB(n), col_BA(n)
  {}

  void insert( int idx, ll start_t, int src, int dest, bool inf ) {
    sex[idx] = { start_t, src, dest, inf ? start_t : +INF };
    start.emplace( start_t, idx );
    stop.emplace( start_t + std::abs( dest - src ) + 1, idx );
  }

  ll peek_next() const { return peek( stop ); }

  void spawn( int idx ) {
    // maximul e B_l2r, xoruiesti de acolo
    int state = 2 * (sex[idx].src <= sex[idx].dest) + (sex[idx].inf_t < +INF);
    ll time = sex[idx].start, val;
    vec<int> inf_idx;

    // std::cerr << "spawn of " << idx << ", state = " << state << std::endl;

    switch( state ){
    case 0: // A_r2l
      val = sex[idx].start + sex[idx].src;
      col_BA.insert_right( time, idx, val );
      A_r2l.emplace( val, idx );

      {
	auto it = B_r2l.lower_bound({ val, -INF_INT });
	if( it != B_r2l.end() && it->first == val ) infect( idx, time );
      }
      
      break;
    case 1: // B_r2l
      val = sex[idx].start + sex[idx].src;
      col_AB.insert_right( time, idx, val );
      B_r2l.emplace( val, idx );

      {
	auto begin = A_r2l.lower_bound({ val, -INF_INT });
	auto end = A_r2l.upper_bound({ val, +INF_INT });
	for( auto it = begin; it != end; it++ )
	  inf_idx.push_back( it->second );
      }

      for( int x : inf_idx ) infect( x, time );
      break;
    case 2: // A_l2r
      val = sex[idx].start - sex[idx].src;
      col_AB.insert_left( time, idx, val );
      A_l2r.emplace( val, idx );

      {
	auto it = B_l2r.lower_bound(std::pair<ll, int>(val, -INF_INT));
	if( it != B_l2r.end() && it->first == val ) infect( idx, time );
      }

      break;
    case 3: // B_l2r
      val = sex[idx].start - sex[idx].src;
      col_BA.insert_left( time, idx, val );
      B_l2r.emplace( val, idx );

      {
	auto begin = A_l2r.lower_bound({ val, -INF_INT });
	auto end = A_l2r.upper_bound({ val, +INF_INT });
	for( auto it = begin; it != end; it++ )
	  inf_idx.push_back( it->second );
      }

      for( int x : inf_idx ) infect( x, time );
      break;
    }

    // std::cerr << "val = " << val << ", ca idee" << std::endl;
  }

  void infect( int idx, ll inf_t ) {
    // std::cerr << "infect of " << idx << ", at t=" << inf_t << std::endl;
    
    assert( sex[idx].inf_t == +INF );
    assert( inf_t < +INF );
    sex[idx].inf_t = inf_t;

    if( sex[idx].src <= sex[idx].dest ){
      ll val = sex[idx].start - sex[idx].src;
      col_AB.erase_left( inf_t, idx );
      A_l2r.erase({ val, idx });

      col_BA.insert_left( inf_t, idx, val );
      B_l2r.emplace( val, idx );
    }else{
      ll val = sex[idx].start + sex[idx].src;
      col_BA.erase_right( inf_t, idx );
      A_r2l.erase({ val, idx });

      col_AB.insert_right( inf_t, idx, val );
      B_r2l.emplace( val, idx );
    }
  }

  void AAAAAAAAAAAAAAAAAAA( int idx, ll time ) {
    // std::cerr << "PIZDA MATII PLEACA " << idx << " COAIE" << std::endl;
    int state = 2 * (sex[idx].src <= sex[idx].dest) + (sex[idx].inf_t < +INF);
    ll val;

    switch( state ){
    case 0: // A_r2l
      val = sex[idx].start + sex[idx].src;
      col_BA.erase_right( time, idx );
      A_r2l.erase({ val, idx });
      
      break;
    case 1: // B_r2l
      val = sex[idx].start + sex[idx].src;
      col_AB.erase_right( time, idx );
      B_r2l.erase({ val, idx });

      break;
    case 2: // A_l2r
      val = sex[idx].start - sex[idx].src;
      col_AB.erase_left( time, idx );
      A_l2r.erase({ val, idx });

      break;
    case 3: // B_l2r
      val = sex[idx].start - sex[idx].src;
      col_BA.erase_left( time, idx );
      B_l2r.erase({ val, idx });

      break;
    }
  }

  std::pair<int, int> pop_next() {
    assert( !stop.empty() );
    auto [target, s_idx] = *stop.begin();
    stop.erase( stop.begin() );

    // std::cerr << "alo pizda matii, about to pop " << s_idx << std::endl;

    ll t_AB, t_BA, t_start, t_all;
    while( (t_all = std::min({
	  t_AB = col_AB.peek_next(),
	  t_BA = col_BA.peek_next(),
	  t_start = peek( start )
	  })) < target ){

      if( t_start == t_all ){
        int idx = start.begin()->second;
	start.erase( start.begin() );
	spawn( idx );
	continue;
      }

      if( t_AB == t_all ){
	auto [A, B] = col_AB.next_col();
	infect( A, t_AB );
	continue;
      }

      if( t_BA == t_all ){
	auto [B, A] = col_BA.next_col();
	infect( A, t_BA );
	continue;
      }

      assert( false );
    }

    AAAAAAAAAAAAAAAAAAA( s_idx, target );
    int time_inf = std::max( 0LL, target - sex[s_idx].inf_t );
    return std::pair<int, int>(s_idx, time_inf);
  }
};

struct Line {
  Testiculatorul par, impar;
  Line( int n ): par(n), impar(n) {}
  void insert( int idx, ll start, int src, int dest, bool inf ) {
    bool P = (start + src) % 2;
    // std::cerr << "(insert) routing to " << P << std::endl;
    
    if( P ) par.insert( idx, start, src, dest, inf );
    else impar.insert( idx, start, src, dest, inf );
  }
  std::pair<int, int> pop_next() {
    if( par.peek_next() < impar.peek_next() )
      return par.pop_next();
    else
      return impar.pop_next();
  }
};

vec<int> solve( vec<std::pair<int, int>> R, vec<ll> D, vec<int> S, vec<int> T, vec<bool> I ) {
  int n = (int)R.size() + 1;
  int q = (int)D.size();

  for( int i = 0; i + 1 < n; i++ )
    assert( R[i].first == i && R[i].second == i + 1 );

  Line zile(q);
  for( int i = 0; i < q; i++ )
    zile.insert( i, D[i], S[i], T[i], I[i] );

  vec<int> ret(q, -69);
  for( int i = 0; i < q; i++ ){
    auto [idx, inf_t] = zile.pop_next();
    ret[idx] = inf_t;
  }

  return ret;
}
