Reconciled event log: hints, no solution

Two recording devices captured the same session and each wrote its own event log. Every log is a list of event times in non-decreasing order, and one log may hold the same time more than once when several events fired together.

Reconcile the logs into a single non-decreasing list. An event that both devices captured must appear only once. Treat times as identities: if a given time occurs m times in the first log and n times in the second, it must occur exactly the larger of m and n times in the result. Either log may be empty.

Examples

Input

first = [1, 4, 6], second = [2, 4, 9]

Output

[1, 2, 4, 6, 9]

Note

Time 4 was captured by both devices, so it appears once.

Input

first = [3, 3, 5], second = [3, 8]

Output

[3, 3, 5, 8]

Note

Time 3 occurs twice in the first log and once in the second, so it occurs twice in the result.

Input

first = [], second = [2, 2]

Output

[2, 2]

Note

An empty log leaves the other log unchanged.

Constraints

• 0 <= first.length, second.length <= 400
• 0 <= time <= 1000, each log is non-decreasing
• Return a non-decreasing list

Hint 1: a nudge

At any moment, which event from the two logs can you safely put next in the result?

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