Design a subscription email scheduler with changes and renewals

Implement an email notification scheduler for subscription accounts. Inputs:

• send_schedule: a mapping whose keys include: • "start": label to send on an account’s begin_date. • Integer negative offsets (e.g., - 15): labels to send at end_date + offset, where end_date = begin_date + duration. • "end": label to send on end_date.
• user_accounts: a list of objects {name: string, plan: string, account_date: int (days), duration: int (days)}. Output:
• Emit all notifications in chronological order as lines: " <time> : [ <Label> ] Subscription for <name> ( <plan> )" and terminate after the last message.
• When multiple notifications share the same timestamp, apply this deterministic ordering:
  1. State changes (defined below) in the order: Changed, then Renewed.
  2. "start" events.
  3. Relative-offset events sorted by their numeric offset (more negative first).
  4. "end" events.
• For ties within the same priority bucket, sort by name lexicographically. Sub-questions: (a) Baseline scheduling: Using only send_schedule and user_accounts, generate all scheduled notifications for each account (welcome on begin_date, each negative-offset notification relative to end_date, and expired on end_date) and merge them into the global, ordered output. (b) Plan changes: Add a list changes1 of entries {name: string, new_plan: string, change_date: int}. At change_date, emit "[Changed] Subscription for <name> (<new_plan>)" and update the account’s plan effective immediately; any notifications at the same timestamp and all future notifications must use the updated plan. (c) Renewals/extensions: Now allow a change list where each entry is either a plan change as above or a renewal entry {name: string, extension: int (days), change_date: int}. On a renewal, emit "[Renewed] Subscription for <name> (<current_plan>)" and extend the account’s end_date by extension days from its current end_date. Recompute all future relative-offset and end events to reflect the new end_date. If a renewal and a plan change occur for the same account on the same timestamp, apply the ordering rules above. Constraints/expectations:
• Support up to N accounts and M change/renewal events efficiently; describe data structures and time complexity.
• Your API design is flexible (e.g., a Notifier class with send_emails(user_accounts, send_schedule, changes=None)).
• Clearly state any additional assumptions you make and ensure deterministic output under all tie cases.