How can you use the two data structures mentioned in our first coding club meeting of 2024 to solve this problem?

Jason suffers from a rare condition known as "clown behaviour". As a result, Jason attempts to cure his condition by hitting the gym. Jason's muscles can be modeled as \(N\) muscles in a line. Jason decides to work out ranges of his \(N\) muscles across \(Q\) days, adding a value of \(a_i\) to his muscles from \(l_i\) to \(r_i\) inclusive. At the end of his grind, Jason is afraid that some of of his muscle ranges sum to \(0\), cancelling their strength, meaning the muscles in that range won't be any different compared to before! Jason also doesn't know how to workout, meaning that on some days his muscles become weaker instead of stronger! Can you tell Jason how many of his muscle ranges sum to \(0\)?

Help Jason find out how many muscle ranges sum to \(0\) after \(N\) workouts.

A range from \(l\) to \(r\) sums to \(0\) if \(a_l + a_{l+1} + ... + a_{r-1} + a_r = 0\)

Contraints

\(1 \le l_i \le r_i \le N\)

\(-10^{5} \le a_i \le 10^{5}\)

Subtask 1 [30%]

\(1 \le N, Q \le 10^{3}\)

Subtask 2 [70%]

\(1 \le N, Q \le 10^{6}\)

Input Specification

The first line will contain two space seperated integers \(N\) and \(Q\) representing the amount of muscles and days. The next \(Q\) lines contain three integers \(l_i\) \(r_i\) and \(a_i\).

Output Specification

Output a integer \(C\) denoting how many ranges sum to \(0\).

Sample Input

10 4
4 7 1
2 6 6
9 10 3
4 5 -5

Sample Output

2

Explanation for sample output:

The array after each operation is as follows

Query 1:

\(0 \space 0 \space0\space 1\space 1\space 1\space 1\space 0\space 0\space 0\)

Query 2:

\(0 \space 6 \space6\space 7\space 7\space 7\space 1\space 0\space 0\space 0\)

Query 3:

\(0 \space 6 \space6\space 7\space 7\space 7\space 1\space 0\space 3\space 3\)

Query 4:

\(0 \space 6 \space6\space 2\space 2\space 7\space 1\space 0\space 3\space 3\)

There are 2 ranges, 1-1 and 8-8 that sum to 0, so the answer to Jason's problem is 2