1943. Merging Sorted Streams, Tie Broken By Source

There are k streams, and each one is already sorted in non-decreasing order. Build an iterator that hands back every value from every stream in non-decreasing order overall.

next print the next value and consume it peek print the next value without consuming it source print which stream, 1-indexed, the next value will come from hasnext print yes or no

## The tie rule, stated before any test asserts it

When two or more streams are offering the SAME value, the next value comes from the one with the SMALLEST stream number.

That rule is not decoration. Without it source has no single answer: two correct readers would disagree about which stream a tied value came from, and the five reference solutions for this problem would disagree with each other. The values printed by next are the same either way, which is exactly what makes the omission easy to miss and expensive to ship.

``` k = 3, the streams are [1 5] [1 9] []

source -> 1 both stream 1 and stream 2 offer 1; the lower index wins next -> 1 source -> 2 stream 2 still offers 1, stream 1 now offers 5 next -> 1 next -> 5 next -> 9 next -> done ```

This is not problem 1942. That one is a ROUND ROBIN merge, where the order is positional and the values are never compared. Here the order is by value and the stream number only settles a tie. Reading the two side by side is worth doing, because the same input produces different output.

## What most people try first

Scan all k cursors on every operation and take the smallest. It is correct, and it is O(k) per operation, so 200000 operations over 200000 streams is about 4 * 10^10 comparisons. The scan also hides the tie rule: whether it keeps the first minimum or the last decides the answer to source, and a careless <= quietly chooses the wrong one.

## A heap keyed by value and then by source

Keep a min-heap holding one entry per stream that still has a value: the stream's current value, paired with its stream number.

``` heap: (value, stream) ordered by value, then by stream

next: pop the smallest, print its value, advance that stream's cursor, and push its new value if it has one peek: the value at the top source: the stream number at the top hasnext: whether the heap is non-empty ```

Putting the stream number INSIDE the key is what makes the tie rule a property of the data structure rather than something the surrounding code has to remember. There is no comparison written anywhere that could get it wrong.

## Why it is correct

The heap holds exactly one candidate per live stream, namely that stream's smallest unconsumed value, because each stream is sorted. The overall smallest unconsumed value is therefore the smallest of those candidates, which is what the heap's top is. Since the key is the pair, and pairs compare by value first and stream number second, the top among equal values is the one with the smallest stream number, which is the stated rule.

The invariant is restored after every next: the consumed stream's next value is pushed, so it is represented again, and a stream that has run out is not pushed, so it is absent from every later comparison.

## The boundary that breaks a careless implementation

Forgetting to push the consumed stream's next value. Each stream then contributes only its first element and everything behind it disappears, which looks right on any test where every stream has length one.

The other case is an empty stream. It must never enter the heap at all, and k streams may all be empty, in which case every operation answers immediately.

## Overflow

Values reach 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. Nothing is summed or multiplied here, only compared, so 32 bit arithmetic is safe. The one quantity to size properly is the total number of values, which reaches 200000 and is also well inside 32 bits.

## Cost

O(log k) for next and O(1) for peek, source and hasnext, so the run is O(k + q log k). The judge cannot enforce that: the declared tests are small and there is no test generator yet, so the O(k) scan passes all of them while costing about 4 * 10^10 comparisons at the stated limits.

Constraints - `1 ≤ k ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ m`, and the total of all `m` is at most `200000` - `0 ≤` each value `≤ 1000000000`, and each stream is non-decreasing - `next` must run in `O(log k)` and `peek`, `source` and `hasnext` in `O(1)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so an `O(k)` scan per operation passes them while doing about `4 * 10^10` comparisons at the stated limits