Movie Recommendation System

Given a list of users with their rated movies and a list of available movies, your task is to recommend one unwatched movie for each user. The recommendation is based on the highest average rating of the movie computed across all users' ratings. If a user has watched all movies, output None.

The average rating for a movie is computed as follows:

$$\text{avg} = \frac{\sum_{i=1}^{n} \text{rating}_i}{n} $$

In case of ties, choose the movie that appears earlier in the movies list.

inputFormat

The input is read from standard input (stdin) with the following format:

1. The first line contains an integer U, the number of users.
2. For each user, the first line contains two integers: user_id and R (the number of ratings for that user).
3. Then follow R lines, each containing a movie title (a string without spaces) and an integer rating.
4. After all users, a line with an integer M, the number of available movies.
5. Then follow M lines, each containing a movie title (a string without spaces).

outputFormat

For each user (in order of increasing user_id), output a single line in the format:

user_id recommended_movie

If the user has watched all movies, output None in place of the movie title.

## sample

3
1 2
Movie1 5
Movie2 3
2 2
Movie1 4
Movie3 5
3 2
Movie2 2
Movie3 4
4
Movie1
Movie2
Movie3
Movie4

1 Movie3
2 Movie2
3 Movie1

</p>