← 返回 databricks 的题目列表Design Tic-Tac-Toe
类型：online_judge
Design Tic-Tac-Toe
Implement Tic-Tac-Toe for an n × n board. Two players, numbered 1 and 2, take turns placing marks.
Implement the following operation:
move(row, col, player): player player places a mark at (row, col) and the operation returns the current winner.
A player wins if, after this move, they occupy all n cells in any row, any column, the main diagonal, or the anti-diagonal.
Return the winning player's ID if there is a winner; otherwise return 0.
You do not need to validate moves. Every move is guaranteed to target an empty cell, and player is either 1 or 2.
Input Format
First line: two integers n and m, the board size and number of moves.
Next m lines: three integers row col player describing one move.
Print the return value of move after every move.
Output Format
Print m lines. Line i is the winner after move i; print 0 when there is no winner.
Constraints
2 ≤ n ≤ 100,000
1 ≤ m ≤ 200,000
0 ≤ row, col < n
Example
Input:
3 5
0 0 1
0 2 2
2 2 1
1 1 2
2 0 1
Output:
0
0
0
0
1
Example
Input
3 5
0 0 1
0 2 2
2 2 1
1 1 2
2 0 1
Output
0
0
0
0
1