Reconstructing the Sequence

You are given three sequences of integers \(x_1,x_2,\dots,x_n\), \(y_1,y_2,\dots,y_n\) and \(z_1,z_2,\dots,z_n\). It is known that there exists a nonnegative integer sequence \(a_1,a_2,\dots,a_n\) with \(0 \le a_i < 10^9+7\) such that for every \(1 \le i \le n\) the following congruence holds:

[ x_i \left(\sum_{j=1}^{i} a_j\right) + y_i \left(\sum_{j=i}^{n} a_j\right) \equiv z_i \pmod{10^9+7}. ]

Your task is to reconstruct the original sequence \(a_1,a_2,\dots,a_n\) from the given sequences \(x\), \(y\) and \(z\).

Note: It is guaranteed that the input is chosen in such a way that a unique solution exists. In all test cases, it is ensured that \(x_i \ne 0\) so that the solution can be computed using modular inverses under the modulus \(10^9+7\).

inputFormat

The first line contains a single integer \(n\) denoting the length of the sequences.

The second line contains \(n\) space-separated integers \(x_1,x_2,\dots,x_n\).

The third line contains \(n\) space-separated integers \(y_1,y_2,\dots,y_n\).

The fourth line contains \(n\) space-separated integers \(z_1,z_2,\dots,z_n\).

All calculations are performed modulo \(10^9+7\).

outputFormat

Output \(n\) space-separated integers \(a_1,a_2,\dots,a_n\) representing the reconstructed sequence.

sample

3
2 4 1
3 1 2
20 17 12

1 2 3