A music streaming platform wants to rank songs based on user preferences.

There are n users and m songs.

Each user provides a preference list pref[i], which is a permutation of song IDs from 0 to m - 1.

If a < b, then user i prefers song pref[i][a] over song pref[i][b].

A song ranking is determined using the following rules:

1. Song x beats song y if:

   • More than half of the users prefer x over y, or
   • Exactly half of the users prefer x over y, and x < y.

2. Song x is more popular than song y if x beats more songs than y.

3. If two songs beat the same number of songs, the song with the smaller ID ranks higher.

Return the song IDs sorted from most popular to least popular.

---

Function Description

Complete the function:

vector<int> getPopularityOrder(vector<vector<int>> song_preferences)

Parameters

• song_preferences[i]: the preference list of the i-th user.

Returns

• vector<int>: the song IDs sorted in decreasing order of popularity.

---

Example

n = 3
m = 3

song_preferences = [
    [0, 1, 2],
    [0, 2, 1],
    [1, 2, 0]
]

User Preferences

User	Preference
0	0 > 1 > 2
1	0 > 2 > 1
2	1 > 2 > 0

Pairwise Results

• Song 0 beats Song 1.
• Song 0 beats Song 2.
• Song 1 beats Song 2.

Number of songs beaten:

Song	Beats
0	2
1	1
2	0

Output

[0, 1, 2]

---