话说昨天我在hihocoder找数学期望练习题时，无意中发现了hihocoder有挑战赛！发现的时候，已经开赛了有十多分钟了，我匆忙地参加了比赛。

首先，我打开了第一题：

#1299 : 打折机票

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

因为思念新宿的"小姐姐"们，岛娘计划6月份再去一趟东京，不过这次看来她需要自掏腰包。经过了几天的夜战，岛娘终于在体力耗尽之前，用Python抓下了所有6月份，上海至东京的全部共 n 张机票。现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的，最贵的机票。

输入

输入数据的第一行包含两个整数 n, m(1 ≤ n, m ≤ 10⁵)，分别表示机票的总数，和询问的总数。接下来的 n 行，每行两个整数 t, v (1 ≤ t, v ≤ 10⁵)，表示每张机票出发的时间和价格。 接下来的 m 行，每行两个整数 a, b (1 ≤ a ≤ b ≤ 10⁵)，表示每个询问所要求的时间区间。

输出

对于每组询问，输出一行表示最贵的价格。如果没有符合要求的机票，输出一行"None"。

样例输入

7 6
1 1
2 1
4 3
4 4
4 5
6 9
7 9
1 7
1 2
6 7
3 3
4 4
5 5

样例输出

9
1
9
None
5
None

嗯..这是一道很有节操的题目，首先我们拥有可爱的男♂孩子，啊♂，然后呢，还他喵还会写代码，还挺会勤俭持家（选最贵的机票），啊，盆友，票子要伐？

可惜，我实在是对伪娘提不起兴♂趣，嗯，咱们还是好好看题吧。

思路：

我第一个想到的就是线段树啦，于是我打了出来。

但是！令我奇怪的是，这棵线段树，不是RE，就是WA，就是TLE!

（好吧其实都是我的错）

然后，我在这道题，生生卡了俩小时.....

对，你没看错，俩小时，而且我一道都没有AC...

我不服，果断把这锅甩给了亲爱的机房的电脑:

]

嗯，我觉得这个锅，机房的电脑背定了。没错！都是你的错！

然后，第二天，也就是今天，我，决定向hihocoder群友伸手——求助= =

然后，有几个致命的错误：

1. 我特么把大数组存为临时变量了;
2. 我没及时return.

然后这些错误给亲爱的群友11提出来，我修改了后：

是的，我顶多改了三句代码

然后

我

AC

了

来，让我先Orz一下

这个故事教训我

我特么就是个

思博

湿笔

让我满脑子CNM地，贴上我的AC代码...

#include
#include
#include
#define MAXN 400100
using namespace std;
int l[MAXN], r[MAXN];
struct Node{
	int l, r, v;
}node[MAXN];

void build(int i, int l, int r){
//	if (l > r) return;
//	cout << i << " " <<  l << " " <<  r << endl;
	node[i].l = l;
	node[i].r = r;
	node[i].v = -1;
	if (l == r) return;
	build(i << 1, l, (l + r) >> 1);
	build((i << 1) + 1,((l + r) >> 1) + 1, r);	
}

int query(int i, int l, int r){
//	cout << i << endl; 
	int s = -1;
	if (node[i].l > r || node[i].r < l) return s;
	if (node[i].l >= l && node[i].r <= r) return node[i].v;
	if (node[i].l == node[i].r) return s;
	int mid = i << 1;
	s = max(s, query(mid, l, r));
	s = max(s, query(mid + 1, l, r));
	return s;
}

void insert(int i, int v, int n){
//	cout << i << " " << node[i].l << " " << node[i].r << endl;
	
	if (node[i].l > n || node[i].r < n) return;
	if (node[i].l <= n && node[i].r >= n) node[i].v = max(node[i].v ,v);
//	cout << i << endl;
	int l = node[i].l, r = node[i].r;
	if (l == r){
		return;
	}
	insert(i << 1, v, n);
	insert((i << 1) + 1, v, n);

}
int main(){
	int n, m;
//	freopen("c.in", "r", stdin);
//	freopen("c.out", "w", stdout);
	scanf("%d%d", &n, &m);

	int bt = -1;
	for (int i = 0; i < n; i++){
		scanf("%d%d", &l[i], &r[i]);
		bt = max(l[i], bt);
	}
//	cout << bt << endl;
	build(1, 1, bt + 1);
	for (int i = 0; i < n; i++){
		insert(1, r[i], l[i]);
	}
//	cout << query(1, 4, 5) << " xxsxsxs" << endl;
	for (int i = 0; i < m; i++){
		scanf("%d%d", &l[i], &r[i]);
//		cout << l[i] << " " << r[i] << endl; 
	}
	for (int i = 0; i < m; i++){
		int a = query(1, l[i], r[i]);
		if (a != -1){
			printf("%dn", a);
		}else{
			printf("Nonen");
		}
	}
	return 0;
}