Design a no-repeat top-frequency music player

You are building a music player that receives a stream of new users and their song lists. Each event is: - addUserSongs(userId, songs): a new user arrives with a list of song IDs (strings or ints). Each appearance of a song in the input increases that song’s global frequency by 1. You must support: - getNextSong(): returns the song ID to play next. Playback rules: 1) Always choose, among songs that have **not yet been played in the current cycle**, 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 cycle resets (all songs become eligible again), and selection continues. 4) New songs may arrive at any time; they should be considered immediately as eligible (unless already played in the current cycle). If multiple eligible songs tie on frequency, you may break ties arbitrarily (or specify a deterministic tie-break such as lexicographically smallest ID). Design the data structures and implement these APIs efficiently. Discuss time complexity. You may assume up to 1e5 total song additions and 1e5 getNextSong calls.