The municipal corporation of Bandra is preparing a redevelopment plan for a large sea-facing promenade.
The promenade is divided into n rows and m columns of square plots. Each plot can potentially host a streetlight, but some plots are already reserved for cafés, benches, or pathways.
Engineers have provided the corporation with a list of reserved plots. Each reserved space is always a continuous stretch along a single row, starting from one column and ending at another.
Your task is to calculate the number of plots where new streetlights can actually be installed.
Note: If two reserved stretches overlap or touch within the same row, they should be treated as a single reserved block.
Constraints
1≤n,m≤10^9 — number of rows and columns
0≤k≤10^5 — number of reserved stretches
1≤r≤n — row number of reserved stretch
1≤c1≤c2≤m — starting and ending columns of reserved stretch
Input Format
The first line contains three integers:
n = number of rows of the promenade
m = number of columns of the promenade
k = number of reserved stretches
Each of the next k lines contains three integers:
r = row number (1-indexed)
c1 = starting column of reserved stretch
c2 = ending column of reserved stretch
Output Format
Print a single integer — the total number of plots where new streetlights can be installed.
Example 1
Input:
4 4 3
2 2 3
3 1 4
4 4 4
Output:
9
Explanation:
The promenade is a 4 × 4 grid of plots.
Row 2 has reserved [2, 3]
Row 3 has reserved [1, 4]
Row 4 has reserved [4]
Total plots = 16.
Reserved = 7.
Available for streetlights = 9.
Log In to solve the Question