{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid 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$.\u003c/p\u003e\n\n\u003cp\u003e\nRecall that\n\u003c/p\u003e\u003cul\u003e\n\u003cli\u003e\u003cp\u003eA subsequence $b_1, b_2, \\dots, b_m$ of length $m$ is a sequence satisfying $b_1 \u003d a_{k_1}, b_2 \u003d a_{k_2}, \\dots, b_m \u003d a_{k_m}$ and $1 \\le k_1 \u0026lt; k_2 \u0026lt; \\dots \u0026lt; k_m \\le n$.\u003c/p\u003e\u003c/li\u003e\n\u003cli\u003e\u003cp\u003eAn increasing subsequence $b_1, b_2, \\dots, b_m$ is a subsequence satisfying $b_1 \u0026lt; b_2 \u0026lt; \\dots \u0026lt; b_m$.\u003c/p\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eDreamGrid 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\u0027t know how to derive the helper sequence, he provides you with the following pseudo-code which calculates the helper sequence.\u003c/p\u003e\n\n\u003cp style\u003d\"border: 1px solid black; float: left; margin-left: 100px; padding: 10px;\"\u003e\n\u003cb\u003eprocedure\u003c/b\u003e lis_helper($a$: original sequence)\u003cbr\u003e\n{Let $n$ be the length of the original sequence,\u003cbr\u003e\n$f(i)$ be the $i$-th element in sequence $f$, and $a(i)$\u003cbr\u003e\nbe the $i$-th element in sequence $a$}\u003cbr\u003e\n\u003cb\u003efor\u003c/b\u003e $i$ :\u003d 1 \u003cb\u003eto\u003c/b\u003e $n$\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$f(i)$ :\u003d 1\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb\u003efor\u003c/b\u003e $j$ :\u003d 1 \u003cb\u003eto\u003c/b\u003e ($i$ - 1)\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb\u003eif\u003c/b\u003e $a(j) \u0026lt; a(i)$ \u003cb\u003eand\u003c/b\u003e $f(j) + 1 \u0026gt; f(i)$\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$f(i)$ :\u003d $f(j)$ + 1\u003cbr\u003e\n\u003cb\u003ereturn\u003c/b\u003e $f$ {$f$ is the helper sequence}\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cdiv style\u003d\"clear: both;\"\u003e\u003c/div\u003e\n\n\u003cp\u003eDreamGrid 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$.\u003c/p\u003e\n\n\u003cp\u003ePlease help DreamGrid restore the original sequence which is compatible with the helper sequence and the two range sequences.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^5$), indicating the length of the original sequence.\u003c/p\u003e\n\n\u003cp\u003eThe 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.\u003c/p\u003e\n\n\u003cp\u003eFor 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.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the original sequence exists, and the sum of $n$ of all test cases will not exceed $5 \\times 10^5$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor 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.\u003c/p\u003e\n\n\u003cp\u003ePlease, DO NOT print extra spaces at the end of each line, or your solution may be considered incorrect!\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n6\n1 2 3 2 4 3\n0 5\n2 4\n3 3\n1 2\n3 5\n1 5\n5\n1 2 1 3 1\n100 200\n200 300\n200 400\n400 500\n100 500\n7\n1 2 3 1 1 4 2\n0 3\n0 3\n0 3\n0 3\n0 3\n0 3\n0 3\n2\n1 1\n1 2\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 3 2 5 3\n200 300 200 500 200\n0 1 2 0 0 3 1\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}