Grid Query

Time limit4sMemory limit1024 MB

Summary
Process N rectangle-add updates and Q rectangle-sum queries on a sparse 200000 by 200000 grid, then XOR all query answers.
Level

Medium7 of 10

Topics
Prefix sum, Matrix, Implementation, Sorting
Solved
No attempts yet

Problem

There is a two-dimensional array of size 200000 by 200000, filled entirely with zeros. In this array, row numbers increase downward and column numbers increase to the right. The position at row i, column j is written as (i,j).

To watch everyone suffer, Jongyeong performed an update operation N times, each adding V to the value at every position between (X1,Y1) and (X2,Y2).

You must process Q queries, each asking for the sum of the values at every position between (X1,Y1) and (X2,Y2).

Input

The first line gives N and Q. (1 ≤ N, Q ≤ 2.5×105)

Over the next N lines, X1, Y1, X2, Y2, V for Jongyeong's updates are given in order. (1 ≤ X1 ≤ X2 ≤ 2×105, 1 ≤ Y1 ≤ Y2 ≤ 2×105, 1 ≤ V ≤ 10)

Over the next Q lines, X1, Y1, X2, Y2 for the queries are given in order. (1 ≤ X1 ≤ X2 ≤ 2×105, 1 ≤ Y1 ≤ Y2 ≤ 2×105)

Output

Print one value: the XOR of the answers to all queries. In C and C++ this is expressed with the ^ operator. The meaning of the XOR operator has nothing to do with solving this problem.

Examples1

  1. Example 1

    Input
    5 5
522 1426 2758 2745 2
81 629 4167 3705 2
2775 3982 4503 4878 7
2156 902 3822 2544 7
3857 1918 4203 3364 9
3506 1568 4860 2317
16 1263 30 3397
1449 310 4071 3507
2068 3580 4378 3675
4218 4328 4272 4475
    Expected output
    39263476