Từ một mảng ~a_1, a_2, \dots, a_n~, Phong xây dựng ra đồ thị vô hướng đầy đủ ~G~ với ~n~ đỉnh được đánh số từ ~1~ đến ~n~, trong đó giữa hai đỉnh ~i~ và ~j~ (~i < j~) có một cạnh vô hướng kết nối chúng với trọng số là ~LCM(A_i, A_{i+1}, \dots, A_j)~. Nhắc lại, ~LCM(A_i, A_{i+1}, \dots, A_j)~ là số nguyên dương nhỏ nhất chia hết cho ~A_i, A_{i+1}, \dots, A_j~.

Phong đánh dấu ~k~ đỉnh khác nhau ~p_1, p_2, \dots, p_k~ trên đồ thị ~G~ làm các đỉnh đặc biệt. Anh muốn chọn một số cạnh trong ~G~ sao cho mỗi cặp đỉnh đặc biệt đều được kết nối với nhau. Hai đỉnh ~u~ và ~v~ được xem là kết nối với nhau nếu tồn tại một đường đi giữa hai đỉnh đó, sao cho với mỗi cặp đỉnh liên tiếp được kết nối trực tiếp với nhau bằng một cạnh đã chọn. Vì có nhiều cách chọn, Phong muốn tổng trọng số của các cạnh đã chọn là nhỏ nhất.

Yêu cầu: Hãy giúp Phong tìm ra tổng trọng số nhỏ nhất đó!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~ (~1 \le k \le n \le 3 \times 10^5~) lần lượt là số đỉnh của đồ thị ~G~ và số đỉnh đặc biệt.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 3 \times 10^5~) mô tả mảng ~a~.
• Dòng cuối cùng chứa ~k~ số nguyên dương phân biệt ~p_1, p_2, \dots, p_k~ (~1 \le p_i \le n~) mô tả dãy ~p~ — các đỉnh đặc biệt được chọn.

Output

• Dòng đầu tiên chứa một số nguyên duy nhất ~t~ (~0 \le t \le 10^{18}~) là tổng trọng số nhỏ nhất trong phương án tối ưu.
• Dòng thứ hai chứa một số nguyên ~m~ (~0 \le m \le 10^6~) mô tả số cạnh được chọn trong phương án tối ưu.
• ~m~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le n, u \ne v~) mô tả một cạnh được chọn.

Sample Input 1

3 2
1 2 3
1 3

Sample Output 1

6
1
3 1

Sample Input 2

8 4
6 3 2 3 1 10 3 15
6 8 2 7

Sample Output 2

61
4
2 5
7 8
5 6
5 8