1941. Walking a List of Lists, Empties Included

There are g groups, each holding zero or more values. Build an iterator that walks every value, group by group and in order within each group, with four operations:

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

g = 4, the groups are [] [5 6] [] [7] hasnext -> yes group -> 2 group 1 is empty, so the first value is in group 2 next -> 5 next -> 6 group -> 4 group 3 is empty too next -> 7 hasnext -> no group -> done next -> done

## The rules, stated so the answer is decidable

• Every operation prints exactly one line.
• An empty group contributes nothing and must disappear completely. It never
• makes hasnext say yes, never becomes the answer to group, and never
• produces a value.
• next, peek and group print done when every value has been consumed.
• hasnext prints yes exactly when a next would print a value.
• An empty group may sit anywhere: before the first value, between two values,
• after the last value, or several in a row. All of those are legal input, and
• each is a different bug.
• Every group may be empty, in which case the iterator is finished before it
• starts.

## What most people try first

Keep a group index and a position inside it, then on next check whether the position has run off the end of the current group and, if so, move to the next group. That is almost right, and it fails on two empty groups in a row, because moving on ONCE leaves the cursor inside another empty group. The usual symptom is a done in the middle of the data, or a crash reading past the end of a group that holds nothing.

The other common approach is to flatten everything into one list in the constructor. That is correct and it is O(total) time and memory up front, which defeats the point of an iterator: a structure whose whole job is to avoid materialising the sequence.

## Keep the cursor on a real value at all times

State one invariant and maintain it everywhere:

either the cursor is past the last group, or it points at a value that actually exists

The code that enforces it is a LOOP, not an if:

settle(): while the group index is in range and the position is past that group's end: move to the next group, position 0

Call settle once at the start, and again immediately after every consumption. Then every query is a direct read with no checking beyond "is the group index past the end":

next: value at the cursor, advance the position, settle peek: value at the cursor hasnext: whether the group index is still in range group: the group index, plus one

## Why it is correct

With the invariant in force, "the group index is past the last group" is exactly the same statement as "there are no values left", which is what makes every query a one line answer. The loop establishes the invariant because it only stops in one of those two states, and it terminates because the group index strictly increases on every iteration.

Calling settle at construction time is what handles empty groups at the START, which an implementation that only settles after a consumption gets wrong: its first hasnext or group reports from inside an empty group before anything has been consumed.

## Why the loop is cheap

A settle call can skip many groups, so a single next is not constant time. But the group index never moves backwards, so across the whole run the loop body runs at most g times in total. Every operation is amortised O(1), and the whole run is O(g + q) with no flattening and no copying.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. The total number of values across all groups reaches 2 * 10^5. Nothing here is summed or multiplied, so 32 bit arithmetic is safe.

## Cost

Amortised O(1) per operation, O(g + q) for the run, and no extra memory beyond the input.

Constraints - `1 ≤ g ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ m`, and the total of all `m` is at most `200000` - `0 ≤` each value `≤ 1000000000` - each operation must run in amortised `O(1)`, so the whole run is `O(g + q)`, and the groups must not be flattened into one list - the judge cannot enforce the no-flattening rule: the declared tests are small and there is no test generator yet, so a solution that copies everything into one list up front passes them while using `O(total)` extra memory