Movie Recommendation Based on Similarity Scores

You are given a user's watch history for movies and a collection of similarity scores between pairs of movies. Your task is to recommend movies that the user hasn't seen yet, based on the accumulated similarity scores from the movies in the user's watch history.

The recommendation algorithm works as follows:

For each similarity record \( (a, b, s) \):

• If movie \( a \) is in the watch history and movie \( b \) is not, add \( s \) to the accumulated score of movie \( b \).
• If movie \( b \) is in the watch history and movie \( a \) is not, add \( s \) to the accumulated score of movie \( a \).

After processing all similarity records, select the top \( k \) movies (where \( k \) can be provided as input, default is 5) with the highest accumulated similarity scores. If there is a tie in scores, you may order by the movie ID in increasing order.

The input is given via standard input and the output should be printed to standard output.

Note: If the watch history is empty or no movie qualifies for recommendation, output an empty line.

In mathematical terms, for each candidate movie \( i \) (not in the user's watch history), its score \( S_i \) is computed as:

[ S_i = \sum_{\substack{(a, b, s) ;\text{s.t.}; (a \in H ;\wedge; b=i) ;\text{or}; (b \in H ;\wedge; a=i)}} s, ]

where \( H \) is the set of movies in the watch history. Then, output the top \( k \) movies with the highest scores.

inputFormat

The input format is as follows:

<n>
<movie_id[1] movie_id[2] ... movie_id[n]>
<m>
<a1 b1 s1>
<a2 b2 s2>
... 
<am bm sm>
<k>

Where:

• n (integer): Number of movies in the user's watch history.
• Next line contains n space-separated integers representing the watched movie IDs. (If n = 0, this line can be empty.)
• m (integer): The number of similarity records.
• Each of the next m lines contains two integers and a float: a and b (movie IDs) and s (the similarity score between them).
• k (integer): The number of top recommendations to output.

All inputs are provided via standard input.

outputFormat

Output the recommended movie IDs in one line separated by a single space. If no movie is recommended, output an empty line. The output must be printed to standard output.

## sample

1
1
3
1 2 0.9
2 3 0.7
3 4 0.8
5

2

</p>