先考虑\(D=1\)，明显可以\(O(M)\)模拟预处理出在最上面的每个位置往下走会走到什么位置，之后每次就可以\(O(1)\)查询了。当\(D>1\)时，可以依赖预处理的数据每次\(O(D)\)暴力查询。又注意到每次对所有位置进行的变换操作是一样的，可以倍增后用类似快速幂的方法优化到\(O(\log