P1338 Legend of Doomsday

Anyone who has participated in JSOI events must have heard the legend of the Tower of Hanoi: the disks on three pegs are moved once per day, and when all disks have been moved, the end of the world will come. In a fantasy land of the ancient East, people record dates in a peculiar way: they use special symbols to denote consecutive integers starting from 1, where 1 is the smallest and n is the largest. On the first day of creation, the calendar was given life; it started counting automatically, as permutations keep increasing. We denote the calendar’s elements by 1..n. On day one, the calendar is: $$1,2,\ldots,n-2,n-1,n$$ On the second day, it becomes: $$1,2,\ldots,n-2,n,n-1$$ ... Each time, it produces a “smallest” permutation not seen before—after converting it to base $n+1$, its numeric value is minimal. Days pass one by one. One day, a prophet appeared—he foretold that when this calendar reaches a moment arranged by God, the world would collapse... He also prophesied that if the inversion count of some date reaches a value $m$, doomsday will come. What is an inversion? For two different symbols in the calendar, if the one that appears earlier is greater than the one that appears later, that forms an inversion. When the total number of inversions of a date reaches $m$, doomsday comes. People are waiting for a sage who can foresee exactly when that day will arrive. Your task is to determine that date.

A single line containing two positive integers $n$ and $m$.

Output one line: the date of doomsday, with numbers separated by a single space.

For 10% of the testdata, $n \le 10$. For 40% of the testdata, $n \le 1000$. For 100% of the testdata, $n \le 5 \times 10^4$. All testdata have a solution. Translated by ChatGPT 5