시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 41 11 3 15.000%

문제

동호는 월드 고등학교의 학생이다. 동호는 학교에서 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를 모두 출력한다.

예제 입력

5
1 2
5 9
3 8
4 10
1 3

예제 출력

2
1
2

힌트