Design a no-repeat top-frequency music player

Design and implement a music player that receives song lists from new users and returns songs to play in frequency order without repeating a song in the same cycle.

The system supports two APIs:

• addUserSongs(userId, songs): a new user arrives with a list of song IDs. Each appearance of a song increases that song's global frequency by 1.
• getNextSong(): returns the next song ID to play.

Playback rules:

1. Among songs that have not yet been played in the current cycle, choose the song with the highest global frequency.
2. A song cannot be replayed within the same cycle.
3. Once every known song has been played once in the current cycle, the next selection starts a new cycle and all known songs are eligible again.
4. New songs can arrive at any time and should be eligible in the active cycle unless that song has already been played in that cycle.

Constraints & Assumptions

• Song IDs may be strings or integers.
• The same song may appear multiple times in one user's list, and each appearance counts.
• If multiple songs tie on frequency, any deterministic or arbitrary tie-break is acceptable if you state it.
• Assume up to 100000 total song additions and 100000 getNextSong() calls.
• Returning None or raising an empty-state exception is acceptable when no songs are known; state your choice.

Clarifying Questions to Ask

• Should ties be deterministic, such as lexicographic order, or is arbitrary order acceptable?
• Do song frequencies ever decay or get deleted, or only increase?
• Should a user's songs be deduplicated per user or counted by every appearance?
• Is the system single-threaded for the interview implementation, or do we need concurrency controls?