Description
Fortune magazine has an App that help determine the richest people in the world at any given time T. At the beginning of the year, the N richest people have their net worth estimated in KGold. Depending on their personal investment portfolio, their wealth increases at a constant rate in KGold/sec. Therefore, at time T, the wealth ranking may have changed.
Lately, it was found that there are some bugs in the App. For large time T, the ranking could be wrong. You are hired to enhance the App by adding a debug mode function. When in debug mode, the App is to output how the wealth ranking changes from time to time. First, whenever a person catches up (means equal) with and consequently overtakes another person in terms of overall wealth (KGold), a smiley face icon is flashed on the display screen. So, please count and display the number of times the smiley face is flashed by timeT. Furthermore, information on who overtook whom should also be displayed, in order of the time of the overtake.
Technical Specification
- 1
N250, 000. - Initial wealth of each person is between 0 and 1,000,000 KGold, inclusive.
- The speed in which each person's wealth is incrased is between 0 and 100 KGold per second, inclusive.
- 1, 000, 000T2, 000, 000.
Input
The first line of the input specifies the number of test cases to follow. For each test case, the first line has two integers: N, the number of richest people at the beginning of the year; T, the time in the future in which the wealth of the N people is peeked. The next N lines each contains two integers Gi and Si where Gi is the wealth of person i at the beginning of the year and Si is the speed in which person i's wealth increases in KGold per second. Those N lines are ordered in increasing order of Gi. In other words, no two people's beginning wealth will be the same and G1 < G2 < ... < GN.
Output
For each test case, first output a single integer F on a line indicating the number of times the Smiley face is flashed on the display screen modulo 1,000. Next, display F (or first 10,000 if F > 10, 000) lines of output. Each line contains two integers i and j, indicating that person i overtook person j in terms of overall wealth at some point on or before time T. The list must be in chronological order. In other words, the passing that took place first must be displayed before the passing that took place later in time. Furthermore, if two or more passings took place at the exact same time, the one with less wealth (among the two people passing the other two perople) should be displayed first. For all test cases, no more than two people will have the same exact wealth (in KGold) at any given time.