{"problem":{"name":"B. Battleship","description":{"content":"Arkady is playing Battleship. The rules of this game aren't really important. There is a field of $n \\times n$ cells. There should be exactly one $k$\\-decker on the field, i. e. a ship that is $k$ ce","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF965B"},"statements":[{"statement_type":"Markdown","content":"Arkady is playing Battleship. The rules of this game aren't really important.\n\nThere is a field of $n \\times n$ cells. There should be exactly one $k$\\-decker on the field, i. e. a ship that is $k$ cells long oriented either horizontally or vertically. However, Arkady doesn't know where it is located. For each cell Arkady knows if it is definitely empty or can contain a part of the ship.\n\nConsider all possible locations of the ship. Find such a cell that belongs to the maximum possible number of different locations of the ship.\n\n## Input\n\nThe first line contains two integers $n$ and $k$ ($1 \\le k \\le n \\le 100$) — the size of the field and the size of the ship.\n\nThe next $n$ lines contain the field. Each line contains $n$ characters, each of which is either '_#_' (denotes a definitely empty cell) or '_._' (denotes a cell that can belong to the ship).\n\n## Output\n\nOutput two integers — the row and the column of a cell that belongs to the maximum possible number of different locations of the ship.\n\nIf there are multiple answers, output any of them. In particular, if no ship can be placed on the field, you can output any cell.\n\n[samples]\n\n## Note\n\nThe picture below shows the three possible locations of the ship that contain the cell $(3, 2)$ in the first sample.\n\n<center>![image](https://espresso.codeforces.com/05652ce3070abad78e4e07145851e9af67b548cb.png)</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Arkady 正在玩战舰游戏。这个游戏的规则实际上并不重要。\\n\\n有一个 $n \\\\times n$ 的格子区域。区域内必须恰好放置一艘 $k$ 型战舰，即长度为 $k$ 个格子、水平或垂直方向排列的船。然而，Arkady 不知道它的确切位置。对于每个格子，他知道它是否一定是空的，或者是否可能包含船的一部分。\\n\\n考虑所有可能的船的位置。找出一个格子，该格子属于最多数量的不同船位置。\\n\\n第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq k lt.eq n lt.eq 100$) —— 格子区域的大小和船的大小。\\n\\n接下来的 $n$ 行包含格子区域。每行包含 $n$ 个字符，每个字符要么是 '_#_'（表示一定为空的格子），要么是 '_._'（表示可能属于船的格子）。\\n\\n请输出两个整数 —— 属于最多可能的不同船位置的一个格子的行号和列号。\\n\\n如果有多个答案，输出任意一个即可。特别是，如果无法放置任何船，你可以输出任意一个格子。\\n\\n下图展示了第一个样例中包含格子 $(3, 2)$ 的三种可能的船位置。\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq k lt.eq n lt.eq 100$) —— 格子区域的大小和船的大小。接下来的 $n$ 行包含格子区域。每行包含 $n$ 个字符，每个字符要么是 '_#_'（表示一定为空的格子），要么是 '_._'（表示可能属于船的格子）。\"},{\"iden\":\"output\",\"content\":\"请输出两个整数 —— 属于最多可能的不同船位置的一个格子的行号和列号。如果有多个答案，输出任意一个即可。特别是，如果无法放置任何船，你可以输出任意一个格子。\"},{\"iden\":\"examples\",\"content\":\"输入\\n4 3\\n#..#\\n#.#.\\n....\\n###\\n输出\\n3 2\\n\\n输入\\n10 4\\n#....#\\n##....\\n#...#\\n......\\n#..#\\n..#....#\\n.#.....#\\n#..##.#.\\n.......#\\n#...#...#\\n##....#\\n#...#.#.......\\n#..#....#.#...#\\n\\n输出\\n6 1\\n\\n输入\\n19 6\\n##..............####\\n......#####.....##\\n.....#########.........\\n###########.......#############\\n.....###############...#################\\n..#################..#################..\\n..#################..#################.\\n#####....##....########\\n............#######............########\\n...####...####.#####..####..#####...\\n###........###......###########\\n.............##........#.................#\\n\\n输出\\n1 8\"},{\"iden\":\"note\",\"content\":\"下图展示了第一个样例中包含格子 $(3, 2)$ 的三种可能的船位置。 \"}]\n\n```json\n[{\"iden\":\"statement\",\"content\":\"Arkady 正在玩战舰游戏。这个游戏的规则实际上并不重要。\\n\\n有一个 $n \\\\times n$ 的格子区域。区域内必须恰好放置一艘 $k$ 型战舰，即长度为 $k$ 个格子、水平或垂直方向排列的船。然而，Arkady 不知道它的确切位置。对于每个格子，他知道它是否一定是空的，或者是否可能包含船的一部分。\\n\\n考虑所有可能的船的位置。找出一个格子，该格子属于最多数量的不同船位置。\\n\\n第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq k lt.eq n lt.eq 100$) —— 格子区域的大小和船的大小。\\n\\n接下来的 $n$ 行包含格子区域。每行包含 $n$ 个字符，每个字符要么是 '_#_'（表示一定为空的格子），要么是 '_._'（表示可能属于船的格子）。\\n\\n请输出两个整数 —— 属于最多可能的不同船位置的一个格子的行号和列号。\\n\\n如果有多个答案，输出任意一个即可。特别是，如果无法放置任何船，你可以输出任意一个格子。\\n\\n下图展示了第一个样例中包含格子 $(3, 2)$ 的三种可能的船位置。\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含两个整数 $n$ 和 $k$ ($1 lt.eq k lt.eq n lt.eq 100$) —— 格子区域的大小和船的大小。接下来的 $n$ 行包含格子区域。每行包含 $n$ 个字符，每个字符要么是 '_#_'（表示一定为空的格子），要么是 '_._'（表示可能属于船的格子）。\"},{\"iden\":\"output\",\"content\":\"请输出两个整数 —— 属于最多可能的不同船位置的一个格子的行号和列号。如果有多个答案，输出任意一个即可。特别是，如果无法放置任何船，你可以输出任意一个格子。\"},{\"iden\":\"examples\",\"content\":\"输入\\n4 3\\n#..#\\n#.#.\\n....\\n###\\n输出\\n3 2\\n\\n输入\\n10 4\\n#....#\\n##....\\n#...#\\n......\\n#..#\\n..#....#\\n.#.....#\\n#..##.#.\\n.......#\\n#...#...#\\n##....#\\n#...#.#.......\\n#..#....#.#...#\\n\\n输出\\n6 1\\n\\n输入\\n19 6\\n##..............####\\n......#####.....##\\n.....#########.........\\n###########.......#############\\n.....###############...#################\\n..#################..#################..\\n..#################..#################.\\n#####....##....########\\n............#######............########\\n...####...####.#####..####..#####...\\n###........###......###########\\n.............##........#.................#\\n\\n输出\\n1 8\"},{\"iden\":\"note\",\"content\":\"下图展示了第一个样例中包含格子 $(3, 2)$ 的三种可能的船位置。 \"}]\n```","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 100 $.  \nLet $ F \\in \\{ \\texttt{.}, \\texttt{\\#} \\}^{n \\times n} $ be the grid, where $ F_{i,j} = \\texttt{.} $ means cell $ (i,j) $ may contain part of the ship, and $ F_{i,j} = \\texttt{\\#} $ means it is definitely empty.\n\nA valid ship placement is a contiguous sequence of $ k $ cells, either:  \n- Horizontal: $ \\{ (i, j), (i, j+1), \\dots, (i, j+k-1) \\} $ for some $ i \\in \\{1, \\dots, n\\}, j \\in \\{1, \\dots, n-k+1\\} $,  \n- Vertical: $ \\{ (i, j), (i+1, j), \\dots, (i+k-1, j) \\} $ for some $ i \\in \\{1, \\dots, n-k+1\\}, j \\in \\{1, \\dots, n\\} $,  \nsuch that $ F_{x,y} = \\texttt{.} $ for all cells $ (x,y) $ in the placement.\n\nLet $ \\mathcal{P} $ be the set of all valid ship placements.\n\nFor each cell $ (i,j) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, n\\} $, define:  \n$$\nc(i,j) = \\left| \\left\\{ P \\in \\mathcal{P} \\mid (i,j) \\in P \\right\\} \\right|\n$$\n\n**Constraints**  \n1. $ 1 \\leq k \\leq n \\leq 100 $  \n2. $ F_{i,j} \\in \\{ \\texttt{.}, \\texttt{\\#} \\} $ for all $ i,j $\n\n**Objective**  \nFind any cell $ (i^*, j^*) $ such that:  \n$$\nc(i^*, j^*) = \\max_{1 \\leq i,j \\leq n} c(i,j)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF965B","tags":["implementation"],"sample_group":[["4 3\n#..#\n#.#.\n....\n.###","3 2"],["10 4\n#....##...\n.#...#....\n..#..#..#.\n...#.#....\n.#..##.#..\n.....#...#\n...#.##...\n.#...#.#..\n.....#..#.\n...#.#...#","6 1"],["19 6\n##..............###\n#......#####.....##\n.....#########.....\n....###########....\n...#############...\n..###############..\n.#################.\n.#################.\n.#################.\n.#################.\n#####....##....####\n####............###\n####............###\n#####...####...####\n.#####..####..#####\n...###........###..\n....###########....\n.........##........\n#.................#","1 8"]],"created_at":"2026-03-03 11:00:39"}}