Company: AMAZON_HACKON

Todd has a grid sheet of paper measuring N by M units and plans to draw squares on it. Each cell in the grid contains an integer X, which represents the center of a square with dimensions (2X - 1) by (2X - 1). Given this grid, Todd wants to know how many squares enclose specific cells. You will be asked Q queries, each with two numbers A and B. Your task is to determine how many of Todd's squares enclose the cell (A, B).

Note: Todd's squares can intersect and form additional shapes, but you only need to consider the original squares he draws, not any new shapes formed by intersections. Even if one square entirely overlaps another, both should be considered separately. The coordinates (A, B) are 0-based. grid[i][j] will contain integer values such that Todd's squares are always contained inside the grid.

Input Format:
The first line contains three integers N, denoting the number of rows in the grid, M, the number of columns in the grid, and Q, the number of queries. The next N lines each contain M integers, representing the grid. The next Q lines each contain two integers: A and B, representing the cell coordinates for the queries.

Output Format:
For each query, print a single integer representing the number of squares that enclose the given cell (A, B).

Constraints:
1 <= N, M <= 10^3
0 <= grid[i][j] <= min(N/2, M/2)
1 <= Q <= 10^5
0 <= A <= N-1
0 <= B <= M-1

Sample Testcase 1:
Input:
5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 2 0 0
0 0 0 2 0
0 1 0 0 0
2 2

Output:
2

Explanation:
Todd's art will look like this: For the query (2, 2), the number of squares enclosing the point is 2 — the red square and the green square.

Sample Testcase 2:
Input:
3 3 2
0 1 0
0 2 1
0 0 0
0 1
1 1

Output:
2
1

Explanation:
Todd's art will look like this: The first query (0, 1) is enclosed by 2 squares, and the second query (1, 1) is enclosed by 1 square. Show More

You are given an 8x8 chess board. The board has your rook denoted by 'R' and the rest of the cells are either blank, denoted by 'B' or they have some piece upon them denoted by 'P'. You can move over the blank cells only. A rook can move along its entire row or column in 1 move, up to the point where blank spaces are available.

If current coordinates of a rook are (x, y) then rook can move in t he following ways in 1 move: Move from (x, y) to (x-1, y), (x-2, y), (x-3, y) and so on; Move from (x, y) to (x+1, y), (x+2, y), (x+3, y) and so on; Move from (x, y) to (x, y-1), (x, y-2), (x, y-3) and so on; Move from (x, y) to (x, y+1), (x, y+2), (x, y+3) and so on. The rook can't move outside the board. As soon as the rook encounters a 'P' cell in its path it stops and can't move further.

The rook needs to reach cell (8,8) in order to prove its worth. Find the minimum number of moves the rook would take to reach cell (8,8) or print -1 if it is impossible to do so. The board follows 1 based indexing. The board contains a single cell with value 'R'. Each string consists of only 3 types of characters: 'P', 'B', or 'R'.

Input Format: The first line contains a single integer T, the number of testcases. Lines from 1 to 8 of each test case take input of a string of size 8 denoting the arrangement on the chess board.

Output Format: Print the minimum number of moves required to reach cell (8,8) or print -1 if it is impossible to do so.

Constraints: 1 <= T <= 10^8, length of each string = 8.

Sample Testcase 1:
Input:
1
BBBBBBBB
BRPPPPPP
PBPPPPPP
PBPPPPPP
PBBBBPPP
PPBBBBBB
PPPPPPPB
PPPPPPPB

Output:
5

Explanation:
In the first move the rook can move from cell (2,2) to (5,2) as all cells in between are blank, i.e. cells (3,2), (4,2), (5,2) are blank. In the second move the rook can move from cell (5,2) to (5,4) as all cells in between are blank, i.e. cells (5,3), (5,4) are blank. In the third move the rook can move from cell (5,4) to (6,4). In the fourth move the rook can move from cell (6,4) to (6,8). In the fifth move the rook can move from cell (6,8) to (8,8). Path: (2,2) > (5,2) > (5,4) > (6,4) > (6,8) > (8,8). Thus, it took 5 moves for the rook to reach cell (8,8). There might be other possible paths too but none of them would take less than 5 moves.

