{"raw_statement":[{"iden":"problem statement","content":"We have a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nEach square contains an integer. For each $i = 1, 2, \\ldots, N$, the square $(r_i, c_i)$ contains a positive integer $a_i$. The other square contains a $0$.\nInitially, there is a piece on the square $(R, C)$. Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied.\n\n*   The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved.\n*   The squares to and from which the piece is moved are in the same row or the same column.\n\nFor each $i = 1, 2, \\ldots, N$, print the maximum number of times Takahashi can move the piece when $(R, C) = (r_i, c_i)$."},{"iden":"constraints","content":"*   $2 \\leq H, W \\leq 2 \\times 10^5$\n*   $1 \\leq N \\leq \\min(2 \\times 10^5, HW)$\n*   $1 \\leq r_i \\leq H$\n*   $1 \\leq c_i \\leq W$\n*   $1 \\leq a_i \\leq 10^9$\n*   $i \\neq j \\Rightarrow (r_i, c_i) \\neq (r_j, c_j)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$ $N$\n$r_1$ $c_1$ $a_1$\n$r_2$ $c_2$ $a_2$\n$\\vdots$\n$r_N$ $c_N$ $a_N$"},{"iden":"sample input 1","content":"3 3 7\n1 1 4\n1 2 7\n2 1 3\n2 3 5\n3 1 2\n3 2 5\n3 3 5"},{"iden":"sample output 1","content":"1\n0\n2\n0\n3\n1\n0\n\nThe grid contains the following integers.\n\n4 7 0\n3 0 5\n2 5 5\n\n*   When $(R, C) = (r_1, c_1) = (1, 1)$, you can move the piece once by moving it as $(1, 1) \\rightarrow (1, 2)$.\n*   When $(R, C) = (r_2, c_2) = (1, 2)$, you cannot move the piece at all.\n*   When $(R, C) = (r_3, c_3) = (2, 1)$, you can move the piece twice by moving it as $(2, 1) \\rightarrow (1, 1) \\rightarrow (1, 2)$.\n*   When $(R, C) = (r_4, c_4) = (2, 3)$, you cannot move the piece at all.\n*   When $(R, C) = (r_5, c_5) = (3, 1)$, you can move the piece three times by moving it as $(3, 1) \\rightarrow (2, 1) \\rightarrow (1, 1) \\rightarrow (1, 2)$.\n*   When $(R, C) = (r_6, c_6) = (3, 2)$, you can move the piece once by moving it as $(3, 2) \\rightarrow (1, 2)$.\n*   When $(R, C) = (r_7, c_7) = (3, 3)$, you cannot move the piece at all."},{"iden":"sample input 2","content":"5 7 20\n2 7 8\n2 6 4\n4 1 9\n1 5 4\n2 2 7\n5 5 2\n1 7 2\n4 6 6\n1 4 1\n2 1 10\n5 6 9\n5 3 3\n3 7 9\n3 6 3\n4 3 4\n3 3 10\n4 2 1\n3 5 4\n1 2 6\n4 7 9"},{"iden":"sample output 2","content":"2\n4\n1\n5\n3\n6\n6\n2\n7\n0\n0\n4\n1\n5\n3\n0\n5\n2\n4\n0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}