CF2160B.Distinct Elements

Given an array $c$, let $f(c)$ be the number of distinct elements in $c$. For example, $f([1,2,2])=2$ because there are two distinct elements in $[1,2,2]$: $1$ and $2$. Also, define $c[i,j]$ as the subarray$^{\text{∗}}$ of $c$ bounded by positions $i$ and $j$ (that is, the array $[c_i,c_{i+1},\ldots,c_j]$).

There is an array $a$ of size $n$. An array $b$ of $n$ elements is constructed such that $b_i=f(a[1,i])+f(a[2,i])+\ldots+f(a[i,i])$. You are given the array $b$. Find any possible $a$ with elements $1 \leq a_i \leq n$. It is guaranteed that at least one possible $a$ exists.

$^{\text{∗}}$An array $x$ is a subarray of an array $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

给定一个数组 $c$，令 $f(c)$ 表示 $c$ 中不同元素的个数。例如，$f([1,2,2])=2$，因为 $[1,2,2]$ 中有两个不同的元素：$1$ 和 $2$。此外，定义 $c[i,j]$ 为数组 $c$ 的一个子数组$^{\text{∗}}$，其范围由位置 $i$ 和 $j$ 界定（即数组 $[c_i,c_{i+1},\ldots,c_j]$）。

现有一个长度为 $n$ 的数组 $a$。据此构造一个长度为 $n$ 的数组 $b$，使得对每个 $i$，有

$$b_i = f(a[1,i]) + f(a[2,i]) + \ldots + f(a[i,i]).$$

你将被给定数组 $b$。请找出任意一个满足条件的数组 $a$，其中每个元素满足 $1 \leq a_i \leq n$。题目保证至少存在一个合法的 $a$。

$^{\text{∗}}$ 若数组 $x$ 可通过从数组 $y$ 的开头删除若干（可能为零或全部）元素、并从结尾删除若干（可能为零或全部）元素而得到，则称 $x$ 是 $y$ 的一个子数组。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$) – the number of elements in $a$ and $b$.

The second line of each test case contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1 \leq b_i \leq 10^{18}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print any possible $a$ on a new line. The array $a$ should satisfy $1\leq a_i\leq n$.

For every test case, it is guaranteed at least one $a$ that satisfies the conditions exists.

对于每个测试用例，在一行中输出任意一个满足条件的 $a$。数组 $a$ 应满足 $1\leq a_i\leq n$。

对于每个测试用例，保证至少存在一个满足条件的 $a$。

Let's verify our output for the second test case is correct:

• $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$

我们来验证第二个测试用例的输出是否正确：

• $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$