C. Возрождение
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим перестановку $$$p$$$ чисел $$$1, 2, \ldots, n$$$. Пусть $$$s_i$$$ обозначает количество инверсий на префиксе $$$p_1, p_2, \ldots, p_i$$$, определённое как:

$$$$$$ s_i = \sum_{1 \le x \lt y \le i} [p_x \gt p_y], $$$$$$

где квадратные скобки обозначают скобку Айверсона.

Для каждой позиции $$$i$$$ ($$$1 \le i \le n$$$) вам дано условие в виде либо $$$p_i = x$$$, либо $$$s_i = x$$$. Ваша задача — восстановить исходную перестановку $$$p$$$.

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

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

Для каждого набора входных данных: Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$). Каждая из следующих $$$n$$$ строк содержит символ $$$c$$$ ($$$c \in \{\text{'p'}, \text{'s'}\}$$$) и целое число $$$x$$$:

  • Если $$$c = \text{'p'}$$$, это означает, что $$$p_i = x$$$, где $$$1 \le x \le n$$$.
  • Если $$$c = \text{'s'}$$$, это означает, что $$$s_i = x$$$, где $$$0 \le x \le \frac{i(i-1)}{2}$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Гарантируется, что допустимая перестановка всегда существует.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, представляющих перестановку $$$p$$$.

Если существует несколько допустимых перестановок, вы можете вывести любую из них.

Пример
Входные данные
5
3
p 1
p 2
p 3
3
s 0
s 1
s 2
3
p 1
s 0
p 2
5
p 1
p 4
s 0
p 2
s 4
6
s 0
s 1
s 3
s 6
s 10
s 15
Выходные данные
1 2 3
3 1 2
1 3 2
1 4 5 2 3
6 5 4 3 2 1
Примечание

В первом наборе входных данных значения всех элементов заданы явно, поэтому единственная допустимая перестановка — $$$\{1, 2, 3\}$$$.

Во втором наборе входных данных нужно восстановить перестановку по количеству инверсий в префиксах:

  • Для позиции $$$2$$$ количество инверсий увеличивается на $$$s_2 - s_1 = 1 - 0 = 1$$$. Это означает, что $$$p_2$$$ должно быть меньше ровно одного предшествующего элемента, то есть $$$p_1 \gt p_2$$$.
  • Для позиции $$$3$$$ количество инверсий увеличивается на $$$s_3 - s_2 = 2 - 1 = 1$$$. Это означает, что $$$p_3$$$ меньше ровно одного предшествующего элемента.
Единственная перестановка, удовлетворяющая этим условиям — $$$\{3, 1, 2\}$$$.

В третьем наборе входных данных задано $$$p_1 = 1$$$ и $$$p_3 = 2$$$. Единственное оставшееся доступное значение для $$$p_2$$$ — это $$$3$$$. Можно проверить, что префикс $$$p_1, p_2$$$ (то есть $$$1, 3$$$) имеет $$$0$$$ инверсий, что в точности удовлетворяет условию $$$s_2 = 0$$$. Таким образом, ответ — $$$\{1, 3, 2\}$$$.

В пятом наборе входных данных заданные значения $$$s_i$$$ в точности совпадают с $$$\frac{i(i-1)}{2}$$$, что является максимально возможным количеством инверсий для префикса длины $$$i$$$. Это означает, что каждый элемент должен быть меньше всех предшествующих элементов, то есть перестановка строго убывает. Следовательно, ответ — $$$\{6, 5, 4, 3, 2, 1\}$$$.