# In Touch

Time Limit
4s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/1)
Description:

There are n soda living in a straight line. soda are numbered by 1,2,…,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 li and no larger than ri. The cost to use i-th soda's teleporter is ci.

The 1-st soda is their leader and he wants to know the minimum cost needed to reach i-th soda (1≤i≤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≤n≤2×105), the number of soda.
The second line contains n integers l1,l2,…,ln. The third line contains n integers r1,r2,…,rn. The fourth line contains n integers c1,c2,…,cn(0≤li≤ri≤n,1≤ci≤109)

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++.

Source:

2015 Multi-University Training Contest 6

Submit