{"code":"pairgcd","name":"Hội những người anh em","description":"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 đỡ.\r\n\r\n**Yêu cầu:**\r\n- 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.\r\n - 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).\r\n- 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])$.\r\n\r\n

Input

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

Output

\r\n\r\n- 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.\r\n- 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)$.\r\n\r\n

Scoring

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5 2 5\r\n 4 20 1 25 30\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 3\r\n 6 0 1 7 \r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Chọn $i = 1, j = 5$ và thêm $gcd(a_1, a_5) = gcd(4,30) = 2$ vào dãy.\r\n\r\n Chọn $i = 2, j = 4$ và thêm $gcd(a_2, a_4) = gcd(20,25) = 5$ vào dãy.\r\n\r\n Chọn $i = 2, j = 5$ và thêm $gcd(a_2, a_5) = gcd(20,30) = 10$ vào dãy.\r\n\r\n Dãy sẽ trở thành $a = [4, 20, 1, 25, 30, 2, 5, 10]$ có $6$ cặp $gcd = 2$, $0$ cặp $gcd = 3 $, $1$ cặp $gcd = 4$ và $7$ cặp $gcd = 5$.","points":2000.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}