증상 분석

의사가 환자를 진단한다. 규칙은 "두 증상이 동시에 관찰되면 환자는 위독하다"이다. 각 증상은 양수(증상 있음) 또는 음수(증상 없음)로 표현되며, 절댓값은 1 이상 M 이하이다.

환자가 생존할 수 있는지(모든 규칙을 위반하지 않는 상태가 존재하는지) 판별하는 프로그램을 작성하시오.

입력

여러 테스트 케이스로 구성된다. 각 케이스의 첫째 줄에 N과 M이 주어진다. (N ≤ 200,000, M ≤ 20,000) 다음 N개의 줄에 각 규칙을 구성하는 두 정수가 주어진다. 입력의 끝은 0 0이다.

출력

각 테스트 케이스마다 생존 가능하면 1, 불가능하면 0을 출력한다.

입출력 예시

입력 1

3 3
1 -2
2 3
-3 -1
4 2
1 2
1 -2
-1 2
-1 -2
0 0

출력 1

1
0