21341번 - Endgame 스페셜 저지다국어

The boardgame Chaos is an exotic variant of Chess, played by two players in alternating turns on an $n\times n$ playing board. All pieces have the same set of $n$ valid moves which are agreed on ahead of the game.

In a single turn a player can pick exactly one of their pieces and perform one of the following actions:

• Perform up to two valid moves using the chosen piece, capturing any piece that the chosen piece lands on along the way.
• Teleport the chosen piece to any cell on the board that is not already occupied by another piece.
• Leave the chosen piece untouched in its current cell.

Having recently discovered Chaos, Alice and Bob are currently in the endgame of a very exciting match. Each player has a single piece left on the board and there are only two turns left, with Alice going next.

Having analysed the situation, she realises that the only way she can win is to capture Bob's piece in her turn. If that is not possible, Alice may be able to force a tie if she can teleport her piece to a cell that Bob cannot capture in his turn. Otherwise Bob will be able to win by capturing Alice's piece, no matter what she does in her turn. Help Alice determine her optimal outcome.

The input consists of:

• One line with an integer $n$ ($2 \leq n \leq 10^5$), the size of the playing board and the number of valid moves.
• One line with two integers $a_x$ and $a_y$ ($1 \leq a_x, a_y \leq n$), the column and row in which Alice's piece is currently located.
• One line with two integers $b_x$ and $b_y$ ($1 \leq b_x, b_y \leq n$), the column and row in which Bob's piece is currently located.
• $n$ lines, the $i$th of which contains two integers $x_i$ and $y_i$ ($-n < x_i, y_i < n$) representing one of the valid moves. This moves the given piece $x_i$ columns to the right and $y_i$ rows up, provided this does not take the piece outside of the board.

Columns are numbered $1$ to $n$ from left to right and rows are numbered $1$ to $n$ from bottom to top. All valid moves are distinct.

If Alice can capture Bob's piece in her turn, output "Alice wins".

If Alice can use her turn to force a tie by teleporting her piece to a cell that Bob cannot capture in his turn output "tie" followed by two integers $a'_x$ and $a'_y$, the location of any such cell. If there are multiple valid solutions, you may output any one of them.

Otherwise, if Bob is able to capture Alice's piece no matter what she does in her turn, output "Bob wins".