시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 82 20 9 18.750%

문제

동호는 월드 고등학교의 학생이다. 동호는 학교에서 N개의 시험을 봤다. 시험 점수는 Ti와 Pi로 주어진다. Ti는 i번째 시험에서 동호가 받은 점수를 의미하고, Pi는 i번째 시험의 토탈 점수를 의미한다.

이제 이 N개의 점수를 가지고 성적을 매겨야 하는데 성적은 Ti들의 합을 Pi들의 합으로 나눈 값을 의미한다. 만약에 동호가 1/2, 5/9, 3/8, 4/10, 1/3 의 점수를 얻었다면 (Ti/Pi의 형식) 동호가 받을 성적은 1+5+3+4+1/2+9+8+10+3 = 14/32 ≒ 0.44가 될 것이다.

그런데 동호의 담임 선생님은 그냥 이렇게 점수를 주면 동호의 성적이 너무 형편없기 때문에 동호가 본 N개의 시험 중, Ti를 Pi로 나눈 값, 즉 백분율이 작은 D개의 시험을 빼서 N-D개의 시험에 대해서만 성적을 합산하려 한다. 예를 들어 위에서 D가 1일 경우에는 1/3이 가장 작기 때문에 동호의 성적은 1/3을 뺀 1/2, 5/9, 3/8, 4/10을 더한 1+5+3+4/ 2+9+8+10 = 13/29 ≒ 0.45가 된다.

그런데 동호는 이러한 선생님의 선택에 반발을 하였다. 어차피 D개의 성적을 뺄 거면 다른 것을 빼지 왜 백분율이 작은 것을 빼냐는 것이다. 만약에 D가 1일 경우 1/3을 빼지 않고 3/8을 빼면 점수가 11/24 ≒ 0.46이 되어 위의 경우보다 점수가 더 높게 된다는 것이다.

동호의 담임선생님은 점수를 올려준다는데도 이에 반발한 동호에게 매우 화가 났다. 그래서 동호의 담임선생님은 즉석에서 다음과 같은 문제를 동호에게 내 주었다. 동호의 시험 점수가 주어져 있을 때, 동호의 이론이 성립하는 D를 모두 구하라는 것이다. 즉, 백분율이 작은 D개를 빼는 것 보다 다른 D개를 빼서 점수를 더 높이는 것이 가능한 D를 모두 구하라는 것이다. 동호는 매우 당황하였다. 점수를 올리려다가 큰 난관에 부딪힌 것이다. 여러분은 동호를 도와서 위의 조건은 만족하는 D를 모두 구하는 프로그램을 작성하여야 한다.

입력

첫째 줄에 동호가 시험을 본 개수 N(1≤N≤5,000, 단 마지막 데이터의 경우에 한해서 N=50,000이다). 그리고 두 번째 줄부터 N+1번째 줄까지 N개의 줄에 걸쳐 Pi와 Ti가 (0 ≤ Ti ≤ Pi ≤ 40,000  0<Pi) 공백을 사이에 두고 주어진다.

출력

첫 줄에 가능한 D의 개수 K(0≤K≤N) 를 출력한다. 그리고 두 번째 줄부터 K+1번째 줄까지 가능한 D를 모두 출력한다.

예제 입력 1

5
1 2
5 9
3 8
4 10
1 3

예제 출력 1

