For a set of positive integers S, let's define gcd(S) as the greatest integer which divides each element of S. If gcd(S)=1, the set S is called coprime. For example, the set {7,12,15} is coprime, but {6,12,15} is not coprime, since every element of this set is divisible by 3.
Your task is to find an integer sequence A0,A1,…,AN−1 such that:
for each valid i, 1≤Ai≤109
A0,A1,…,AN−1 are pairwise distinct
for each valid i, the set {Ai,A(i+1)%N} is not coprime (% denotes the modulo operator)
for each valid i, the set {Ai,A(i+1)%N,A(i+2)%N} is coprime
It is possible that there is no solution. If there are multiple solutions, you may find any one.
Example Input
2
3
4
Example Output
6 10 15
374 595 1365 858
Explanation
Example case 1: Let's check the answer: gcd(6,10)=2, gcd(10,15)=5, gcd(15,6)=3, gcd(6,10,15)=1. Every two cyclically consecutive numbers are not coprime, but every three cyclically consecutive numbers are coprime.
Example case 2:
gcd(374,595)=17, gcd(595,1365)=35, gcd(1365,868)=39, gcd(858,374)=22
gcd(374,595,1365)=1, gcd(595,1365,858)=1, gcd(1365,858,374)=1, gcd(858,374,595)=1
Problem link :
https://www.codechef.com/JAN19A/problems/EARTSEQ/