P2471 [SCOI2007] Rainfall

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.

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".

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

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