D. Absolute Cinema
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует скрытая последовательность $$$a_1,a_2,\ldots,a_n$$$ из $$$n$$$ целых чисел ($$$n \ge 2$$$). Гарантируется, что $$$|a_i| \le 1000$$$ для всех $$$1 \le i \le n$$$.

Определим функцию $$$f(x)$$$ следующим образом:

$$$$$$f(x)=\sum_{i=1}^n a_i \cdot |i-x|$$$$$$

Даны $$$n$$$ значений $$$f(1),f(2),\ldots,f(n)$$$, пожалуйста, определите значения $$$a_1,a_2,\ldots,a_n$$$.

Гарантируется, что значения $$$a_1,a_2,\ldots,a_n$$$ могут быть определены однозначно.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$\color{red}{2} \le n \le 300\,000$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$f(1),f(2),\ldots,f(n)$$$ ($$$-10^{14} \le f(i) \le 10^{14}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$300\,000$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ на отдельной строке ($$$|a_i| \le 1000$$$).

Гарантируется, что значения $$$a_1,a_2,\ldots,a_n$$$ могут быть определены однозначно.

Пример
Входные данные
4
4
17 9 9 13
6
-37 -32 -15 4 27 42
5
-26 -32 -24 -4 2
2
420 -69
Выходные данные
1 4 2 3
3 6 1 2 -4 -7
-6 7 6 -7 -6
-69 420
Примечание

В первом примере скрытая последовательность равна $$$a=[1,4,2,3]$$$.

Значения $$$f(1),f(2),\ldots,f(n)$$$ следующие:

  • $$$f(1) = 1 \cdot |1-1| + 4 \cdot |2-1| + 2 \cdot |3-1| + 3 \cdot |4-1| = 0+4+4+9 = 17$$$;
  • $$$f(2) = 1 \cdot |1-2| + 4 \cdot |2-2| + 2 \cdot |3-2| + 3 \cdot |4-2| = 1+0+2+6 = 9$$$;
  • $$$f(3) = 1 \cdot |1-3| + 4 \cdot |2-3| + 2 \cdot |3-3| + 3 \cdot |4-3| = 2+4+0+3 = 9$$$;
  • $$$f(4) = 1 \cdot |1-4| + 4 \cdot |2-4| + 2 \cdot |3-4| + 3 \cdot |4-4| = 3+8+2+0 = 13$$$.