Top K Sold Products

You are given a number of test cases. In each test case, you are given a list of sales records and a time interval. Each sales record contains a timestamp and a product identifier. Your goal is to determine the top K most frequently sold products whose sales occur within the given time range.

For each test case, the input begins with three integers: N (the number of sales), S (the start of the time interval), and E (the end of the time interval). The next N lines each contain two integers: a timestamp and a product identifier. Finally, an integer K is provided, representing the number of top products to output.

The ranking should be determined primarily by the frequency of sales (in descending order). In case of ties, the product with the smaller identifier comes first.

The ranking mechanism can be expressed using the following criteria: \[ \text{For two products } i \text{ and } j, \text{ product } i \text{ comes before product } j \text{ if } \big( f(i) > f(j) \big) \text{ or } \big( f(i) = f(j) \text{ and } i

inputFormat

The first line of the input contains an integer T, the number of test cases.

For each test case, the first line contains three space-separated integers: N, S, and E.

• N: The number of sales records.
• S: The start timestamp of the interval.
• E: The end timestamp of the interval.

This is followed by N lines, each containing two integers representing a sale. Each line contains:

• A timestamp.
• A product identifier.

The next line contains an integer K, indicating the number of top products to output.

outputFormat

For each test case, output a single line containing K space-separated integers, which are the product identifiers of the top K products sorted according to the ranking criteria specified (by descending frequency and then by ascending product identifier in the case of ties).

4
5 1 10
1 3
2 3
5 4
7 2
10 4
3
7 5 15
8 2
9 2
10 3
11 4
13 4
14 5
15 5
3
1 0 10
8 2
1
6 0 10
1 1
2 1
3 2
4 2
5 3
6 3
2

3 4 2
2 4 5
2
1 2