提示: 欢迎访问OurACM平台。
Problem 2100 排队

Accept: 102    Submit: 472
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一些人在排队买车票,假设每个人都有不同的买票紧急程度,如果某个人的紧急程度比排在他前一个的人的紧急程度更大,则这个人可以和前一个人调换位置,并且假设每个人都有一个耐心值,若某人的耐心值为x,则他最多可以向前调换x次,当然前提是他之前x个人的紧急程度都比他小,若遇到前面一个人紧急程度比他大的他将停止往前调换。现假设有N个人,按顺序一个个进入队列,并且每进去一个人立即按照紧急程度和其耐心值向前进行调换,调换停止后下一个人才进入队列。给出这N个人的紧急程度和耐心值,问最终的排队情况。

Input

第一行输入一个整数T,表示数据组数。接下来T组数据,对于每组数据,第一行输入一个整数n (1<=n<=10^5),接下来第2到n+1行每行输入两个整数a[i],c[i] (1<=a[i]<=n,0<=c[i]<=n),分别表示第i个人的紧急程度在n个人种排第几及其耐心值,a[i]越大表示紧急程度越大。

Output

对于每组数据,请输出一行n个数,以一个空格隔开,表示最终队列的排队情况,第i个数表示最终排在第i个位置的人是第几个进入队列的。

Sample Input

1 5 2 3 1 4 4 3 3 1 5 2

Sample Output

3 1 5 4 2

Source

FOJ有奖月赛-2012年11月

Submit  Back  Status  Discuss