When Masha came to math classes today, she saw two integer sequences of length n−1n−1 on the blackboard. Let's denote the elements of the first sequence as aiai (0≤ai≤30≤ai≤3), and the elements of the second sequence as bibi (0≤bi≤30≤bi≤3).

Masha became interested if or not there is an integer sequence of length nn, which elements we will denote as titi (0≤ti≤30≤ti≤3), so that for every ii (1≤i≤n−11≤i≤n−1) the following is true:

• ai=ti|ti+1ai=ti|ti+1 (where || denotes the bitwise OR operation) and
• bi=ti&ti+1bi=ti&ti+1 (where && denotes the bitwise AND operation).

The question appeared to be too difficult for Masha, so now she asked you to check whether such a sequence titi of length nn exists. If it exists, find such a sequence. If there are multiple such sequences, find any of them.

The first line contains a single integer nn (2≤n≤1052≤n≤105) — the length of the sequence titi.

The second line contains n−1n−1 integers a1,a2,…,an−1a1,a2,…,an−1 (0≤ai≤30≤ai≤3) — the first sequence on the blackboard.

The third line contains n−1n−1 integers b1,b2,…,bn−1b1,b2,…,bn−1 (0≤bi≤30≤bi≤3) — the second sequence on the blackboard.

In the first line print "YES" (without quotes), if there is a sequence titi that satisfies the conditions from the statements, and "NO" (without quotes), if there is no such sequence.

If there is such a sequence, on the second line print nn integers t1,t2,…,tnt1,t2,…,tn (0≤ti≤30≤ti≤3) — the sequence that satisfies the statements conditions.

If there are multiple answers, print any of them.

In the first example it's easy to see that the sequence from output satisfies the given conditions:

• t1|t2=(012)|(112)=(112)=3=a1t1|t2=(012)|(112)=(112)=3=a1 and t1&t2=(012)&(112)=(012)=1=b1t1&t2=(012)&(112)=(012)=1=b1;
• t2|t3=(112)|(102)=(112)=3=a2t2|t3=(112)|(102)=(112)=3=a2 and t2&t3=(112)&(102)=(102)=2=b2t2&t3=(112)&(102)=(102)=2=b2;
• t3|t4=(102)|(002)=(102)=2=a3t3|t4=(102)|(002)=(102)=2=a3 and t3&t4=(102)&(002)=(002)=0=b3t3&t4=(102)&(002)=(002)=0=b3.

In the second example there is no such sequence.

题意：求一个n长度的t数组，满足t[i]&t[i+1] == b[i]   同时 t[i]|t[i+1] == a[i]。 a,b数组长度为n-1

枚举法，想过枚举但是没有想到是这样做的。因为t数组中，最后一个是最特殊的，只与a和b数组中的一个元素相关（自己没有发现）。同时没有发现如果确定了一个点，那么下一个点的值是唯一确定的。这样想来，其实枚举第一个也是可行的了。

同时，需要记住，如果t[i]确定了，那么与不同的t[i+1]进行或，与运算一定会得到的是不同的结果。

和之前做过的一道Fliptile有些像。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <stack>

#define ll long long

//#define local

using namespace std;

const int MOD = 1e9+;

const int inf = 0x3f3f3f3f;

const double PI = acos(-1.0);

const int maxn = (1e5+);

const int maxedge = *;

int a[maxn], b[maxn];

int t[maxn];

int main() {

#ifdef local

    if(freopen("/Users/Andrew/Desktop/data.txt", "r", stdin) == NULL) printf("can't open this file!\n");

#endif

    int n;

    scanf("%d", &n);

    for (int i = ; i < n-; ++i) {

        scanf("%d", a+i);

    }

    for (int i = ;i < n-; ++i) {

        scanf("%d", b+i);

    }

    for (int i = ; i < ; ++i) {

        memset(t, -, sizeof(t));

        t[n-] = i;

        for (int j = n-; j >= ; --j) {

            for (int k = ; k < ; ++k) {

                if ((k|t[j+])==a[j] && (k&t[j+])==b[j]) {

                    t[j] = k;

                    break;

                }

            }

            if (t[j] == -) break;

        }

        if (t[] != -) break;

    }

    if (t[] == -) printf("NO\n");

    else {

        printf("YES\n");

        for (int i = ; i < n; ++i) {

            printf("%d", t[i]);

            if (i != n-) printf(" ");

        }

        printf("\n");

    }

#ifdef local

    fclose(stdin);

#endif

    return ;

}