Co-prime Array

Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

   

Description

You are given an array of n elements, you must make it a co-prime array in as few moves as possible.

In each move you can insert any positive integral number you want not greater than 10⁹ in any place in the array.

An array is co-prime if any two adjacent numbers of it are co-prime.

In the number theory, two integers a and b are said to be co-prime if the only positive integer that divides both of them is 1.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of elements in the given array.

The second line contains n integers a_i (1 ≤ a_i ≤ 10⁹) — the elements of the array a.

Output

Print integer k on the first line — the least number of elements needed to add to the array a to make it co-prime.

The second line should contain n + k integers a_j — the elements of the array a after adding k elements to it. Note that the new array should be co-prime, so any two adjacent values should be co-prime. Also the new array should be got from the original array a by addingk elements to it.

If there are multiple answers you can print any one of them.

Sample Input

Input

3 2 7 28

Output

1 2 7 9 28 题意：让加最少的数使成为互质集合:相邻两个数互质；。。。水，1与任何数互质

#include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF = 0x3f3f3f3f;#define mem(x,y) memset(x,y,sizeof(x))const int MAXN = 1010;int num[MAXN];int ans[MAXN << 1];int gcd(int a,int b){    return b == 0 ? a : gcd(b, a%b);}/*int find(int a, int b){    for(int i )}*/int main(){    int N;    while(~scanf("%d", &N)){        int tp = 0;        for(int i = 1; i <= N; i++){            scanf("%d", num + i);        }        ans[tp++] = num[1];        for(int i = 2; i <= N; i++){            if(gcd(num[i], num[i - 1]) != 1){                ans[tp++] = 1;                ans[tp++] = num[i];            }            else ans[tp++] = num[i];        }        printf("%d\n", tp - N);        for(int i = 0; i < tp; i++){            if(i)printf(" ");            printf("%d", ans[i]);        }        puts("");    }    return 0;}
             
            
           
          
         

Seating On Bus

Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

   

Description

Consider 2n rows of the seats in a bus. n rows of the seats on the left and n rows of the seats on the right. Each row can be filled by two people. So the total capacity of the bus is 4n.

Consider that m (m ≤ 4n) people occupy the seats in the bus. The passengers entering the bus are numbered from 1 to m (in the order of their entering the bus). The pattern of the seat occupation is as below:

1-st row left window seat, 1-st row right window seat, 2-nd row left window seat, 2-nd row right window seat, ... , n-th row left window seat, n-th row right window seat.

After occupying all the window seats (for m > 2n) the non-window seats are occupied:

1-st row left non-window seat, 1-st row right non-window seat, ... , n-th row left non-window seat, n-th row right non-window seat.

All the passengers go to a single final destination. In the final destination, the passengers get off in the given order.

1-st row left non-window seat, 1-st row left window seat, 1-st row right non-window seat, 1-st row right window seat, ... , n-th row left non-window seat, n-th row left window seat, n-th row right non-window seat, n-th row right window seat.

The seating for n = 9 and m = 36.

You are given the values n and m. Output m numbers from 1 to m, the order in which the passengers will get off the bus.

Input

The only line contains two integers, n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 4n) — the number of pairs of rows and the number of passengers.

Output

Print m distinct integers from 1 to m — the order in which the passengers will get off the bus.

Sample Input

Input

2 7

Output

5 1 6 2 7 3 4

Input

9 36

Output

19 1 20 2 21 3 22 4 23 5 24 6 25 7 26 8 27 9 28 10 29 11 30 12 31 13 32 14 33 15 34 16 35 17 36 18 题意：坐公交车。。。水； 代码：

#include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;const int INF = 0x3f3f3f3f;#define mem(x,y) memset(x,y,sizeof(x))const int MAXN = 110;int num[4][MAXN];int main(){    int n,m;    while(~scanf("%d%d",&n, &m)){        int tp = 0;        for(int i = 1; i <= n; i++){            num[0][i] = ++tp;            num[3][i] = ++tp;        }        for(int i = 1; i <= n; i++){            num[1][i] = ++tp;            num[2][i] = ++tp;        }        int x = 0;        for(int i = 1; i <= n; i++){            if(num[1][i] <= m){            if(x)printf(" ");            printf("%d",num[1][i]);            x++;            }            if(num[0][i] <= m){                if(x)printf(" ");            printf("%d",num[0][i]);            x++;            }            if(num[2][i] <= m){                if(x)printf(" ");            printf("%d",num[2][i]);            x++;            }            if(num[3][i] <= m){            if(x)printf(" ");            printf("%d",num[3][i]);            x++;                }                    }        puts("");    }    return 0;}