Dictionary Medians

You are given a dictionary where each key is associated with a list of integers. Your task is to compute the median of each list and output a new dictionary (or key-value pairs) where the keys remain the same but the values are replaced by the median of the corresponding list.

The median is defined as follows:

• If the list is empty, then its median is None.
• If the list has an odd number of elements, the median is the middle element after sorting the list in non-decreasing order.
• If the list has an even number of elements, the median is the average of the two middle elements. If the average is an integer, output it as an integer; otherwise, output it as a decimal (e.g. 3.5).

Note: You must use standard input (stdin) for reading the input and standard output (stdout) for writing the result. The order of keys in the output should be the same as the input order.

inputFormat

The input begins with an integer N indicating the number of keys. Following that, for each key there are two or three lines:

1. A line containing the key (a string without spaces) and an integer M (the number of integers in the list) separated by a space.
2. If M > 0, then a line containing M space-separated integers.

If M is 0, no additional line is provided for that key.

outputFormat

For each key, output a line containing the key and its median separated by a space. If the list is empty, output 'None' as the median. The order of the output lines should be the same as the input order.

## sample

3

a 3
1 3 5
b 4
2 4 6 8
c 0

a 3
b 5
c None

</p>