Bicolored Segments

You are given n segments [l_1, r_1], [l_2, r_2], ..., [l_n, r_n]. Each segment has one of two colors: the i-th segment's color is t_i.

Let's call a pair of segments i and j bad if the following two conditions are met:

• t_i ≠ t_j;
• the segments [l_i, r_i] and [l_j, r_j] intersect, embed or touch, i. e. there exists an integer x such that x ∈ [l_i, r_i] and x ∈ [l_j, r_j].

Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — number of segments.

The next n lines contains three integers l_i, r_i, t_i (1 ≤ l_i ≤ r_i ≤ 10^9; t_i ∈ {1, 2}) — description of the i-th segment.

Output

Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.

Examples

Input

3 1 3 1 4 6 2 2 5 1

Output

2

Input

5 5 8 1 1 3 2 3 4 2 6 6 1 2 10 2

Output

4

Input

7 19 20 1 13 15 2 6 11 2 4 10 1 14 17 1 13 13 2 5 9 1

Output

5

inputFormat

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — number of segments.

The next n lines contains three integers l_i, r_i, t_i (1 ≤ l_i ≤ r_i ≤ 10^9; t_i ∈ {1, 2}) — description of the i-th segment.

outputFormat

Output

Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.

Examples

Input

3 1 3 1 4 6 2 2 5 1

Output

2

Input

5 5 8 1 1 3 2 3 4 2 6 6 1 2 10 2

Output

4

Input

7 19 20 1 13 15 2 6 11 2 4 10 1 14 17 1 13 13 2 5 9 1

Output

5

样例

7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1

5

</p>