Maximizing Profit from Non-overlapping Events

You are given a list of events, where each event has a name, a profit value and a duration specified by its start day and end day. Your task is to select a subset of these events such that no two events overlap (i.e. for any two chosen events, the end day of one is less than or equal to the start day of the other) and the total profit is maximized.

In case of a tie for the maximum profit, you must choose the set of events that is lexicographically smallest when compared as a list of event names.

The events are provided in the input as follows:

• The first line contains an integer \(n\) denoting the number of events.
• Each of the next \(n\) lines contains an event description with four items: Name Profit Start End separated by spaces. Here, Name is a string identifying the event (without spaces), and Profit, Start and End are integers where \(Start < End\).

Your program must output the names of the selected events in order (separated by a single space) to achieve the highest total profit.

Note: All formulas are shown in \(\LaTeX\) format. For example, the non-overlapping condition can be written as: \(\text{if event } i \text{ and event } j \text{ are selected, then } E_i \leq S_j \text{ or } E_j \leq S_i\), where \(S\) and \(E\) represent start and end times respectively.

inputFormat

The first line contains a single integer \(n\) representing the number of events.

Each of the following \(n\) lines contains an event description with four space-separated values:

• Name: A string without spaces representing the event name.
• Profit: An integer representing the profit of the event.
• Start: An integer representing the starting day of the event.
• End: An integer representing the ending day of the event.

It is guaranteed that for each event, Start < End.

outputFormat

Print the selected events' names in order, separated by a single space, which yield the maximum total profit under the condition that no events overlap.

## sample

3
EventA 10 1 2
EventB 20 3 4
EventC 15 5 6

EventA EventB EventC