CF1773B.BinCoin

There are $n$ employees in the BinCoin company numbered from $1$ to $n$. The subordination structure in this company is a rooted tree. In other words:

• There is one CEO in the company — the main boss.
• Each other employee has exactly one direct superior.
• There are no cycles in the subordination structure.

Moreover, due to the inexplicable love of the CEO of BinCoin for all the binary stuff, the subordination structure in the company is a binary rooted tree. That means each employee is directly superior to exactly zero or two other employees.

In the CEO's opinion, working in this company is almost as dangerous as in mines. So, employees should sign the waiver of claims sometimes. This process happens in the following way. Initially, CEO takes the journal, then recursively the following procedure is performed:

• If an employee that holds the journal does not have any subordinates, they sign the waiver in the journal and give it back to their superior. The procedure stops if that was the CEO, who has no superior.
• Otherwise
  • they choose one of two of their direct subordinates uniformly at random and give the journal to one of them;
  • when they get the journal back, they sign it;
  • and then they give it to another direct subordinate;
  • when they get it back again, they give it back to their superior. The procedure stops if that was the CEO, who has no superior.

All random choices are independent.

One day, the CEO realized that they could not remember the subordination tree. Fortunately, they have the journal with $k$ records. Each record is a sequence of employees in the order they've signed in a journal.

Help CEO restore the subordination tree.

BinCoin 公司共有 $n$ 名员工，编号从 $1$ 到 $n$。该公司内部的上下级关系构成一棵有根树，即满足以下条件：

• 公司中恰好有一名首席执行官（CEO）——即最高领导者；
• 除 CEO 外，每名员工恰好有一名直属上级；
• 上下级关系中不存在环。

此外，由于 BinCoin 公司 CEO 对一切与“二进制”相关事物有着难以理解的热爱，公司内部的上下级结构是一棵二叉有根树。这意味着：每名员工恰好是零名或两名其他员工的直属上级。

在 CEO 看来，在该公司工作几乎和在矿井中工作一样危险。因此，员工需不时签署免责协议（waiver of claims）。该流程按如下方式执行：初始时，CEO 持有登记簿（journal），然后递归地执行以下过程：

• 若当前持有登记簿的员工没有下属，则其在登记簿上签名，并将登记簿交还给自己的直属上级；若该员工即为 CEO（无上级），则流程终止；
• 否则：
  • 该员工从其两名直属下属中等概率随机选择一人，并将登记簿交给此人；
  • 待登记簿被返还后，该员工在登记簿上签名；
  • 然后，该员工再将登记簿交给另一名直属下属；
  • 待登记簿再次被返还后，该员工将其交还给自己的直属上级；若该员工即为 CEO（无上级），则流程终止。

所有随机选择相互独立。

某日，CEO 意识到自己已无法回忆起上下级关系树的结构。幸运的是，他们保留了记载着 $k$ 次签署过程的登记簿。每次记录均为一次签署过程中，员工在登记簿上签名的顺序序列。

请帮助 CEO 还原出原始的上下级关系树。

The first line contains two integers $n$ and $k$ — the number of employees and the number of records in the journal ($1 \le n \le 999$; $50 \le k \le 100$).

Each of the next $k$ lines contains a permutation of integers from $1$ to $n$ — the order of employees in the corresponding record.

It is guaranteed that the input was obtained as described in the statement with a real random choice.

第一行包含两个整数 $n$ 和 $k$ —— 分别表示员工人数和日志中的记录条数（$1 \le n \le 999$；$50 \le k \le 100$）。

接下来的 $k$ 行中，每行包含一个从 $1$ 到 $n$ 的整数排列 —— 表示对应记录中员工的顺序。

保证输入数据如题面所述，由真实的随机选择生成。

Output $n$ integers $p_i$. If $i$ is a CEO, then $p_i$ should be $-1$. Otherwise, $p_i$ should be the index of the direct superior of $i$-th employee.

Your output should correspond to a binary rooted tree. If there are several trees satisfying the input, you can output any one of them.

输出 $n$ 个整数 $p_i$。若员工 $i$ 是首席执行官（CEO），则 $p_i$ 应为 $-1$；否则，$p_i$ 应为第 $i$ 位员工的直属上级的编号。

你的输出应对应一棵二叉有根树。若存在多棵满足输入条件的树，你可以输出其中任意一棵。

In order to fit on the page, several consecutive lines in the examples were joined into one. The real inputs follow the input description.

为了适应页面宽度，示例中的若干连续行被合并为一行。实际输入遵循输入描述。