The Informatics Teacher's Ambition

Interview

Time limit2sMemory limit1024 MB

Summary

Pick two of the five weekdays so that the most students can attend both lecture days, then print that count and the chosen schedule.

Level: Easy2 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

Park Sangjin, the informatics teacher at Songdo High School, wants to make Songdo a well-known school that anyone who likes coding wants to attend.

To do this, Park Sangjin plans to hold an algorithm lecture twice a week. There are $n$ students who want to take the lecture. Each student submitted, for each day from Monday to Friday, whether they can attend class that day. A student can take the lecture only if they can attend both lecture sessions.

Help Park Sangjin choose the lecture schedule so that as many students as possible can take the lecture. Write a program that finds this schedule.

Input

The first line contains the number of students $n$ who want to take the algorithm lecture.

From the second line through line $n+1$ , line $i+1$ contains five integers $a\_{i,1}, \ldots, a\_{i,5}$ , separated by spaces, which describe whether student $i$ can attend each day. Each integer is $0$ or $1$ . The values are listed from Monday to Friday. A value of $1$ means student $i$ can attend that day, and $0$ means they cannot.

Output

Print the maximum number of students who can take the lecture on the first line.

On the second line, print five integers separated by spaces. Each integer is $0$ or $1$ , and exactly three of them are $0$ and exactly two are $1$ . The values are listed from Monday to Friday. A value of $1$ means the lecture is held that day, and $0$ means it is not. The schedule you print must allow the maximum number of students to take the lecture. If several schedules work, print any of them.

Constraints

$1\le n\le 10^6$ .

For $1 \leq i \leq n, 1 \leq j \leq 5$ , $a\_{i,j}$ is $0$ or $1$ .

Examples1

Example 1

Input

Expected output

3
0 1 1 0 0