P4737 [CERC2017] Buffalo Barricades

（西进运动时期）美国西部的一块牧场可以被表示为坐标系第一象限中的一块矩形网格。有 $n$ 头水牛在其中分布着，每一头都占据着一个单位正方形。水牛们从 $1$ 到 $n$ 编号；$j$ 号水牛位于右上角坐标为 $(x_j, y_j)$ 的单位正方形中。坐标轴表示了两条交汇于原点处的河流，阻止水牛向左下方移动。 一共有 $m$ 个殖民者接连到达，每个人都要宣称一块土地的所有权，其过程遵循以下规则： 1. 殖民者选定一个整数坐标点，并在此处安装一个栅栏柱。他选定的点必须没有被此前安装的栅栏或栅栏柱占据。并且，不存在两个栅栏柱会拥有相同的 $x$ 坐标，也不存在两个栅栏柱会拥有相同的 $y$ 坐标。 2. 从栅栏柱开始，殖民者分别朝着左侧或下侧修建水平或竖直的栅栏片段。每段栅栏都修建得尽可能长：即直到碰到了河流或另一段栅栏才停下。 3. 殖民者宣称以他的栅栏柱为右上角的，被栅栏和河流包围住的连通区域的所有权。当然，他也宣称了其中的所有水牛的所有权。注意后到来的殖民者也有可能宣称了已被先到来的殖民者宣称过的土地。 对于每个殖民者，请求出当他刚到来时，被他宣称了所有权的水牛的数量。

无

无

对于全部数据，$1 \le n, m \le 3 \times {10}^5$，$1 \le x_j, y_j, x'_j, y'_j \le {10}^9$，所有有序数对 $(x_j, y_j)$ 互不相同，所有 $x'_j$ 互不相同，所有 $y'_j$ 互不相同。 **翻译来源**：IOI 2021 集训队第一部分作业，PinkRabbit。