Raze is a new agent in Valorant Inc. Currently, she is training on how to use Boom Bot.
The training arena is an grid where each cell has a height. We call a cell ground cell if its height is .
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 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.
First line contains an integer , denoting the number of testcases.
In each testcase, the first line contains two integers and , denoting the number of rows and columns in the grid respectively.
Each of the next lines contains integers, where each integer denotes the height of the cell .
Following line contains an integer , denoting the number of queries.
Each of the next lines contains two integers and , denoting the cell where the bot will be placed.
For each query, you need to print the expected time required for the bot to blast off. The answer can be written in form where and are relatively prime integers and .
Output the value of modulo .
1 1 3 1 2 2 3 1 1 1 2 1 3
0 3 4
1 2 2 2 2 2 1 3 1 1 1 2 2 2
4 3 0
Login to submit