Alternate merge: hints, no solution

A party host combines two playlists into one. Each playlist arrives as an array of track ids from the first track to the last. The combined list takes one track from the first playlist, then one from the second, then the next from the first, and so on. The ids are not sorted and are copied exactly, including repeats.

When one playlist runs out, every remaining track of the other is appended in its original order. Return the combined list. Either playlist can be empty.

A linked-list solution splices nodes together with two moving cursors and no copying of the ids.

Examples

Input

first = [10, 20, 30], second = [7, 8]

Output

[10, 7, 20, 8, 30]

Note

The order is 10, 7, 20, 8, 30, and 30 is left after the second list ends.

Input

first = [], second = [4, 5]

Output

[4, 5]

Note

The first list is empty, so the second list comes through unchanged.

Constraints

• 0 <= first.length, second.length <= 300
• 0 <= id <= 999
• Ids are not sorted and may repeat

Hint 1: a nudge

At any moment, whose turn is it, and what changes when one side has nothing left to give?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing