Problem Description

Kagamiz is thinking about a Christmas present for his son, Cucumber-kun.

Kagamiz has a concern. Cucumber-kun loves competitive programming, and there is a risk that he might be inspired by the strange problem statements commonly seen in contests and ask for arrays or graphs as presents.

Instead of being caught off guard, Kagamiz decided to ask Cucumber-kun what he wants for Christmas. Cucumber-kun replied as follows:

"I want a natural problem setting for the problem I'm about to describe!"

Input Format

$ N $ $ X_1 $ $ K_1 $ $ D_1 $ : $ X_N $ $ K_N $ $ D_N $

Output Format

If it is impossible to add any points to satisfy the problem's conditions, output impossible.

If it is possible to add points to satisfy the conditions but the number of points added would exceed $ 10^5 $, output too many.

If it is possible to satisfy the conditions by adding $ 10^5 $ or fewer points, output the specific example in the following format:

$ M $ $ A_1 $ … $ A_M $

Where $ M $ is the number of points to add, and $ A_j $ is the coordinate of the point to add. Here, $ M $ must be $ 10^5 $ or less, and each $ A_j $ must be within the range representable by a 32-bit signed integer. Also, there must be no extra blank lines or spaces in the output. (Added at 16:36)

Sample Input and Output

Sample Input #1

2
0 2 1
2 2 1

Sample Output #1

1
1

Sample Input #2

2
0 2 1
3 2 1

Sample Output #2

2
-1 2

Sample Input #3

1
1 1 1

Sample Output #3

impossible

Sample Input #4

1
1 114514 1

Sample Output #4

too many

Sample Input #5

1
1 1 0

Sample Output #5

0

Notes/Hints

Task

There are $ N $ points in a 1-dimensional space, where the coordinate of the $ i $-th point $ P_i $ is $ X_i $.

We want to add some new points so that the $ N $ points satisfy certain conditions, which are represented by the integer sequences $ K $ and $ D $ as follows:

• Condition: For $ i = 1, ..., N $, the distance from point $ P_i $ to the $ K_i $-th nearest point is $ D_i $. The distance between two points is the absolute difference of their coordinates.

The points considered for the distance include both the originally existing $ N $ points and the newly added points. That is, the nearest point to a given point could be itself.

Determine if it is possible to add some points to satisfy the above conditions. If possible, also determine if the number of points added can be kept within $ 10^5 $. If so, find one specific example of the coordinates of the points to add.

All $ X_i $, $ D_i $, and the coordinates of the points to add are integers. The coordinates of the points to add must also be within the range representable by a 32-bit signed integer.

Note that multiple points can share the same coordinate.

Constraints

All input data satisfies the following constraints:

• $1 \leq N \leq 10^3$.
• $-10^9 \leq X_i \leq 10^9$.
• $1 \leq K_i \leq 10^9$.
• $0 \leq D_i \leq 10^9$.

Additionally, there are partial points for this problem, and the input data for those points satisfies the following additional constraints:

• $N \leq 10$.
• $ K_i = 2 $.

Sample Explanation 1

Since the number of points added only needs to be $ 10^5 $ or less, the following output is also acceptable for this problem: 2 -1 1

Sample Explanation 3

Note that the nearest point to a given point is itself, and the distance is $ 0 $.

Sample Explanation 4

For example, placing $ 114,513 $ points at coordinate $ 2 $ would satisfy the condition. However, since it is impossible to satisfy the condition within $ 10^5 $ points, output too many.

Sample Explanation 5

Be careful not to add extra blank lines to this case. (Added at 16:36)

见题面 Input 部分

见题面 Output 部分