Dear Engineer,

You have been tasked with controlling a sophisticated light display system for the grand opening of the new tech center.

The display consists of a sequence of n lights, numbered from 1 to n, all initially turned off. You have been given m control sequences, each described by three parameters: a, b, and r.

The head electrician left you this note: Remember, in lighting design, patterns create magic. Every switch tells a story, every toggle builds the show.

Each control sequence works as follows: for every multiple of r within the range [a, b], toggle that light. Toggling switches an off light to on, and an on light to off.

You need to determine how many lights will be turned on after executing all the control sequences in order.

Input Format

The first line contains two integers n and m, where n is the number of lights and m is the number of control sequences.

The next m lines each contain three integers a, b, and r, representing a control sequence that affects lights in range [a, b] for every multiple of r.

All positions are 1-indexed, and it is guaranteed that 1 ≤ a ≤ b ≤ n and 1 ≤ r ≤ n.

Output

Return the number of lights that are turned on after executing all control sequences.

Sample Input 1

6 3
1 4 2
2 5 1
3 6 3

Sample Output 1

2

Explanation

Initial lights: [OFF, OFF, OFF, OFF, OFF, OFF]

First sequence (a=1, b=4, r=2): Toggle multiples of 2 within range [1,4]

• Multiples: 2, 4 → Toggle lights 2 and 4: [OFF, ON, OFF, ON, OFF, OFF]

Second sequence (a=2, b=5, r=1): Toggle multiples of 1 within range [2,5]

• Multiples: 1, 2, 3, 4, 5 (but only 2, 3, 4, 5 are in range) → Toggle lights 2, 3, 4, 5: [OFF, OFF, ON, OFF, ON, OFF]

Third sequence (a=3, b=6, r=3): Toggle multiples of 3 within range [3,6]

• Multiples: 3, 6 → Toggle lights 3 and 6: [OFF, OFF, OFF, OFF, ON, ON]

Final lights: [OFF, OFF, OFF, OFF, ON, ON] → Count of ON lights = 2