Description

Consider arranging nine clocks in a 3×3 grid:

The goal is to find the minimum sequence of moves to point all the hands to 12 o'clock. The table below lists 9 different methods for rotating the hands, each method is called one move. Choosing methods 1 to 9 will cause the corresponding clocks in the table to rotate 90 degrees clockwise.

Example

Input Format

Input consists of three lines, each containing three positive integers, representing the initial time of each clock. The meaning of the numbers is the same as explained in the first example.

Output Format

A single line including a space-separated list of the shortest move sequence to point all the clocks to 12 o'clock.

If there are multiple solutions, output the one that results in the smallest concatenated number (for example, 5 2 4 6 < 9 3 1 1).

9 9 12
6 6 6
6 3 6 

4 5 8 9