Sugar Sweet II

Sugar is sweet.

There are $n$ children asking for sugar. Prof. Chen gives sugar to the children. The $i$-th child initially has $a_i$ bags of sugar.

There are $n$ events, happening in uniformly random order. The $i$-th event is:

• If the $i$-th child has strictly fewer bags of sugar than the $b_i$-th child, the $i$-th child gets $w_i$ extra bags of sugar. Otherwise, nothing happens.

Because the events happen in random order, Randias, Prof. Chen's assistant, wants the expected number of bags each child has after all events happen.

It can be shown that the answer is an irreducible fraction $\frac{x}{y}$, where $x$ and $y$ are integers and $y \not\equiv 0 \pmod{10^9+7}$. Output the integer $x \cdot y^{-1} \bmod (10^9+7)$. That is, output the integer $a$ with $0 \le a < 10^9+7$ and $a \cdot y \equiv x \pmod{10^9+7}$.

The first line contains $t$ ($1 \le t \le 5 \cdot 10^5$), the number of test cases. Each test case is given as follows.

The first line contains $n$ ($1 \le n \le 5 \cdot 10^5$), the number of children. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$). 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$).

The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

For each test case, print $n$ integers on one line: the expected number of bags each child has at the end, modulo $10^9+7$ as described above.