#P2471. [SCOI2007] 降雨量

[SCOI2007] 降雨量

题目描述

我们常常会说这样的话:“XX 年是自 YY 年以来降雨量最多的”。它的含义是 XX 年的降雨量不超过 YY 年,且对于任意 Y<Z<XY < Z < XZZ 年的降雨量严格小于 XX 年。例如 2002、2003、2004 和 2005 年的降雨量分别为 49204920590159012832283238903890,则可以说“2005 年是自 2003 年以来最多的”,但不能说“2005 年是自 2002 年以来最多的”由于有些年份的降雨量未知,有的说法是可能正确也可以不正确的。

输入格式

输入仅一行包含一个正整数 nn,为已知的数据。以下 nn 行每行两个整数 yiy_irir_i,为年份和降雨量,按照年份从小到大排列,即 yi<yi+1y_i<y_{i+1}。下一行包含一个正整数 mm,为询问的次数。以下 mm 行每行包含两个数 YYXX,即询问“XX 年是自 YY 年以来降雨量最多的。”这句话是“必真”、“必假”还是“有可能”。

输出格式

对于每一个询问,输出 truefalse 或者 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

提示

100%100 \% 的数据满足:1n500001 \le n \le 500001m100001 \le m \le 10000109yi109-10^9 \le y_i \le 10^91ri1091 \le r_i \le 10^9109X,Y109-10^9 \le X, Y \le 10^9