장바구니 동기화 구간

문제

온라인 쇼핑몰의 장바구니 단말은 서버와 통신하면서 동기화 패킷을 순서대로 기록한다. 단말의 임베디드·네트워크 담당자는 이 기록에서 단말 상태를 바꾸지 않는 가장 긴 연속 구간을 찾으려 한다. 단말 상태는 0번부터 14번까지 총 15개의 상태 비트로 구성되며, 각 비트의 값은 0 또는 1이다. 패킷 하나는 정확히 네 자리인 16진수 문자열로 주어진다. 왼쪽 자리가 가장 높은 자릿수이며, 문자열을 정수로 해석했을 때 가장 낮은 비트를 0번 비트라고 한다. 15번 비트는 폐기 표시이고, 0번부터 14번까지의 비트는 변경 마스크다. 폐기 표시가 1인 패킷은 변경 마스크의 값과 관계없이 단말 상태를 전혀 바꾸지 않는다. 폐기 표시가 0인 패킷은 변경 마스크에서 값이 1인 위치의 상태 비트를 각각 뒤집는다. 뒤집기는 0을 1로, 1을 0으로 바꾸는 연산이다. 변경 마스크가 0이면 아무 비트도 바뀌지 않는다. 기록의 패킷에는 입력 순서대로 1번부터 N번까지 번호를 붙인다. 연속 구간 [L, R]은 L번부터 R번까지의 모든 패킷을 순서대로 처리하는 구간이다. 구간을 처리하기 직전과 직후의 단말 상태가 같으면 그 구간을 복원 구간이라고 한다. 구간 내부에서 상태가 잠시 달라지는 것은 허용한다. 폐기된 패킷도 기록의 한 항목이므로 구간의 길이에 포함한다. 구간의 길이는 R-L+1이다. 상태 비트를 뒤집는 규칙만 사용하므로 복원 구간인지 여부는 처리 직전의 실제 상태에 영향을 받지 않는다. 따라서 초기 상태는 입력으로 주어지지 않는다. 길이가 1 이상인 복원 구간 중 가장 긴 구간을 구한다. 길이가 같은 구간이 여러 개이면 시작 번호 L이 가장 작은 구간을 선택한다. 복원 구간이 하나도 없으면 지정된 형식으로 없음을 출력한다.

입력

첫째 줄에 패킷 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 75,000이다.
다음 N개 줄에 패킷 문자열이 하나씩 주어진다. 각 문자열은 정확히 네 글자이며, 각 글자는 0부터 9 또는 대문자 A부터 F 중 하나다. 모든 패킷 값은 0000부터 FFFF까지 허용되며, 앞자리의 0도 생략하지 않는다.

출력

선택한 복원 구간의 길이, 시작 번호 L, 끝 번호 R을 공백으로 구분하여 한 줄에 출력한다. 길이가 1 이상인 복원 구간이 없으면 0 0 0을 출력한다.

7
0001
0002
800F
0003
0004
0004
0008

6 1 6

3
0001
0002
0004

0 0 0

5
0001
0001
0002
0001
0001

2 1 2

출처: Devin.KR 자체 제작