Problem Background

(三) Old Capital

Emerging from the narrow cave, the view suddenly opens up.

Unusual snowflakes drift in the sky.

Contrary to the previous claustrophobic environment, now there is a bustling market, where the sound of wine bowls clashing can be heard.

This is a small society composed of despised oni and other youkai, a scene of harmony and joy.

Suddenly, some densely packed dots appear in the distance, resembling large particles of dust.

As we get closer, we finally see clearly.

Oni with horns gather together, watching the performance of another oni.

That "dust" is actually a barrage of projectiles.

One of the moves of Yugi, within three steps, the area is filled with projectiles, leaving almost no chance of survival.

To strengthen this skill, Yugi will attack a row of pillars.

The pillars of the old hell are incredibly sturdy, but for safety, it is necessary to understand the damage caused by such an attack, and also to test the effectiveness of the practice.

Yugi decides to discuss it with the other oni...

"I know the kappa clan of the youkai mountain has a magical tool called a computer, maybe we can borrow it," says Sika.

So, the oni of the old hell decide to ask Kawashiro Nitori for help.

"Do you need to record the damage level of all the pillars?" Nitori asks.

After further inquiry, Nitori finds out that they only need the damage level of the pillars after all attacks are completed.

The task is almost understood, Nitori extracts the important parts and records them in her work notebook:

(The content of the record is in the problem description)

And so the experiment begins.

In the thunderous collision, every time Yugi completes an attack, Nitori faithfully records the damage to each pillar. Meanwhile, Yugi waits beside her for the recording to be completed before proceeding with the next round of attacks.

On the ground, the sky is getting dark.

"I don't want to stay here until深夜, or I won't be able to go home," Nitori thinks, still repeatedly inputting new information into the computer.

"Do I really have to record the damage to each pillar from each round of attacks one by one? Is there a more efficient way?" This thought flashes through Nitori's mind...

(The subsequent plot is in the solution, next please see T3)

Problem Description

Problem Summary:

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

Next, Yugi will perform $M$ attacks, each attack can be described by 4 parameters $l$, $r$, $s$, $e$:

Indicating that this attack affects all pillars from the $l$-th to the $r$-th (including $l$ and $r$), with the first pillar receiving $s$ damage and the last pillar receiving $e$ damage.

The damage values generated by the attack form an arithmetic sequence. If $l=1$, $r=5$, $s=2$, $e=10$, then the 1st to 5th pillars receive 2, 4, 6, 8, 10 damage respectively.

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

Input Output Format

Input Format

The first line contains 2 integers $N$, $M$, separated by spaces.

The next $M$ lines, each containing 4 integers $l$, $r$, $s$, $e$, as described in the problem.

It is guaranteed that the damage values generated for each pillar are integers.

Output Format

Since the output data may be too large to output all, to ensure that you can maintain the damage level of all pillars, just output their XOR sum and the maximum value.

(The XOR sum is the value obtained by XORing all numbers together)

(The XOR operator in C++ is ^)

Sample Input and Output

Input Sample #1

5 2
1 5 2 10
2 4 1 1

Output Sample #1

3 10

Input Sample #2

6 2
1 5 2 10
2 4 1 1

Output Sample #2

3 10

Notes

Sample Explanation:

Sample 1:

Damage from the first attack: 2 4 6 8 10

Damage from the second attack: 0 1 1 1 0

Total damage to each pillar after all attacks: 2 5 7 9 10.

Output the XOR sum and the maximum value, which is 3 10.

Sample 2:

No attack hits the sixth pillar, the answer remains unchanged.

Data Range:

This problem is worth 100 points, divided into 4 sub-tasks. (x/y) indicates (score/number of test cases)

Fairy Level (18/3): $1 \leqslant n, m \leqslant 1000$. This task can be completed even if done playfully like a fairy.

Kappa Level (10/1): $s = e$, can this replace my work?

Tengu Level (20/4): $1 \leqslant n \leqslant 10^5$, $1 \leqslant m \leqslant 10^5$. Playful methods are no longer feasible.

Oni God Level (52/2): No special restrictions. Real thinking begins.

The above four parts of data are disjoint.

For all data: $1 \leqslant n \leqslant 10^7$, $1 \leqslant m \leqslant 3 \times 10^5$, $1 \leqslant l < r \leqslant n$.

All input and output data, as well as the damage level of the pillars, are always within the range $[0, 9 \times 10^{18}]$.

Hints:

Due to various reasons, the time limit may be tight, C++ users please do not use cin to read data.

by orangebird

见题面 Input 部分

见题面 Output 部分