杰克买了一款名为“Rounding”（四舍五入）的新电子游戏，该游戏包含 $n$ 个关卡。游戏设有一个全球排行榜，根据分数对全球所有玩家进行排名。杰克想要打破全球纪录，让每个人都知道谁才是这款游戏的大师，因此他对评分系统进行了深入的研究。

他终于弄懂了评分规则：当玩家完成每个关卡时，他们会获得一定的分数。玩家的最终得分是他们每个关卡获得的平均分数四舍五入到最接近的整数。更准确地说，如果一个玩家总共玩了 $k$ 个关卡，且分别获得了 $p_1, p_2, \dots, p_k$ 分，他们的得分将是 $\lfloor \frac{\sum_{i=1}^k p_i}{k} + 0.5 \rfloor$。例如，如果玩家在 3 个关卡中获得了 $[2, 3, 3]$ 分，他们的得分将是 $\lfloor \frac{2+3+3}{3} + 0.5 \rfloor = 3$。

杰克已经练习了多次，并且知道自己在第 $i$ 个关卡中将获得的分数 $a_i$。他发现游戏中的一个漏洞，允许他跳过开头的某些关卡，并在任何时候停止。这意味着杰克可以选择一对数字 $(l, r)$，其中 $1 \le l \le r \le n$，并且只游玩从第 $l$ 关到第 $r$ 关的关卡。

杰克很好奇，对于每个起始关卡 $l$（$1 \le l \le n$），他能获得的最高得分是多少，以及他应该游玩多少个关卡才能达到该最高得分。如果有多个游玩关卡数都能获得最高得分，他应该输出最小的关卡数，因为长时间玩游戏对身体健康不利。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

每个测试用例包含两行。 第一行包含一个整数 $n$，表示游戏中的关卡数量。 第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$，表示杰克在每个关卡中将获得的分数。

输出格式

对于每个测试用例，在一行中输出 $n$ 个整数。第 $i$ 个数字表示杰克从第 $i$ 关开始游玩时，为了获得最高得分应该游玩的关卡数量。如果有多个答案都能达到最高得分，输出最小的关卡数量。

数据范围

• $1 \le t \le 10^5$
• $1 \le n \le 2 \times 10^5$
• $0 \le a_i \le 10^9$ 对于 $i \in \{1, 2, \dots, n\}$。
• 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

样例

输入样例 1

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

输出样例 1

2 1 1
4 2 2 1
2 1 2 1 1