“Man, this year has the worst weather ever!”, David said as
he sat crouched in the small cave where we had sought shelter
from yet another sudden rainstorm.
“Nuhuh!”, Diana immediately replied in her traditional
knowitall manner.
“Is too!”, David countered cunningly.
Terrific. Not only were we stuck in this cave, now we would
have to listen to those two nagging for at least an hour. It
was time to cut this discussion short.
“Big nuhuh. In fact, 93 years ago it had already rained
five times as much by this time of year.”
“Duh”, David capitulated, “so it’s the worst weather in 93
years then.”
“Nuhuh, this is actually the worst weather in 23 years.”,
Diana again broke in.
“Yeah, well, whatever”, David sighed, “Who cares
anyway?”.
Well, dear contestants, you care, don’t you?
The Problem
Your task is to, given information about the amount of rain
during different years in the history of the universe, and a
series of statements in the form “Year $X$ had the most rain since year
$Y$”, determine whether
these are true, might be true, or are false. We say that such a
statement is true if:

The amount of rain during these two years and all years
between them is known.

It rained at most as much during year $X$ as it did during year
$Y$.

For every year $Z$
satisfying $Y < Z <
X$, the amount of rain during year $Z$ was less than the amount of
rain during year $X$.
We say that such a statement might be true if there is an
assignment of amounts of rain to years for which there is no
information, such that the statement becomes true. We say that
the statement is false otherwise.
Input
The input will consist of several test cases, each
consisting of two parts.
The first part begins with an integer $1 \leq n \leq 50\, 000$, indicating
the number of different years for which there is information.
Next follow $n$ lines. The
$i$th of these contains
two integers $10^9 \leq y_ i
\leq 10^9$ and $1 \leq r_
i \leq 10^9$ indicating that there was $r_ i$ millilitres of rain during year
$y_ i$ (note that the
amount of rain during a year can be any nonnegative integer,
the limitation on $r_ i$
is just a limitation on the input). You may assume that
$y_ i < y_{i+1}$ for
$1 \leq i < n$.
The second part of a test case starts with an integer
$1 \leq m \leq 10\, 000$,
indicating the number of queries to process. The following
$m$ lines each contain two
integers $10^9 \leq Y < X
\leq 10^9$ indicating two years.
There is a blank line between test cases. The input is
terminated by a case where $n =
0$ and $m = 0$.
This case should not be processed.
Technical note: Due to the size of the input, the use of
cin/cout in C++ might be too slow in this problem. Use
scanf/printf instead. In Java, make sure that both input and
output is buffered.
Output
There should be $m$
lines of output for each test case, corresponding to the
$m$ queries. Queries
should be answered with “true” if the
statement is true, “maybe” if the
statement might be true, and “false”
if the statement is false.
Separate the output of two different test cases by a blank
line.
Sample Input 1 
Sample Output 1 
4
2002 4920
2003 5901
2004 2832
2005 3890
2
2002 2005
2003 2005
3
1985 5782
1995 3048
2005 4890
2
1985 2005
2005 2015
0
0

false
true
maybe
maybe
