Problem Statment

You're given a matrix of $$$N$$$ rows and $$$M$$$ columns, and $$$Q$$$ queries. $$$(1 <= N, M, Q <= 1000)$$$

For each query $$$(x, y, c)$$$, you need to rotate clockwise the square child matrix whose upper left corner is $$$(x, y)$$$ and lower right corner is $$$(x+c-1, y+c-1)$$$.

Print the final matrix as result.

Sample

input:

4 5 3
9 9 3 4 5
5 0 2 1 3
9 3 6 4 3
5 9 3 9 0
1 3 1
2 1 2
2 2 1

output:

9 9 3 4 5
9 5 2 1 3
3 0 6 4 3
5 9 3 9 0

Obviously there is an $$$O(n^3)$$$ brute force algorithm which is not fast enough. Are there any solution faster than $$$O(n^3)$$$?

I guess the technique of dancing links may be useful.

thanks :-)