Cho một mảng $A$ có độ dài $n$, bạn cần tìm hai chỉ số $i, j$ ($1 \le i \lt j \le n$) sao cho $A_i$ và $A_j$ có ước chung lớn hơn $1$.

Nếu tồn tại nhiều đáp án, in ra phương án có $i$ nhỏ nhất; nếu vẫn còn nhiều đáp án, in ra phương án có $j$ nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên là một số nguyên $n$, cho biết độ dài mảng.

Dòng thứ hai gồm $n$ số nguyên $A_1, A_2, \ldots, A_n$.

Dữ liệu ra

In ra hai số nguyên $i$ và $j$, là cặp chỉ số tìm được. Nếu không tồn tại $i, j$ như vậy, in ra hai dòng: dòng thứ nhất in $-1$, dòng thứ hai không in gì.

Ví dụ

Input

5
2 4 6 9 10

Output

1 2

Ghi chú

Giải thích ví dụ

$A_1 = 2$ và $A_2 = 4$ có ước chung $2 > 1$. Đây là cặp có $i$ nhỏ nhất, và với $i = 1$ thì $j = 2$ là nhỏ nhất, nên đáp án là 1 2.

Phạm vi dữ liệu

• $2 \le n \le 10^5$
• $2 \le A_i \le 10^6$