D-gk的爬山之旅_哈尔滨理工大学第12届程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

众所周知，黄山被称为天下第一奇山。 $gk$ 在寒假期间就和 $bkg$ 去了黄山游玩，站在峰顶很愉悦，望着连绵的山峰，他们开始了无尽的想象。假如这 $n$ 个山峰横向排成一排，每个山峰都有自己的高度 $h[i]$ 和愉悦值 $g[i]$ 。他们要在群山之间穿梭，有两个条件：
1. 他们不会去小于等于当前高度的山峰。
2. 他们只能到达自己视野范围内的山峰（当且仅当两者中间没有其他严格更高的山峰时，它才出现在gk的视线中）也就是说：假如gk在第 $i$ 座山上，他可以到达第 $j$ 座山，当且仅当 $h[k]<=h[j] \quad其中 min(i,j)<k<max(i,j)$ 。
规定 $gk$ 从第 $i$ 座山走到第 $j$ 座山获得的愉悦度为 $|g[i]-g[j]|$ 。对于每一座山峰 $i (1<=i<=n)$ ，现在他们想知道如果他从第 $i$ 座山出发，能获得的最大愉悦度是多少？

输入描述:

第一行T表示一共有  组测试数据 

接下来一行输入一个  表示山峰的数量 

接下来一行有  个整数代表山峰的高度

接下来一行有  个整数代表山峰的愉悦值

输入保证: g数组是严格递增或者严格递减的 且

输出描述:

对于每一组测试数据输出n个整数代表：从第i座山出发，能获得的最大愉悦度。

示例1

输入

复制

1
7
9 8 4 4 2 7 6
1 3 4 5 7 8 9

输出

复制

0 2 11 10 14 7 8

说明

假设gk在第5座山，那么他下一步可以走到第  座山

最优的路径是：

获得的愉悦值是：