Bessie's Optimal Dropped Tests

Bessie has taken \(N\) tests. In test \(i\) she scored \(T_i\) out of \(P_i\) points with \(0 \le T_i \le P_i 0\). Her teacher calculates her final grade by dropping exactly \(D\) tests: the \(D\) tests with the lowest score percentages \(\frac{T_i}{P_i}\). Then, Bessie's final grade is computed as

[ \text{grade} = \frac{\sum_{i \in K} T_i}{\sum_{i \in K} P_i}, ]

where \(K\) is the set of tests that remain.

Surprisingly, Bessie has noticed that because no two tests have the same \(\frac{T_i}{P_i}\), the teacher’s method may not always maximize her final grade. In fact, by choosing to drop a different set of \(D\) tests (instead of the \(D\) with the lowest percentages), she might be able to obtain a higher grade. Your task is to help Bessie determine for which values of \(D\) this is possible.

Note: It might be beneficial sometimes to keep a test with a very low percentage if its total points are so small that it does not drag down the overall average very much. Thus, dropping the \(D\) tests with the lowest percentages is not necessarily optimal.

inputFormat

The first line contains a single integer \(N\) (either \(1 \le N \le 5000\) or for one special case \(1 \le N \le 50000\)). Each of the following \(N\) lines contains two integers \(T_i\) and \(P_i\), representing the points earned and total possible points on test \(i\), respectively.

outputFormat

For each possible drop count \(D\) (with \(0 \le D < N\)) for which there exists an alternative set of \(D\) tests to drop that produces a higher final grade than the teacher’s method, output \(D\). The \(D\) values should be printed in increasing order separated by a space. If no such \(D\) exists, print -1.

sample

4
2 3
80 100
1 1
0 1000

-1