F. Solving Equations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an output-only problem. In other words, the test cases are available to you and you will compute the answers on your own machine and submit them as a text file, instead of submitting a program.

Busy Beaver started his math homework a few hours before it is due (don't do that!) There are $$$100$$$ questions on the homework; how many of them can Busy Beaver do before the contest ends?

Each question is a set of simultaneous equations (see the input format for more details on what these equations look like). The task is to find positive integer solutions to as many of these sets as possible. Each set is worth one point, for $$$100$$$ points total.

Input

Please download the test data using this link.

Each set of equations begins with one line with two numbers: the number of variables, $$$N$$$, in the equations (represented by this many of the initial letters in the alphabet), and the number of equations, $$$K$$$, present. This is followed by $$$K$$$ lines, each with one equation.

Each term on the left-hand side of the equation is formatted simply as [positive integer coefficient, at most 1000][list of at most 6 variables]; the left-hand side is always just a sum of at most $$$20$$$ of these terms (separated by plus signs: no term ever has a negative coefficient), and the right-hand side is always a positive integer. Exponents are not used; for example, $$$a^2bc$$$ may be written as aabc or caab.

Every equation set has a solution with all variables not exceeding $$$10^{12}$$$. The equations were generated using a simple random method, not intended to cause worst-case behavior in any algorithm.

Output

First output a positive integer, $$$A$$$ ($$$1 \le A \le 100$$$), on its own line: the number of equations that you have solved.

Then output $$$A$$$ lines, each containing the index of the set you solved (from $$$1$$$ to $$$100$$$), followed by a space-separated list of positive integers: the values for the variables, in alphabetical order.

For example, if you solved equation set $$$5$$$ and the answer was $$$a = 1234$$$, $$$b = 5678$$$, and you solved equation set $$$10$$$ and the answer was $$$a = 123$$$, $$$b = 456$$$, $$$c = 789$$$, your output file may be as follows: 

2
5 1234 5678
10 123 456 789

Each equation set may be listed at most once as an index. Your $$$A$$$ solutions do not have to be in any particular order (so you could have the solution to set $$$10$$$ before the solution to set $$$5$$$). If there are multiple solutions, print any solution with all variables at most $$$10^{18}$$$ (although, as mentioned above, all sets have solutions with all variables at most $$$10^{12}$$$).

Scoring

If your output format is invalid, or if any solution you provided to any equation set is incorrect, you will receive zero points. Otherwise you will receive $$$A$$$ points.

To help you design your algorithm, we provide a table with information about the $$$100$$$ equation sets below, where $$$M$$$ is a number such that the set has a solution with all variables at most $$$M$$$:

  • Sets 1-2: $$$N = 1$$$, $$$K = 1$$$, $$$M = 10$$$
  • Sets 3-7: $$$N = 1$$$, $$$K = 1$$$, $$$M = 10^{12}$$$
  • Sets 8-9: $$$N = 2$$$, $$$K = 2$$$, $$$M = 10^{3}$$$
  • Sets 10-12: $$$N = 2$$$, $$$K = 2$$$, $$$M = 10^{6}$$$
  • Sets 13-20: $$$N = 2$$$, $$$K = 2$$$, $$$M = 10^{12}$$$
  • Sets 21-24: $$$N = 3$$$, $$$K = 3$$$, $$$M = 10^{3}$$$
  • Sets 25-33: $$$N = 3$$$, $$$K = 3$$$, $$$M = 10^{6}$$$
  • Sets 34-40: $$$N = 3$$$, $$$K = 3$$$, $$$M = 10^{12}$$$
  • Sets 41-57: $$$N = 3$$$, $$$K = 2$$$, $$$M = 10^{7}$$$
  • Sets 58-60: $$$N = 2$$$, $$$K = 1$$$, $$$M = 10^{7}$$$
  • Sets 61-70: $$$N = 2$$$, $$$K = 1$$$, $$$M = 10^{9}$$$
  • Sets 71-83: $$$N = 2$$$, $$$K = 1$$$, $$$M = 10^{10}$$$
  • Sets 84-92: $$$N = 2$$$, $$$K = 1$$$, $$$M = 10^{11}$$$
  • Sets 93-100: $$$N = 2$$$, $$$K = 1$$$, $$$M = 10^{12}$$$