1389_F. 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
```python
from operator import add

class LazySegmentTree():
    def __init__(self,n,init,merge=max,merge_unit=-10**18,operate=add,operate_unit=0):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.data=[0 for i in range(1<<(self.n+1))]
        self.lazy=[0 for i in range(1<<(self.n+1))]
        for i in range(n):
            self.data[2**self.n+i]=init[i]
        for i in range(2**self.n-1,0,-1):
            self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            add=self.lazy[v]
            self.lazy[v]=0
            self.data[2*v]=self.operate(self.data[2*v],add)
            self.data[2*v+1]=self.operate(self.data[2*v+1],add)
            self.lazy[2*v]=self.operate(self.lazy[2*v],add)
            self.lazy[2*v+1]=self.operate(self.lazy[2*v+1],add)


    def remerge_above(self,i):
        while i:
            i>>=1
            self.data[i]=self.operate(self.merge(self.data[2*i],self.data[2*i+1]),self.lazy[i])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        while l<r:
            if l&1:
                self.data[l]=self.operate(self.data[l],x)
                self.lazy[l]=self.operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.data[r-1],x)
                self.lazy[r-1]=self.operate(self.lazy[r-1],x)
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.merge_unit
        while l<r:
            if l&1:
                res=self.merge(res,self.data[l])
                l+=1
            if r&1:
                res=self.merge(res,self.data[r-1])
            l>>=1
            r>>=1
        return res

import sys

input=sys.stdin.buffer.readline

n=int(input())
a=[]
b=[]
val=set()
for i in range(n):
    l,r,t=map(int,input().split())
    if t==1:
        a.append((l,r))
    else:
        b.append((l,r))
    val.add(l)
    val.add(r)

val=sorted(list(val))
comp={i:e for e,i in enumerate(val)}
N=len(val)

querya=[[] for i in range(N)]
queryb=[[] for i in range(N)]
for i in range(len(a)):
    l,r=a[i]
    a[i]=(comp[l],comp[r])
    querya[comp[r]].append(comp[l])
for i in range(len(b)):
    l,r=b[i]
    b[i]=(comp[l],comp[r])
    queryb[comp[r]].append(comp[l])

init=[0]*N
LSTA=LazySegmentTree(N,init)
LSTB=LazySegmentTree(N,init)

dp=[0]*N
for i in range(N):
    for l in querya[i]:
        LSTA.update(0,l+1,1)
    for l in queryb[i]:
        LSTB.update(0,l+1,1)
    temp1=LSTA.query(0,i+1)
    temp2=LSTB.query(0,i+1)
    dp[i]=max(temp1,temp2)
    if i!=N-1:
        LSTA.update(i+1,i+2,dp[i])
        LSTB.update(i+1,i+2,dp[i])

print(dp[N-1])

```