URL Query Parameter Parsing

A search page receives URLs like https://stays.example/search?city=Lisbon&guests=2#map and needs the parameters as a dictionary.

Implement:

def parse_query(url: str) -> dict[str, str | list[str]]

Follow these rules, in this order:

1. Fragment. Everything from the first # in the URL onwards is ignored.
2. Query string. The query string is everything after the first ? in what's left. If there is no ?, return {}. Later ? characters are ordinary text.
3. Pieces. Split the query string on &. Empty pieces (from &&, or a leading or trailing &) are skipped.
4. Key and value. Split each piece at its first =: the part before is the key, the rest is the value (it may contain more =). A piece with no = has the value "".
5. Decoding. Decode the key and the value separately, after splitting, so an encoded & or = doesn't split anything:
   • + becomes a space;
   • % followed by two hex digits (either case) becomes the character with that code, e.g. %20 is a space and %3D is = (inputs only encode codes below 0x80);
   • any other % is kept as it is, e.g. 100% or %zz.
6. Empty keys. A piece whose decoded key is empty (like =5) is skipped.
7. Repeated keys. A key seen once maps to its value string. A key seen more than once maps to a list of all its values, in the order they appear.

parse_query("https://stays.example/search?city=Lisbon&guests=2#map")
# {"city": "Lisbon", "guests": "2"}

parse_query("/s?amenity=wifi&amenity=pool&q=sea+view&note=a%3Db%26c&flex")
# {"amenity": ["wifi", "pool"], "q": "sea view", "note": "a=b&c", "flex": ""}

parse_query("/s?&&=oops&x=1=2&disc=100%&y")
# {"x": "1=2", "disc": "100%", "y": ""}

parse_query("/about#faq?x=1")     # {}    the ? is inside the fragment

URLs can be up to 500,000 characters with tens of thousands of pieces, many of them sharing one key. Keep the work linear: don't rebuild a key's list every time you add a value.