Background

Luogu's testdata is only for community sharing and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

There are $n$ warehouses on Xixi Aifu Island, numbered $1 \cdots n$ in order. Each warehouse has an $m$-dimensional vector as its location code, which is used to describe the logistics relationship between warehouses.

Specifically, each warehouse $i$ may have a parent warehouse $j$ such that, in every dimension, the corresponding element of warehouse $j$'s location code is strictly greater than that of warehouse $i$. For example, a warehouse with code $(1, 1, 1)$ can be the parent of $(0, 0, 0)$, but it cannot be the parent of $(0, 1, 0)$. If multiple warehouses satisfy this condition, choose the one with the smallest index as the parent warehouse of warehouse $i$. If no warehouse satisfies the condition, then warehouse $i$ is a logistics center and has no parent warehouse.

Given the location codes of $n$ warehouses, compute the index of the parent warehouse for each warehouse.

Input Format

Read from standard input.

There are $n + 1$ lines in total.

The first line contains two positive integers $n$ and $m$, representing the number of warehouses and the dimension of the location codes.

The next $n$ lines give the location codes of the $n$ warehouses in order. The $i$-th line ($1 \le i \le n$) contains $m$ integers, representing the location code of warehouse $i$.

Output Format

Write to standard output.

There are $n$ lines in total.

The $i$-th line ($1 \le i \le n$) outputs one integer, the index of the parent warehouse of warehouse $i$. If warehouse $i$ has no parent, output $0$ on the $i$-th line.

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

3
1
0
3

Hint

Sample Explanation

For warehouse $2$: $(-1, -1)$, both warehouse $1$: $(0, 0)$ and warehouse $3$: $(1, 2)$ satisfy the parent condition, so we choose warehouse $1$ with the smaller index as its parent.

Subtasks

$50\%$ of the testdata satisfies $m = 2$.

All testdata satisfies $0 < m \le 10$, $0 < n \le 1000$, and every element in the location codes is an integer with absolute value not greater than $10^6$.

Translated by ChatGPT 5