English · Original
Chinese · Translation
Formal · Original
Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules.
The game is played on the following field.
<center></center>Players are making moves by turns. At first move a player can put his chip in any cell of any small field. For following moves, there are some restrictions: if during last move the opposite player put his chip to cell with coordinates (_x__l_, _y__l_) in some small field, the next move should be done in one of the cells of the small field with coordinates (_x__l_, _y__l_). For example, if in the first move a player puts his chip to lower left cell of central field, then the second player on his next move should put his chip into some cell of lower left field (pay attention to the first test case). If there are no free cells in the required field, the player can put his chip to any empty cell on any field.
You are given current state of the game and coordinates of cell in which the last move was done. You should find all cells in which the current player can put his chip.
A hare works as a postman in the forest, he likes to foul bears. Sometimes he changes the game field a bit, so the current state of the game could be unreachable. However, after his changes the cell where the last move was done is not empty. You don't need to find if the state is unreachable or not, just output possible next moves according to the rules.
## Input
First 11 lines contains descriptions of table with 9 rows and 9 columns which are divided into 9 small fields by spaces and empty lines. Each small field is described by 9 characters without spaces and empty lines. character "_x_" (ASCII-code 120) means that the cell is occupied with chip of the first player, character "_o_" (ASCII-code 111) denotes a field occupied with chip of the second player, character "." (ASCII-code 46) describes empty cell.
The line after the table contains two integers _x_ and _y_ (1 ≤ _x_, _y_ ≤ 9). They describe coordinates of the cell in table where the last move was done. Rows in the table are numbered from up to down and columns are numbered from left to right.
It's guaranteed that cell where the last move was done is filled with "_x_" or "_o_". Also, it's guaranteed that there is at least one empty cell. It's not guaranteed that current state of game is reachable.
## Output
Output the field in same format with characters "_!_" (ASCII-code 33) on positions where the current player can put his chip. All other cells should not be modified.
[samples]
## Note
In the first test case the first player made a move to lower left cell of central field, so the second player can put a chip only to cells of lower left field.
In the second test case the last move was done to upper left cell of lower central field, however all cells in upper left field are occupied, so the second player can put his chip to any empty cell.
In the third test case the last move was done to central cell of central field, so current player can put his chip to any cell of central field, which is already occupied, so he can move anywhere. Pay attention that this state of the game is unreachable.
两只熊通过邮件玩井字棋。玩普通的井字棋对他们来说太无聊了，因此他们玩的是一个修改版的游戏。规则如下：
游戏在以下棋盘上进行。
玩家轮流行动。第一步，玩家可以将他的棋子放在任意一个小棋盘的任意格子中。对于后续的移动，存在一些限制：如果上一步对手将他的棋子放在某个小棋盘的坐标为 #cf_span[(xl, yl)] 的格子中，那么下一步必须在坐标为 #cf_span[(xl, yl)] 的小棋盘中的某个格子中进行。例如，如果第一步玩家将棋子放在中心小棋盘的左下角格子，那么第二步玩家必须在左下角的小棋盘中的某个格子放置他的棋子（请参见第一个测试用例）。如果所需的小棋盘中没有空格子，玩家可以在任意一个小棋盘的任意空格子中放置他的棋子。
你将获得当前的游戏状态以及上一步所走格子的坐标。你需要找出当前玩家可以放置棋子的所有格子。
一只兔子是森林里的邮递员，他喜欢捉弄熊。有时他会稍微改变一下游戏棋盘，使得当前游戏状态可能是无法到达的。但经过他的改动后，上一步所走的格子并非空的。你不需要判断该状态是否可达，只需根据规则输出可能的下一步行动即可。
前11行包含一个9行9列的表格描述，该表格通过空格和空行划分为9个小棋盘。每个小棋盘由9个字符（无空格和空行）描述。字符 "_x_"（ASCII码120）表示该格子被第一位玩家的棋子占据，字符 "_o_"（ASCII码111）表示该格子被第二位玩家的棋子占据，字符 "."（ASCII码46）表示空格子。
表格后的那一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ 9]），它们描述了上一步所走格子在表格中的坐标。表格的行从上到下编号，列从左到右编号。
保证上一步所走的格子被 "_x_" 或 "_o_" 占据。同时，保证至少存在一个空格子。但不保证当前游戏状态是可达的。
请以相同格式输出棋盘，其中当前玩家可以放置棋子的格子用字符 "_!_"（ASCII码33）标记，其余格子保持不变。
在第一个测试用例中，第一位玩家将棋子放在了中心小棋盘的左下角格子，因此第二位玩家只能在左下角的小棋盘中的格子放置棋子。
在第二个测试用例中，上一步是将棋子放在了下中区域的小棋盘的左上角格子，但左上角小棋盘的所有格子都被占满了，因此第二位玩家可以在任意空格子中放置棋子。
在第三个测试用例中，上一步是将棋子放在了中心小棋盘的中心格子，因此当前玩家可以在中心小棋盘的任意格子中放置棋子，但该小棋盘已被占满，所以他可以在任意位置行动。请注意，这种游戏状态是无法到达的。
## Input
前11行包含一个9行9列的表格描述，该表格通过空格和空行划分为9个小棋盘。每个小棋盘由9个字符（无空格和空行）描述。字符 "_x_"（ASCII码120）表示该格子被第一位玩家的棋子占据，字符 "_o_"（ASCII码111）表示该格子被第二位玩家的棋子占据，字符 "."（ASCII码46）表示空格子。表格后的那一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ 9]），它们描述了上一步所走格子在表格中的坐标。表格的行从上到下编号，列从左到右编号。保证上一步所走的格子被 "_x_" 或 "_o_" 占据。同时，保证至少存在一个空格子。但不保证当前游戏状态是可达的。
## Output
请以相同格式输出棋盘，其中当前玩家可以放置棋子的格子用字符 "_!_"（ASCII码33）标记，其余格子保持不变。
[samples]
## Note
在第一个测试用例中，第一位玩家将棋子放在了中心小棋盘的左下角格子，因此第二位玩家只能在左下角的小棋盘中的格子放置棋子。在第二个测试用例中，上一步是将棋子放在了下中区域的小棋盘的左上角格子，但左上角小棋盘的所有格子都被占满了，因此第二位玩家可以在任意空格子中放置棋子。在第三个测试用例中，上一步是将棋子放在了中心小棋盘的中心格子，因此当前玩家可以在中心小棋盘的任意格子中放置棋子，但该小棋盘已被占满，所以他可以在任意位置行动。请注意，这种游戏状态是无法到达的。
**Definitions**
Let the game state be represented by a $9 \times 9$ grid $G$, where $G[i][j] \in \{ \text{'x'}, \text{'o'}, \text{'.'} \}$ for $i, j \in \{1, \dots, 9\}$.
Let the last move be at coordinates $(x, y)$, with $1 \le x, y \le 9$.
Define the *small field* containing cell $(i, j)$ as the $3 \times 3$ block indexed by $\left( \left\lfloor \frac{i-1}{3} \right\rfloor, \left\lfloor \frac{j-1}{3} \right\rfloor \right)$.
Let $F_{\text{target}} = \left( \left\lfloor \frac{x-1}{3} \right\rfloor, \left\lfloor \frac{y-1}{3} \right\rfloor \right)$ be the small field corresponding to the last move’s cell.
**Constraints**
1. $G[x][y] \in \{ \text{'x'}, \text{'o'} \}$
2. There exists at least one cell $(i, j)$ such that $G[i][j] = \text{'.'}$
3. The state may be unreachable; no validity check required.
**Objective**
Let $S$ be the set of all empty cells $(i, j)$ such that:
- If the small field $F_{\text{target}}$ contains at least one empty cell, then $(i, j)$ must lie in $F_{\text{target}}$;
- Otherwise (i.e., $F_{\text{target}}$ is full), $(i, j)$ may be any empty cell in the entire grid.
Output a modified grid $G'$, identical to $G$, except that every cell in $S$ is replaced with `'!'`.
API Response (JSON)
{
"problem": {
"name": "B. Tic-Tac-Toe",
"description": {
"content": "Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules. The game is played on the fol",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF907B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules.\n\nThe game is played on the fol...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "两只熊通过邮件玩井字棋。玩普通的井字棋对他们来说太无聊了，因此他们玩的是一个修改版的游戏。规则如下：\n\n游戏在以下棋盘上进行。\n\n玩家轮流行动。第一步，玩家可以将他的棋子放在任意一个小棋盘的任意格子中。对于后续的移动，存在一些限制：如果上一步对手将他的棋子放在某个小棋盘的坐标为 #cf_span[(xl, yl)] 的格子中，那么下一步必须在坐标为 #cf_span[(xl, yl)] 的小棋盘中...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet the game state be represented by a $9 \\times 9$ grid $G$, where $G[i][j] \\in \\{ \\text{'x'}, \\text{'o'}, \\text{'.'} \\}$ for $i, j \\in \\{1, \\dots, 9\\}$. \nLet the last move be at c...",
"is_translate": false,
"language": "Formal"
}
]
}