题目背景

CR400AF-J 是基于 CR400AF 系列研发的高速综合检测列车，简称“动检列车”。它承担着检测高铁线路各项性能指标的任务。通常，动检列车约每隔 $15$ 天在一条线路上运行一次，并会选择白天客运列车的天窗期运行。由于列车通体为黄色，且承担检测任务，因此被人们亲切地称为“黄医生”。

题目描述

春运期间，铁路客流量大幅提高。为了提高运力，铁路局加开了许多旅客列车，使各车站可供动检列车停靠的天窗期缩短。

一条高铁线路上依次排列着编号为 $1$ 到 $n$ 的 $n$ 座车站。第 $i$ 座车站仅能在时间 $t_i$ 停靠动检列车，称 $t_i$ 为该车站的天窗期。

铁路局希望利用这些天窗期开行一列从车站 $1$ 方向驶往车站 $n$ 方向的动检列车。动检列车只能在时间 $t_i$ 停靠车站 $i$，但其通过车站 $i$ 的时间不受限制。

由于 CR400AF 型列车运行速度很快，车站之间的行驶时间可以忽略。因此，对于任意 $i<j$，动检列车能够同时停靠车站 $i,j$ 的充要条件是

铁路局针对每一座车站 $i$ 都规划了一种运行方案，保证动检列车在该方案中一定停靠车站 $i$。设该方案中停靠的车站集合为 $S_i$，则 $i\in S_i$，且对于任意 $x,y\in S_i$，若 $x<y$，则必须满足 $t_x<t_y$。

设 $|S_i|$ 为方案中停靠的车站数。只停靠车站 $i$ 的方案也是合法的。为了提高检测效率，铁路局在所有满足要求的方案中最大化了 $|S_i|$。

由于客流量过大，铁路局计划利用某些车站的天窗期加开旅客列车。若车站 $j$ 的天窗期被占用，动检列车就不能停靠车站 $j$。铁路局需要重新规划每一座车站的运行方案。

设车站 $i$ 的新方案对应的车站集合为 $T_i$。若车站 $j$ 的天窗期被占用，则 $j\notin T_i$。铁路局仍会最大化 $|T_i|$。

对于每座车站 $i$，求有多少座车站 $j\ne i$，满足：当且仅当车站 $j$ 的天窗期被占用时，新的最优方案与原方案的停靠车站数不同，即

输入格式

本题有多组测试数据。

第一行包含两个正整数 $id,T$，分别表示测试点编号和数据组数。

每组测试数据包含两行：

• 第一行包含一个正整数 $n$，表示车站数；
• 第二行包含 $n$ 个正整数 $t_1,t_2,\ldots,t_n$，表示各车站的天窗期。

保证 $t$ 是 $1$ 到 $n$ 的一个排列。

输出格式

对于每组测试数据，输出一行 $n$ 个整数，依次表示每座车站的答案。

样例 1

输入

1 4
6
5 6 3 2 1 4
6
4 1 6 3 2 5
6
4 6 1 3 5 2
5
2 3 5 1 4

输出

1 1 1 1 1 0
0 1 0 2 2 1
0 1 2 2 2 1
1 1 2 1 2

样例解释

考虑第 $4$ 组测试数据：

• 对于车站 $1$，$|S_1|=3$。仅当车站 $2$ 的天窗期被占用时，$|T_1|=2$；其余时候 $|T_1|=3$，故答案为 $1$。
• 对于车站 $2$，$|S_2|=3$。仅当车站 $1$ 的天窗期被占用时，$|T_2|=2$；其余时候 $|T_2|=3$，故答案为 $1$。
• 对于车站 $3$，$|S_3|=3$。当车站 $1$ 或 $2$ 的天窗期被占用时，$|T_3|=2$；其余时候 $|T_3|=3$，故答案为 $2$。
• 对于车站 $4$，$|S_4|=2$。仅当车站 $5$ 的天窗期被占用时，$|T_4|=1$；其余时候 $|T_4|=2$，故答案为 $1$。
• 对于车站 $5$，$|S_5|=3$。当车站 $1$ 或 $2$ 的天窗期被占用时，$|T_5|=2$；其余时候 $|T_5|=3$，故答案为 $2$。

样例 2

输入

2 5
15
12 14 3 7 6 5 1 4 13 15 10 11 9 8 2
15
15 2 11 13 3 12 14 8 10 7 5 1 9 6 4
15
13 5 8 9 10 12 2 11 1 7 14 15 3 4 6
15
5 15 13 14 12 6 9 2 8 11 3 1 4 7 10
15
10 6 4 7 2 9 5 11 12 1 13 15 8 3 14

输出

1 2 0 1 1 1 1 0 1 1 1 1 0 0 1
0 0 2 3 1 2 1 2 3 3 2 0 2 3 2
2 5 5 5 5 6 0 6 0 2 5 5 2 2 2
1 1 2 2 1 1 2 4 2 2 4 3 4 4 4
3 5 5 4 3 4 3 4 4 0 4 5 1 1 5

数据范围与子任务

对于全部测试数据：

且 $t$ 是 $1$ 到 $n$ 的一个排列。

• 性质 A： 存在一个位置 $1\le i\le n$，使得

  $$t_1<t_2<\cdots<t_i>t_{i+1}>\cdots>t_n.$$

• 性质 B： $t_i$ 随机生成。