Bie 皇帝想要创建一个长度为 $n$ 的数组 $A$。他首先选择一个初始位置 $p$ ($1 \le p \le n$)，并将他喜欢的一个正整数赋值给 $A_p$。他还初始化两个变量 $l$ 和 $r$，令 $l = r = p$。随后他进行了 $n - 1$ 次操作，每次操作可以是以下两种之一：

• 向左扩展：仅当 $l > 1$ 时可以进行此操作。Bie 皇帝选择一个满足 $0 \le k < A_r$ 的整数 $k$，并将 $A_r - k$ 赋值给 $A_{l-1}$。之后，他将 $l$ 减 1。
• 向右扩展：仅当 $r < n$ 时可以进行此操作。Bie 皇帝选择一个满足 $0 \le k < A_l$ 的整数 $k$，并将 $A_l - k$ 赋值给 $A_{r+1}$。之后，他将 $r$ 加 1。

多年以后，Bie 皇帝仍然记得他创建的数组，但他忘记了初始位置 $p$。请帮助 Bie 皇帝确定哪些位置可能是初始位置 $p$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示数组的长度。 接下来一行包含 $n$ 个整数 $A_1, A_2 \dots A_n$ ($1 \le A_i \le 10^9$)，表示该数组。 保证 $n$ 的总和不超过 $5 \cdot 10^5$，且至少存在一个合法的 $p$。

输出格式

对于每个测试用例，按升序输出所有可能的初始位置，并在单行内打印。

样例

样例输入 1

3
1
5
2
1 3
3
3 3 3

样例输出 1

1
2
1 2 3