33435번 - Dreamy Putata 다국어

문제

Putata is dreaming that he got lost in a phantom grid world of size $n \times m$. The rows and columns of the grid are numbered from 0ドル$ to $n - 1$ and 0ドル$ to $m - 1,ドル respectively. Putata has no idea how to escape from the phantom world, so he decides to walk randomly. Assuming Putata is now at $(x, y),ドル he will:

• Move to $(x, (y - 1) \bmod m)$ with probability $\frac{\ell(x, y)}{100}$.
• Move to $(x, (y + 1) \bmod m)$ with probability $\frac{r(x, y)}{100}$.
• Move to $((x - 1) \bmod n, y)$ with probability $\frac{u(x, y)}{100}$.
• Move to $((x + 1) \bmod n, y)$ with probability $\frac{d(x, y)}{100}$.

You need to perform $q$ operations. Each operation is one of the following:

• "1 $x$ $y$ $\mathit{c\ell}$ $\mathit{cr}$ $\mathit{cu}$ $\mathit{cd}$}' (0ドル \leq x < n,ドル 0ドル \leq y < m,ドル 1ドル \leq \mathit{c\ell}, \mathit{cr}, \mathit{cu}, \mathit{cd} \leq 100,ドル $\mathit{c\ell} + \mathit{cr} + \mathit{cu} + \mathit{cd} = 100$): Change the values of $\ell(x, y),ドル $r(x, y),ドル $u(x, y),ドル and $d(x, y)$ into $\mathit{c\ell},ドル $\mathit{cr},ドル $\mathit{cu},ドル and $\mathit{cd},ドル respectively.
• "2 $\mathit{sx}$ $\mathit{sy}$ $\mathit{tx}$ $\mathit{ty}$" (0ドル \leq \mathit{sx}, \mathit{tx} < n,ドル 0ドル \leq \mathit{sy}, \mathit{ty} < m,ドル $(\mathit{sx}, \mathit{sy}) \neq (\mathit{tx}, \mathit{ty})$): Assuming Putata is now at $(\mathit{sx}, \mathit{sy}),ドル he is wondering what is the expected number of steps that he will take when he reaches the target position $(\mathit{tx}, \mathit{ty})$ for the first time.

Please write a program to answer his questions.

입력

The first line of the input contains two integers $n$ and $m$ (3ドル \leq n \leq 10^5,ドル 3ドル \leq m \leq 5$) denoting the size of the phantom grid world.

In the next $n$ lines, the $i$-th line contains $m$ integers $\ell(i - 1, 0), \ell(i - 1, 1), \ldots, \ell(i - 1, m - 1)$ (1ドル \leq i \leq n,ドル 1ドル \leq \ell(\cdot, \cdot) \leq 100$).

In the next $n$ lines, the $i$-th line contains $m$ integers $r(i - 1, 0), r(i - 1, 1), \ldots, r(i - 1, m - 1)$ (1ドル \leq i \leq n,ドル 1ドル \leq r(\cdot, \cdot) \leq 100$).

In the next $n$ lines, the $i$-th line contains $m$ integers $u(i - 1, 0), u(i - 1, 1), \ldots, u(i - 1, m - 1)$ (1ドル \leq i \leq n,ドル 1ドル \leq u(\cdot, \cdot) \leq 100$).

In the next $n$ lines, the $i$-th line contains $m$ integers $d(i - 1, 0), d(i - 1, 1), \ldots, d(i - 1, m - 1)$ (1ドル \leq i \leq n,ドル 1ドル \leq d(\cdot, \cdot) \leq 100$).

It is guaranteed that $\ell(i, j) + r(i, j) + u(i, j) + d(i, j) = 100$ holds for all pairs of $(i, j)$ where 0ドル \leq i < n$ and 0ドル \leq j < m$.

The next line contains a single integer $q$ (1ドル \leq q \leq 3 \cdot 10^4$) denoting the number of operations.

Each of the next $q$ lines describes an operation in the format described in the statement above.

출력

For each test query, print a single line containing an integer: the expected number of steps that Putata will take when he reaches the target position $(\mathit{tx}, \mathit{ty})$ for the first time.

More precisely, assuming the reduced fraction of the answer is $\frac{p}{q},ドル you should output the minimum non-negative integer $r$ such that $q \cdot r \equiv p \pmod{10^9 + 7}$. You may safely assume that such $r$ always exists in all test cases.

제한

힌트