Chess Pieces Placement under Influence

You are given a chessboard with N rows and M columns. Certain squares on the board are special and have an influence range defined by a Manhattan distance. A special square located at \( (x, y) \) influences any board cell \( (i, j) \) if and only if

[ | (i+1)-x | + | (j+1)-y | \leq r ]

where \( r \) is the influence range of that special square. Given a number \( P \), determine if it is possible to place exactly \( P \) chess pieces on cells which lie in the influence area (possibly overlapping influence zones) of at least one special square. Note that a cell covered by the influence of one or more special squares can only accommodate one piece.

The input consists of multiple test cases.

inputFormat

The input is read from standard input (stdin). It begins with a single integer \( T \) representing the number of test cases. Each test case is formatted as follows:

• The first line contains four space-separated integers: \( N \) (number of rows), \( M \) (number of columns), \( K \) (number of special squares), and \( P \) (number of chess pieces to place).
• The next \( K \) lines each contain three space-separated integers: \( x \), \( y \), and \( r \). Here, \( (x, y) \) represents the coordinates of a special square (1-indexed) and \( r \) its influence range.

It is guaranteed that \( T \geq 1 \) and each test case follows the above format.

outputFormat

For each test case, output a single line to standard output (stdout) containing "YES" if it is possible to place at least \( P \) pieces on the board within the influence areas of the special squares, otherwise output "NO".

## sample

4
5 5 2 4
1 1 2
3 3 3
10 10 1 5
5 5 10
3 3 1 9
2 2 1
3 3 1 9
2 2 3

YES
YES
NO
YES

</p>