Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Scarlet Speedster

By SMAN2901 · Limits 1s, 64 MB

The scarlet speedster of Central City, popularly known as the Flash is fighting an epic battle against his enemy, the Reverse Flash. Reverse Flash has developed a weapon that can destroy the whole Central City. Flash knows where that weapon is and he must reach there before Reverse Flash.

Central City can be represented by a 2-dimensional grid with N rows where each row contains M square-shaped blocks. Both Flash and Reverse Flash is now at the leftmost block of the topmost row and the weapon is at the rightmost block of the bottom-most row. From any block, it is only possible to reach one of its adjacent blocks. Two blocks are adjacent if they share a common side.

Each block is assigned an integer value as its ID. If the absolute difference of ID’s of two blocks is even, then Flash will take zero second to reach from one of these two blocks to another. Otherwise he will take X seconds to do it. If the absolute difference of ID’s of two blocks is odd, then Reverse Flash will take zero second to reach from one of these two blocks to another. Otherwise he will take Y seconds to do it.

You are Cisco Ramon, a brilliant scientist and friend of Flash. Your task is to find out if it is possible for Flash to reach the bomb before Reverse Flash if they both move optimally.

Input

In the first line, there will be an integer T (1 ≤ T ≤ 100), the number of test cases. It will be followed by T test cases.

First line of each test case will contain four integers N, M, X and Y (1 ≤ N, M ≤ 100, 1 ≤ X, Y ≤ 1000) which are defined in the description above. Each of next N lines will contain M space-separated integers representing ID’s of blocks. Each of these integers will be in the range [1,100].

Output

If it is possible for Flash to reach the weapon before Reverse Flash when they both move optimally, then print “YES”. Otherwise print “NO”.

Sample

InputOutput
2
4 4 5 5
5 9 8 4
6 3 7 2
5 8 4 5
2 6 3 11
4 4 5 10
5 9 8 4
6 3 7 2
5 8 4 5
2 6 3 11
NO
YES


Discussion
Statistics

78% Solution Ratio

alif_biswasEarliest, 4w ago

EgorKulikovFastest, 0.1s

alif_biswasLightest, 131 kB

zh_rifatShortest, 1624B

Submit

Login to submit