ENG  RUS Timus Online Judge
Ural State University
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Archive

1019. A Line painting

Time Limit: 2.0 second
Memory Limit: 16 MB
The segment of numerical axis from 0 to 109 is painted into white color. After that some parts of this segment are painted into black, then some into white again and so on. In total there have been made N re-paintings (1 ≤ N ≤ 5000). You are to write a program that finds the longest white open interval after this sequence of re-paintings.

Input

The first line of input contains the only number N. Next N lines contain information about re-paintings. Each of these lines has a form:
ai bi ci
where ai and bi are integers, ci is symbol 'b' or 'w', ai, bi, ci are separated by spaces.
This triple of parameters represents repainting of segment from ai to bi into color ci ('w' — white, 'b' — black). You may assume that 0 < ai < bi < 109.

Output

Output should contain two numbers x and y (x < y) divided by space(s). These numbers should define the longest white open interval. If there are more than one such an interval output should contain the one with the smallest x.

Sample

input output
4
1 999999997 b
40 300 w
300 634 w
43 47 b
47 634
Problem Source: Ural State University Internal Contest '99 #2