DreamGrid 正在学习最长上升子序列（LIS）问题，他需要找到给定长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ 的最长上升子序列。

回想一下： 长度为 $m$ 的子序列 $b_1, b_2, \dots, b_m$ 是满足 $b_1 = a_{k_1}, b_2 = a_{k_2}, \dots, b_m = a_{k_m}$ 且 $1 \le k_1 < k_2 < \dots < k_m \le n$ 的序列。 上升子序列 $b_1, b_2, \dots, b_m$ 是满足 $b_1 < b_2 < \dots < b_m$ 的子序列。

DreamGrid 定义了辅助序列 $f_1, f_2, \dots, f_n$，其中 $f_i$ 表示以 $a_i$ 结尾的最长上升子序列的长度。如果你不知道如何推导该辅助序列，他提供了以下计算辅助序列的伪代码：

procedure lis_helper(a: original sequence)
{Let n be the length of the original sequence,
f(i) be the i-th element in sequence f, and a(i)
be the i-th element in sequence a}
for i := 1 to n
f(i) := 1
for j := 1 to (i – 1)
if a(j) < a(i) and f(j) + 1 > f(i)
f(i) := f(j) + 1
return f {f is the helper sequence}

DreamGrid 已经使用该程序导出了辅助序列，但原始序列 $a_1, a_2, \dots, a_n$ 被 BaoBao 偷走并丢失了！DreamGrid 现在手头只有辅助序列以及两个范围序列 $l_1, l_2, \dots, l_n$ 和 $r_1, r_2, \dots, r_n$，表示对于所有 $1 \le i \le n$，都有 $l_i \le a_i \le r_i$。

请帮助 DreamGrid 恢复与辅助序列及两个范围序列兼容的原始序列。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示原始序列的长度。

第二行包含 $n$ 个整数 $f_1, f_2, \dots, f_n$ ($1 \le f_i \le n$)，由空格分隔，表示辅助序列。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($0 \le l_i \le r_i \le 2 \times 10^9$)，表示范围序列。

保证原始序列存在，且所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个由空格分隔的整数，表示原始序列。如果存在多个有效答案，输出其中任意一个即可。

请注意，不要在每行末尾打印多余的空格，否则你的答案可能会被判定为错误！

样例

输入 1

4
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

输出 1

1 2 3 2 5 3
200 300 200 500 200
0 1 2 0 0 3 1
2 2