框选星辰

矿道深处的天花板上，嵌着一幅星空图——不是真的星星，是Zero在火星轨道上部署的监控卫星。每个卫星有一个扇形扫描区，覆盖地面上一段区域。

"要统计某个矩形窗口里有多少颗卫星。"Echo说，"不是一颗一颗数——是用推窗法，从左推到右，一路上登记和注销。"

"推窗？"CC问。

"就像拉窗帘。"你说，"窗帘从左往右拉，遇到一颗星星就记下来，遇到窗口的右边界就把这颗星星划掉。同时维护一个y轴上的名册，随时查当前窗帘里有多少颗星星。"

"y轴名册又是啥子？"

"一个分层计数器。"你说，"星星的上下位置各不相同，用一个倒过来的树来管——每遇到一颗星星，就在它的y坐标位置加一；星星离开窗口时，减一。查询时，看上下边界之间有多少个星星。"

你开始写。先把所有星星按左右位置排好，然后把星星出现、窗口左边界、窗口右边界三种事件混在一起，从左到右推进。一路上，用分层计数器维护当前活跃的y坐标。遇到窗口左边界时，查询计数器里y范围内的数量。

屏幕上跳出了结果。第47号窗口里，有47颗卫星。

"又是47。"CC说。

"那个窗口……"Echo说，"是G-30矿区的正上方。Zero把最多的眼睛放在了那里。"

题目描述

平面上 $n$ 个点。$m$ 个查询，每个查询给一个矩形，问矩形内有多少个点。

输入格式

$n, m$。然后 $n$ 个点坐标。然后 $m$ 个查询，每个查询给矩形左下角和右上角坐标。

输出格式

每个查询输出矩形内点的数量。

输入样例

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

输出样例

5

提示

• 扫描线 + 树状数组。
• 把所有事件按x排序，从左到右扫描。
• 树状数组维护y坐标，支持单点修改和区间查询。

矿道的尽头是一扇巨大的铁门，门上刻着Zero的疆域图——整个矿区被划分成很多段，每段有一个驻军数量。Echo说Zero会不断调兵遣将，某一段的驻军可能突然增加或减少。

"要实时知道任意一段的驻军总数。"Echo说，"如果一段一段地加，每次查询都要从头数到尾，太慢了。"

"刷卡记账。"你说，"每次调兵不是在单段上加加减减，而是在两端做标记——起点加，终点减。查询的时候，把前面的标记一路累加，就是当前段的实际驻军。"