题目描述

疾旋鼬是甜的。

有 n 只疾旋鼬要糖。匡学长给疾旋鼬们发糖。最初有 i 只疾旋鼬要了 ai 袋糖。有 n 个事件以均匀随机的顺序发生。第 i 个事件是



	如果第 i 只疾旋鼬的糖袋比第 bi 只疾旋鼬的少，那么第 i 只疾旋鼬将得到额外的 wi 袋糖。否则，什么也不会发生。



现在，由于事件发生的顺序是随机的，匡学长想知道所有事件发生后每只疾旋鼬能得到的糖的预期数量。

输入格式

每个测试包含多个测试用例。第一行包含一个互斥项 t ( 1≤t≤1e5 )，表示测试用例的数量。对于每个测试用例

第一行包含一个整数 n ( 1≤n≤1e5 ) 表示子测试用例中疾旋鼬的总数。


第二行包含 n 个整数 ai ( 1≤ai≤1e9 )：每只疾旋鼬拥有的初始糖袋数量。


第三行包含 n 个整数 bi ( 1≤bi≤n )。


第四行包含 n 个整数 wi ( 1≤wi≤1e9 )。


保证所有测试用例中 n 的总和不超过 1e5 。

输出格式

对于每个测试用例，在一行中输出 n 个整数：每只疾旋鼬预计能得到的糖袋数。如上所述，将答案输出为取模 1e9+7 的整数。

4
4
2 5 5 2
4 2 1 3
3 2 1 4
3
5 4 3
1 1 1
6 6 6
3
5 4 3
2 3 1
1 2 3
5
2 1 3 2 1
5 1 1 3 4
1 3 4 2 4

500000007 5 5 6 
5 10 9 
166666673 5 6 
500000006 4 3 4 5

提示

样例2的解释：第1只疾旋鼬无论事件在何时发生都满足不了要求，无法获得糖果。第2、3只疾旋鼬无论事件在何时发生都满足要求，所以可以获得糖果。