Description

There are $N$ pillars in a row, and initially each pillar has damage $0$.

Yuugi will perform $M$ attacks. Each attack is described by four parameters $l, r, s, e$:

It means this attack affects all pillars from the $l$-th to the $r$-th (inclusive), dealing damage $s$ to the first pillar and $e$ to the last pillar within the range.

The damage values form an arithmetic progression. For example, if $l = 1, r = 5, s = 2, e = 10$, then the damages to pillars $1 \sim 5$ are $2, 4, 6, 8, 10$ respectively.

The oni need the final damage of each pillar after all attacks are completed.

Input Format

The first line contains $2$ integers $N, M$, separated by a space; same below.

Each of the next $M$ lines contains $4$ integers $l, r, s, e$, as described above.

It is guaranteed that every individual damage applied to any pillar is an integer.

Output Format

Because the output might be too large to print in full, to ensure you can indeed maintain all pillars’ damage, output two integers separated by a space: the XOR sum of all pillars’ final damages and the maximum of them.

(The XOR sum is the value obtained by bitwise XOR over all numbers.)

(The XOR operator in C++ is ^.)

5 2
1 5 2 10
2 4 1 1

3 10

6 2
1 5 2 10
2 4 1 1

3 10

Hint

Sample explanation:

Sample 1:

Damage from the first attack: $2, 4, 6, 8, 10$.

Damage from the second attack: $0, 1, 1, 1, 0$.

Final damage of each pillar after all attacks: $2, 5, 7, 9, 10$.

Output the XOR sum and the maximum, which are $3, 10$.

Sample 2:

The sixth pillar is not hit, so the answer remains unchanged.

Constraints:

This problem is worth $100$ points, split into $4$ subtasks. $(x/y)$ means (score/testcase count).

• Fairy level $(18/3)$: $1 \le N, M \le 1000$. Even fairies playing around could finish this job, right?
• Kappa level $(10/1)$: $s = e$. Can this replace my work?
• Tengu level $(20/4)$: $1 \le N, M \le 10^5$. Small tricks no longer suffice.
• Oni God level $(52/2)$: No special restrictions. Time to really think.

These four parts of testdata do not overlap.

For all data: $1 \le N \le 10^7$, $1 \le M \le 3 \times 10^5$, $1 \le l < r \le N$.

All input, output, and pillar damage values are always within $[0, 9 \times 10^{18}]$.

Tip:

Due to various reasons, the time limit may be tight. C++ participants, please do not use cin for input.

by orangebird.

Translated by ChatGPT 5