给定一个数组 $$$c$$$,令 $$$f(c)$$$ 为 $$$c$$$ 中不同元素的数量。例如,$$$f([1,2,2])=2$$$,因为 $$$[1,2,2]$$$ 中有两个不同的元素:$$$1$$$ 和 $$$2$$$。另外,将 $$$c[i,j]$$$ 定义为以 $$$i$$$ 和 $$$j$$$ 为边界的 $$$c$$$ 的子数组 $$$^{\text{∗}}$$$(即数组 $$$[c_i,c_{i+1},\ldots,c_j]$$$)。
存在一个大小为 $$$n$$$ 的数组 $$$a$$$。构造一个由 $$$n$$$ 元素组成的数组 $$$b$$$,使得 $$$b_i=f(a[1,i])+f(a[2,i])+\ldots+f(a[i,i])$$$。您将获得数组 $$$b$$$。查找任何可能的包含元素 $$$1 \leq a_i \leq n$$$ 的 $$$a$$$。保证至少存在一个可能的$$$a$$$。
$$$^{\text{*}}$$$数组 $$$x$$$ 是数组 $$$y$$$ 的子数组,如果 $$$x$$$ 可以通过从 $$$y$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) – $$$a$$$ 和 $$$b$$$ 中的元素数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq 10^{18}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在新行上打印任何可能的 $$$a$$$。数组 $$$a$$$ 应满足 $$$1\leq a_i\leq n$$$。
对于每个测试用例,保证至少存在一个满足条件的$$$a$$$。
示例
输入复制
431 3 631 3 531 3 441 2 3 7
输出复制
1 3 2 2 3 2 3 2 2 4 4 4 1
注意
让我们验证第二个测试用例的输出是否正确:
- $$$b_1=f([2])=1$$$
- $$$b_2=f([2,3])+f([3])=2+1=3$$$
- $$$b_3=f([2,3,2])+f([3,2])+f([2])=2+2+1=5$$$