Description

We often say statements like: "Year $X$ has the highest rainfall since year $Y$." It means that the rainfall in year $X$ does not exceed that in year $Y$, and for any year $Z$ with $Y < Z < X$, the rainfall in year $Z$ is strictly less than that in year $X$. For example, if the rainfalls in years 2002, 2003, 2004, and 2005 are 4920, 5901, 2832, and 3890 respectively, then we can say "2005 is the highest since 2003," but we cannot say "2005 is the highest since 2002." Since the rainfalls of some years are unknown, some statements may be true or may be false.

Input Format

The first line contains a positive integer $n$, the number of known records.
Each of the following $n$ lines contains two integers $y_i$ and $r_i$, the year and its rainfall, sorted in strictly increasing order of year, i.e., $y_i < y_{i+1}$.
The next line contains a positive integer $m$, the number of queries.
Each of the following $m$ lines contains two integers $Y$ and $X$, asking whether the statement "Year $X$ has the highest rainfall since year $Y$." is "true", "false", or "maybe".

Output Format

For each query, output true, false, or maybe.

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

false
true
false
maybe
false

Hint

Constraints: For 100% of the testdata, $1 \le n \le 50000$, $1 \le m \le 10000$, $-10^9 \le y_i \le 10^9$, $1 \le r_i \le 10^9$, $-10^9 \le X, Y \le 10^9$.
It is guaranteed that $Y < X$.

Translated by ChatGPT 5