#P18542. Min or Max 2

Min or Max 2

Min or Max 2

故事还在继续。现在小青鱼已经掌握了最小值和最大值的概念,想通过一些整数二元组练习自己的理解。

给定两个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n 和 b1,b2,…,bnb_1,b_2,\ldots,b_n,它们分别都是 1,2,…,n1,2,\ldots,n 的排列。

初始有二元组 (x,y)=(a1,b1)(x,y)=(a_1,b_1)。接着,按照 i=2,3,…,ni=2,3,\ldots,n 的顺序,对于每一个 ii,必须恰好选择并执行下面两种操作中的一种:

  • 将 xx 更新为 min⁡(x,ai)\min(x,a_i),同时将 yy 更新为 min⁡(y,bi)\min(y,b_i);
  • 将 xx 更新为 max⁡(x,ai)\max(x,a_i),同时将 yy 更新为 max⁡(y,bi)\max(y,b_i)。

两坐标必须同时取最小值或同时取最大值;不能分别独立选择。

全部 n−1n-1 次操作完成后,会得到一个最终二元组 (x,y)(x,y)。请对每个 k=0,1,…,n−1k=0,1,\ldots,n-1,求满足 ∣x−y∣=k|x-y|=k 的不同最终二元组的个数。不同操作序列得到相同二元组时只计一次。

输入格式

第一行包含整数 TT,表示测试用例数,1≤T≤1051\le T\le10^5。

对于每个测试用例:

  • 第一行包含整数 nn,2≤n≤5×1052\le n\le5\times10^5;
  • 第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n;
  • 第三行包含 nn 个整数 b1,…,bnb_1,\ldots,b_n。

aa 和 bb 分别是 1,2,…,n1,2,\ldots,n 的排列:所有元素均在 [1,n][1,n] 中,且每个序列内任意两个元素不同。

保证同一输入文件中所有测试用例的 nn 之和不超过 5×1055\times10^5。

输出格式

对于每个测试用例输出一行 nn 个整数,第 ii 个整数表示 k=i−1k=i-1 时的答案。

样例

输入:

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

输出:

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