Sengoku still remembers the mysterious "colourful meteoroids" she discovered with Lala-chan when they were little. In particular, one of the nights impressed her deeply, giving her the illusion that all her fancies would be realized.
On that night, Sengoku constructed a permutation p1, p2, ..., pn of integers from 1 to n inclusive, with each integer representing a colour, wishing for the colours to see in the coming meteor outburst. Two incredible outbursts then arrived, each with n meteorids, colours of which being integer sequences a1, a2, ..., an and b1, b2, ..., bn respectively. Meteoroids' colours were also between 1 and n inclusive, and the two sequences were not identical, that is, at least one i (1 ≤ i ≤ n) exists, such that ai ≠ bi holds.
Well, she almost had it all — each of the sequences a and b matched exactly n - 1 elements in Sengoku's permutation. In other words, there is exactly one i (1 ≤ i ≤ n) such that ai ≠ pi, and exactly one j (1 ≤ j ≤ n) such that bj ≠ pj.
For now, Sengoku is able to recover the actual colour sequences a and b through astronomical records, but her wishes have been long forgotten. You are to reconstruct any possible permutation Sengoku could have had on that night.
The first line of input contains a positive integer n (2 ≤ n ≤ 1 000) — the length of Sengoku's permutation, being the length of both meteor outbursts at the same time.
The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ n) — the sequence of colours in the first meteor outburst.
The third line contains n space-separated integers b1, b2, ..., bn (1 ≤ bi ≤ n) — the sequence of colours in the second meteor outburst. At least one i (1 ≤ i ≤ n) exists, such that ai ≠ bi holds.
Output n space-separated integers p1, p2, ..., pn, denoting a possible permutation Sengoku could have had. If there are more than one possible answer, output any one of them.
Input guarantees that such permutation exists.
5
1 2 3 4 3
1 2 5 4 5
1 2 5 4 3
5
4 4 2 3 1
5 4 5 3 1
5 4 2 3 1
4
1 1 3 4
1 4 3 4
1 2 3 4
In the first sample, both 1, 2, 5, 4, 3 and 1, 2, 3, 4, 5 are acceptable outputs.
In the second sample, 5, 4, 2, 3, 1 is the only permutation to satisfy the constraints.
/*---------------------------------------------- File: F:ACM源代码code forces418B.cpp Date: 2017/6/8 17:17:55 Author: LyuCheng ----------------------------------------------*/ /* 题意：给你序列a,b，让你构造一个1到n的全排列序列p，使得恰好有一个i使得ai!=pi,恰好有一个j使得bj!==pj 给出的样例保证有解 思路：考虑下来，a,b不相等的位置最多有两处，并且a,b序列中出现过的数一定是1-n中的n-1个 当有一处不同的时候： 直接将a中两个重复数字的其中一个数字换成没有出现过的那个数字，然后输出 当有两处不同的时候： 这种情况有很多种，但是简单粗暴的办法就是，先求出，在a,b序列中分别没出现过的数，有两个，然后 a[i]==b[i]的地方，p[i]=a[i],不相等的地方，先假定p[a,b不相等位置1]=tmp1,p[a,b不相等位置2]=tmp2, 然后加一个判断是否满足，输出的条件：恰好有一个i使得ai!=pi,恰好有一个j使得bj!==pj,如果不满足，就挑换位置 */ #include <bits/stdc++.h> #define MAXN 1005 #define LL long long using namespace std; int n; int a[MAXN]; int visa[MAXN]; int b[MAXN]; int visb[MAXN]; int c[MAXN]; int main(int argc, char *argv[]) { // freopen("in.txt","r",stdin); scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); visa[a[i]]=true; } for(int i=0;i<n;i++){ scanf("%d",&b[i]); visb[b[i]]=true; } vector<int>v; for(int i=0;i<n;i++){ if(a[i]==b[i]){ c[i]=a[i]; }else{ c[i]=0; v.push_back(i); } } if(v.size()==1){//只有一个的时候 for(int i=1;i<=n;i++){ if(visa[i]==false&&visb[i]==false){ c[v[0]]=i; break; } } }else{//有两个位置不同的时候 int tmp1,tmp2; for(int i=1;i<=n;i++){ if(visa[i]==false) tmp1=i; if(visb[i]==false) tmp2=i; } c[v[0]]=tmp1; c[v[1]]=tmp2; int cur=0; for(int i=0;i<n;i++){ if(a[i]!=c[i]){ cur++; } } for(int i=0;i<n;i++){ if(b[i]!=c[i]){ cur++; } } if(cur>2){ swap(c[v[0]],c[v[1]]); } } for(int i=0;i<n;i++){ printf(i==0?"%d":" %d",c[i]); } printf(" "); return 0; }