This page is still under construction.

Parts of this page are still being built. What you see may change.

Posters on the wall

Time limit2sMemory limit1024 MB

Summary
Given up to 50000 non-overlapping axis-aligned rectangles, answer online queries that ask for the total rectangle area inside a query rectangle, with coordinates decoded from the previous answer.
Level

Hard8 of 10

Topics
Segment tree, Sorting, Binary search, Prefix sum
Solved
No attempts yet

Problem

Deep inside a secret base there is a wall covered with rectangular posters. The posters are hard to come by, so they are placed without overlapping.

Every now and then a batch of new posters worth a place on the wall arrives, and the keepers have to decide where to put them. Your part of that process is one step: for a candidate position, compute the total area of the posters already hanging that a new poster placed there would cover.

You are given nn grey rectangles in a plane, no two of which overlap. Answer qq queries. Each query gives one rectangle and asks for the total grey area inside it. A query does not change the plane.

The answers have to be produced online. The coordinates of each query are encoded with the answer to the previous query, so you cannot read every query before answering the first one.

Input

The first line contains five integers rr, cc, nn, qq, mm (1≤r,c<m≤109+91 \leq r, c < m \leq 10^9 + 9, 0≤n,q≤50 0000 \leq n, q \leq 50\,000): the height of the wall, the width of the wall, the number of posters on the wall, the number of queries, and the modulus used to encode the queries.

Each of the next nn lines contains four integers x1,y1,x2,y2x_1, y_1, x_2, y_2 (0≤x1,x2≤r0 \leq x_1, x_2 \leq r, 0≤y1,y2≤c0 \leq y_1, y_2 \leq c), two opposite corners of one poster.

Each of the last qq lines contains five integers x1′,y1′,x2′,y2′,vx_1', y_1', x_2', y_2', v, each between 00 and m−1m - 1 inclusive. Let ll be the answer to the previous query, with l=0l = 0 for the first query. The real coordinates follow from the formulas below.

xi=(xi′+l⋅v)(modm)x_i = (x_i' + l \cdot v) \pmod m

yi=(yi′+l⋅v)(modm)y_i = (y_i' + l \cdot v) \pmod m

The decoded values x1,y1,x2,y2x_1, y_1, x_2, y_2 are two opposite corners of the query rectangle and satisfy 0≤x1,x2≤r0 \leq x_1, x_2 \leq r and 0≤y1,y2≤c0 \leq y_1, y_2 \leq c.

In some inputs vv is zero in every query. The encoding then leaves the coordinates unchanged.

Output

For each query print one line with a single integer: the total grey area inside the query rectangle.

Hint

The picture below shows the whole plane of the first example.

The second example encodes the same four queries as the first one with a nonzero vv. After decoding, the queries of the two examples agree, and so do the answers.

Examples2

  1. Example 1

    Input
    8 11 3 4 13
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8 0
2 2 4 3 0
3 4 6 7 0
2 9 3 10 0
    Expected output
    24
2
6
0

  2. Example 2

    Input
    8 11 3 4 13
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8 4
6 6 8 7 2
2 3 5 6 7
11 5 12 6 5
    Expected output
    24
2
6
0