Sample Testcase 2:
Input:
BBBBBBBB
BBBBBBBB
RBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBPP
BBBBBBPB

Output:
-1

Explanation:
Since cell (8,8) is blocked by pieces ('P') from all directions, it is impossible for the rook to reach cell (8,8) regardless of the path taken. Show More

Prince was playing games on his computer all day, so his father decided to give him the task of arranging the books kept on the bookshelf. Prince can arrange the books on the bookshelf according to the book type, where an English alphabet denotes each book type. He is required to arrange the books in such a way that the book type having the lowest number of copies is kept first, and the book type having the maximum number of copies is kept last. If two or more book types have the same number of books, arrange them in lexicographically ascending order.

You are given two numbers, L and R. Return the total number of books of type A E I O U between [L, R], which are present on the bookshelf.

Input Format: The first line contains an integer n denoting the number of books. The second line contains n space-separated uppercase English alphabets that denote the type of book. The third line contains two space-separated integers denoting L and R.

Output Format: Return the total number of books of type A E I O U between [L, R] on the bookshelf.

Constraints: 1 <= N <= 100. The book type is uppercase English alphabet only.

Sample Testcase 1
Input:
7
BBAABCC
1 2

Output:
2

Explanation: In this case, 2 books are of type A, 2 books are of type C, and 3 books are of type B. Hence, after arranging them according to the given condition, the shelf looks like this: AACCBBB (let's say string y). Here, the frequency of A and C are the same, so they are sorted in lexicographically ascending order. The distinct types of book that is kept on the shelf after arrangement is ACB (let's say string x). The value of L=1 and R=2. Therefore, the number of books of type A E I O U in the range [1,2] in string x is 1, i.e., the type A. The number of books of type A in string y is 2; hence, the answer is 2.

Sample Testcase 2
Input:
7
CABCABB
1 3

Output:
[Output not provided] Show More

You are given an NxN matrix 'mat' where each cell contains one of the two characters 'a' or 'z'. A man stands at the bottom-right corner of the matrix (mat[N-1][N-1]) and wants to reach the top-left corner of the matrix (mat[0][0]). The man can only move up or left at each step. Your task is to find the lexicographically smallest string that can be formed by following any valid path from mat[N-1][ N-1] to mat[0][0]. Additionally, determine the number of distinct paths that yield this lexicographically smallest string.

Input Format: First line of input takes integer 'N' denoting the dimensions of the matrix 'mat'. The next 'N' lines take 'N' space-separated characters either 'a' or 'z' representing the values in the matrix 'mat'.

Output Format: The first line of output shows the lexicographically smallest string that can be formed by any valid path from mat[N-1][N-1] to mat[0][0]. The last line of the output shows the number of distinct paths that yield this lexicographically smallest string.

Constraints: 2 <= N <= 40

Sample Testcase 1
Input:
3
z a z
a a a
z z z

Output:
zaaaz
2

Explanation: Starting from mat[2][2] = 'z', the next move can either be up or left. If we move up to mat[1][2] = 'a', then move left to mat[1][1] = 'a', then move either up or left to mat[1][0] or mat[0][1] = 'a', and finally move up to mat[0][0] = 'z', the path forms the string "zaaaz", the lexicographically smallest string. Therefore, the number of possible paths = 2.

Sample Testcase 2
Input:
4
z z a z
z z a a
z z a z
a a a a

Output:
aaaaazz
1

Explanation: Starting from mat[3][3] = 'a', the next move can either be up or left. Moving up to mat[2][3] = 'a', then up to mat[1][3] = 'a', then up to mat[0][3] = 'a', then left to mat[0][2] = 'a', then left to mat[0][1] = 'z', and finally left to mat[0][0] = 'z', the path forms the string "aaaaazz", which is the lexicographically smallest string. Therefore, the number of possible paths that form the string is 1. Show More