Video Recommendation Based on Similar Users

You are given rating logs from multiple users, and a target user U. Two users are considered similar if they have rated at least one common video with the same rating. For each test case, your task is to recommend the top K videos that the target user has not yet rated, by aggregating the ratings from similar users.

For every video not rated by the target user, its score is defined as the sum of ratings given by similar users. The recommended videos should be output in descending order of their aggregated score. If multiple videos have the same score, output the one with a smaller video ID first. If no videos are recommended, output -1.

Note: If there are fewer than K candidate videos, output all of them. Use the following steps to solve the problem:

• For each test case, read N (the number of users), M (the number of rating entries), the target user U, and K (the number of videos to recommend).
• Each of the next M lines contains three integers: user_id, video_id, and rating.
• Determine all users who are similar to the target user U.
• For each video not rated by U, if it is rated by at least one similar user, sum up those ratings.
• Sort the candidate videos by their total score in descending order. If two videos have the same score, the video with the smaller ID comes first.
• Output the top K video IDs (space-separated) on a single line, or -1 if there are no recommendations.

The formula for the score of a video v is given by:

[ Score(v) = \sum_{u \in S} rating(u, v) \quad \text{if } v \notin ratings(U) ]

where S is the set of users similar to the target user.

inputFormat

The input begins with an integer T representing the number of test cases. Each test case is formatted as follows:

N M U K
user_id1 video_id1 rating1
user_id2 video_id2 rating2
... (M lines total)

For each test case:

• N: the number of users (users are labeled from 1 to N).
• M: the number of rating records.
• U: the target user ID.
• K: the number of top recommended videos.
• Next, there are M lines, each containing three integers: user_id, video_id, and rating.

outputFormat

For each test case, output a single line containing the recommended video IDs separated by a single space, or output -1 if no video can be recommended.

## sample

5
5 10 2 2
1 101 4
1 102 5
2 101 4
2 103 2
3 101 3
3 102 5
4 103 2
4 104 5
5 103 2
5 101 4
3 5 1 3
1 201 2
1 202 3
2 203 4
3 204 5
3 205 1
4 8 1 2
1 301 5
2 301 5
2 302 3
2 303 4
3 301 5
3 304 1
4 301 2
4 305 3
3 4 1 5
1 401 3
2 401 3
2 402 4
3 401 3
3 6 1 3
1 501 4
2 501 4
2 502 5
3 501 4
3 503 2
3 504 3

102 104
-1
303 302
402
502 504 503

</p>