À l'ouest du continent australien s'étend le vaste océan Indien. M. JOI, chercheur en océanographie, étudie les caractéristiques de $N$ espèces de poissons vivant dans l'océan Indien.

Pour chaque espèce de poisson, un habitat ayant la forme d'un parallélépipède rectangle est défini dans la mer. Les poissons peuvent se déplacer en tout point de leur habitat, frontière comprise, mais ils ne sortent jamais de leur habitat. Un point dans la mer est représenté par $3$ nombres réels $(x, y, d)$ : $(x, y, d)$ représente le point situé, vu du ciel, à une distance $x$ vers l'est et $y$ vers le nord par rapport à un certain point de référence, et à une profondeur $d$ sous la surface de la mer. On suppose ici que la surface de la mer est un plan.

M. JOI souhaite savoir quelle est l'étendue des endroits où les habitats d'au moins $K$ espèces de poissons se chevauchent. Écrivez un programme permettant de calculer le volume total de l'ensemble de ces endroits.

Entrée

L'entrée est composée de $1 + N$ lignes.

La $1$-re ligne contient $2$ entiers $N, K$ ($1 \le K \le N \le 50$) séparés par un espace. Cela indique qu'il y a $N$ espèces de poissons et que l'on souhaite trouver le volume des endroits où les habitats d'au moins $K$ espèces de poissons se chevauchent.

La $i$-e ligne ($1 \le i \le N$) des $N$ lignes suivantes contient $6$ entiers $X_{i,1}, Y_{i,1}, D_{i,1}, X_{i,2}, Y_{i,2}, D_{i,2}$ ($0 \le X_{i,1} < X_{i,2} \le 1000000 \ (= 10^6)$, $0 \le Y_{i,1} < Y_{i,2} \le 1000000 \ (= 10^6)$, $0 \le D_{i,1} < D_{i,2} \le 1000000 \ (= 10^6)$). Cela indique que l'habitat de la $i$-e espèce de poisson est le parallélépipède rectangle ayant pour sommets les $8$ points $(X_{i,1}, Y_{i,1}, D_{i,1})$, $(X_{i,2}, Y_{i,1}, D_{i,1})$, $(X_{i,2}, Y_{i,2}, D_{i,1})$, $(X_{i,1}, Y_{i,2}, D_{i,1})$, $(X_{i,1}, Y_{i,1}, D_{i,2})$, $(X_{i,2}, Y_{i,1}, D_{i,2})$, $(X_{i,2}, Y_{i,2}, D_{i,2})$, $(X_{i,1}, Y_{i,2}, D_{i,2})$.

Sortie

Affichez sur $1$ ligne le volume total de l'ensemble des endroits où les habitats d'au moins $K$ espèces de poissons se chevauchent.

Exemples

Entrée 1

3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70

Sortie 1

49000

Remarque

Dans l'exemple 1, par exemple, le point $(45, 65, 65)$ appartient aux habitats de la $1$-re espèce de poisson et de la $3$-e espèce de poisson, c'est donc un endroit qui vérifie la condition. En revanche, le point $(25, 35, 45)$ n'appartient qu'à l'habitat de la $2$-e espèce de poisson, ce n'est donc pas un endroit qui vérifie la condition. Par ailleurs, les habitats des poissons sont illustrés dans la figure ci-dessous. Le point $O$ représente le point de référence à la surface de la mer.

Entrée 2

1 1
0 0 0 1000000 1000000 1000000

Sortie 2

1000000000000000000