#P10963. [2015杭电多校]In Touch

    ID: 10105 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>CF2100提高Dijkstra势能重赋权有序集合

[2015杭电多校]In Touch

In Touch

Problem Description

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

Input

There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case: The first line contains an integer nn (1≤n≤2×105)(1 \le n \le 2 \times 10^5), the number of soda. The second line contains nn integers l1,l2,…,lnl_1,l_2,\dots,l_n. The third line contains nn integers r1,r2,…,rnr_1,r_2,\dots,r_n. The fourth line contains nn integers c1,c2,…,cnc_1,c_2,\dots,c_n. (0≤li≤ri≤n,1≤ci≤109)(0 \le l_i \le r_i \le n, 1 \le c_i \le 10^9)

Output

For each case, output nn integers where ii-th integer denotes the minimum cost needed to reach ii-th soda. If 11-st soda cannot reach ii-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