날카로운 눈

정수 더미는 여러 개의 등차수열로 표현된다. 한 줄 A C B는 A, A+B, A+2B, ... 중에서 C 이하인 모든 정수가 더미에 들어 있음을 뜻한다.

더미 전체에서 어떤 정수 하나만 홀수 번 나타날 수 있고, 나머지 정수들은 모두 짝수 번 나타난다. 주어진 등차수열들을 모두 합쳤을 때 홀수 번 나타나는 정수를 찾아라.

첫째 줄에 수열의 개수 N이 주어진다. 1 <= N <= 20,000이다.

다음 N개의 줄에는 세 정수 A C B가 주어진다. 각 값은 1 이상 2,147,483,647 이하이다. 한 줄은 A + kB <= C를 만족하는 모든 정수 A + kB (k >= 0)가 더미에 들어 있음을 의미한다.

홀수 번 나타나는 정수가 있으면 그 정수와 등장 횟수를 공백으로 구분해 출력한다.

그런 정수가 없으면 NOTHING을 출력한다.

어떤 값 x 이하에 들어 있는 원소 수의 합을 세면, 홀수 번 나타나는 값 이전까지는 누적 개수가 짝수이고 그 값부터는 홀수가 된다. 따라서 누적 개수의 홀짝성을 이용해 이분 탐색할 수 있다.