Fie o matrice A de dimensiuni 2N x 2N date. Aceasta se construiește astfel:
Se pornește de la o matrice de dimensiune 2 x 2 având ca elemente litere mici ale alfabetului englez. Matricea B de dimensiune 2k x 2k se formează din patru submatrice de dimensiune 2k-1 x 2k-1 și se obține din matricea C de dimensiune 2k-1 x 2k-1, astfel:

• Submatricea din stânga sus va fi C
• Submatricea din dreapta sus va fi formată din C, crescând fiecare element cu 3 (a devine d, b devine e, z devine c)
• Submatricea din stânga jos va fi formată din C, scăzând fiecare element cu 4 (a devine v, b devine x, …, z devine u)
• Submatricea din dreapta jos este C rotită cu 180 de grade

De exemplu dacă C de dimensiune 2 x 2 are valoarea:

Atunci matricea B de dimensiune 22 x 22 are valoarea:

Cerința

Se dau Q triplete (i, j, L), cu semnificația: pe poziția A[i][j] se află litera L. Care este numărul maxim de triplete care se pot selecta astfel încât toate să fie adevărate?
Exemplu:
N = 2, Q = 7
(1, 2, b)
(2, 3, f)
(2, 1, d)
(1, 2, z)
(4, 1, y)
(4, 4, a)
(3, 3, d)
Răspunsul este 5 (prima, a doua și ultimele trei). De exemplu, dacă matricea de pornire este:
ab
cd
Atunci matricea A va fi:
abde
cdfg
vxdc
yzba

Date de intrare

Fișierul de intrare expandmat.in conține pe prima linie numerele N și Q, despărțite printr-un spațiu, cu semnificaţia de mai sus, iar pe fiecare din următoarele Q linii va fi câte un triplet de numere i, j, L cu semnificațiile din enunț.

Date de ieșire

Fișierul de ieșire expandmat.out va conține pe prima linie numărul maxim de triplete care se pot selecta astfel încât toate să fie adevărate.

Restricții și precizări

• 1 ≤ N ≤ 60
• 1 ≤ Q ≤ 100.000
• Matricea este indexată de la 1.
• Subtask 1, în valoare de 21 puncte: matricea inițială conține doar literele a, b, c, d şi N ≤ 8, Q ≤ 100
• Subtask 2, în valoare de 19 de puncte: matricea inițială conține doar literele a, b, c, d şi N ≤ 60, Q ≤ 300
• Subtask 3, în valoare de 13 puncte: literele matricei inițiale sunt egale
• Subtask 4, în valoare de 21 puncte: în matricea inițială literele de pe aceeași linie sunt egale
• Subtask 5, în valoare de 9 puncte: se garantează că răspunsul este cel puțin Q / 2.
• Subtask 6, în valoare de 17 puncte: fără restricții suplimentare.

Exemplu:

expandmat.in

2 7
1 2 b
2 3 f
2 1 d
1 2 z
4 1 y
4 4 a
3 3 d

expandmat.out

5

Explicație

N = 2 și Q = 7.

Cele 5 triplete care se pot alege sunt:
1 2 b
2 3 f
4 1 y
4 4 a
3 3 d

Dacă matricea inițială este:
ab
cd
Atunci matricea finală este:
abde
cdfg
wxdc
yzba

Această matrice satisface toate cele 5 triplete.