Un grup de geologi romani
a descoperit in Muntii Apuseni un mare zacamant de aur. Folosind cele mai performante
aparate, acestia au reusit sa cartografieze cu mare exactitate zacamantul. Acesta
poate fi asimilat unei zone cubice impartite in NxNxN
cuburi de latura 1 unitate. Au
fost determinate de asemenea acele cuburi care contin un minereu aurifer de
puritate necorespunzatoare. Pentru a putea realiza o exploatare eficienta din
punct de vedere economic, geologii trebuie sa identifice zone cubice cu latura
suficient de mare.
Cerinta
Scrieti
un program care sa determine latura celui mai mare cub, format din cuburi unitate,
care contine numai zacamant aurifer pur si numarul de cuburi distincte cu aceasta
proprietate.
Date de intrare
Fisierul de
intrare cub1.in contine pe prima
linie doua numere naturale N
si K, reprezentand dimensiunea
zacamantului, respectiv numarul cuburilor unitate de puritate necorespunzatoare.
Pe urmatoarele K linii se afla
cate trei numere Xi,
Yi, Zi,
i apartinand multimii {1,
2, …, K},
reprezentand coordonatele cuburilor unitate cu minereu impur. Tripletele nu
sunt neaparat distincte doua cate doua.
Date de iesire
Fisierul de iesire cub1.out va
contine, pe linii separate, doua numere naturale reprezentand latura maxima
a cubului cerut, respectiv numarul cuburilor cu aceasta latura.
Restrictii
3
<= N <= 120
0 <= K <= min(N3, 10000)
Exemple
cub1.in
cub1.out
Explicatii
3 6
1 1 1
1 1 3
1 3 3
3 1 3
3 3 1
3 2 2
2
1
Cubul gasit contine
cuburile unitate de coordonate: (1,2,1);
(1,3,1); (2,2,1); (2,3,1); (1,2,2); (1,3,2); (2,2,2); (2,3,3)