你拥有一个操作整数变量 $X$ 的程序，初始时 $X=1$。该程序包含 $n$ 条指令，分为两种类型：

• “1 $p$” ($1 \le p \le n$)：将变量 $X$ 的值赋为 $p$。
• “2 $p$ $q$” ($1 \le p, q \le n, p \neq q$)：仅当当前变量 $X$ 的值为 $p$ 时，将变量 $X$ 的值赋为 $q$。

在一步操作中，你可以从程序中移除任意一条指令。你不能重新排列指令或添加新指令。对于每个 $k$（从 $1$ 到 $n$），求出使得程序运行结束后变量 $X$ 的值为 $k$ 所需的最少移除步数。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，表示程序中的指令条数。 接下来的 $n$ 行包含上述格式的指令描述。

输出格式

输出 $n$ 个整数，其中第 $i$ 个整数表示使得程序运行结束后变量 $X$ 的值为 $i$ 所需的最少移除步数，如果无法达到则输出 $-1$。

样例

样例输入 1

3
1 1
1 2
1 3

样例输出 1

2 1 0

样例输入 2

4
2 1 2
1 3
2 2 3
2 3 1

样例输出 2

0 2 1 -1