描述

“伙计，今年的天气真是史上最差！”大卫蜷缩在我们躲避又一场突发暴雨的小洞里说道。

“才不是呢！”戴安娜立刻用她那副无所不知的经典口吻反驳道。

“就是最差！”大卫狡黠地回击。太棒了——我们不仅被困在这个洞里，现在还得听这两人至少唠叨一个小时。是时候打断这场争论了。

“才不是呢。事实上，93年前的这个时候降雨量已经是今年的五倍了。”

“呃，”大卫认输了，“那就是93年来最差的天气咯。”

“不是的，这其实是23年来最差的天气。”戴安娜再次打断他。

“好吧，随便啦，”大卫叹了口气，“反正谁在乎呢？”

亲爱的参赛者们，你们在乎，对吗？

你的任务是：给定宇宙历史中不同年份的降雨量信息，以及一系列形如“X年是Y年以来降雨量最多的年份”的陈述，判断这些陈述是正确（true）、可能正确（maybe） 还是错误（false）。我们定义：

• 若陈述为正确，需满足：
  1. 这两年及中间所有年份的降雨量信息已知；
  2. X年的降雨量至多等于Y年的降雨量；
  3. 对于每个满足Y < Z < X的年份Z，其降雨量严格小于X年的降雨量。
• 若存在一种为未知年份分配降雨量的方式，使陈述成立，则称该陈述可能正确；
• 否则称该陈述错误。

输入

输入包含多个测试用例，每个测试用例分为两部分：

1. 第一部分以整数$1 \leq n \leq 50000$开头，表示已知降雨量信息的年份数量。接下来n行，第i行包含两个整数$-10^9 \leq y_i \leq 10^9$和$1 \leq r_i \leq 10^9$，表示年份$y_i$的降雨量为$r_i$毫升（注：年份的降雨量可以是任意非负整数，对$r_i$的限制仅针对输入）。保证$y_1 < y_2 < \dots < y_n$。
2. 第二部分以整数$1 \leq m \leq 10000$开头，表示查询数量。接下来m行，每行包含两个整数$-10^9 \leq Y < X \leq 10^9$，表示待查询的两个年份。

测试用例之间用空行分隔。输入以$n=0$且$m=0$终止，该用例无需处理。

技术提示：由于输入规模较大，C++中使用cin/cout可能过慢，请改用scanf/printf；Java中请确保输入输出已缓冲。

输出

每个测试用例输出m行，对应m个查询的结果，分别为“true”（正确）、“maybe”（可能）或“false”（错误）。不同测试用例的输出之间用空行分隔。

输入数据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  

输出数据1

false  
true  

maybe  
maybe  

来源

2005年北欧竞赛