409402: GYM103500 A Existence

There may or may not exist a sequence of nonnegative integers $$$a_1,a_2,\dots,a_n$$$.

You are told that for all $$$1\le i\le n$$$, $$$0\le a_i<10^9+7$$$. You are further given three sequences $$$x_1,x_2,\dots,x_n$$$, $$$y_1,y_2,\dots,y_n$$$, and $$$z_1,z_2,\dots,z_n$$$, and it supposedly holds that for all $$$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}$$$$$$

Determine how many sequences $$$a_1,a_2,\dots,a_n$$$ satisfy the given information, and if such sequence is unique, find it.

The first line contains a single integer $$$t$$$, the number of test cases. For each test case:

The first line contains a positive integer $$$n$$$ ($$$1\le 2\times 10^5$$$).

The $$$i$$$-th of the next $$$n$$$ lines contain three integers $$$x_i$$$, $$$y_i$$$ and $$$z_i$$$ ($$$1\le x_i,y_i< 10^9+7$$$, $$$0\le z_i<10^9+7$$$).

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

For each test case:

Print one line containing one integer, the number of sequences $$$a_1,a_2,\dots,a_n$$$ that satisfy the given information.

Only when the aforementioned integer is $$$1$$$, print another line containing $$$n$$$ integers, representing $$$a_1,a_2,\dots,a_n$$$.

• In the first subtask, worth $$$10$$$ points, $$$n=1$$$.
• In the second subtask, worth $$$19$$$ points, $$$\sum n\le 100$$$.
• In the third subtask, worth $$$19$$$ points, $$$x_i=y_i=1$$$.
• In the fourth subtask, worth $$$22$$$ points, the test data guarantees an unique solution.
• In the final subtask, worth $$$30$$$ points, no additional constraints are posed.

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