Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
The game of hex is played on a rhombic field of size n × n divided to hexagonal cells. An example of the field for n = 6 is shown on the picture below.
Two players, one playing for noughts and one for crosses, make moves in turn. A move consists of putting a player’s piece to one of the free cells. Two cells are considered adjacent if they have a common side. The goal of noughts is to make a chain of adjacent cells from the left edge of the field to the right edge of the field, the goal of crosses is to make such chain from the top edge to the bottom edge. A picture below shows the game won by noughts.
The gameplay of hex strongly depends on so called templates. In this problem we will consider two simple templates. The two-bridge template is the situation when two player’s pieces can be connected in two ways in one move. Such pieces can be considered connected. A picture below shows the two-bridge for crosses. Note that the cells marked by dots must not be occupied. If noughts play to one of these cells, crosses reply to another cell connecting their pieces. The two cells marked by dots are called bridge cells.
Another simple template is a similar construction at the edge of the board, called template II. A piece in the second row at the player’s edge, with no pieces in the two cells at the edge adjacent to it, can always be connected to the edge. A picture below shows template II for noughts.
Given the position of the field, find out whether the game is won up to simple templates by one of the players.
The first line of the input file contains two integer numbers: n and m — the size of the field and the number of pieces on the field (3 ≤ n ≤ 10 000, 1 ≤ m ≤ 30 000). The following m lines describe pieces. Each piece is described by three integer numbers: x, y and s — the coordinates of the piece and the player who owns the piece. Coordinates range from 1 to n, s is 0 for noughts and 1 for crosses. The position need not be a valid game position, so the number of pieces of different players can be different. No two pieces occupy the same cell. The coordinate system is shown on the picture below, each cell is marked as x, y.
Output “noughts” if the game is won by noughts up to simple templates, “crosses” if the game is won by crosses up to simple templates and “none” if the game is not won up to simple templates yet.
2 4 0
4 3 0
5 4 0
3 5 1
4 2 1
5 1 1
2 4 0
3 2 0
4 3 0
6 2 0
3 4 1
4 5 1
4 6 1
5 1 1
Andrew Stankevich Contest 23