#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1.0)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn = 3e5+;

const int maxm = 1e5+;

const int mod = 1e9+;

ll qpow(ll a,ll b){

    ll res=;

    while(b){

        if(b&) res=res*a%mod;

        b>>=;

        a=a*a%mod;

    }

    return res;

}

ll inv = ;

void IFWT(int a[],int n){

    for(int d=;d<n;d<<=)

        for(int m=d<<,i=;i<n;i+=m)

            for(int j=;j<d;j++){

                int x = a[i+j],y=a[i+j+d];

                a[i+j]=(x+y)%mod*inv%mod;

                a[i+j+d]=(x-y+mod)%mod*inv%mod;

            }

}

void FWT(int a[],int n){

    for(int d=;d<n;d<<=)

        for(int m=d<<,i=;i<n;i+=m)

            for(int j=;j<d;j++){

                int x = a[i+j],y=a[i+j+d];

                a[i+j]=(x+y)%mod;

                a[i+j+d]=(x-y+mod)%mod;

            }

}

int a[maxn],b[maxn];

int main(){

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#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]);

    FWT(a,n);

    IFWT(b,n);

    for(int i=;i<n;i++) a[i]=b[i]*qpow(a[i],mod-)%mod;

    FWT(a,n);

    for(int i=;i<n;i++) cout<<a[i]<<endl;

    return ;

}