Read repeated keys from a URL query string

A search page keeps its filters in the URL's query string, the part after the ?. Some filters, such as tags, can appear more than once.

Write parse_query(qs) that returns the keys and values in qs as a dictionary.

Input and output:

• qs: a query string of up to 10,000 characters, with or without its leading ?.
• Returns a dictionary from each decoded key to its decoded value. A key that appears once maps to a string. A key that appears more than once maps to a list of all its values, in the order they appear. Key order does not matter.

Rules:

• If qs starts with ?, drop that one character first.
• Split on & into pairs. Skip empty pairs, which come from && or from a & at the start or end.
• Split each pair at its first =. The key is the text before it, and the value is everything after it, including any later =.
• A pair with no = has the empty string as its value. A pair that starts with = has the empty string as its key.
• Decode each key and value only after splitting, so an encoded & or = never splits anything.
• To decode, read left to right. A % followed by two hex digits, in either case, stands for one byte. Each run of such escapes is read as UTF-8 text. The input always encodes complete, valid UTF-8 characters.
• A % without two hex digits right after it stays as it is. Every other character stays as it is too, including +.
• Decoding happens once. A character that decoding produced is never decoded again.
• Keys are compared after decoding.
• An empty string returns an empty dictionary.