Fie X o matrice cu M coloane (numerotate de la 1 la M) şi N linii (numerotate de la 1 la N) cu componente din mulţimea {0, 1}. Pe fiecare linie a matricei se află o singură secvenţă (eventual vidă) formată din elemente egale cu 1, secvenţă identificată prin poziţia de început (indicele coloanei pe care se află primul 1 din secvenţă) şi lungimea ei. Restul elementelor de pe linie sunt egale cu 0.
Cerinţă
Să se determine numărul de dreptunghiuri cu dimensiunile A şi B, formate numai din 1 care se află în matricea X. Dreptunghiurile numărate au fie A linii şi B coloane, fie A coloane şi B linii.
Date de intrare
Fişierul de intrare drept1.in conţine pe prima linie cele 4 numere naturale separate prin câte un spaţiu cu semnificaţia din enunţ, în ordinea M N A B. Pe fiecare dintre următoarele N linii se află câte două numere naturale separate prin spaţiu, descriind matricea X. Mai exact linia i a fişierului se află poziţia de început şi lungimea secvenţei de elemente egale cu 1 de pe linia i-1 a matricei X.
Date de ieşire
Fişierul de ieşire drept1.out va conţine o singură linie pe care veţi scrie numărul de dreptunghiuri care respectă condiţiile din enunţ.
Restricţii
1 ≤ N, A, B ≤ 2 000 099
1 ≤ M ≤ 5 000 099
0 ≤ Lungimea unei secvenţe formată din elemente egale cu 1 ≤ M
Exemple
drept1.in
drept1.out
Explicaţii
5 6 2 3
1 5
1 3
1 2
1 1
3 3
2 4
3
Cele 3 dreptunghiuri au colţurile stânga-sus/dreapta-jos: (1,1)/(3, 2)
(1,1)/(2,3)
(5,3)/(6,5)
