Problem A. Pizza schedule ≡

Author:T. Chistyakov   Time limit:1 sec
Input file:input.txt   Memory limit:2 Mb
Output file:output.txt  

Statement

PizzaSocks company makes and delivers pizza. Pizza is delivered on regular schedule. A schedule has a period of 1, 2, 3 or 4 weeks. Quantity of pizzas to be delivered is known for each day of the period. First day of a period is always the first day of the week.

So formally pizza delivery schedule can be described by the following numbers: L — length of the schedule period (from 1 to 4), A1, A2, …, AL × 7 — quantity of pizzas to be delivered for each day of the period (Ai ≥ 0).

Once an absent-minded PizzaSocks manager lost a schedule for one Very Big and Important Client. Only the history of past deliveries was preserved. Your task is to restore the schedule from the history.

The problem is complicated by the fact that occasionally Very Big and Important Client changed his orders, ordering either more or less pizzas than scheduled, even sometimes cancelling the order competely or placing an unscheduled order.

So it's often impossible to restore the original schedule exactly. That is why your task is to find an optimal schedule, i. e. to minimize the total number of days when historically ordered quantity is different from the quantity according to that schedule. The days before the first recorded order and after the last recorded one should not be taken into consideration.

Input file format

Input file contains the following integer numbers:

N — number of fulfilled orders in the delivery history w1 d1 q1 w2 d2 q2… wN dN qN — description of historical orders: week number, day of the week, and quantity of pizzas delivered. For each day there is no more than one record. It's considered that on those days that are not explicitly mentioned in the input file, but fall between the earliest and the latest mentioned days, zero-quantity orders were fulfilled.

Output file format

Output periodicity of the optimal schedule — integer number L from 1 to 4. Then output numbers Ai for each i from 1 to L × 7. If several solutions exist, output any of them. However, make sure that the first week of your schedule corresponds to the earliest week mentioned in the input file.

Constraints

1 ≤ qi ≤ 100, 1 ≤ wi ≤ 52, 1 ≤ di ≤ 7

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
6
1 5 3  3 1 3  3 5 3
5 1 3  5 5 3  7 5 3
 
2
3 0 0 0 3 0 0
0 0 0 0 0 0 0
2 
15
1 3 1  1 5 2
2 3 1  2 5 2
3 3 1   
4 3 1  4 5 3
5 3 1  5 5 2
6 3 1  6 5 2
7 3 1  7 5 2
8 3 1  8 5 2
 
1
0 0 1 0 2 0 0
0.061s 0.008s 13