#P17702. [ICPC 2019 Nanjing R] Holes
[ICPC 2019 Nanjing R] Holes
Problem Description
Given an chessboard, the rows and columns are numbered from to respectively. RDC, a handsome juvenile, punched several holes in specified locations, the -th of which locates at .
RDC also has a pet Pork Ribs dragon whose name is PRD. Now, PRD is drunk and was left on the chessboard at the cell . It will walk randomly and move to an adjacent cell every second with equal probability. Here two cells are adjacent if they share a common edge. PRD will fall into the hole and start to sleep when it arrives at a cell with a punched hole.
Now, RDC wonders the expected time consumption of his pet for each hole that his pet will finally stay in.
Input Format
The first line contains an integer (), indicating the number of test cases.
For each test case, the first line contains two integers and () indicating the size of the given chessboard and the number of holes. Then lines follow, the -th of which contains two integers and () indicating the location of the -th hole. The last line of each test case contains two integers and () described as above.
We guarantee that PRD is not locating at a hole initially, and all given holes are distinct. We also guarantees that hold in at most one test case.
Output Format
For each test case, output the expected time consumption (in seconds) for each hole in order in a single line.
More precisely, if a hole is reachable and the reduced fraction of the expected time consumption is , you should output the minimum non-negative integer such that . You may safely assume that such always exists in all test cases. If a hole is unreachable, output GG at the right place.
2
3 3
1 1
1 2
2 1
2 2
5 3
5 3
4 1
3 2
4 5
GG 4 4
669185882 381533358 341349117