最近,Polycarp 连续完成了 $$$n$$$ 任务。
对于每个已完成的任务,给出的时间 $$$s_i$$$ 是已知的,不会同时给出两个任务。还给出了任务完成的时间$$$f_i$$$。对于每个任务,都有一个未知值 $$$d_i$$$ ($$$d_i>0$$$) — 任务执行的持续时间。
已知任务是按其到来的顺序完成的。坡旅甲执行的任务如下:
- 第一个任务一到来,波利卡普就立即开始执行。
- 如果在 Polycarp 完成前一个任务之前到达了新任务,他会将新任务放在队列末尾。
- 当Polycarp执行完下一个任务并且队列不为空时,他立即从队列头部取出一个新任务(如果队列为空——他只是等待下一个任务)。
查找每个任务的$$$d_i$$$(持续时间)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
输入数据集的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$s_1 < s_2 < \dots < s_n$$$ ($$$0 \le s_i \le 10^9$$$)。
每个测试用例的第三行恰好包含 $$$n$$$ 整数 $$$f_1 < f_2 < \dots < f_n$$$ ($$$s_i < f_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个 $$$t$$$ 测试用例,打印 $$$n$$$ 正整数 $$$d_1, d_2, \dots, d_n$$$ — 每个任务的持续时间。
示例
输入 #1
4 3 0 3 7 2 10 11 2 10 15 11 16 9 12 16 90 195 1456 1569 3001 5237 19275 13 199 200 260 9100 10000 10914 91066 5735533 1 0 1000000000
输出 #1
2 7 1 1 1 1 183 1 60 7644 900 914 80152 5644467 1000000000
注意
第一个测试用例:
队列一开始是空的:$$$[ ]$$$。这就是第一个任务的用武之地。在 $$$2$$$ 时刻,Polycarp 完成了第一个任务,因此第一个任务的持续时间为 $$$2$$$。队列是空的,所以波利卡普只是在等待。
在时间$$$3$$$,第二个任务到达。在 $$$7$$$ 时刻,第三个任务到达,现在队列如下所示:$$$[7]$$$。
在$$$10$$$时,Polycarp完成了第二个任务,因此第二个任务的持续时间为$$$7$$$。
在时间$$$10$$$,Polycarp 立即开始执行第三个任务并在时间$$$11$$$ 完成。因此,第三个任务的持续时间为 $$$1$$$。
第一个测试用例的示例。