After testing the game "The Maze Runner" in T246, GL decided to enter the Beta testing phase, so he invited $Q$ testers to try to play the game.

In this game, the maze is represented as an $N \times M$ rectangular grid. The rows of the grid are numbered from $1$ to $N$ (from top to bottom), and the columns are numbered from $1$ to $M$ (from left to right). The cell located in the $r$-th row and $c$-th column is denoted as $(r, c)$. Initially, no cells are blocked, and the player starts at cell $(X, Y)$.

The player can move to any adjacent cell that shares an edge, as long as it’s not blocked. Specifically, if the player is at $(r, c)$, they can move to:

• $(r-1, c)$ if $r > 1$ and the cell $(r-1, c)$ is not blocked.
• $(r+1, c)$ if $r < N$ and the cell $(r+1, c)$ is not blocked.
• $(r, c-1)$ if $c > 1$ and the cell $(r, c-1)$ is not blocked.
• $(r, c+1)$ if $c < M$ and the cell $(r, c+1)$ is not blocked.

However, GL discovered a very serious bug, that the player can teleport to another cell! As a result, some testers ends up in really weird positions, like a cell that is blocked or a cell that is not reachable at all. Therefore, he wants to know for each tester, if it is possible to end up at the cell they are currently on, without exploiting the bug. It is given that the $i$-th tester has moved for $T_i$ times and is at the cell $(R_i, C_i)$. It is guaranteed that $(X, Y)$ is not blocked.

Input

The first line of input contains five integers: $N$, $M$, $Q$, $X$ and $Y$.
The following $N$ lines contains $M$ characters, where the $j$-th character in $i$-th line represents the state of the cell $(i, j)$.

• . means $(i, j)$ is not blocked, and
• # means $(i, j)$ is blocked

Output

For all $Q$ cases, output 1 if it is possible to reach $(R_i, C_i)$ with exactly $T_i$ moves, and 0 otherwise.

Constraints

For all cases, $1 \le N, M \le 10^3, 1 \le Q \le 10^5, 1 \le X, R_i \le N, 1 \le Y, C_i \le M, 1 \le T_i \le 10^9$
Subtask 1 (15%): $N = 1$ or $M = 1$
Subtask 2 (30%): $1 \le N, M, T_i \le 100$
Subtask 3 (20%): No cells are blocked
Subtask 4 (35%): No additional constraints