Reachable Flowers in a Fenced Pasture

The pasture is a grid with \(10^6\) rows and \(10^6\) columns, with rows numbered from 1 to \(10^6\) (top to bottom) and columns numbered from 1 to \(10^6\) (left to right). There are three kinds of objects on the grid:

• A herd of \(n\) cows, each occupying a unit square.
• \(m\) dandelion flowers (which cows like), each occupying a unit square.
• \(p\) fences. Each fence is a rectangle whose perimeter runs along the edges of unit squares. Fences do not intersect or touch, though a fence may contain other fences entirely in its interior.

Due to unfavorable wind conditions, cows can only move in two directions: down or right. A cow may visit any square (even if occupied by another cow or a flower) provided it does not cross any fence boundary. In other words, a cow must remain in the same fenced region (or the outer region) in which it starts. Two adjacent unit squares are connected by a legal move if and only if they are in the same region. For example, if a fence has top-left corner \((r_1,c_1)\) and bottom-right corner \((r_2,c_2)\), then the fence’s vertical boundaries are at columns \(c_1\) and \(c_2+1\) and its horizontal boundaries are at rows \(r_1\) and \(r_2+1\); a cow cannot cross these boundaries.

Your task is: for each cow, determine the total number of flowers that are reachable from the cow’s current location by moving only down or right and without crossing any fence boundaries.

Note: A cow is reachable to a flower if there exists at least one path (using only down and right moves) that stays entirely within the same fenced region and ends at the square containing that flower.

The solution uses coordinate compression to reduce the huge grid to a manageable size and then applies dynamic programming over the compressed grid. In the DP the state at a cell \((i,j)\) will represent the union of all cells that can be reached (via legal moves) from \((i,j)\). Since moves are only down or right, the union operation is computed from the already processed neighbors. Two adjacent compressed grid cells are connected by a move if and only if they have the same fence inclusion (i.e. they lie in the same region).

For any cell, let its reachable set be the union of the cell itself and all cells reachable by legal moves. The answer for a cow is simply the sum of the flower counts in the reachable set of the compressed cell in which the cow lies.

The mathematical formulation of the grid boundaries is given by:

[ \begin{aligned} R &= {x: x = 1 \text{ or } x = r \text{ for some cow or flower or } x = r_1 \text{ or } x = r_2+1 \text{ for a fence}}, \ C &= {y: y = 1 \text{ or } y = c \text{ for some cow or flower or } y = c_1 \text{ or } y = c_2+1 \text{ for a fence}}. \end{aligned} ]

Then the compressed grid cell \((i,j)\) covers the region \([\text{rows}[i], \text{rows}[i+1]-1]\times[\text{cols}[j], \text{cols}[j+1]-1]\). A flower is counted in a cell if its coordinates belong to that interval.

inputFormat

The first line contains three integers \(n\), \(m\), \(p\), representing the number of cows, flowers, and fences respectively. The cows, flowers, and fences are given in the following format:

• Next \(n\) lines: each contains two integers: the row and column of a cow.
• Next \(m\) lines: each contains two integers: the row and column of a flower.
• Next \(p\) lines: each contains four integers \(r_1\), \(c_1\), \(r_2\), \(c_2\), describing a fence with top-left corner \((r_1,c_1)\) and bottom-right corner \((r_2,c_2)\).

The pasture is a \(10^6\times10^6\) grid, with rows numbered 1 to \(10^6\) and columns numbered 1 to \(10^6\).

outputFormat

Output \(n\) lines. The \(i\)th line should contain a single integer, the total number of flowers reachable from the \(i\)th cow’s current location.

sample

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

2
1

</p>