Se consideră o matrice binară B (cu valori 0 sau 1) cu N linii şi M coloane, liniile şi coloanele fiind numerotate de la 1 la N, respectiv de la 1 la M. Matricea B este generată după regula B[i][j] = R[i] xor C[j], unde R şi C sunt vectori binari de lungime N, respectiv M. Numim dreptunghi de colţuri (x1,y1) (x2,y2) cu x1 ≤ x2 şi y1 ≤ y2, mulţimea elementelor B[i][j] cu x1 ≤ i ≤ x2 și y1 ≤ j ≤ y2. Aria unui astfel de dreptunghi este (x2 - x1 + 1) * (y2 - y1 + 1).

Cerința

Determinaţi numărul maxim de elemente egale cu 0 într-un dreptunghi a cărui arie este exact A, precum şi numărul de dreptunghiuri pentru care se obţine acest număr maxim.

Date de intrare

Fișierul de intrare matrice.in conține pe prima linie pe prima linie numerele naturale N, M, A separate prin câte un spaţiu. A doua linie va conţine N valori 0 sau 1 separate prin câte un spaţiu, reprezentând elementele vectorului R, iar a treia linie va conţine M valori 0 sau 1 separate prin câte un spaţiu, reprezentând elementele vectorului C.

Date de ieșire

Fișierul de ieșire matrice.out va conține o singură linie pe care vor fi scrise două numere naturale separate printr-un singur spaţiu Zmax Nsol, reprezentând în ordine numărul maxim de elemente egale cu 0 într-un dreptunghi a cărui arie este exact A, precum şi numărul de dreptunghiuri pentru care se obţine acest număr maxim.

Restricții și precizări

• 1 ≤ N, M ≤ 30.000
• 1 ≤ A ≤ 5.000.000
• Pentru 40% din teste N, M ≤ 300
• Prin xor se înţelege operatorul sau exclusiv (^ în C++). Mai exact: x ^ y = 1 dacă și numai dacă un operand este 0, iar celălalt 1, deci 0 ^ 0 = 0, 1 ^ 1 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1.

Exemplu:

matrice.in

2 4 4
0 1
1 0 0 1

matrice.out

2 5

Explicație

Matricea B este:

1 0 0 1
0 1 1 0

Numărul maxim de valori 0 dintr-un dreptunghi de arie 4 este 2. Cele 5 dreptunghiuri de arie 4 cu număr maxim de 0 sunt:

• (1,1) (1,4)
• (2,1) (2,4)
• (1,1) (2,2)
• (1,2) (2,3)
• (1,3) (2,4)