H. Sugar Sweet II
time limit per test
2 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Sugar is sweet.

There are $$$n$$$ children asking for sugar. Prof. Chen gives out sugar to the children. The $$$i$$$-th child initially has $$$a_{i}$$$ bags of sugar. There are $$$n$$$ events happening in uniformly randomized order. The $$$i$$$-th event is:

  • If the $$$i$$$-th child has strictly less bags of sugar than the $$$b_{i}$$$-th child, then the $$$i$$$-th child will get extra $$$w_{i}$$$ bags of sugar. Otherwise, nothing happens.

Now, since the events happen in random order, Randias, which is the assistant of Prof. Chen, wants to know the expected number of bags of sugar each child will have after all the events happen.

It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not \equiv 0 \pmod {10^9 + 7}$$$. Output the integer equal to $$$x \cdot y^{-1} \pmod {10^9 + 7}$$$. In other words, output such an integer $$$a$$$ that $$$0\leq a < 10^9 + 7$$$ and $$$a \cdot y \equiv x \pmod {10^9 + 7}$$$.

Input

Each test contains multiple test cases. The first line contains a single interger $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^5$$$) denoting the number of test cases. For each test case:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) denoting the number of children.

The second line contains $$$n$$$ integers $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^9$$$): the initial number of bags of sugar each child has.

The third line contains $$$n$$$ integers $$$b_{i}$$$ ($$$1 \le b_{i} \le n$$$).

The fourth line contains $$$n$$$ integers $$$w_{i}$$$ ($$$1 \le w_{i} \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers in a line: the expected number of bags of sugar each child will get. Output the answers as integers modulo $$$10^9 + 7$$$, as described above.

Example
Input
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
Output
500000007 5 5 6 
5 10 9 
166666673 5 6 
500000006 4 3 4 5