## An Animal Contest 3 P6 - Monkey Station

View as PDF

Points: 17
Time limit: 2.0s
Python 3.0s
Memory limit: 256M
Python 512M

Author:
Problem type

Sanjay the monkey loves trains! To prepare for his aspirations as a conductor, Sanjay practices with the train set he received last Christmas. Sanjay has a board of rows by columns, indexed from to and to respectively. He has trains lined up on the leftmost column, column , and trains lined up on the topmost row, row , each occupying a single cell on the board.

The trains placed on the first column move horizontally, across the row they are initially parked at, until they reach column , at which point they stay there and no longer move. The trains placed on the first row move vertically, down the column they are initially parked at, until they reach row , at which point they stay there and no longer move. Sanjay wants to coordinate the departure of each of his trains so that the last train reaches its destination at the earliest time possible and no trains collide at any point, meaning no two trains can arrive at the same cell at the exact same time.

If a train starts at the topmost row and starts moving at time , it will arrive at row at time . Similarly, if a train starts at the leftmost column and starts moving at time , it will arrive at column at time .

Sanjay has his answer, but he wants to receive confirmation. Your task is to determine the minimum possible time such that all trains have arrived at their destination with no collisions and configure the departure times of each of Sanjay's trains to achieve this.

for all .

for all .

#### Input Specification

The first line will contain two space-separated integers, and .

The second line will contain two space-separated integers, and .

The third line will contain space-separated integers denoting the position of the train on the leftmost column.

The fourth line will contain space-separated integers denoting the position of the train on the topmost row.

#### Output Specification

On the first line output one integer , the minimum time possible that all trains can arrive at their destination without collisions.

On the second line output space-separated integers, the departure time of the train on the leftmost column. These trains must arrive at column at or before .

On the third line output space-separated integers, the departure time of the train on the topmost row. These trains must arrive at row at or before .

Note: Any valid output will be accepted.

#### Sample Input

2 1
1 1
1
1

#### Sample Output

3
1
0

#### Explanation

For the purposes of this explanation, assume that cell is the top-leftmost cell and cell is the bottom-rightmost cell in the above diagrams. The train on the leftmost column is labeled and the train on the topmost row is labeled .

The initial configuration at time and direction of movement is shown by the leftmost diagram, with each subsequent diagram representing the situation at times , , and respectively.

At time , train reaches cell having departed at time . Train departs.

At time train reaches cell and train reaches cell . No collision occurs.

At time trains and reach cells and respectively, and since both trains have reached their destination, is . It can be shown that this is the best possible answer.