Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Pizza schedule
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 456Accepted: 147Special 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), 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

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.

Constraints

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

Output

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.

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

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator