人群淹没，你我不及诉说。一声雁过，往事如昨。只望离别不多，再赏盛世烟火。

Initially Ildar has an empty array. He performs nn steps. On each step he takes a subset of integers already added to the array and appends the mex of this subset to the array.

The mex of an multiset of integers is the smallest non-negative integer not presented in the multiset. For example, the mex of the multiset [0,2,3][0,2,3] is 11, while the mex of the multiset [1,2,1][1,2,1] is 00.

More formally, on the step mm, when Ildar already has an array a1,a2,…,am−1a1,a2,…,am−1, he chooses some subset of indices 1≤i1<i2<…<ik<m1≤i1<i2<…<ik<m (possibly, empty), where 0≤k<m0≤k<m, and appends the mex(ai1,ai2,…aik)mex(ai1,ai2,…aik) to the end of the array.

After performing all the steps Ildar thinks that he might have made a mistake somewhere. He asks you to determine for a given array a1,a2,…,ana1,a2,…,an the minimum step tt such that he has definitely made a mistake on at least one of the steps 1,2,…,t1,2,…,t, or determine that he could have obtained this array without mistakes.

Input

The first line contains a single integer nn (1≤n≤1000001≤n≤100000) — the number of steps Ildar made.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109) — the array Ildar obtained.

Output

If Ildar could have chosen the subsets on each step in such a way that the resulting array is a1,a2,…,ana1,a2,…,an, print −1−1.

Otherwise print a single integer tt — the smallest index of a step such that a mistake was made on at least one step among steps 1,2,…,t1,2,…,t.

Examples

input

Copy

4
0 1 2 1

output

Copy

-1

input

Copy

3
1 0 1

output

Copy

1

input

Copy

4
0 1 2 239

output

Copy

4

Note

In the first example it is possible that Ildar made no mistakes. Here is the process he could have followed.

• 11-st step. The initial array is empty. He can choose an empty subset and obtain 00, because the mex of an empty set is 00. Appending this value to the end he gets the array [0][0].
• 22-nd step. The current array is [0][0]. He can choose a subset [0][0] and obtain an integer 11, because mex(0)=1mex(0)=1. Appending this value to the end he gets the array [0,1][0,1].
• 33-rd step. The current array is [0,1][0,1]. He can choose a subset [0,1][0,1] and obtain an integer 22, because mex(0,1)=2mex(0,1)=2. Appending this value to the end he gets the array [0,1,2][0,1,2].
• 44-th step. The current array is [0,1,2][0,1,2]. He can choose a subset [0][0] and obtain an integer 11, because mex(0)=1mex(0)=1. Appending this value to the end he gets the array [0,1,2,1][0,1,2,1].

Thus, he can get the array without mistakes, so the answer is −1−1.

In the second example he has definitely made a mistake on the very first step, because he could not have obtained anything different from 00.

In the third example he could have obtained [0,1,2][0,1,2] without mistakes, but 239239 is definitely wrong.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int s[100010];
int N,X,mx=-1;
int main()
{
    scanf("%d",&N);
    for(int i=1; i<=N; i++)
    {
        scanf("%d",&X);
        if(X>mx+1)
        {
            printf("%d\n",i);
            return 0;
        }
        mx=max(mx,X);
    }
    printf("-1\n");
    return 0;
}

At a break Vanya came to the class and saw an array of nn kk-bit integers a1,a2,…,ana1,a2,…,an on the board. An integer xx is called a kk-bit integer if 0≤x≤2k−10≤x≤2k−1.

Of course, Vanya was not able to resist and started changing the numbers written on the board. To ensure that no one will note anything, Vanya allowed himself to make only one type of changes: choose an index of the array ii (1≤i≤n1≤i≤n) and replace the number aiai with the number ai¯¯¯¯ai¯. We define x¯¯¯x¯ for a kk-bit integer xx as the kk-bit integer such that all its kk bits differ from the corresponding bits of xx.

Vanya does not like the number 00. Therefore, he likes such segments [l,r][l,r] (1≤l≤r≤n1≤l≤r≤n) such that al⊕al+1⊕…⊕ar≠0al⊕al+1⊕…⊕ar≠0, where ⊕⊕ denotes the bitwise XOR operation. Determine the maximum number of segments he likes Vanya can get applying zero or more operations described above.

Input

The first line of the input contains two integers nn and kk (1≤n≤2000001≤n≤200000, 1≤k≤301≤k≤30).

The next line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤2k−10≤ai≤2k−1), separated by spaces — the array of kk-bit integers.

Output

Print one integer — the maximum possible number of segments with XOR not equal to 00 that can be obtained by making several (possibly 00) operations described in the statement.

Examples

input

Copy

3 2
1 3 0

output

Copy

5

input

Copy

6 3
1 4 4 7 3 4

output

Copy

19

Note

In the first example if Vasya does not perform any operations, he gets an array that has 55 segments that Vanya likes. If he performs the operation with i=2i=2, he gets an array [1,0,0][1,0,0], because 3¯¯¯=03¯=0 when k=2k=2. This array has 33 segments that Vanya likes. Also, to get an array with 55 segments that Vanya likes, he can perform two operations with i=3i=3 and with i=2i=2. He then gets an array [1,0,3][1,0,3]. It can be proven that he can't obtain 66 or more segments that he likes.

In the second example, to get 1919 segments that Vanya likes, he can perform 44 operations with i=3i=3, i=4i=4, i=5i=5, i=6i=6 and get an array [1,4,3,0,4,3][1,4,3,0,4,3].

