Ant Colony

The Integer Forest holds a large colony of tree ants. The Integer Forest is an infinite two-dimensional plane with a tree at every point that has integer coordinates. The colony consists of a number of integer points, and some pairs of adjacent points are connected by tunnels. Two points $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent if $|x_1-x_2|+|y_1-y_2| = 1$, so the colony forms a graph. Tree ants are special because, besides living in trees, their colony is itself a tree: it is connected and has exactly $N-1$ tunnels, where $N$ is the number of points in the colony.

The researcher Anthony wants to run an experiment on the colony. He wants to know what happens when a rectangular area is cut off from the rest of the colony. His theory is that ants in different components of the graph form their own colonies and start wars against the others. A rectangle is the set of all integer points $(x, y)$ with $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y_2$, where $x_1, y_1, x_2, y_2$ are given integers.

Anthony has not yet decided which rectangle to use, but he has several ideas. For each rectangle, determine how many components of the graph form inside the rectangle when it is cut off. Two points belong to the same component if one can reach the other through tunnels without visiting a point outside the rectangle. Anthony only cares about the components inside the cut-off rectangle and ignores the rest of the colony.

The first line contains two integers $A$ and $B$ ($1 \leq A, B \leq 150\,000$), the size of the area the colony lives in.

The second line contains two integers $N$ and $Q$ ($2 \leq N \leq 150\,000$, $1 \leq Q \leq 150\,000$), the number of points in the colony and the number of rectangles.

The next $N-1$ lines describe the tunnels. Each tunnel has one of two types:

1. h $x$ $y$: points $(x, y)$ and $(x+1, y)$ are connected by a tunnel ($1 \leq x \leq A-1$, $1 \leq y \leq B$).
2. v $x$ $y$: points $(x, y)$ and $(x, y+1)$ are connected by a tunnel ($1 \leq x \leq A$, $1 \leq y \leq B-1$).

The next $Q$ lines describe the rectangles. Each line contains four integers $x_1$, $y_1$, $x_2$, and $y_2$ ($1 \leq x_1 \leq x_2 \leq A$, $1 \leq y_1 \leq y_2 \leq B$). The rectangle consists of all points $(x, y)$ with $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y_2$.

All coordinates $(x, y)$ of the colony satisfy $1 \leq x \leq A$ and $1 \leq y \leq B$. It is guaranteed that the graph formed by the points and tunnels is a tree.

Print $Q$ lines, one for each rectangle, containing the number of components that form inside that rectangle when it is cut off.

• $1 \leq A, B \leq 150\,000$
• $2 \leq N \leq 150\,000$
• $1 \leq Q \leq 150\,000$