Cerința

Se citesc două matrice rare și se cere să se calculeze suma lor.

O matrice A(n,m) se numește rară dacă majoritatea elementelor sale sunt egale cu zero (cel puţin jumătate). Datorită numărului mic de numere nenule, o matrice rară A(n,m), având k elemente nenule, poate fi memorată folosind un șir X conţinând k triplete de forma (linie, coloană , valoare), corespunzătoare valorilor nenule ale matricei. Elementele șirului X se memorează în ordine lexicografică după (linie,coloana).

De exemplu matricea cu n = m = 3

1 0 2
0 0 5
0 2 0

se va memora sub forma sirului X continand 4 triplete : {(1,1,1) , (1,3,2) , (2,3,5) , (3,2,2)}.

Date de intrare

Fișierul de intrare matrice_rara.in conține pe prima linie , dimensiunile celor două matrice n m – reprezentând numărul de linii şi coloane, şi N1 N2, numărul de elemente nenule ale matricei A, respectiv matricei B. Apoi următoarele N1 linii vor conține triplete – elementele nenule ale matricei A în ordine lexicografică, iar ultimele N2 linii vor conține triplete reprezentând elementele nenule ale matricei B, tot în ordine lexicografică .

Date de ieșire

Fișierul de ieșire matrice_rara.out va conține pe prima linie numărul de elemente diferite de 0 din matricea sumă C şi apoi matricea în sine sub forma tripletelor în ordine lexicografică, câte unul pe o linie .

Restricții și precizări

• 1 ≤ n , m ≤ 1.000.000
• 1 ≤ N1 , N2 ≤ 300.000
• -1.000.000.000 ≤ A[i][j], B[i][j] ≤ 1.000.000.000

Exemplu:

matrice_rara.in

5 6 3 3
1 1 2
3 4 3
4 6 1
1 2 3
3 4 -2
4 6 2

matrice_rara.out

4
1 1 2
1 2 3
3 4 1
4 6 3