给出n个数字，他们可以被替换为自身按位取反的数，给出区间[ l , r ]询问在这段区间内异或和不为零的区间的个数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll N,K,sum[200010],jg;
map<ll,ll>mp;
int main()
{
    ll x,d1,d2;
    scanf("%lld%lld",&N,&K);
    ll ls=(1<<K)-1;//2^k
    for(int i=1; i<=N; i++)
    {
        scanf("%lld",&sum[i]);
        sum[i]^=sum[i-1];
        mp[min(sum[i],sum[i]^ls)]++;
    }
    mp[0]++;
    jg=N*(N+1)/2;
    map<ll,ll>::iterator it;
    for(it=mp.begin(); it!=mp.end(); it++)
    {
        x=it->second;
        d1=x/2;
        d2=x-d1;
        jg-=d1*(d1-1)/2;
        jg-=d2*(d2-1)/2;
    }
    printf("%lld\n",jg);
    return 0;
}

There are nn children numbered from 11 to nn in a kindergarten. Kindergarten teacher gave aiai (1≤ai≤n1≤ai≤n) candies to the ii-th child. Children were seated in a row in order from 11 to nn from left to right and started eating candies.

While the ii-th child was eating candies, he calculated two numbers lili and riri — the number of children seating to the left of him that got more candies than he and the number of children seating to the right of him that got more candies than he, respectively.

Formally, lili is the number of indices jj (1≤j<i1≤j<i), such that ai<ajai<aj and riri is the number of indices jj (i<j≤ni<j≤n), such that ai<ajai<aj.

Each child told to the kindergarten teacher the numbers lili and riri that he calculated. Unfortunately, she forgot how many candies she has given to each child. So, she asks you for help: given the arrays ll and rr determine whether she could have given the candies to the children such that all children correctly calculated their values lili and riri, or some of them have definitely made a mistake. If it was possible, find any way how she could have done it.

Input

On the first line there is a single integer nn (1≤n≤10001≤n≤1000) — the number of children in the kindergarten.

On the next line there are nn integers l1,l2,…,lnl1,l2,…,ln (0≤li≤n0≤li≤n), separated by spaces.

On the next line, there are nn integer numbers r1,r2,…,rnr1,r2,…,rn (0≤ri≤n0≤ri≤n), separated by spaces.

Output

If there is no way to distribute the candies to the children so that all of them calculated their numbers correctly, print «NO» (without quotes).

Otherwise, print «YES» (without quotes) on the first line. On the next line, print nn integers a1,a2,…,ana1,a2,…,an, separated by spaces — the numbers of candies the children 1,2,…,n1,2,…,n received, respectively. Note that some of these numbers can be equal, but all numbers should satisfy the condition 1≤ai≤n1≤ai≤n. The number of children seating to the left of the ii-th child that got more candies than he should be equal to lili and the number of children seating to the right of the ii-th child that got more candies than he should be equal to riri. If there is more than one solution, find any of them.

Examples

input

Copy

5
0 0 1 1 2
2 0 1 0 0

output

Copy

YES
1 3 1 2 1

input

Copy

4
0 0 2 0
1 1 1 1

output

Copy

NO

input

Copy

3
0 0 0
0 0 0

output

Copy

YES
1 1 1

Note

In the first example, if the teacher distributed 11, 33, 11, 22, 11 candies to 11-st, 22-nd, 33-rd, 44-th, 55-th child, respectively, then all the values calculated by the children are correct. For example, the 55-th child was given 11 candy, to the left of him 22 children were given 11 candy, 11child was given 22 candies and 11 child — 33 candies, so there are 22 children to the left of him that were given more candies than him.

In the second example it is impossible to distribute the candies, because the 44-th child made a mistake in calculating the value of r4r4, because there are no children to the right of him, so r4r4 should be equal to 00.

In the last example all children may have got the same number of candies, that's why all the numbers are 00. Note that each child should receive at least one candy.

n个小朋友排排坐吃糖，小朋友从左到右编号1到n。每个小朋友手上有一定数量的糖。对于第i个小朋友来说，编号比他小的小朋友中有li个小朋友拥有的糖比他多，编号比他大的小朋友中有ri个小朋友拥有的糖比他多。已知每个小朋友手上至少有1颗糖、最多有n颗糖，求一种可能的每个小朋友手上的糖的数量的情形，输出YES和一种情形；如果不存在这样的可能，则输出NO。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int N,ri,li;
struct node
{
    int l;
    int r;
    int jg;
} p[1010];
int main()
{
    scanf("%d",&N);
    for(int i=1; i<=N; i++)
        scanf("%d",&p[i].l);
    for(int i=1; i<=N; i++)
        scanf("%d",&p[i].r);
    for(int i=1; i<=N; i++)
        p[i].jg=N-(p[i].l+p[i].r);
    for(int i=1; i<=N; i++)
    {
        li=0;
        for(int j=1; j<i; j++)
            if(p[j].jg>p[i].jg)
                li++;
        ri=0;
        for(int j=i+1; j<=N; j++)
            if(p[j].jg>p[i].jg)
                ri++;
        if(li!=p[i].l||ri!=p[i].r)
        {
            printf("NO\n");
            return 0;
        }
    }
        printf("YES\n");
        for(int i = 1; i <= N; i++)
            printf("%d ", p[i].jg);
    return 0;
}