A factory floor is laid out as a grid of m conveyor lanes, each carrying n numbered crates. Once every night, an automated system nudges every lane by exactly k crate-widths at once: lanes at an even row index (0-indexed from the top) are nudged to the left, and lanes at an odd row index are nudged to the right — both cyclically, so a crate pushed off one end of a lane reappears at the other end. After the nightly nudge finishes, the floor supervisor wants to know whether the crate layout looks exactly like it did before the nudge, without having to check it by eye.
The first line contains three space-separated integers m, n, and k. Each of the next m lines contains n space-separated integers, where the j-th integer on the i-th of these lines gives the id of the crate sitting at row i, column j (both 0-indexed) before the nudge.
Print YES if the crate layout after the nightly nudge is identical to the layout before it, and NO otherwise.
Example 1
Input
2 4 2 5 9 5 9 7 7 7 7
Expected
YES
Explanation
n=4 and k=2, so the effective shift amount is 2. Row 0 has an even index, so it is nudged left by 2: [5,9,5,9] shifted left by 2 gives [5,9,5,9] again, since the row repeats with period 2 — unchanged. Row 1 has an odd index, so it is nudged right by 2: [7,7,7,7] shifted right by 2 is still [7,7,7,7], since every crate id is the same — unchanged. Both rows come back to themselves, so the whole layout matches the original: YES.
Example 2
Input
1 3 1 1 2 3
Expected
NO
Explanation
n=3 and k=1, so the effective shift amount is 1. The single row has index 0, which is even, so it is nudged left by 1: [1,2,3] shifted left by 1 gives [2,3,1], which is not the same as the original [1,2,3]. Since this row does not come back to itself, the layout does not match the original: NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →