You are implementing a shard management system for a distributed key-value store. Each shard is identified by a string and covers a contiguous range of integer keys, represented as "<id>:<start>:<end>".

To balance load, the system enforces a coverage limit: no key may be covered by more than limit active shards simultaneously. Implement rebalance(limit, shards) which resolves overlaps and fills gaps according to these deterministic rules: ...