题目描述

A labyrinth is obtained by tiling the entire plane with a pattern – a rectangular grid consisting of n rows and m columns where every cell is either empty or blocked. The result is an infinite grid of cells with the pattern repeating in all four directions.

Formally, suppose we denote both rows and columns of the infinite grid with integers (including the negative integers). The row number increases as we move downwards in the grid, while the column number increases as we go to the right. The cell at coordinates (0,0) is called the origin. The labyrinth is obtained by copying the pattern (without mirroring or rotation) to every n-by-m rectangular area that, in the upper-left corner, has a cell with the row number divisible by n and the column number divisible by m. In particular, the upper-left corner of the pattern gets copied to the origin, while the lower-right corner gets copied to the cell with coordinates (n−1,m−1).

To escape the labyrinth starting from a particular cell, we need to reach the origin via a sequence of empty cells, going up, down, left or right in each step.

You are given a pattern and a sequence of possible starting cells. For each starting cell determine if it is possible to escape the labyrinth.

输入格式

The first line contains two integers n and m (1≤n, m≤100)–the number of rows and columns in the pattern, respectively. Each of the following n lines contains a string of exactly m characters describing one row of the pattern. The character # denotes a blocked cell while the dot character denotes an empty cell. The following line contains an integer q (1≤q≤200,000) – the number of starting cells. The k-th of the following q lines contains two integers r and c ($−10^9$ ≤ r, c ≤ $10^9$) – the row and column of the k-th starting cell.

The origin and all starting cells will be empty.

输出格式

Output should consist of q lines. The k-th line should contain the word yes if it is possible to exit the labyrinth from the k-th starting cell and the word no otherwise.

题目大意

一个$n×m$的矩形，其中每格为路或墙，通过将图案平移来获得迷宫。迷宫是一个大小有限的坐标系，其图案在四个方向上重复。

用整数（包括负整数）表示横纵坐标。向下行数增加，向右列数增加，坐标$(0,0)$处称为原点。特别地，图案的左上角在原点，而右下角在坐标$(n-1,m-1)$。

原点是出口，为了从开始逃离迷宫，我们要从不同的起点到达原点，每一步可向上，下，左或右。对于每个起点，确定是否可以逃离迷宫。

输入格式：

第一行包含两个整数$n$和$m$（$1≤n$，$m≤100$）。

以下每一行包含$m$个字符。“#”表示墙，“.”表示路。 以下的一行包含整数$q$（$1≤q≤200000$）表示起点的数量。

以下$q$行每行包含两个整数$r$和$c$（$-10^9≤r$，$c≤10^9$），表示每个起点的坐标。

保证原点和所有起点为路。

输出格式： 输出$q$行。如果可以从当前起点逃出迷宫，则每行输出$yes$，否则输出$no$。

6 9 
..#####.. 
..#...#.. 
......#.. 
..#####.. 
..#...... 
..#...#.. 
5 
1 4 
5 4 
1 -5 
5 -5 
-1000000000 0

yes 
no 
no 
yes 
yes

提示

Central Europe Regional Contest 2015 Problem L