Description
Gomoku, also known as 五子棋, is a kind of board game with the following rules.
Players alternate turns to place a stone of their color on an empty intersection. Black plays first. The winner is the first player to form an unbroken chain of five stones horizontally, vertically, or diagonally. And the game will stop immediately if someone wins the game.
Today LSC and TSC, are playing Gomoku on a \(15x15\) board. Where LSC plays the black side, TSC plays the white side.
It is known that in LSC's \(i\)th turn, he'll place his black stones to the position \((x_{2i-1}, y_{2i-1})\). And in TSC's \(i\)th turn, he'll place his white stones to the position \((x_{2i}, y_{2i})\).
Now given the length of the array \(x\) and \(y\), please determine who wins the game and at what turn he satisfied the winning condition. Or suppose that no one wins, please print "There's no winner." in one line.
Note that all index used in this problem are 1-based.
Solution(click here to view the solution if you don't want to solve it yourself)
Input
The first line of the input contains \(1\) integer \(N\), the length of array \(x\) and \(y\).
The following \(N\) lines, each contains two intergers \(x_i, \space y_i\).
- \(1 \le N \le 15*15\)
- \(1 \le x_i, y_i \le 15\)
- \((x_i, y_i) \neq (x_j, y_j) \forall i \neq j\)
Constraints
Output
Print your answer in one line.
Suppose LSC wins at the \(i\)th step, you should print("LSC wins at the %dth step", i), it is similar if TSC wins.
Print "There's no winner." if there's no winner.