Given $n$ concentric sectors, calculate the total area covered by at least $k$ sectors.

Input

The first line contains three integers $n$, $m$, and $k$. $n$ represents the number of concentric sectors, and $m$ represents that the angular interval $(-\pi, \pi]$ is divided into $2m$ equal parts.

The next $n$ lines each contain three integers $r$, $a_1$, and $a_2$. Each line describes a sector with its center at the origin, radius $r$, and a central angle ranging from $\frac{\pi a_1}{m}$ to $\frac{\pi a_2}{m}$ (where $a_1 < a_2$).

Output

Output an integer $ans$ such that $\frac{\pi}{2m} \times ans$ equals the total area covered by at least $k$ sectors.

The data guarantees that the answer is within the range $2^{63}-1$.

Examples

Input 1

3 8 2
1 -8 8
3 -7 3
5 -5 5

Output 1

76

Input 2

2 4 1
4 -4 2
1 -4 4

Output 2

98

Constraints

For 30% of the data, $1 \le n \le 10^3, 1 \le m \le 10^3$.

For 50% of the data, $k = 1$.

For 100% of the data, $1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le k \le 5000, 0 \le r_i \le 10^9, -m \le a_1, a_2 \le m$.