#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define for if(0);else for #define WHITE false #define BLACK true struct period { int l, r; bool color; period(int l, int r, bool color) : l(l), r(r), color(color) {} period() : l(0), r(1000000000), color(false) {} }; static bool operator < (const period& a, const period& b) { return a.l < b.l; } static inline int search(int pos, const vector& ps) { int l = 0, r = ps.size(); // [l, r) while(l < r) { int c = (l + r) >> 1; if(ps[c].l <= pos && pos <= ps[c].r) return c; if(pos < ps[c].l) r = c; else l = c + 1; } return l; } static bool included(const period& a, const period& b) { return !(a.r < b.l || a.l > b.r); } void period_push( vector& ps, const period& p ) { if( p.l == p.r ) return; if( ps.empty() || ps.back().color != p.color ) ps.push_back(p); ps.back().r = p.r; } static pair solve(const vector& prob) { list state; state.push_back(period()); for(int i = 0; i < prob.size(); i++) { period p = prob[i]; list::iterator lit = state.begin(); for(;;++lit) if( lit->l <= p.l && p.l < lit->r ) // [l,r) break; list::iterator rit = lit; for(;;++rit) if( rit->l <= p.r && p.r < rit->r ) // [l,r) break; const period lp = *lit; const period rp = *rit; list::iterator it = state.erase(lit, ++rit); // splitted:lit if( lp.l < p.l ) it=state.insert( it, period(lp.l, p.l, lp.color) ), ++it; // p bool do_not_add_rp = false; if( p.color == rp.color ) { p.r = rp.r; do_not_add_rp = true; } { if( it == state.begin() ) it=state.insert( it, p ), ++it; else { --it; if( it->color == p.color ) it->r = p.r, ++it; else it=state.insert( ++it, p ), ++it; } } // splitted:rit if( !do_not_add_rp ) state.insert( it, period(p.r, rp.r, rp.color) ); /* vector nst; const period p = prob[i]; const int lidx = search(p.l, state), ridx = search(p.r, state); // 0 - lidx for(int j=0; j!=lidx; ++j) nst.push_back( state[j] ); // lidx:splitted period_push( nst, period(state[lidx].l, p.l, state[lidx].color) ); // new-period period_push( nst, p ); // ridx:splitted period_push( nst, period(p.r, state[ridx].r, state[ridx].color) ); // and the next if( ridx+1 != state.size() ) { period_push( nst, state[ridx+1] ); for(int k=ridx+2; k!=state.size(); ++k) nst.push_back( state[k] ); } swap(state, nst); */ } int maxlen = 0; list::iterator maxat = state.end(); for(list::iterator i = state.begin(); i!=state.end(); ++i) { //cout << '(' << i->l << ',' << i->r << ") : " << (i->color?"b":"w") << endl; const int len = i->r - i->l; if(len > maxlen && i->color==WHITE) maxlen = len, maxat = i; } return make_pair(maxat->l, maxat->r); } int main() { vector prob; int N; cin >> N; while(N--) { int l, r; char c; cin >> l >> r >> c; prob.push_back(period(l, r, c == 'b')); } pair ans = solve(prob); cout << ans.first << ' ' << ans.second << endl; return 0; }