Counting Non‐Conflicting Segment Selections

Consider \(n\) segments on the number axis. The \(i\)th segment has left endpoint \(l_i\) and right endpoint \(r_i\) and a color \(c_i\) (with \(c_i = 0\) for red and \(c_i = 1\) for blue). Two segments \(i\) and \(j\) are said to overlap if there exists some real number \(x\) satisfying \(l_i \le x \le r_i\) and \(l_j \le x \le r_j\).

You are to choose a subset of these segments (possibly empty) such that if any two chosen segments overlap then they must have the same color. In other words, the selection is valid if there is no red segment and blue segment that overlap.

Calculate the number of valid ways to choose segments. Two ways are considered different if there is at least one segment which is chosen in one selection but not in the other.

Note: Any formula must be written in \(\LaTeX\) format. For instance, the overlap condition is written as: \(\lnot\,(r_i < l_j \text{ or } r_j < l_i)\).

inputFormat

The first line contains an integer \(n\), the number of segments. Each of the following \(n\) lines contains three values: \(l_i\), \(r_i\) and \(c_i\), where \(l_i\) and \(r_i\) are real numbers representing the endpoints of the segment, and \(c_i\) is an integer (either 0 for red or 1 for blue).

It is guaranteed that all values are given in a space‐separated format.

outputFormat

Output a single integer, the number of valid ways to choose segments satisfying the condition that any two overlapping segments have the same color.

sample

3
1 3 0
2 5 1
6 7 0

6