Problem Description

There may exist a sequence of non-negative integers $a_1,a_2,\dots,a_n$ such that $0\le a_i<10^9+7$.

Given $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 for $1\le i\le n$:

$$x_i\left(\sum_{j=1}^ia_j\right)+y_i\left(\sum_{j=i}^na_j\right)\equiv z_i\pmod{10^9+7}$$

Find $a_1,a_2,\dots,a_n$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases. For each test case:

The first line contains a positive integer $n$.

The next $n$ lines each contain three positive integers $x_i,y_i,z_i$.

Output Format

For each test case, output in order:

The first line contains a non-negative integer $k$, the number of valid solutions.

If $k=1$, output $n$ non-negative integers on the second line, in order: $a_1,a_2,\dots,a_n$.

2
3
3 1 9
2 2 16
1 3 15
6
3 6 246
5 7 283
2 7 179
4 6 214
8 7 337
3 5 151

1
1 2 3
1
8 8 0 6 7 8

Hint

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n=1$.
• Subtask 2 (19 pts): $\sum n\le100$.
• Subtask 3 (19 pts): $x_i=y_i=1$.
• Subtask 4 (22 pts): It is guaranteed that there is a unique solution.
• Subtask 5 (30 pts): No special restrictions.

For all testdata:

• $1\le n,\sum n\le 2\times10^5$;
• $1\le x_i,y_i<10^9+7$;
• $0\le z_i<10^9+7$.

Translated by ChatGPT 5