Path Existence in Grid

You are given an n x n grid. The grid is indexed from 0 to n-1 in both dimensions. Some cells are blocked, and you are given the starting coordinate (startX, startY). Your task is to determine whether there exists a path from the starting cell to the bottom‐right cell at coordinate (n-1, n-1) that does not pass through any blocked cell.

You can move in four directions: up, down, left, and right. Formally, from cell (x, y) you can move to (x-1, y), (x+1, y), (x, y-1), or (x, y+1) provided the destination cell is within the grid boundaries and is not blocked.

The grid size is given by n, and the set of blocked cells is given as a list of coordinates. The existence of the path should be determined using the following condition in mathematical terms:

Find if there exists a sequence of moves \( \{(x_i, y_i)\}_{i=0}^k \) such that:

[ \begin{aligned} &(x_0, y_0) = (startX, startY) \ &(x_k, y_k) = (n-1, n-1) \ &\text{for each } i, ; (x_{i+1}, y_{i+1}) \text{ is reachable from } (x_i, y_i) \text{ via a valid move,} \ &(x_i, y_i) \notin \text{BlockedCells} \quad \text{for all } i. \end{aligned} ]

Output True if such a path exists, otherwise output False.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n (the size of the grid).
• The second line contains two integers separated by a space: startX and startY, the starting coordinates.
• The third line contains an integer k representing the number of blocked cells.
• The next k lines each contain two integers separated by a space representing the coordinates of a blocked cell.

It is guaranteed that the coordinates provided are within the grid boundaries.

outputFormat

Print to stdout a single line containing either True or False depending on whether a valid path exists from the starting position to the bottom-right corner.

## sample

5
0 0
3
1 2
2 1
3 3

True