Frugal testing

Time limit1sMemory limit1024 MB

Summary

Pick the smallest test set that fails every incorrect solution to the Assembling times task, which asks for two hh:mm times with the largest possible sum.

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

Problem

Time limit: 1000 ms. Memory limit: 1024 MB.

Juku is preparing the following task for a programming contest:

Assembling times

You are given eight cards, each with a digit ( $0 \ldots 9$ ) on it. You also have two cards, each with the character : on it.

Combine the cards to form two valid times so that their sum is as large as possible. If several arrangements give the maximal sum, output the lexicographically largest one.

Valid times have the form $hh:mm$ , where

$hh$ is one of $00, 01, \ldots, 23$ ;

$mm$ is one of $00, 01, \ldots, 59$ .

If it is not possible to form two valid times, output -1.

To reduce the time needed to evaluate solutions, Juku wants a test set with as few cases as possible that still ensures no incorrect solution achieves full score.

To prepare the test data, Juku proceeds as follows:

write a large number of known incorrect solutions;
generate a set of test cases that fails all of those incorrect solutions.

A test set fails a solution if the solution gives a wrong answer on at least one test case in the set.

Help Juku find the smallest possible test set that fails all the incorrect solutions he has.

Output

The first line of your output should contain $N$ , the number of test cases. Each of the following $N$ lines should contain 8 digits separated by spaces, the input data for one test case.

Examples1

Example 1

Input

Expected output

5
0 6 4 5 2 3 1 7
4 6 4 5 2 3 4 7
0 1 1 8 9 9 9 8
8 1 9 9 9 1 1 9
7 2 5 3 0 0 0 0