logo AlgoBeat OnlineJudge
登录 注册

#216070. [CSPro 32] 仓库规划

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

洛谷的测试数据仅供民间交流使用,非官方测试数据。官方评测链接:https://www.cspro.org/


西西艾弗岛上共有 个仓库,依次编号为 。每个仓库均有一个 维向量的位置编码,用来表示仓库间的物流运转关系。

具体来说,每个仓库 均可能有一个上级仓库 ,满足:仓库 位置编码的每一维均大于仓库 位置编码的对应元素。比如编码为 的仓库可以成为 的上级,但不能成为 的上级。如果有多个仓库均满足该要求,则选取其中编号最小的仓库作为仓库 的上级仓库;如果没有仓库满足条件,则说明仓库 是一个物流中心,没有上级仓库。

现给定 个仓库的位置编码,试计算每个仓库的上级仓库编号。

输入格式

从标准输入读入数据。

输入共 行。

输入的第一行包含两个正整数 ,分别表示仓库个数和位置编码的维数。

接下来 行依次输入 个仓库的位置编码。其中第 行()包含 个整数,表示仓库 的位置编码。

输出格式

输出到标准输出。

输出共 行。

行()输出一个整数,表示仓库 的上级仓库编号;如果仓库 没有上级,则第 行输出

样例

样例输入 1

4 2
0 0
-1 -1
1 2
0 -1

样例输出 1

3
1
0
3

数据范围与提示

样例解释

对于仓库 : 来说,仓库 : 和仓库 : 均满足上级仓库的编码要求,因此选择编号较小的仓库 作为其上级。

子任务

的测试数据满足

全部的测试数据满足 ,且位置编码中的所有元素均为绝对值不大于 的整数。