문제
동호는 월드 고등학교의 학생이다. 동호는 학교에서 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개의 줄에 걸쳐 Ti와 Pi가 (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
로그인해야 코드를 작성할 수 있어요.