WOSS Triolympiad: J2

Problem: Santa’s Candy Crisis

It’s Christmas Eve at the White Oaks Mall, and there are $N$ kids waiting to take a photo with Santa.

Kid $i$ needs $t_i$ minutes for their photo.
If kid $i$ has to wait $W_i$ minutes before their turn starts, they will drop $W_i \cdot c_i$ candies on the floor.

Santa can reorder the kids in any order he wants before the photo session starts, but once the order is fixed, he must take them in that order with no gaps between photos.

Your task is to determine an order of the kids so that the total number of candies dropped on the floor is minimized.

---

Input

• The first line contains one integer $N$ ($1 \le N \le 2 \times 10^5$), the number of kids.
• Each of the next $N$ lines contains two integers $t_i$ and $c_i$ ($1 \le t_i, c_i \le 10^9$): the time for kid $i$’s photo, and the number of candies they drop per minute of waiting.

---

Output

Output a permutation of the integers $1,2,\dots,N$ on a single line:

• These are the indices of the kids in the order Santa should take photos with them to minimize the total number of candies dropped.
• If multiple orders are optimal, output any one of them.