Монокарп и Поликарп изучают новые приемы программирования. Сейчас они решили попробовать парное программирование.
Известно, что они проработали вместе \(n + m\) минут, работая над одним файлом. Каждую минуту ровно один из них делал одно изменение в файле. До начала их работы в файле было \(k\) строк.
За одну минуту любой из них может выполнить одно из двух действий: добавить новую строку в конец файла или изменить одну его строку.
Суммарно Монокарп работал \(n\) минут и выполнил последовательность действий \([a_1, a_2, \dots, a_n]\), где \(a_i = 0\), если он добавил новую строку в конец файла или \(a_i > 0\), если он изменил строку с номером \(a_i\). Действия Монокарп производил именно в таком порядке: сначала \(a_1\), затем \(a_2\) и так далее до \(a_n\).
Суммарно Поликарп работал \(m\) минут и выполнил последовательность действий \([b_1, b_2, \dots, b_m]\), где \(b_j = 0\), если он добавил новую строку в конец файла или \(b_j > 0\), если он изменил строку с номером \(b_j\). Действия Поликарп производил именно в таком порядке: сначала \(b_1\), затем \(b_2\) и так далее до \(b_m\).
Восстановите их общую последовательность действий длины \(n + m\), такую, в которой все действия были бы корректными — то есть не должно быть изменений еще не существующих строк. Имейте в виду, что в общей последовательности действия Монокарпа должны образовывать подпоследовательность \([a_1, a_2, \dots, a_n]\), а Поликарпа — подпоследовательность \([b_1, b_2, \dots, b_m]\). Монокарп и Поликарп могут сменять друг друга за компьютером произвольное количество раз.
Рассмотрим пример. Пусть изначально \(k = 3\). Монокарп сначала изменил строку с номером \(2\), а затем добавил новую строку (то есть \(n = 2, \: a = [2, 0]\)). Поликарп же сначала добавил новую строку, а затем изменил строку с номером \(5\) (то есть \(m = 2, \: b = [0, 5]\)).
Так как изначальная длина файла равна \(3\), для того, чтобы Поликарп смог изменить строку с номером \(5\), необходимо сначала добавить две новые строки. Примером правильных последовательностей изменений в таком случае будет \([0, 2, 0, 5]\) или \([2, 0, 0, 5]\). Последовательности изменений \([0, 0, 5, 2]\) (нарушен порядок действий) и \([0, 5, 2, 0]\) (нельзя отредактировать строку \(5\)) не являются корректными.