Охрана поезда
На железнодорожной стрелке стоят два состава вагонов, каждый из которых охраняет некоторое количество человек (от 0 до 9). Требуется составить из этих вагонов единый состав, который будет максимально защищенным, при этом менять порядок следования вагонов, принадлежащих изначально одному составу, нельзя.
Будем считать, что k-ый вагон состава имеет защиту, равную общему количеству охранников в вагонах с 1-го по k-ый. Тогда из двух составов равной длины первый защищен лучше, чем второй, если для наименьшего номера m из всех номеров n, таких что защита вагона с номером n в первом и во втором составах различна, вагон с номером m имеет большую защиту в первом составе.
Входные данные
В первой строке последовательность чисел от 0 до 9 без пробелов, где i-ое число равно количеству охранников i-го вагона первого состава.
В второй строке последовательность чисел от 0 до 9 без пробелов, где i-ое число равно количеству охранников i-го вагона второго состава.
Количество вагонов в каждом составе не менее 1 и не более 50000.
Выходные данные
В первой строке последовательность чисел от 0 до 9 без пробелов, где i-ое число равно количеству охранников i-го вагона наиболее защищенного состава, который можно получить из имеющихся составов согласно описанным выше правилам. Длина этого состава, очевидно, равна сумме длин исходных составов.