Robot Meeting on a 5x5 Grid

Two robots are placed on a 5x5 grid at distinct starting positions. The grid may contain obstacles. The robots can move in the four cardinal directions (up, down, left, right) by one cell per move. They are allowed to pass over obstacles and each other, but they cannot end a move on an obstacle cell. The goal is for the two robots to meet in the same cell such that the sum of their moves does not exceed a given limit m.

Formally, let the number of moves taken by robot A to reach a meeting cell be \(d_A\) and by robot B be \(d_B\). The robots can meet if there exists a cell that both can reach with \(d_A + d_B \le m\).

You are given multiple games. For each game, determine whether the robots can meet within the allowed total moves. Output YES if they can, and NO otherwise.

inputFormat

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

• The first line contains an integer T, the number of games.
• For each game, the input is as follows:
• A line with five integers: \(r_1\), \(c_1\), \(r_2\), \(c_2\), and \(k\) where \((r_1, c_1)\) and \((r_2, c_2)\) are the starting positions of the two robots and \(k\) is the number of obstacle cells.
• If \(k > 0\), then the next \(k\) lines each contain two integers representing the row and column of an obstacle cell.
• A line with an integer \(m\) which is the maximum allowed total moves.

Note: The grid rows and columns are 1-indexed (i.e. valid cells satisfy \(1 \leq r,c \leq 5\)).

outputFormat

For each game, output a single line containing YES if the robots can meet within \(m\) total moves, or NO otherwise. The output is written to stdout.

## sample

1
1 1 2 2 0
10

YES

</p>