Top N Spenders

You are given a list of transactions and a date range. Each transaction contains a user_id, item_id, amount (the money spent) and a timestamp in the format \(YYYY-MM-DD\). Your task is to identify the top \(N\) users who spent the most money within the specified date range (inclusive).

For each transaction, if its timestamp \(t\) satisfies \(start\_date \leq t \leq end\_date\), include its amount in the total spending for that user. After processing all transactions, sort the users by their total spending in descending order. In case of ties, choose the user with the smaller user id first.

If there are fewer than \(N\) users with valid transactions, output all such users. If no transaction falls within the date range, output nothing.

inputFormat

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

T
user_id item_id amount timestamp
user_id item_id amount timestamp
... (T lines in total)
start_date end_date N

Where:

• T is the number of transactions.
• Each transaction line contains four space-separated values: user_id (an integer), item_id (an integer), amount (an integer) and timestamp (a string in the format YYYY-MM-DD).
• The last line contains two dates (start_date and end_date) and an integer N.

outputFormat

Output the top \(N\) user ids (space-separated) in one line based on total spending in the given date range. If there are no valid transactions, output an empty line.

5
1 10 100 2021-05-01
2 20 300 2021-05-02
1 30 400 2021-05-03
3 40 200 2021-05-04
2 50 100 2021-05-05
2021-05-01 2021-05-04 2

1 2