It’s a new winter season at Yellow Mountain ski resort. This time, the resort has hired you to calculate the amount of routes a person can go down the hill in certain areas so that they can put the information in their brochure.
A map of the hill is given as a square grid of rows and columns. Places where one can ski are marked with
O's, while trees and other impassable terrain are marked with
Skiers start at the spaces given at the top of the hill and can ski to one of the three squares directly or diagonally below them. They can end their descent at any of the open places at the bottom of the hill.
The first line contains \(N\ (1 \le N \le 10^3)\), the height and width of the hill.
Then \(N\) lines follow with \(N\)
O's on each line
The next line contains the number of queries, \(Q\ (1 \le Q \le 10^6)\), in which \(Q\) lines of \(N_1\) and \(N_2\) will follow, where \(0 \le N_1 \le N_2 \le N\), with \(N_1\) being the lower bound and \(N_2\) being the upper bound, inclusive, of the positions at the bottom of the hill the skiers can end at.
Output the number of paths given the bounds.
3 OXO XOX OXO 2 1 2 2 3