2
1
2
W3sicHJvYmxlbV9pZCI6IjE4NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzFcdWM4MDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYzOFx1YjI5NCBcdWM2ZDRcdWI0ZGMgXHVhY2UwXHViNGYxXHVkNTU5XHVhZDUwXHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc3NFx1YjJlNC4gXHViM2Q5XHVkNjM4XHViMjk0IFx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExYyBOXHVhYzFjXHVjNzU4IFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWJkMjRcdWIyZTQuIFx1YzJkY1x1ZDVkOCBcdWM4MTBcdWMyMThcdWIyOTQgVGlcdWM2NDAgUGlcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBUaVx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzJkY1x1ZDVkOFx1YzVkMFx1YzExYyBcdWIzZDlcdWQ2MzhcdWFjMDAgXHViYzFiXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIFBpXHViMjk0IGlcdWJjODhcdWM5ZjggXHVjMmRjXHVkNWQ4XHVjNzU4IFx1ZDFhMFx1ZDBjOCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+PHA+XHVjNzc0XHVjODFjIFx1Yzc3NCBOXHVhYzFjXHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjMTMxXHVjODAxXHVjNzQ0IFx1YjllNFx1YWNhOFx1YzU3YyBcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMTMxXHVjODAxXHVjNzQwIFRpXHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc0NCBQaVx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YWMxMlx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWIzZDlcdWQ2MzhcdWFjMDAgMVwvMiwgNVwvOSwgM1wvOCwgNFwvMTAsIDFcLzMgXHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWM1YzhcdWIyZTRcdWJhNzQgKFRpXC9QaVx1Yzc1OCBcdWQ2MTVcdWMyZGQpIFx1YjNkOVx1ZDYzOFx1YWMwMCBcdWJjMWJcdWM3NDQgXHVjMTMxXHVjODAxXHVjNzQwIDErNSszKzQrMVwvMis5KzgrMTArMyA9IDE0XC8zMiBcdTIyNTIgMC40NFx1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+PHA+XHVhZGY4XHViN2YwXHViMzcwIFx1YjNkOVx1ZDYzOFx1Yzc1OCBcdWIyZjRcdWM3ODQgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1YWRmOFx1YjBlNSBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjODEwXHVjMjE4XHViOTdjIFx1YzhmY1x1YmE3NCBcdWIzZDlcdWQ2MzhcdWM3NTggXHVjMTMxXHVjODAxXHVjNzc0IFx1YjEwOFx1YmIzNCBcdWQ2MTVcdWQzYjhcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjNkOVx1ZDYzOFx1YWMwMCBcdWJjZjggTlx1YWMxY1x1Yzc1OCBcdWMyZGNcdWQ1ZDggXHVjOTExLCBUaVx1Yjk3YyBQaVx1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyLCBcdWM5ODkgXHViYzMxXHViZDg0XHVjNzI4XHVjNzc0IFx1Yzc5MVx1Yzc0MCBEXHVhYzFjXHVjNzU4IFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWJlN2NcdWMxMWMgTi1EXHVhYzFjXHVjNzU4IFx1YzJkY1x1ZDVkOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWI5Y2MgXHVjMTMxXHVjODAxXHVjNzQ0IFx1ZDU2OVx1YzBiMFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNzA0XHVjNWQwXHVjMTFjIERcdWFjMDAgMVx1Yzc3YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMVwvM1x1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIzZDlcdWQ2MzhcdWM3NTggXHVjMTMxXHVjODAxXHVjNzQwIDFcLzNcdWM3NDQgXHViZTgwIDFcLzIsIDVcLzksIDNcLzgsIDRcLzEwXHVjNzQ0IFx1YjM1NFx1ZDU1YyAxKzUrMys0XC8gMis5KzgrMTAgPSAxM1wvMjkgXHUyMjUyIDAuNDVcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+PHA+XHVhZGY4XHViN2YwXHViMzcwIFx1YjNkOVx1ZDYzOFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzU4IFx1YzEyMFx1ZDBkZFx1YzVkMCBcdWJjMThcdWJjMWNcdWM3NDQgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM1YjRcdWNjMjhcdWQ1M2MgRFx1YWMxY1x1Yzc1OCBcdWMxMzFcdWM4MDFcdWM3NDQgXHViZTg0IFx1YWM3MFx1YmE3NCBcdWIyZTRcdWI5NzggXHVhYzgzXHVjNzQ0IFx1YmU3Y1x1YzljMCBcdWM2NWMgXHViYzMxXHViZDg0XHVjNzI4XHVjNzc0IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NDQgXHViZTdjXHViMGQwXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIERcdWFjMDAgMVx1Yzc3YyBcdWFjYmRcdWM2YjAgMVwvM1x1Yzc0NCBcdWJlN2NcdWM5YzAgXHVjNTRhXHVhY2UwIDNcLzhcdWM3NDQgXHViZTdjXHViYTc0IFx1YzgxMFx1YzIxOFx1YWMwMCAxMVwvMjQgXHUyMjUyIDAuNDZcdWM3NzQgXHViNDE4XHVjNWI0IFx1YzcwNFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWJjZjRcdWIyZTQgXHVjODEwXHVjMjE4XHVhYzAwIFx1YjM1NCBcdWIxOTJcdWFjOGMgXHViNDFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPjxwPlx1YjNkOVx1ZDYzOFx1Yzc1OCBcdWIyZjRcdWM3ODRcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YzYyY1x1YjgyNFx1YzkwMFx1YjJlNFx1YjI5NFx1YjM3MFx1YjNjNCBcdWM3NzRcdWM1ZDAgXHViYzE4XHViYzFjXHVkNTVjIFx1YjNkOVx1ZDYzOFx1YzVkMFx1YWM4YyBcdWI5ZTRcdWM2YjAgXHVkNjU0XHVhYzAwIFx1YjBhY1x1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YjNkOVx1ZDYzOFx1Yzc1OCBcdWIyZjRcdWM3ODRcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVjOTg5XHVjMTFkXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYjM4XHVjODFjXHViOTdjIFx1YjNkOVx1ZDYzOFx1YzVkMFx1YWM4YyBcdWIwYjQgXHVjOGZjXHVjNWM4XHViMmU0LiBcdWIzZDlcdWQ2MzhcdWM3NTggXHVjMmRjXHVkNWQ4IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViM2Q5XHVkNjM4XHVjNzU4IFx1Yzc3NFx1Yjg2MFx1Yzc3NCBcdWMxMzFcdWI5YmRcdWQ1NThcdWIyOTQgRFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVhZDZjXHVkNTU4XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWJjMzFcdWJkODRcdWM3MjhcdWM3NzQgXHVjNzkxXHVjNzQwIERcdWFjMWNcdWI5N2MgXHViZTdjXHViMjk0IFx1YWM4MyBcdWJjZjRcdWIyZTQgXHViMmU0XHViOTc4IERcdWFjMWNcdWI5N2MgXHViZTdjXHVjMTFjIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWIzNTQgXHViMTkyXHVjNzc0XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWMgRFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVhZDZjXHVkNTU4XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViM2Q5XHVkNjM4XHViMjk0IFx1YjllNFx1YzZiMCBcdWIyZjlcdWQ2NjlcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM2MmNcdWI5YWNcdWI4MjRcdWIyZTRcdWFjMDAgXHVkMDcwIFx1YjA5Y1x1YWQwMFx1YzVkMCBcdWJkODBcdWI1MmFcdWQ3OGMgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHViM2Q5XHVkNjM4XHViOTdjIFx1YjNjNFx1YzY0MFx1YzExYyBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQwIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBEXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNkOVx1ZDYzOFx1YWMwMCBcdWMyZGNcdWQ1ZDhcdWM3NDQgXHViY2Y4IFx1YWMxY1x1YzIxOCBOKDEmbGU7TiZsZTs1LDAwMCwgXHViMmU4IFx1YjljOFx1YzljMFx1YjljOSBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1ZDU1Y1x1ZDU3NFx1YzExYyBOPTUwLDAwMFx1Yzc3NFx1YjJlNCkuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBQaVx1YzY0MCBUaVx1YWMwMCAoMCAmbGU7IFRpICZsZTsgUGkgJmxlOyA0MCwwMDAmbmJzcDsgMCZsdDtQaSkgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAiLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBEXHVjNzU4IFx1YWMxY1x1YzIxOCBLKDAmbGU7SyZsZTtOKSBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgSysxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyYTVcdWQ1NWMgRFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4NTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3cgU2Nob29sIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzeSBpcyBnb2luZyB0byBzY2hvb2wgYW5kIGRvaW5nIHdlbGwuIFNoZSBoYXMgdGFrZW4gTiAoMSAmbHQ7PSBOICZsdDs9IDUwMDAgLS0gZXhjZXB0IG9uZSBjYXNlIHdoZXJlIDEgJmx0Oz0gTiAmbHQ7PSA1MCwwMDApIHRlc3RzIGFuZCByZWNvcmRlZCB0aGUgc2NvcmVzIChUX2kgcG9pbnRzIG91dCBvZiBQX2kgcG9pbnRzIGZvciB0ZXN0IGk7IDAgJmx0Oz0gVF9pICZsdDs9IFBfaSAmbHQ7IDQwLDAwMDsgMCAmbHQ7IFBfaSkgYXMgdGhpcyB0YXNrJiMzOTtzIGlucHV0LjxcL3A+XHJcblxyXG48cD5IZXIgdGVhY2hlciB3aWxsIGRyb3AgdGhlIEQgdGVzdHMgd2l0aCB0aGUgbG93ZXN0IHBlcmNlbnRhZ2UgKFRfaVwvUF9pKSBiZWZvcmUgY2FsY3VsYXRpbmcgQmVzc2llJiMzOTtzIGZpbmFsIGdyYWRlICh3aGljaCBpcyB0aGUgc3VtIG9mIHRoZSByZW1haW5pbmcgdGVzdCBzY29yZSBwb2ludHMgb3ZlciB0aGUgc3VtIG9mIHRoZSByZW1haW5pbmcgdG90YWwgdGVzdCBwb2ludHMpLiBCZXNzeSBpcyBnb29kIGF0IG1hdGggYW5kIHF1aWNrbHkgcmVhbGl6ZXMgdGhhdCB0aGlzIGRvZXMgbm90IGJlbmVmaXQgaGVyIGFzIG11Y2ggYXMgaXQgbWlnaHQuPFwvcD5cclxuXHJcbjxwPlRvIHByb3ZlIGhlciBwb2ludCwgQmVzc3kgd2FudHMgdG8gZmluZCBhbGwgdmFsdWVzIG9mIEQgZm9yIHdoaWNoIHNoZSBjb3VsZCBoYXZlIGVuZGVkIHVwIHdpdGggYSBoaWdoZXIgZ3JhZGUgYnkgY2hvb3NpbmcgdG8gZHJvcCBkaWZmZXJlbnQgdGVzdHMgdGhhbiB0aGUgdGVhY2hlciB3b3VsZCBoYXZlLiBIZWxwIGhlciBieSBmaW5kaW5nIGFuZCBwcmludGluZyBhbGwgdmFsdWVzIG9mIEQgZm9yIHdoaWNoIHRoaXMgaXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkJlc3N5IGhhcyBub3RlZCB0aGF0LCBhbWF6aW5nbHksIHNoZSBoYXMgbmV2ZXIgc2NvcmVkIHRoZSBzYW1lIHBlcmNlbnRhZ2Ugb24gdHdvIGRpZmZlcmVudCB0ZXN0cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCBOPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBUX2kgYW5kIFBfaTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIEsgKDAgJmx0Oz0gSyAmbHQ7PSBOKSB0aGF0IGlzIHRoZSBudW1iZXIgb2YgdmFsdWVzIG9mIEQgZm9yIHdoaWNoIEJlc3N5IGNvdWxkIGhhdmUgZW5kZWQgdXAgd2l0aCBhIGhpZ2hlciBncmFkZSBieSBkcm9wcGluZyBhIGRpZmZlcmVudCBzZXQgb2YgRCB0ZXN0cyB0aGFuIHRoZSB0ZWFjaGVyLjxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLksrMTogVGhlIHZhbHVlcyBvZiBEIGZvciB3aGljaCB0aGlzIGlzIHRydWUsIGluIGFzY2VuZGluZyBudW1lcmljYWwgb3JkZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d