{"raw_statement":[{"iden":"statement","content":"Famous abstract painter Va Sya plans to start new painting. It will be composed as square with grid n × n, where each unit square is painted by some color.\n\nVa Sya already defined the colors for some unit squares. Color of other squares does not matter for him.\n\nFor this work Va Sya is planning use the #cf_span(class=[tex-font-style-underline], body=[continuous technics]): he paints whole row or whole column in some color. Moreover, each row and each column must be painted exactly once, so each unit square will be painted twice and its final color will be the #cf_span(class=[tex-font-style-underline], body=[last]) of two used colors.\n\nHelp Va Sya to find appropriate sequence of paints.\n\nFirst line of the input contains one integer n — length of the painting side in units (1 ≤ n ≤ 3000).\n\nEach of the next n lines contains n characters. If i-th character in j-th line equals to '_?_', it means that color of i-th cell in j-th row of painting does not matter. Otherwise it contains lowercase English letter from '_a_' to '_z_' inclusively, which represents the color of corresponding cell (it is well known that Va Sya uses only 26 colors).\n\nPrint 2n lines, i-th of those lines contains description of i-th paint in the following format:\n\n«_h_ y c» — row y is painted with color c;\n\n«_v_ x c» — column x is painted with color c.\n\nRows are numbered sequentially upside down, columns are numbered sequentially leftside right, so upper left corner is on intersection of row 1 and column 1. Each row and each column must be mentioned in the output exactly once.\n\nYou may assume that there exists at least one solution for the given input. If there are several correct solutions, print any of them.\n\n"},{"iden":"input","content":"First line of the input contains one integer n — length of the painting side in units (1 ≤ n ≤ 3000).Each of the next n lines contains n characters. If i-th character in j-th line equals to '_?_', it means that color of i-th cell in j-th row of painting does not matter. Otherwise it contains lowercase English letter from '_a_' to '_z_' inclusively, which represents the color of corresponding cell (it is well known that Va Sya uses only 26 colors)."},{"iden":"output","content":"Print 2n lines, i-th of those lines contains description of i-th paint in the following format:«_h_ y c» — row y is painted with color c;«_v_ x c» — column x is painted with color c.Rows are numbered sequentially upside down, columns are numbered sequentially leftside right, so upper left corner is on intersection of row 1 and column 1. Each row and each column must be mentioned in the output exactly once.You may assume that there exists at least one solution for the given input. If there are several correct solutions, print any of them."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 3000 $, be the grid size.  \nLet $ C \\in (\\mathbb{Z}_{\\leq n} \\times \\mathbb{Z}_{\\leq n}) \\to (\\{\\texttt{a}, \\dots, \\texttt{z}\\} \\cup \\{?\\}) $ be the fixed color constraint matrix, where $ C[i,j] = ? $ means no constraint on cell $ (i,j) $, otherwise $ C[i,j] $ is a color.  \n\nEach cell $ (i,j) $ is painted twice: once by row $ i $, once by column $ j $. The final color is the *last* applied color.  \n\n**Constraints**  \n1. Each row $ i \\in \\{1, \\dots, n\\} $ is painted exactly once.  \n2. Each column $ j \\in \\{1, \\dots, n\\} $ is painted exactly once.  \n3. The sequence of $ 2n $ operations (row/column paints) determines the final color of each cell as the color of the later operation in the sequence.  \n4. For each $ (i,j) $, if $ C[i,j] \\neq ? $, then the final color of cell $ (i,j) $ must equal $ C[i,j] $.  \n\n**Objective**  \nFind a sequence of $ 2n $ operations:  \n- $ n $ row-paints: $ \\texttt{h } y \\texttt{ } c $, where $ y \\in \\{1, \\dots, n\\} $, $ c \\in \\{\\texttt{a}, \\dots, \\texttt{z}\\} $  \n- $ n $ column-paints: $ \\texttt{v } x \\texttt{ } c $, where $ x \\in \\{1, \\dots, n\\} $, $ c \\in \\{\\texttt{a}, \\dots, \\texttt{z}\\} $  \n\nsuch that every row and column appears exactly once, and for every cell $ (i,j) $, the final color (from the later of the row $ i $ and column $ j $ paint) equals $ C[i,j] $.","simple_statement":"You are given an n×n grid. Some cells have fixed colors (a–z), others are '?' (don't care).  \nYou must paint all rows and all columns exactly once, in some order.  \nEach cell’s final color is the color of the *last* paint applied to it (either its row or its column).  \nOutput any sequence of 2n operations: n row-paints and n column-paints, each with a color, such that all fixed cells end up with their required color.","has_page_source":false}