Statement
정수 이하의 서로 다른 두 양의 정수 가 정해져 있다. 항상 이다.
다다스는 의 값만 알고 있다. 모그는 의 값만 알고 있다. 두 사람은 와 문제의 모든 규칙을 알고 있다.
두 사람은 첫째 날부터 매일 다음 선언 중 하나를 동시에 한다.
- 두 정수 를 유일하게 결정할 수 있다면 알겠다고 선언한다.
- 그렇지 않다면 모르겠다고 선언한다.
각 사람은 선언하기 전에 이전 날까지 두 사람이 한 모든 선언을 알고 있다. 같은 날 상대방이 하는 선언은 자신의 선언을 결정할 때 사용할 수 없다. 모든 선언은 참이다.
처음으로 한 명 이상이 알겠다고 선언하는 날을 구하여라. 그런 날이 영원히 오지 않는다면 -1을 출력하라.
Input
입력은 다음과 같은 형식으로 주어진다.
각 케이스는 다음과 같은 형식으로 주어진다.
Output
각 테스트 케이스마다, 처음으로 한 명 이상이 알겠다고 선언하는 날을 출력한다.
그런 날이 영원히 오지 않는다면 -1을 출력한다.
Constraints
- .
- .
Subtasks
Samples
入力例
9
10 1 2
10 2 5
16 7 16
16 13 15
17 14 16
17 13 17
17 12 16
8 3 7
9 2 8
出力例
1
-1
1
2
2
3
4
4
-1