Hexagonal Grid Game Winner

You are given a hexagonal grid game board represented as an n x n matrix. Two players take turns marking cells in the grid. The first player (represented by 1) and the second (represented by 2) add their marks to the grid. The goal is to determine which player, if any, achieves k consecutive marks in one of the six possible directions on a hexagonal grid. The six directions are defined as follows:

• Right: \((0, 1)\)
• Down-right: \((1, 0)\)
• Down-left: \((1, -1)\)
• Left: \((0, -1)\)
• Up-left: \((-1, -1)\)
• Up-right: \((-1, 0)\)

The game input consists of the size of the grid n, the winning sequence length k, and a list of moves. Each move specifies which cell was marked by which player. Your task is to determine the winner by checking if any player has exactly k consecutive marks in any of these directions. If a player satisfies the condition, output that player's number (1 or 2). If neither player meets the condition, output 0.

Note: The grid indices start from 0 and moves are applied in the given sequence.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n k
 m
 side1 row1 col1
 side2 row2 col2
 ...
 sidem rowm colm

Where:

• n is the size of the grid.
• k is the number of consecutive marks needed to win.
• m is the total number of moves.
• Each move consists of three integers: the player (1 or 2) and the row and column indices of the move.

outputFormat

Output a single integer to standard output (stdout):

• 1 if Player 1 has a winning sequence of k consecutive marks.
• 2 if Player 2 has a winning sequence of k consecutive marks.
• 0 if neither player has such a sequence.

## sample

3 3
9
1 0 0
2 0 1
1 0 2
2 1 0
1 1 2
2 1 1
1 2 0
2 2 2
1 2 1

0