Parse a URL Query String

The part of a web address after the ? carries parameters, like q=python+books&page=2. Write parse_query(query) that turns such a string into a dictionary from keys to values:

• Pairs are separated by &. Each pair is split at its first = into a key and a value, and a pair with no = gets the value ''. Empty pairs (from && or a trailing &) are skipped.
• In keys and values, + stands for a space, and % followed by two hex digits (in either case) is the character with that code: %20 is a space, %2B is + and %3D is =. Turn the + signs into spaces before decoding the % codes, so that %2B ends up as a real plus.
• If a key appears more than once, its value is a list of all its values in order. Otherwise the value is a string.
• Keys are in the order in which they first appear.

Examples

parse_query("q=python+books&page=2")
# returns {'q': 'python books', 'page': '2'}
parse_query("tag=a&tag=b&sort=new&tag=c")
# returns {'tag': ['a', 'b', 'c'], 'sort': 'new'}
parse_query("debug&name=Ada%20Lovelace&sum=1%2B1%3D2")
# returns {'debug': '', 'name': 'Ada Lovelace', 'sum': '1+1=2'}

Constraints

• query has 0 to 10,000 characters and does not include the ?.
• Every % is followed by two hex digits between 00 and 7F (a plain ASCII character).