Shard Rebalancing

You are implementing a shard management system for a distributed key-value store. Each shard is represented as a string in the format "id:start:end", where the shard covers the inclusive key range [start, end]. Given an integer limit and an array shards, rebalance the shards so that:

• No key is covered by more than limit shards.
• Processing happens after sorting the original shards by start ascending, then end ascending.
• If a shard would cover a key that already has limit active shards, shift that shard's start to the earliest key where coverage becomes strictly less than limit.
• If shifting makes start > end, delete that shard.
• After all shifts and deletions, coverage must stay continuous from the original minimum start to the original maximum end. If a gap appears, extend the most recently kept shard to fill it. Return the rebalanced shards in the same "id:start:end" format. You may return them in any order. Identifiers are distinct and do not contain colons.

Shard C cannot start at 80 because keys 80..100 are already covered by A and B. It shifts to 101. Then C is extended to 209 to fill the gap before D.

After A and B, shard C must move to 31. Shard D is processed later and must start after the saturated region, so it becomes 32:100.