{"problem":{"name":"[常州市赛 2024] 早起的鸟儿有虫吃","description":{"content":"清晨，丛林里的鸟儿开始了一天的忙碌，吃早餐。 丛林可以看成是一个无限大的网格，每个格子在 $0$ 时刻都有且仅有一只虫子。丛林里有 $n$ 只鸟，第 $i$ 只鸟在 $0$ 时刻在第 $x_i$ 行，第 $y_i$ 列。其中，对于所有数据保证 $x_i=1$ 或 $y_i=1$，即第 $i$ 只鸟初始时一定在第 $1$ 行或第 $1$ 列。 为了简化问题，我们假设鸟都只会向下或向右直线飞行，而","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4223"},"statements":[{"statement_type":"Markdown","content":"清晨，丛林里的鸟儿开始了一天的忙碌，吃早餐。\n\n丛林可以看成是一个无限大的网格，每个格子在 $0$ 时刻都有且仅有一只虫子。丛林里有 $n$ 只鸟，第 $i$ 只鸟在 $0$ 时刻在第 $x_i$ 行，第 $y_i$ 列。其中，对于所有数据保证 $x_i=1$ 或 $y_i=1$，即第 $i$ 只鸟初始时一定在第 $1$ 行或第 $1$ 列。\n\n为了简化问题，我们假设鸟都只会向下或向右直线飞行，而虫子是不动的。当鸟儿在任何时刻（包括时刻 $0$）飞过一个格子时，就会吃掉该格子内的虫子。相应的，该时刻之后，该格子就不再有虫子了。\n\n同时保证：如果一只鸟往下飞，则它的起始位置一定在第一行；如果一只鸟往右飞，则它的起始位置一定在第一列。为了保证鸟的飞行方向唯一，鸟的初始位置不会是 $(1,1)$。\n\n因为所有鸟都喜欢享受连续的免费早餐，所以如果在飞行时到达了一个已经没有虫子的格子，它就会非常不爽，直接停止在这个格子中。测试数据保证所有的鸟在任意时刻的位置互不相同。\n\n需要注意的是，吃早餐的时间是有限的，只有 $W$ 个单位的时间。因此，如果一只鸟在时刻 $W$ 开始时还没有停止，那它会在这个时刻开始前被强制停止。\n\n现在，想请聪明的你求出，对于每个 $i(1\\le i\\le n)$，第 $i$ 只鸟吃了多少只虫子？\n\n## Input\n\n第一行，两个正整数 $n, W$，分别表示鸟的数量和吃早餐的总时刻数。\n\n接下来 $n$ 行，每行两个正整数 $x_i,y_i$。\n\n## Output\n\n共 $n$ 行，第 $i$ 行一个正整数，表示第 $i$ 只鸟吃的虫子数。\n\n[samples]\n\n## Background\n\n搬运自 <http://czoj.com.cn/p/949>。数据为民间数据。\n  \n感谢 @[kradcigam](https://www.luogu.com.cn/user/180242) 提供的数据。\n\n## Note\n\n### 样例 $\\textbf 1$ 解释\n\n仅有的 $1$ 只鸟在时刻 $0$ 从第 $2$ 行第 $1$ 列向右依次飞过 $1\\sim 5$ 列， 在时刻 $0,1,2,3,4$ 各吃了一只虫子，在时刻 $5$ 开始前被强制停止了，所以共吃了 $5$ 只虫子。\n\n### 样例 $\\textbf 2$ 解释\n\n第 $1$ 只鸟在时刻 $0$ 从第 $2$ 行第 $1$ 列向右依次飞过 $1\\sim4$ 列，在时刻 $4$ 时飞到了第 $2$ 行第 $5$ 列，发现这一格的虫子在时刻 $1$ 就被第 $2$ 只鸟吃掉了，所以共吃了 $4$ 只虫子就停下了。\n\n第 $2$ 只鸟在时刻 $0$ 从第 $1$ 行第 $5$ 列向下沿着第 $5$ 列依次飞过 $1\\sim20$ 行，共吃了 $20$ 只虫子后于时刻 $20$ 停止。\n\n### 数据范围\n\n对于所有数据，$1\\leq n\\leq 3$，$1≤x_i,y_i≤10^9$，$1\\leq W\\leq 10^{18}$。对于每个 $i$ 有 $x_i=1$ 或 $y_i=1$，且 $x_i=y_i=1$ 不被同时满足。\n\n保证所有未停止的鸟在任意时刻位置互不相同，即任意时刻不会有两只鸟到达同一格子。\n\n|测试点编号|特殊性质|\n|:-:|:-:|\n|$1$|$\\alpha$|\n|$2\\sim 3$|$\\alpha,\\beta$|\n|$4\\sim5,8\\sim9$|$\\beta$|\n|$6\\sim7,10$|无|\n\n- 特殊性质 $\\alpha$：$n=1$。\n- 特殊性质 $\\beta$：所有鸟的前进方向相同。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4223","tags":["2024","江苏","分支结构","科创活动","小学活动"],"sample_group":[["1 5\n2 1","5"],["2 20\n2 1\n1 5","4\n20"]],"created_at":"2026-03-03 11:09:25"}}