Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3887
LCGCDS

Time Limit: 10 Seconds      Memory Limit: 524288 KB

Given two sequences {A0, A1, ..., AN-1} and {B0, B1, ..., BM-1}. Defined a function called G(L, R, S) on sequence S, where G(L, R, S) = GCD(Si) (Li < R) that is the greatest common divisor of all the integers in the subsequence of S. The definition of the LCGCDS two integer sequences A and B is the maximum L that G(i, i + L, A) = G(j, j + L, B) for some (i, j) (0 ≤ i < N, 0 ≤ j < M).

You task is to calculate the length of LCGCDS and the number of LCGCDS of two given sequences A and B.

Note: Two LCGCDS are considered different if one of the two integer (i, j) is different.

Input

There are multiple test cases. Each case begin with a line contains two integers N and M (1 ≤ N, M ≤ 100000). The second line contains N integers, A0, A1, ..., AN-1 (1 ≤ Ai ≤ 109). The third line contains M integers, B0, B1, ..., BM-1 (1 ≤ Bi ≤ 109).

Output

One line for each case, you should output the length of LCGCDS and the number of LCGCDS, seprated by one space. If you can't find any LCGCDS, please just output "0 0" (without quotes).

Sample Input

5 3
1 1 1 1 1
1 1 1

Sample Output

3 3

Hint

The three LCGCDS are (0, 0, 3), (1, 0, 3), (2, 0, 3). The first number is i, the second number is j, and the third number is L.
Author: LIN, Xi
Source: ZOJ Monthly, July 2015
Submit    Status