Hội anh em là hội gồm nhóm trưởng NHPT(ác quỷ đia ngục, chúa tể tội đồ, trùm dính phốt) cùng với 4 quỷ dữ và 2 thiên thần đã trải qua nhiều sóng gió phủ đời trai. Tưởng như thiên thần TVT sẽ dễ dàng vào nhóm quỷ dữ khi đã vượt quả 3 cửa ải(DAB, NGGM, NTR) nhưng anh ấy bị người gác cổng cuối cùng MT đưa ra vấn đề nan giải không thể giải quyết được. Vì hội anh em hiện đang chiến đấu với drama nên TVT nhờ các bạn giúp đỡ.

Yêu cầu:

• Cho dãy nguyên \(a_1, a_2, ..., a_n\) và 2 số \(l, r\). Bạn được phép thực hiện thao tác sau trên dãy.
• Chọn 2 số \(a_i, a_j, 1 \leq i \leq j \leq n\) sao cho \(gcd(a_i, a_j)\) không có trong mảng và thêm \(gcd(a_i, a_j)\) vào cuối mảng(mảng sẽ thay đổi sau mỗi thao tác và các thao tác tiếp theo được thực hiện trên mảng mới).
• Số lần tối đa bạn có thể thực hiện thao tác trên dãy là bao nhiêu, và in ra số căp \((i, j)\) của mảng mới nhận \(x_i\) làm \(gcd\) \((x = [l, l + 1, ..., r])\).

Input

• Dòng đầu tiên cho 3 số nguyên \(n, l, r \leq 3 \cdot 10^6, l \leq r\).
• Dòng thứ hai cho \(n\) số nguyên \(a_1, a_2, ..., a_n (1 \leq a_i \leq 3 \cdot 10^6)\).

Output

• Dòng đầu tiên ghi số lần tối đa bạn có thể thực hiện thao tác trên dãy.
• Dòng thứ hai gồm \(r - l + 1\) số là số cặp nhận \(x_i\) làm \(gcd\) \((1 \leq i \leq r - l + 1)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n, l, r \leq 100\)
• Subtask \(2\) (\(50\%\) số điểm): \(n, l, r \leq 3 \cdot 10^6\)

Example

5 2 5
4 20 1 25 30

3
6 0 1 7