← 返回题目列表

Codeforces · 91/E

E. 冰屋摩天大楼

中文机器翻译题面 查看原题

今天,北极举办了一场奥林匹克运动会,这项运动名为……玩具冰屋摩天大楼!

有 n 只海象参加比赛。每只海象都有一个从 1 到 n 的唯一编号。开始后,每只海象都开始建造自己的冰屋摩天大楼。最初,在时间等于0的时刻,第i座摩天大楼海象的高度等于ai。每分钟,第 i 个海象就会完成双层楼层的建造。

在奥运会现场进行报道的记者向主办方提出了疑问。每个查询由一组三个数字 li、ri、ti 来表征。组织者用数字 x 来响应每个查询,这样:

1. 数字 x 位于从 li 到 ri(含 li ≤ x ≤ ri)的区间内。

2、第x号海象的摩天大楼在时间ti时刻具有区间[li,ri]内所有海象摩天大楼中的最大高度。

对于每个记者的查询,打印出满足上述条件的海象 x 的数量。如果有多个可能的答案,请打印其中任何一个。

输入

第一行包含数字 n 和 q (1 ≤ n, q ≤ 105)。接下来的 n 行包含数字对 ai、bi (1 ≤ ai, bi ≤ 109)。然后按照 q 查询 i,格式为 li、ri、ti,每行一个 (1 ≤ li ≤ ri ≤ n,0 ≤ ti ≤ 106)。所有输入数字均为整数。

输出

对于每个记者的查询,请打印符合声明中给出的标准的海象 x 的数量。每行打印一个数字。

示例

输入 #1

5 4
4 1
3 5
6 2
3 5
6 5
1 5 2
1 3 5
1 1 0
1 5 0

输出 #1

5
2
1
5

输入 #2

5 4
6 1
5 1
2 5
4 3
6 1
2 4 1
3 4 5
1 4 5
1 2 0

输出 #2

3
3
3
1