This is an approximate problem.

Let $s$ be an $N \times N$ matrix. We can distinguish four types of cells in this matrix: start cell, finish cell, empty cell, and cell with an obstacle. You can change at most $X$ cells from the type "empty cell" to type "cell with an obstacle" and at most $Y$ cells from the type "cell with an obstacle" to type "empty cell".

A path of size $t$ in matrix $s$ is a collection of cells $(x_1, y_1), (x_2, y_2), \dots, (x_t,y_t)$ $(1 \le x_i, y_i \le N)$ such that $|x_i - x_{i + 1}| + |y_i - y_{i + 1}| = 1$ $(1 \le i < t)$ and every $(x_i,y_i)$ is not a cell with an obstacle.

It is guaranteed that there is at least one path from every start cell to every finish cell. Please note that the final matrix must also satisfy this condition.

Assume that the matrix has $A$ start cells and $B$ finish cells. A pointer will be placed in one of the $A$ start cells and in each one with the same probability of $\frac{1}{A}$. In the next moves, we will move the pointer in one of four adjacent cells (from $(x,y)$ to $\{ (x+1,y), (x,y - 1), (x-1,y), (x,y + 1) \}$), whenever possible. If it is not possible to move the pointer in a certain direction (in case there is an obstacle in that cell or it will go outside the matrix), it will remain in its initial position. Moreover, at the $i^{th} (1 \le i \le C)$ move, we will move our pointer to the left with probability $l_i$, to right with probability $r_i$, up with probability $u_i$ ,and down with probability $d_i$. Note that after the pointer has reached a finish cell, it will stop there and will not move further.

Let $D_{t,x,y}$ $(1 \le x,y \le N, 1 \le t \le C)$ be the probability that we will end up in cell $(x,y)$ after $t$ moves. You need to change matrix $s$, such that $\sum_{i = 1}^{C} \sum_{(x,y) \text{ is a finish cell}} D_{i,x,y} \cdot i$ is minimized.

Note that the up direction of $(x,y)$ is $(x+1,y)$ and towards the right is $(x,y+1)$.

Input format

• First line: Numbers  $N, X$ , and $Y$
• Next $N$ lines: $N$ characters 
  • The $j^{th}$ character on the $(i + 1)^{th}$ line represents $s_{i,j}.$
  • If $s_{i,j} = 'A'$ then $(i,j)$ is a start cell, if $s_{i,j} = 'B'$ then $(i,j)$ is a finish cell, if $s_{i,j} = '.'$ then $(i,j)$ is an empty cell, else if $s_{i,j} = 'X'$ then $(i,j)$ is a cell with an obstacle.
•  $(i + N + 1)^{th}$ line: Four reals - $r_i, u_i, l_i, d_i$$(0.1 \le l_i, r_i, d_i, u_i \le 0.7, l_i + r_i + d_i + u_i = 1).$

Output format

Print $N$ lines where the $i^{th}$ line comprises $N$ characters - $v_{i,1}, v_{i,2}, \dots, v_{i,N}$ $(v_{i,j} \in \{ 'A', 'B', '.', 'X' \})$, where $v$ is the modified matrix $s$. 

Note that there must be at most $X$ cells $(x,y)$ with $s_{x,y} = '.', v_{x,y} = 'X'$ and at most $Y$ cells with $s_{x,y} = 'X', v_{x,y} = '.'$. If $s_{x,y} \in \{ 'A', 'B' \}$, then $v_{x,y}$ must be equal to $s_{x,y}.$

Scoring

Your scoring will be equal to $\sum_{i = 1}^{C} \sum_{(x,y) \ \text{with} \ v_{x,y} = 'B'} D_{i,x,y} \cdot i$.

Test generation

• $C = 10^5$
• $N = 50$
• For the first $50$ tests, $X = Y = 100$ and there are $300$ cells with obstacles.
• For the next $50$ tests, $X = Y = 25$ and there are $100$ cells with obstacles.
• All the start cells, finish cells, and cells with obstacles are distributed across the matrix with the same probability.
• The tests $10t + k$,  $10t + k + 50$ $(1 \le k \le 10, 0 \le t \le 4)$ have exactly $t + 4$ start cells and exactly $t+4$ finish cells.