5287: Escape along Water Pipe

You're trapped into a map with n×mgrids, each grid has a strange water pipe.
There are six types of water pipes, denote them as ID0,1,2,3,4,5.

You are located at the top of grid (1,1)and you want to reach the bottom of grid(n,m). In each step, you should travel along the pipe and move to another grid.


Before each move, you can do beautiful magic once: pick one of the degrees from{0,90,180,270}, select any number of grids except the one you are located at, and rotate their water pipes with the same degree you pick in the clockwise direction. Note that after you step in a grid along the water pipe, you must walk along the other end of the pipe to leave this grid.

You may step in the same grid multiple times, and the direction can be different every time you enter.

Determine whether you can escape from the entrance to the exit successfully.

There are multiple test cases. The first line of the input contains an integerT(1≤T≤10000), indicating the number of test cases. For each test case:

The first line contains two integersn,m(2≤n,m≤1000)indicating the size of the map.

In the next nlines, there are mintegersai,j(0≤ai,j≤5), indicating the ID of waterpipe in each grid.

It's guaranteed that the sum of n×mover all test cases does not exceed1e6.

For each test case, output 'YES' if you can escape from the map, otherwise output 'NO'.

If the answer is YES, then output a valid solution from the top of (1,1)to the bottom of(n,m). You should first output an integer k(k≤20nm)indicating the length of your operations, and then output klines to describe your escaping line.

If you try to rotate some cells, first output two integerst,d(0<t≤nm,d∈{0,90,180,270}), indicating the number of cells and the degree you rotate, and then output 2tintegers(x1,y1,x2,y2,…,xt,yt), indicating the cells you rotate. Two consecutive rotation requests are not allowed.

If you try to step into another cell, output three integers(0,x,y), indicating the next cell you pass by. You should assure that the first pair of (x,y)is(1,1), the last pair of (x,y)is(n,m), and your direction when stepping into the last cell is downward.

If there are multiple solutions, you can print any of them. 

Your submission is not accepted if the total number of (x,y)you output (including the cells you rotate and the cells you pass by) exceeds20nm.

2
2 2
4 5
0 1
2 2
0 1
2 3

YES
5
2 90 1 1 2 1
0 1 1
0 2 1
2 180 1 2 2 2
0 2 2
NO