A zoo has a straight walking path with n zones numbered from 1 to n.

There are q animal movement reports. Each report contains l, r, and c. This means animal type c was seen in every zone from l to r.

A zone is called crowded if at least k different animal types were seen in that zone.

Multiple reports of the same animal type in a zone still count as only one animal type.

Your task is to count the number of crowded zones.

The first line contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression — the number of zones, the number of reports, and the minimum number of different animal types needed.

Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and one lowercase English letter KaTeX can only parse string typed expression.

Print a single integer — the number of crowded zones.