엔드게임

Chaos는 체스의 변형 게임이다. 두 플레이어가 $n\times n$ 크기의 판에서 번갈아 한 수씩 둔다. 모든 말은 같은 $n$개의 유효한 이동 규칙을 공유하며, 이 규칙은 게임 시작 전에 정해진다.

한 턴에 플레이어는 말 하나를 골라 다음 중 하나를 할 수 있다.

• 그 말로 유효한 이동을 최대 두 번 한다. 이동 도중 도착한 칸에 있던 말은 잡힌다.
• 그 말을 다른 말이 없는 판 위의 아무 칸으로 순간이동시킨다.
• 그 말을 현재 칸에 그대로 둔다.

앨리스와 밥은 경기 끝부분에 있다. 각자 말이 하나씩 남았고, 남은 턴은 두 번뿐이다. 앨리스가 먼저 둔다.

앨리스는 자신의 턴에 밥의 말을 잡아야만 이길 수 있다. 잡을 수 없다면, 밥이 자신의 턴에 잡을 수 없는 칸으로 말을 순간이동시켜 비길 수 있다. 둘 다 불가능하면 앨리스가 무엇을 하든 밥이 그녀의 말을 잡아 밥이 이긴다. 앨리스에게 가장 좋은 결과를 구하라.

첫 줄에 판의 크기이자 유효한 이동의 개수인 정수 $n$ ($2 \leq n \leq 10^5$)이 주어진다.

둘째 줄에 앨리스 말의 열 $a_x$와 행 $a_y$ ($1 \leq a_x, a_y \leq n$)가 주어진다.

셋째 줄에 밥 말의 열 $b_x$와 행 $b_y$ ($1 \leq b_x, b_y \leq n$)가 주어진다.

이어지는 $n$개 줄에는 정수 $x_i$와 $y_i$ ($-n < x_i, y_i < n$)가 주어진다. 이는 말을 오른쪽으로 $x_i$칸, 위로 $y_i$칸 옮기는 이동이며, 판 밖으로 나가지 않을 때만 유효하다. 모든 유효한 이동은 서로 다르다.

열은 왼쪽에서 오른쪽으로 1부터 $n$까지, 행은 아래에서 위로 1부터 $n$까지 번호가 매겨진다.

앨리스가 자신의 턴에 밥의 말을 잡을 수 있으면 Alice wins를 출력한다.

앨리스가 자신의 말을 밥이 자신의 턴에 잡을 수 없는 칸으로 순간이동시켜 비길 수 있으면 tie와 그 칸의 좌표 $a'_x$, $a'_y$를 출력한다. 그런 칸이 여럿이면 어느 것을 출력해도 된다.

그 밖에 앨리스가 무엇을 하든 밥이 그녀의 말을 잡을 수 있으면 Bob wins를 출력한다.