复兴

英文题名：C. Revival
来源：Codeforces 2239C
比赛：Codeforces Round 1105 (Div. 1)
时间限制：2.5 seconds
空间限制：256 megabytes

题目描述

设 $p$ 是一个置换，$s_i$ 是前缀 $p_1...p_i$ 的逆序对数。每个位置给出条件 $p_i=x$ 或 $s_i=x$。保证有解，构造任意合法置换。

输入格式

第一行输入 $t$。每组输入 $n$，接着 $n$ 行条件。

输出格式

每组输出一个合法置换。

样例

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