Parse a URL Query String

Web servers turn ?q=hello+world&tag=ai&tag=ml&empty= into data. Implement it yourself, without urllib.

parse_qs(query) returns a dict mapping each key to a list of values in order:

• An optional leading ? is ignored. Pairs are separated by &, and empty pairs are skipped.
• + means a space, and %XX is a percent-encoded byte. Decode the bytes as UTF-8, so %C3%A9 is é.
• A key with no = gets the value "".
• Malformed percent escapes (%G1, or %4 at the end) raise ValueError.

Also implement build_qs(params): the inverse, taking a dict of lists, percent-encoding everything except letters, digits and -_.~, and encoding spaces as +.