Nodea Eugen (eugen_nodea) Tanărul Pagnad proaspăt ajuns la facultate, vrea să prindă și el ceva. Fiind nemulțumit de celebra aplicație Tinder acesta dorește să-și creeze propria lui aplicație. Aplicația se folosește de datele strânse de pe diferite rețele de socializare ale utilizatorului și le codează într-o matrice. Stați calmi, nu trebuie sa creați voi matricea, dar pentru a-și studia compatibilitatea cu o persoana Pagnad se folosește de următoarele noțiuni.
Acesta definește o structură de dimensiune k o submatrice pătratică de latura k. Compatibilitatea se stabilește în funcție de câte perechi de două structuri, nu neapărat de aceleași dimensiuni, dar de sumă egală se găsesc în două matrici (prima structură trebuie să aparțină primei matrici, a doua celei de-a doua matrici).
Definim o structură prin coordonatele colțului stânga sus (x,y) și dimensiunea laturii acesteia k. Două perechi x1, y1, k1 și x2, y2, k2 sunt diferite daca: x1≠x2 sau k1≠k2 sau daca x1=x2 si k1=k2 si y1≠y2 sau x1=x2, y1=y2 si k1≠k2 (acestea fac referință pentru submatrice din aceeași matrice).
Cerința
Se cere să se afle compatibilitatea între cele două matrice.
Date de intrare
Fișierul de intrare match.in conține pe prima linie numerele n1 si m1. Pe a doua linie se vor găsi n1 numere. Pe următoarea linie n2 și m2, iar pe linia a patra cele n2 numere.
Unde m1 și m2 reprezintă numărul de coloane, iar n1 și n2 reprezintă dimensiunea totala a matricei.
Date de ieșire
Fișierul de ieșire match.out va conține pe prima linie un singur număr, respectiv compatibilitatea dintre cele două matrice.
Restricții și precizări
n1,n2 ≤ 31.000- numerele din matrice
<109 - se garantează că suma acestora este
<1018 m1≤n1;m2≤n2;(n1,m1)≠1;(n1,m2)≠1, unde(a,b)=cmmdc(a,b);
Exemplu:
match.in
9 3 1 2 3 4 5 6 7 8 9 9 3 1 2 3 4 5 6 7 8 9
match.out
14
Explicație
Matricile sunt identice, deci se consideră toate submatricele primei matrice.