You're given an integer n, answer the number of inversions in all the derangement permutations of length n. For example, if n = 3, there are two derangement premutations, 231 and 312, so the answer is 4.

There is such a sequence in OEIS. But I want to know how this is derived.

It's welcomed if you have other linear solution.

Hello guys, I've made a short video editorial about the upcoming april fools day contest.

Video solution on youtube

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 :-)