영희는 $1,2,\cdots,n$의 순열을 무작위로 생성하는 알고리즘을 가지고 있습니다. 이 알고리즘의 의사코드는 아래와 같습니다.

클래스 node는 이진 트리의 노드를 구성합니다.

node는 클래스 변수로 L,R,Lc,Rc,x를 가집니다.

L,R은 왼쪽과 오른쪽 자식 노드를 가리키는 포인터 또는 인덱스입니다.

Lc와 Rc는 왼쪽과 오른쪽에 추가할 수 있는 리프 노드의 수를 나타냅니다.

예를 들어 새로운 노드에 대해 Lc와 Rc는 기본적으로 1입니다.

x는 노드가 저장하는 정수 값입니다.

def makenode(a): return ("'x=a인 새로운 node의 포인터 또는 인덱스"')

def insert(rt,a): while True: range = rt.Lc+rt.Rc v = ("'0 이상 range 미만의 무작위 정수"') if v < rt.Lc: # 라인 A rt.Lc += 1 if rt.Lc == 2: rt.L = makenode(a) return rt = ("'rt.L이 가리키는 node"') else: rt.Rc += 1 if rt.Rc == 2: rt.R = makenode(a) return rt = ("'rt.R이 가리키는 node"')

def inorder(rt): if rt.Lc > 1: inorder("'rt.L이 가리키는 node"') print(rt.x) if rt.Rc > 1: inorder("'rt.R이 가리키는 node"')

...

데이터를 생성하는 방법

root="'makenode(1)의 반환값이 가리키는 node"' for i in range(2,n+1): insert(root,i)

이제 inorder(root)의 출력은 무작위 순열이 됩니다.

알고리즘을 실행하면 $1,2,\cdots,n$의 무작위 순열이 출력되며, $n!$가지 순열 각각이 나올 확률은 같습니다. 또한 이 알고리즘의 평균 시간 복잡도는 $\mathcal{O}(n \log n)$으로, 놀라울 만큼 낮습니다.

영희에게 이 알고리즘을 배운 철수는 직접 구현해 보았습니다. 그런데 기억이 흐릿했던 철수는 주석 처리된 **라인 A**의 코드를 `v < rt.Lc` 대신 `v >= rt.Lc`로 잘못 작성했습니다. 오타를 알아챘을 때는 이미 길이 $n=1\,000$의 순열을 셀 수 없이 많이 생성한 뒤였습니다.

철수의 실수는 생각보다 심각합니다. 영희의 알고리즘은 모든 순열을 같은 확률로 반환하지만, 철수의 알고리즘은 그렇지 않습니다. 이 알고리즘이 어떤 문제의 채점 데이터를 만드는 데 쓰였다는 사실이 드러나면 논란이 생길 것이 분명합니다. 그런데 이미 어떤 문제의 채점 데이터에 잘못 생성된 데이터가 섞여 있습니다. 데이터를 새로 만들 시간이 없으므로, 잘못 생성된 데이터를 걸러내야 합니다.

영희의 알고리즘을 **알고리즘 A**, 철수의 알고리즘을 **알고리즘 B**라고 합시다. 길이 $n=1\,000$의 순열이 $m=1\,000$개 있으며, 각각은 알고리즘 A 또는 알고리즘 B로 생성되었습니다. 어느 알고리즘으로 생성할지는 공정한 동전을 던져서 정했습니다. 즉, 순열이 알고리즘 A로 생성되었을 확률은 $50\%$, 알고리즘 B로 생성되었을 확률은 $50\%$입니다. 각 순열이 어느 알고리즘으로 생성되었는지 알아내야 합니다.

두 알고리즘이 같은 순열을 생성할 수도 있으므로, 모든 입력에 대해 $100\%$ 정답을 맞히는 방법은 없습니다. $1\,000$개의 순열 중 적어도 $900$개에 대해 정답을 맞히면 정답으로 인정합니다.

첫 번째 줄에 순열의 개수 $m$이 주어집니다. ($m=1\,000$)

그다음 줄부터 $2m$개의 줄에 걸쳐 순열의 정보가 주어집니다. 각 순열의 정보는 두 줄로 구성됩니다.

• 첫 번째 줄에 순열의 길이 $n$이 주어집니다. ($n=1\,000$)
• 두 번째 줄에 순열의 원소를 나타내는 $n$개의 정수 $a_1,a_2,\cdots,a_n$이 공백으로 구분되어 주어집니다. ($1 \le a_i \le n$)

모든 입력은 문제에 주어진 과정에 따라 생성되었습니다. 입력 파일은 최대 $150$개입니다.

각 순열에 대해 알고리즘 A로 생성되었으면 "Alice", 알고리즘 B로 생성되었으면 "Bob"을 새로운 줄에 출력합니다.

$1\,000$개의 순열 중 적어도 $900$개에 대해 정답을 맞히면 정답으로 인정합니다.

이 문제는 형식상 인터랙티브 문제입니다.

각 줄을 출력한 후에는 표준 출력 버퍼를 비워야 합니다(flush). 언어별 방법은 다음과 같습니다.

• C: fflush(stdout)
• C++: cout.flush()
• Java: System.out.flush()
• Python: sys.stdout.flush()
• 이외의 언어: 언어별 레퍼런스를 참고합니다.

참가자의 편의를 위해 testlib을 사용하는 C++ 인터랙터의 원본 소스 코드를 제공합니다.

• interactor-baddata.cpp

인터랙터는 처음에 데이터를 생성하기 위한 시드를 입력에서 읽습니다. 그다음 문제에 설명된 대로 데이터를 생성하면서 인터랙션을 진행합니다. 맞힌 테스트 케이스의 수는 변수 cntr에 저장되어 스트림 tout을 통해 체커로 전달됩니다. 이 값이 $900$ 이상이면 체커는 정답으로 판정합니다.