만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

화성: 평행 5도 찾기

면접 대비

시간 제한3초메모리 제한1024 MB

요약
N개의 동시 두 성부 음정이 주어질 때, i번째와 i+1번째 모두 완전5도(12로 나눈 나머지가 7)이고 두 성부가 모두 움직인 위치 i를 모두 출력한다.
난이도

쉬움10점 중 3점

유형
구현, 배열, 수학, 시뮬레이션
정답자
아직 제출이 없습니다

문제

고전 화성학에서는 다성부 성부를 작성할 때 이른바 평행 5도를 피해야 합니다. 평행 5도란 다음 조건이 모두 성립하는 상황을 말합니다.

  • 어떤 시점에서 두 성부 사이의 음정(반음 단위의 거리)을 1212로 나눈 나머지가 77이다.
  • 바로 다음 시점에서 두 성부 모두 음높이가 변한다.
  • 그 다음 시점에서도 두 성부 사이의 음정을 1212로 나눈 나머지가 다시 77이다.

평행 5도는 두 성부 모두 음높이가 변할 때에만 발생합니다. 즉, 연속한 두 순간에서 두 성부의 음정을 1212로 나눈 나머지가 모두 77이더라도, 두 성부 중 하나 이상이 음높이를 바꾸지 않았다면 평행 5도가 아닙니다.

두 성부로 이루어진 악보에서 평행 5도의 존재 여부를 판별하는 프로그램을 작성하세요.

음높이는 정수로 표현합니다. 숫자 00은 1옥타브의 도(C) 음을 나타내며, 양의 정수 kk는 그보다 kk반음 높은 음을, 음의 정수는 그만큼 낮은 음을 나타냅니다. 예를 들어 숫자 44는 1옥타브의 미(E) 음에, −3-3은 작은 옥타브의 라(A) 음에 해당합니다.

참고(음악 이론에 관심 있는 독자용): 때로는 평행 5도를 연속한 두 개의 완전 5도뿐 아니라, 예를 들어 완전 5도와 감(減) 5도(각각 7반음과 6반음)가 이어지는 경우까지 포함하기도 합니다. 이 문제에서는 오직 연속한 두 개의 완전 5도만을 평행 5도로 간주합니다.

문제를 푸는 데 음 이름을 이해할 필요는 없습니다.

입력

첫 번째 줄에 정수 NN (0≤N≤1 000 0000 \le N \le 1\,000\,000)이 주어집니다. 이는 각 성부에 있는 음의 개수입니다.

이어지는 NN개의 줄에는 각각 공백으로 구분된 두 정수 AiA_i와 BiB_i가 주어집니다. 이는 각각 첫 번째 성부와 두 번째 성부에서 울리는 음의 음높이이며, −100≤Bi≤Ai≤100-100 \le B_i \le A_i \le 100 (i∈1…Ni \in 1 \ldots N)을 만족합니다. 같은 줄에 주어진 두 음은 동시에 울리고, 연속한 줄의 음들은 바로 이어서 울립니다.

출력

악보에 평행 5도가 존재하지 않으면 한 줄에 단어 POLE을 출력합니다.

악보에 서로 다른 MM개의 음 쌍 사이에서 평행 5도가 존재한다면, MM개의 줄에 각각 정수 ii를 출력합니다. 여기서 ii는 한 평행 5도를 이루는 첫 번째 음의 순서 번호입니다 (1≤i<N1 \le i < N). 순서 번호는 오름차순으로 출력합니다.

예제3

  1. 예제 1

    입력
    5
    7 0
    10 -2
    14 -5
    12 -7
    7 0
    
    예상 출력
    3
    4
    
  2. 예제 2

    입력
    0
    
    예상 출력
    POLE
    
  3. 예제 3

    입력
    2
    7 0
    7 0
    
    예상 출력
    POLE