15214번 - Posters on the wall 다국어

Deep in the top-secret base of Keepers of the Sacred Postulates, there's The Wall with many rectangular posters depicting deep knowledge derived from their most valuable postulates. They are quite rare, thus they are placed so that they don't overlap.

Occasionally, a batch of new posters worthy of the honor of being placed on The Wall arrives. The Keepers then have to decide, where to place the new posters. It's a complicated process and you are to help with one of its steps.

The Keepers are currently picking candidate positions for the posters. You are to quickly compute the total area of currently hanging posters that would be shadowed by placing a new poster at a given position.

You are given a description of $n$ disjoint gray rectangles in a plane. You are to answer $q$ queries of the form: What is the total grey area in a given rectangle? Note that this doesn't affect the plane.

The answer has to be produced online

The first line contains five numbers, $r, c, n, q, m$, ($1 \leq r, c < m \leq 10^9 + 9$, $0 \leq n,q \leq 50\,000$), the height and width of the wall, number of posters on the wall, number of queries and a modulus for computing the queries (we will explain that below).

Each of the next $n$ lines contains four numbers, $x_1, y_1, x_2, y_2$ ($0 \leq x_1, x_2 \leq r$, $0 \leq y_1, y_2 \leq c$), the coordinates of two opposite corners of the rectangle.

The last $q$ lines contain five numbers $x_1', y_1', x_2', y_2', v$, each between $0$ and $m - 1$ (inclusive). You can compute the real coordinates $x_1, y_1, x_2, y_2$ using the formula below.

Let's denote by $l$ the answer to the last query (with $l=0$ for the first query). Then $$x_i = (x_i' + l \cdot v) \pmod m$$ $$y_i = (y_i' + l \cdot v) \pmod m$$

The decoded coordinates $x_1, y_1, x_2, y_2$ satisfy following conditions: $0 \leq x_1, x_2 \leq r$, $0 \leq y_1, y_2 \leq c$. 

There are several subtasks. In offline subtasks, the value $v$ will be zero for each query. 

For each query output one line containing a single number: Answer to the query.

Sample 1: You can view the whole plane below.

Sample 2: This is the same input as above, using online queries.