점

좌표 평면에 자연수 좌표를 갖는 점 하나로 구성된 집합 \(S\)가 주어진다. \(S\)에 속하는 점으로부터 아래의 세 가지 생성규칙 중 하나를 적용하여 새로운 점을 만들고, 그 점을 집합 \(S\)에 추가한다. 이 과정을 반복적으로 수행하면, 매번 새로운 점을 집합 \(S\)에 계속 추가할 수 있다.

• 규칙 1: 점 (\(x\), \(y\))가 \(S\)에 속해 있다면, 점 (x+1, y+1)을 \(S\)에 추가한다.

• 규칙 2: 점 (\(x\), \(y\))가 \(S\)에 속해 있고, \(x\)와 \(y\)가 모두 짝수이면, 점 (x/2, y/2)를 \(S\)에 추가한다.

• 규칙 3: 두 점 (\(x\), \(y\))와 (\(y\), \(z\))가 \(S\)에 속해 있다면, 점 (\(x\), \(z\))를 \(S\)에 추가한다.

예를 들어, \(S = {(3,\) 5)}일 때, 규칙 1을 점 (3, 5)에 적용하여 만들어진 점 (4, 6)을 \(S\)에 추가하면, \(S = {(3,\) 5), (4, 6)}이 된다. 다시 점 (4, 6)에 규칙 1을 적용하면, \(S = {(3,\) 5), (4, 6), (5, 7)}이 된다. 다음에 점 (4, 6)에 규칙 2를 적용하면 \(S = {(3,\) 5), (4, 6), (5, 7), (2, 3)}이 된다. 또 두 점 (3, 5)와 (5, 7)에 규칙 3을 적용하면, \(S = {(3,\) 5), (4, 6), (5, 7), (2, 3), (3, 7)}이 된다.

문제는 집합 \(S\)를 구성하는 점 (\(a\), \(b\))가 주어질 때, 이 집합에 위의 세 가지 규칙을 임의의 순서로 반복 적용하여 새로운 점 (\(p\), \(q\))가 \(S\)에 추가될 수 있는지를 판명하는 것이다.

첫째 줄에는 처음에 \(S\)에 속하는 점 (\(a\), \(b\))의 좌표인 두 자연수 \(a\)와 \(b\)가 하나의 공백을 두고 순서대로 주어진다. 그리고 그 다음 다섯 줄에는 각 줄마다 한 개의 점 (\(p\), \(q\))의 두 자연수 \(p\)와 \(q\)가 하나의 공백을 두고 순서대로 주어진다. 입력되는 모든 점의 좌표는 1 이상 100,000 이하의 자연수이다.

첫째 줄에는 입력 파일에 제시된 다섯 개의 점에 대하여, 각 점이 세 개의 규칙을 반복 적용하여 만들어질 수 있는지의 여부를 출력한다. 가능하면 \(Y\)를, 불가능하면 \(N\)을 한 줄에 하나씩 순서대로 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2007 > 2차 대회 > 중등부 2번 / 고등부 1번