An Animal Contest 3 P6 - Monkey Station

View as PDF

Submit solution


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 R+2 rows by C+2 columns, indexed from 0 to R+1 and 0 to C+1 respectively. He has N trains a_i lined up on the leftmost column, column 0, and M trains b_i lined up on the topmost row, row 0, 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 C+1, 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 R+1, 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 x, it will arrive at row r at time x+r. Similarly, if a train starts at the leftmost column and starts moving at time x, it will arrive at column c at time x+c.

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.

Constraints

1 \le R, C \le 10^9

1 \le N \le \min(R, 10^6)

1 \le M \le \min(C, 10^6)

1 \le a_i \le R

1 \le b_i \le C

a_i < a_{i+1} for all 1 \le i < N.

b_i < b_{i+1} for all 1 \le i < M.

Input Specification

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

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

The third line will contain N space-separated integers a_i denoting the position of the i^\text{th} train on the leftmost column.

The fourth line will contain M space-separated integers b_i denoting the position of the i^\text{th} train on the topmost row.

Output Specification

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

On the second line output N space-separated integers, the departure time of the a_i^\text{th} train on the leftmost column. These trains must arrive at column C+1 at or before t.

On the third line output M space-separated integers, the departure time of the b_i^\text{th} train on the topmost row. These trains must arrive at row R+1 at or before t.

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 (0, 0) is the top-leftmost cell and cell (R+1, C+1) is the bottom-rightmost cell in the above diagrams. The train on the leftmost column is labeled 1 and the train on the topmost row is labeled A.

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

At time 1, train A reaches cell (1, 1) having departed at time 0. Train 1 departs.

At time 2 train 1 reaches cell (1, 1) and train A reaches cell (2, 1). No collision occurs.

At time 3 trains A and 1 reach cells (3, 1) and (1, 2) respectively, and since both trains have reached their destination, t is 3. It can be shown that this is the best possible answer.


Comments

There are no comments at the moment.