Train Security#1431
At a railway switch, there are two trains, each consisting of carriages guarded by a certain number of people (from to ). Your task is to form a single train that is as well-protected as possible, while maintaining the original order of carriages within each train.
Assume that the protection of the -th carriage in a train equals the total number of guards in the carriages from the -st to the -th one. Between two trains of equal length, the first train is better protected than the second if, for the smallest index where the protection of the -th carriage differs between the two trains, the -th carriage in the first train has a greater protection value than in the second.
The first line contains a sequence of digits from to without spaces, where the -th digit is the number of guards in the -th carriage of the first train.
The second line contains a sequence of digits from to without spaces, where the -th digit is the number of guards in the -th carriage of the second train.
Each train contains at least and at most carriages.
Output a single line containing a sequence of digits from to without spaces. The -th digit should be the number of guards in the -th carriage of the most well-protected train that can be obtained from the given ones according to the rules described above. The length of this train is equal to the sum of the lengths of the two original trains.
Example 1