<?xml version="1.0" encoding="Windows-1251"?>
<CATS version="1.2">
<Problem title="Pizza schedule" lang="en"
  author="T. Chistyakov" tlimit="1" mlimit="2"
  inputFile="input.txt" outputFile="output.txt">

<ProblemStatement>

 <p>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.

 </p><p>
 So formally pizza delivery schedule can be described by the following 
 numbers: $L$ -- length of the schedule period (from 1 to 4), 
 $A_1, A_2, \dots, A_{L \times 7}$ -- quantity of pizzas to be delivered for 
 each day of the period ($A_i \ge 0$).
 </p><p>
 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.
 </p><p>
 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.
 </p><p>
 So it's often impossible to restore the original schedule exactly. 
 That is why your task is to find an <i>optimal schedule</i>, 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.</p>
</ProblemStatement>

<ProblemConstraints>
 $1 \le q_i \le 100, 1 \le w_i \le 52, 1 \le d_i \le 7$
</ProblemConstraints>

<InputFormat>
 <p>
 Input file contains the following integer numbers:
 </p><p>$N$ -- number of fulfilled orders in the delivery history
 $w_1 d_1 q_1 w_2 d_2 q_2 \dots w_N d_N q_N$ -- 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.</p>
</InputFormat>

<OutputFormat>
 Output periodicity of the optimal schedule -- integer number $L$ 
 from 1 to 4. Then output numbers $A_i$ for each $i$
 from 1 to $L \times 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<!--(no circular shifts are 
 allowed)-->.
</OutputFormat>

<Sample rank="1">
  <SampleIn>6
1 5 3  3 1 3  3 5 3
5 1 3  5 5 3  7 5 3</SampleIn>
  <SampleOut>2
3 0 0 0 3 0 0
0 0 0 0 0 0 0</SampleOut>
</Sample>

<Sample rank="2">
  <SampleIn>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</SampleIn>
  <SampleOut>1
0 0 1 0 2 0 0</SampleOut>
</Sample>

<Generator name="g1" src="g1.dpr" outputFile="*STDOUT"/>
<Generator name="g1m" src="g1m.dpr" outputFile="*STDOUT"/>
<Generator name="g2" src="g2.dpr" outputFile="*STDOUT"/>
<Generator name="g1mm" src="g1mm.dpr" outputFile="*STDOUT"/>
<Solution name="sol" src="pizza_tim.dpr"/>
<Solution name="sol_ask" src="pizza_ask.dpr"/>

<Checker src="pizza_check.dpr" style="testlib"/>
<TestRange from="1" to="7"><In src="%0n.in"/><Out src="%0n.out"/></TestRange>
<TestRange from="8" to="11"><In src="%0n.in"/><Out src="08-11.out"/></TestRange>
<TestRange from="12" to="13"><In src="%n.in"/><Out src="%n.out"/></TestRange>
<Test rank="14"><In use="g1"/><Out src="14.out"/></Test>
<TestRange from="15" to="16"><In src="%n.in"/><Out use="sol"/></TestRange>

<Test rank="17"><In use="g1m" param="1 2"/><Out use="sol"/></Test>
<Test rank="18"><In use="g1m" param="2 20"/><Out use="sol"/></Test>
<Test rank="19"><In use="g1m" param="3 4"/><Out use="sol"/></Test>

<Test rank="20"><In use="g2" param="4 50"/><Out use="sol"/></Test>
<Test rank="21"><In use="g2" param="5 300"/><Out use="sol"/></Test>

<Test rank="22"><In use="g1mm" param="6 3 5"/><Out use="sol"/></Test>
<Test rank="23"><In use="g1mm" param="8 2 30"/><Out use="sol"/></Test>
<Test rank="24"><In use="g1mm" param="9 1 3"/><Out use="sol"/></Test>

</Problem>
</CATS>
