Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Boom Bot

By fsshakkhor · Limits 2s, 512 MB

Raze is a new agent in Valorant Inc. Currently, she is training on how to use Boom Bot.

The training arena is an N×MN \times M grid where each cell has a height. We call a cell ground cell if its height is 11.

The boom bot is placed on a cell in the grid. In each second, the bot can move to an adjacent cell whose height is not greater than the current cell. If there are multiple such cells, the bot picks a cell out of them randomly. If the bot reaches a ground cell, it blasts off immediately.

Raze has QQ queries to ask. She will place the bot on a cell and wants to know the expected time required for the boom bot to blast off.

Two cells are called adjacent if they share a side horizontally or vertically.

It is guaranteed that there will be at least one ground cell and no two ground cells will be adjacent.

Input

First line contains an integer T(1T10)T (1 \leq T \leq 10), denoting the number of testcases.

In each testcase, the first line contains two integers N(1N20)N (1 \leq N \leq 20) and M(1M20)M (1 \leq M \leq 20), denoting the number of rows and columns in the grid respectively.

Each of the next NN lines contains MM integers, where each integer Hij(1Hij2)H_{ij} (1 \leq H_{ij} \leq 2) denotes the height of the cell (i,j)(i, j).

Following line contains an integer Q(1QN×M)Q (1 \leq Q \leq N \times M), denoting the number of queries.

Each of the next QQ lines contains two integers X(1XN)X (1 \leq X \leq N) and Y(1YM)Y (1 \leq Y \leq M), denoting the cell where the bot will be placed.

Subtask

  • Subtask 1 (25 points): N=1N = 1
  • Subtask 2 (75 points): Original constraints

Output

For each query, you need to print the expected time required for the bot to blast off. The answer can be written in form PQ\frac{P}{Q} where PP and QQ are relatively prime integers and Q0mod998244353Q \neq 0\mod 998244353 .

Output the value of P×Q1P \times Q^{-1} modulo 998244353998244353.

Samples

InputOutput
1
1 3
1 2 2
3
1 1
1 2
1 3
0
3
4
InputOutput
1
2 2
2 2
2 1
3
1 1
1 2
2 2
4
3
0

    Discussion

    Statistics


    86% Solution Ratio

    NirjhorEarliest, 1M ago

    MujahidFastest, 0.1s

    NirjhorLightest, 786 kB

    Deshi_TouristShortest, 2185B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.