Socks от (Demo) Java Advanced Exam - 17 Feb 2019

Здравейте!Може ли да помогнете с тази задача?Мерси предварително!

https://paste.ofcode.org/3bnDtciqRDAtNLeyGSavgrC

Socks

George is a young poorly organized person and he always have problems with his socks. He has always dreamed of a program that makes sets of his washed socks. You are the chosen one to help him with his problem. Good luck!

First you will be given a sequence of integers representing the left socks. Afterwards you will be given another sequence of integers representing the right socks. 

Check all of the left socks and right socks in order to make sets. Take the last given left sock, and the first given right sock and check if the left sock is bigger than the right sock and if it is – you have to create a pair. A pair is created when you add the value of the right sock to the value of the left one. If you have a pair, remove both the left and the right socks from their collections. 

If the right sock value is bigger –and check remove the left one the next one. 

If their values are equal – remove the right sock and increment the value of the left one with 1

George wants to wear the biggest set, so you have to find out which one it is.

Afterwards print the created pairs from the first added to the last, separated by a space. 

Input

  • On the first line of input you will receive the integers, representing the left socks, separated by a single space. 
  • On the second line of input you will receive the integers, representing the right socks, separated by a single space.

Output

  • On the first line of output - print the biggest pair in the format specified above. 
  • On the second line - print the pairs, separated by a single space in the order specified above.

Constraints

  • All of the given numbers will be valid integers in the range [1, 10000].
  • There will always be at least 1 pair.
  • Allowed time/memory: 100ms/16MB.

Examples

Input

Output

Comment

10 8 7 13 8 4

4 7 3 6 4 12

16

15 16 13 12

First, we take the last given left sock – 4 and the first given right sock – 4. They are equal, so we have to remove the right sock and increment the left with 1. The left sock becomes 5 and the collection looks like this

Left: 10 8 7 13 8 5

Right: 7 3 6 4 12

Next, we take the left with value 5 and the right with value 7 – the right is bigger, so we remove the left and the collections should look like this:

Left: 10 8 7 13 8

Right: 7 3 6 4 12

After that we the left 8 and the right 7 – the left is bigger, so we have our first pair with value 15. In the end we have to print the biggest pair, which in this case is with value 16, and the collection of pairs, that we have created.

9 5 4 7 8 5 2 6 9

1 4 5 7 9 6 3 5 4 7

16

10 10 15 16