今天,北极举办了一场奥林匹克运动会,这项运动名为……玩具冰屋摩天大楼!
有 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