Counting Special Paths in a Grid

You are given a grid with n rows and m columns. Some cells in the grid are marked as restricted, and you are not allowed to step on these cells. You will be given q queries. Each query gives you a start cell and a destination cell (both in 1-indexed format). Your task is to count the number of "special paths" from the start to the destination. In each move, you can only move to the right or down.

If either the starting cell or the destination cell is restricted, the answer for that query is 0. Otherwise, the number of paths can be computed using dynamic programming. In particular, if we denote by dp[i][j] the number of ways to reach cell \( (i, j) \) from the start, then the recurrence relation is:

[ dp[i][j] = dp[i-1][j] + dp[i][j-1] ]

provided that the cell \( (i, j) \) is not restricted and lies within the bounds specified by the query. The cells outside the query region or that are restricted are not used in the computation.

Your solution must read input from stdin and output the results to stdout.

inputFormat

The first line contains four integers n, m, k, and q where:

• n and m represent the number of rows and columns respectively,
• k is the number of restricted cells,
• q is the number of queries.

The next k lines each contain two integers representing the 1-indexed coordinates of a restricted cell.

The next q lines each contain four integers: sr sc dr dc, where (sr, sc) is the starting cell and (dr, dc) is the destination cell.

outputFormat

For each query, output a single integer on a new line representing the number of special paths from the starting cell to the destination cell.

## sample

3 3 1 2
2 2
1 1 3 3
1 2 3 3

2
1

</p>