Top Products Analysis

You are given a list of sales transactions. Each transaction includes the date of sale, a product ID, and a quantity sold. Your task is to determine the top k products with the highest total quantity sold within a specified date range.

The transactions should be filtered based on their dates. Only consider transactions where the date falls in the inclusive range \( [\text{start\_date},\, \text{end\_date}] \). After filtering, sum up the quantities for each product and then output the top k products, sorted first in descending order of the total quantity and then in ascending order of the product ID.

Note: Dates are given in the format YYYY-MM-DD and comparisons can be done lexicographically.

inputFormat

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

1. The first line contains the start_date, end_date, and an integer k separated by spaces.
2. The second line contains an integer n representing the number of sales transactions.
3. The next n lines each contain a transaction in the format: date product_id quantity, separated by spaces.

For example:

2023-01-01 2023-01-03 2
6
2023-01-01 101 5
2023-01-02 101 15
2023-01-01 102 20
2023-01-03 103 7
2023-01-03 101 2
2023-01-04 104 12

outputFormat

Output to standard output (stdout) the top k products that satisfy the condition. Each line of the output contains two values: product_id and the total quantity sold, separated by a space.

If no transactions fall in the date range, output nothing.

For example, the output for the sample input above would be:

101 22
102 20

## sample

2023-01-01 2023-01-03 2
6
2023-01-01 101 5
2023-01-02 101 15
2023-01-01 102 20
2023-01-03 103 7
2023-01-03 101 2
2023-01-04 104 12

101 22
102 20

</p>