Trong cuộc chiến của BanQ và Lolicodedao, hiện BanQ đang bị thua thiệt về sức mạnh khá nhiều nên BanQ đành sử dụng tuyệt chiêu cuối đó là kết hợp sức mạnh của các kĩ năng.

BanQ có 2 loại kĩ năng gọi tắt là ~A~ và ~B~, với các bộ chỉ số sức mạnh ~A_1, A_2, ..., A_n~ và ~B_1, B_2, ..., B_n~. Sức mạnh của BanQ sau khi hợp nhất sẽ là chỉ số ~K_{max}~ được tính như sau:

1. Xét tất cả các số nguyên dương ~2 \le M~. Với mỗi ~M~ ta tính ~K_M~, tương đương với đoạn ~[l, r] (1 \le l \le r \le n)~ dài nhất thỏa mãn:
   • ~A_l~ mod ~M~ == ~B_l~ mod ~M~
   • ~A_{l + 1}~ mod ~M~ == ~B_{l + 1}~ mod ~M~
   • ...
   • ~A_r~ mod ~M~ == ~B_r~ mod ~M~
2. Từ đó, ta tính được ~K_{max}~ chính là giá trị ~K_M~ lớn nhất tìm được

Cho bộ chỉ số sức mạnh ~A~ và ~B~. Hãy tính sức mạnh ~K_{max}~ của BanQ sau khi hợp nhất, bạn cũng phải in ra ~M~ lớn nhất tương ứng với ~K_{max}~ tìm được.

Nếu không tính được ~K_{max}~ nào chứng tỏ bộ kĩ năng không thể hợp nhất được với nhau: in ra -1.

Nếu ~M~ có thể lên tới vô hạn chứng tỏ bộ kĩ năng vô cùng thích hợp để hợp nhất, ta in ra 0 cho giá trị của ~M~.

Input

Dòng đầu tiên chứa N ~1 \le N \le 10^6~

Dòng thứ hai chứa ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^9)~, là bộ chỉ số sức mạnh của ~A~

Dòng thứ ba chứa ~B_1, B_2, ..., B_n~ ~(1 \le B_i \le 10^9)~, là bộ chỉ số sức mạnh của ~B~

Output

In ra -1 nếu không tìm được M nào thỏa mãn.

Ngược lại in ra hai số ~K_{max}~ và ~M~ theo thứ tự trên cùng một dòng và cách nhau bởi một dấu cách.

Nếu M tiến đến vô cùng thì in ra 0 cho giá trị của ~M~.

Input Sample 1

8
8 14 5 17 23 6 10 13
6 10 11 8 26 18 18 9

Output Sample 1

4 3

Input Sample 2

3
1 3 5
2 4 6

Output Sample 2

-1

Subtask

• Subtask 1 (30%): ~n \le 10 ^ 3~
• Subtask 2 (30%): ~n \le 10 ^ 5~
• Subtask 3 (40%): không có ràng buộc gì thêm