
ZOJ Problem Set  4028
DreamGrid is learning the LIS (Longest Increasing Subsequence) problem and he needs to find the longest increasing subsequence of a given sequence $a_1, a_2, \dots, a_n$ of length $n$. Recall that
DreamGrid defines the helper sequence $f_1, f_2, \dots, f_n$ where $f_i$ indicates the maximum length of the increasing subsequence which ends with $a_i$. In case you don't know how to derive the helper sequence, he provides you with the following pseudocode which calculates the helper sequence.
procedure lis_helper($a$: original sequence) DreamGrid has derived the helper sequence using the program, but the original sequence $a_1, a_2, \dots, a_n$ is stolen by BaoBao and is lost! All DreamGrid has in hand now is the helper sequence and two range sequences $l_1, l_2, \dots, l_n$ and $r_1, r_2, \dots, r_n$ indicating that $l_i \le a_i \le r_i$ for all $1 \le i \le n$. Please help DreamGrid restore the original sequence which is compatible with the helper sequence and the two range sequences. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the length of the original sequence. The second line contains $n$ integers $f_1, f_2, \dots, f_n$ ($1 \le f_i \le n$) seperated by a space, indicating the helper sequence. For the following $n$ lines, the $i$th line contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 2 \times 10^9$), indicating the range sequences. It's guaranteed that the original sequence exists, and the sum of $n$ of all test cases will not exceed $5 \times 10^5$. OutputFor each test case output one line containing $n$ integers separated by a space, indicating the original sequence. If there are multiple valid answers, print any of them. Please, DO NOT print extra spaces at the end of each line, or your solution may be considered incorrect! Sample Input4 6 1 2 3 2 4 3 0 5 2 4 3 3 1 2 3 5 1 5 5 1 2 1 3 1 100 200 200 300 200 400 400 500 100 500 7 1 2 3 1 1 4 2 0 3 0 3 0 3 0 3 0 3 0 3 0 3 2 1 1 1 2 2 3 Sample Output1 2 3 2 5 3 200 300 200 500 200 0 1 2 0 0 3 1 2 2 Author: CHEN, Shihan Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 