Train Security
At a railway switch, there are two trains, each consisting of carriages guarded by a certain number of people (ranging from 0 to 9). Your task is to merge these carriages into a single train that is as well-protected as possible, while maintaining the original order of carriages within each train.
Assume that the protection level of the k-th carriage in a train is determined by the total number of guards from the 1-st to the k-th carriage. Between two trains of the same length, the first train is considered better protected than the second if, for the smallest index m where the protection levels differ, the protection level of the m-th carriage in the first train is greater than that in the second train.
Input
The first line contains a sequence of digits from 0 to 9 without spaces, where the i-th digit represents the number of guards in the i-th carriage of the first train.
The second line contains a sequence of digits from 0 to 9 without spaces, where the i-th digit represents the number of guards in the i-th carriage of the second train.
Each train has at least 1 carriage and no more than 50000 carriages.
Output
The output should be a single line containing a sequence of digits from 0 to 9 without spaces. Each digit represents the number of guards in the corresponding carriage of the most protected train that can be formed from the given trains, following the rules described. The length of this train will be the sum of the lengths of the two original trains.