First n across logs: hints, no solution

Several dispatch centres each keep a call log: a list of call timestamps in minutes, already sorted in ascending order. Timestamps can repeat, within one log and across logs, and a log may be empty.

Combine all the logs into one ascending sequence in which every timestamp from every log appears, repeats included, and return its first n entries. If the logs together hold fewer than n timestamps, return all of them. The logs can be long compared with n, so do not build and sort the whole combined sequence.

Examples

Input

logs = [[1, 4, 9], [2, 3, 10], []], n = 4

Output

[1, 2, 3, 4]

Note

Taking the smallest available timestamp four times gives 1, 2, 3, 4.

Input

logs = [[5, 5], [5]], n = 5

Output

[5, 5, 5]

Note

Only three timestamps exist, so all are returned.

Constraints

• 0 <= number of logs <= 100000 and 0 <= total timestamps <= 100000
• 0 <= timestamp <= 1000000
• 0 <= n <= 60000

Hint 1: a nudge

Which single timestamp is guaranteed to be the smallest of everything not yet taken, and where in the logs could you find it by looking at very few entries?

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