3430 -- Pizza schedule

Language:

Pizza schedule

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 484		Accepted: 152		Special Judge

Description

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), A₁, A₂, …, A_L × 7 — quantity of pizzas to be delivered for each day of the period (A_i ≥ 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

Input file contains the following integer numbers:

N — number of fulfilled orders in the delivery history w₁ d₁ q₁ w₂ d₂ q₂... 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.

Constraints

1 ≤ q_i ≤ 100, 1 ≤ w_i ≤ 52, 1 ≤ d_i ≤ 7

Output

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

Sample Input

Sample input 1
6
1 5 3  3 1 3  3 5 3
5 1 3  5 5 3  7 5 3
Sample input 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

Sample Output

Sample output 1
2
3 0 0 0 3 0 0
0 0 0 0 0 0 0
Sample output 2
1
0 0 1 0 2 0 0

Hint

Bold texts appearing in the sample sections are informative and do not form part of the actual data.

Source

Northeastern Europe 2005, Far-Eastern Subregion