In Touch

Problem Description

There are n soda living in a straight line. soda are numbered by $1, 2, \dots, n$ from left to right. The distance between two adjacent soda is 1 meter. Every soda has a teleporter. The teleporter of $i$-th soda can teleport to the soda whose distance between $i$-th soda is no less than $l_i$ and no larger than $r_i$. The cost to use $i$-th soda's teleporter is $c_i$. The $1$-st soda is their leader and he wants to know the minimum cost needed to reach $i$-th soda $(1 \le i \le n)$.

Input

There are multiple test cases. The first line of 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 2 \times 10^5)$, the number of soda. The second line contains $n$ integers $l_1,l_2,\dots,l_n$. The third line contains $n$ integers $r_1,r_2,\dots,r_n$. The fourth line contains $n$ integers $c_1,c_2,\dots,c_n$. $(0 \le l_i \le r_i \le n, 1 \le c_i \le 10^9)$

Output

For each case, output $n$ integers where $i$-th integer denotes the minimum cost needed to reach $i$-th soda. If $1$-st soda cannot reach $i$-the soda, you should just output -1.

Sample Input

1
5
2 0 0 0 1
3 1 1 0 5
1 1 1 1 1

Sample Output

0 2 1 1 -1

Hint

If you need a larger stack size, please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6