Since the latest Great War, the Galaxy has been ruled by the Galatic Empire. Lord Edsidious was finally able to conquer the status of Emperor, after centuries of planning. In his Empire, the following definitions and conventions apply:

• $$$X \ \% \ Y$$$ (both integers) represents the remainder when dividing $$$X$$$ by $$$Y$$$ if $$$X \geq 0$$$ and $$$Y \gt 0$$$. Additionaly, $$$X \ \% \ Y = X$$$ if $$$X \lt 0$$$ and $$$Y \gt 0$$$, and $$$X \ \% \ Y = 0$$$ if $$$Y = 0$$$.
• $$$NCP(X, Y)$$$ is the smallest integer $$$K \geq X$$$ such that $$$gcd(K, Y) = 1$$$.
• The Super Shift Function, $$$SSF$$$, is defined as: $$$SSF(X, Y, Z) = ((X-Z) \ \% \ (Y-Z)) + Z$$$.
• The Collatz Function, $$$CF$$$, is defined as: $$$CF(X) = \begin{cases} \frac{X}{2} & \text{if } X \text{ is even} \\ \frac{3 \cdot X+1}{4} & \text{if } X \ \% \ 4 = 1 \\ 3 \cdot X+1 & \text{if } X \ \% \ 4 = 3 \end{cases}$$$.
• About the value of a fraction mod $$$X$$$: consider the fraction $$$\frac{P}{Q}$$$ with $$$Q$$$ coprime to $$$X$$$ (if it's not, the value is not defined). The value of this fraction mod $$$X$$$ is $$$(P \cdot Q^{-1}) \ \% \ X$$$, where $$$Q^{-1}$$$ is the value such that $$$(Q \cdot Q^{-1}) \ \% \ X = 1$$$ and $$$0 \leq Q^{-1} \lt X$$$ (it can be proven a unique $$$Q^{-1}$$$ exists if $$$Q$$$ is coprime to $$$X$$$).
• About grid notation: a $$$X$$$ x $$$Y$$$ grid has $$$X$$$ rows and $$$Y$$$ columns. A cell $$$(i, j)$$$ of the grid is at the $$$i$$$-th row and $$$j$$$ column. A subgrid $$$Z = (Z_{x1}, Z_{y1}, Z_{x2}, Z_{y2})$$$ is the set of cells $$$(i, j)$$$ with $$$Z_{x1} \leq i \leq Z_{x2}$$$ and $$$Z_{y1} \leq j \leq Z_{y2}$$$).

To maintain his dominance, Lord Edsidious hired the famous botanic Collatz (the creator of the Collatz Function) to build him a Collatz-Star of Pain and Suffering, which is a massive device able to exterminate whole planets with a single blast. And to protect this strategic weapon, he assigned his most prestigious general: Darth Caetanus. Caetanus recently became aware of a weakness in the Star: it's energy board.

The energy board is composed of independent cells disposed in a $$$H$$$ x $$$W$$$ grid, and it is associated with a fixed integer $$$M \gt 2$$$. A cell $$$(i, j)$$$, at any time $$$t$$$ (measured in some integer unit) has two positive integers associated with it: $$$A_{t,i,j}$$$ and $$$B_{t,i,j}$$$. These numbers describe the probability of a failure in the cell at that time, which is equal to $$$\frac{A'_{t,i,j}}{B'_{t,i,j}}$$$, where $$$B'_{t,i,j} = NCP(SSF(B_{t,i,j}, M, 2), M)$$$ and $$$A'_{t,i,j} = SSF(A_{t,i,j}, B'_{t,i,j}, 1)$$$. At any time, if a failure occurs in any cell, it shuts down, leaving the Collatz-Star with no power temporarily. These values $$$A$$$ and $$$B$$$ vary in time as follows: $$$A_{t+1,i,j} = CF(A_{t,i,j})$$$ and $$$B_{t+1,i,j} = CF(B_{t,i,j})$$$.

Vinicius Solo, an influent person in the fallen Galatic Republic, used his connections to find (at time $$$0$$$) all the numbers $$$A_{0,i,j}$$$ and $$$B_{0,i,j}$$$ and the fixed number $$$M$$$. He also became aware that, at a certain unknown time $$$T$$$, Lord Edsidius will order the Collatz-Star to fire against the poor U.n.Balloon planet. To prevent its destruction, Vinicius will need the help of his ally Daniel Skywalker, who can Mystic Focus on subgrids of the energy board grid.

Let's consider that Daniel tries to Mystic Focus on a subgrid $$$S$$$ in a period of time from $$$t_l$$$ to $$$t_r$$$ (inclusive), and let $$$Prob(S, t_l, t_r)$$$ be the probability that any cell in $$$S$$$ shuts down at any time between $$$t_l$$$ and $$$t_r$$$ (which means the Collatz-Star would lose power in this time interval). Daniel can explode the cells in $$$S$$$ using his ability, but only if the value of $$$Prob(S, t_l, t_r)$$$ mod $$$M$$$ is greater than $$$\lfloor \frac{M}{2} \rfloor$$$ (it can be proven $$$Prob(S, t_l, t_r)$$$ is always representable by a fraction $$$\frac{P}{Q}$$$ with $$$Q$$$ coprime to $$$M$$$). This explosion would provoke a chain reaction that would destroy the whole Collatz-Star!

However, saving U.n.Balloon will not be that easy. To protect the Collatz-Star, Darth Caetanus casted a spell which prevents Daniel from trying to Mystic Focus on subgrids $$$S$$$ not contained in a special unknown subgrid $$$K$$$. Also, if Daniel tries to Mystic Focus on some subgrid $$$S$$$, he will be forced to do so from $$$t_l = S_{x1} + S_{y1} + K_{x1} + K_{y1}$$$ to $$$t_r = T - (S_{x2} + S_{y2} + K_{x2} + K_{y2})$$$.

Vinicius and Daniel don't know what is the actual time $$$T$$$ or the special subgrid $$$K$$$, so they decided to prepare themselves. They will conduct $$$Q$$$ studies: in the study $$$i$$$, they will count, for chosen values of $$$T_i$$$ and $$$K_i$$$, the number of subgrids $$$S_i$$$ that Daniel would be able to Mystic Focus on and explode, causing the destruction of the Collatz-Star. Help them write a program that calculates this!