#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1<<21
using namespace std;
int m,n;
int a[22][N],b[22][N];
int c[22][N];
int mod=1000000009;
inline void OR(int *f,int opt){
	for(int mid=1,R=2;R<=n;R<<=1,mid<<=1){
		for(int j=0;j<n;j+=R){
			for(int k=0;k<mid;k++){
				if(opt>0)f[j+k+mid]=f[j+k+mid]+f[j+k];
				else f[j+k+mid]=f[j+k+mid]-f[j+k];
				if(f[j+k+mid]<0)f[j+k+mid]+=mod;
				if(f[j+k+mid]>mod) f[j+k+mid]-=mod;
			}
		}
	}
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
int main(){
	m=read();n=(1<<m);
	for(int i=0;i<n;i++) a[__builtin_popcount(i)][i]=read();
	for(int i=0;i<n;i++) b[__builtin_popcount(i)][i]=read();
	for(int i=0;i<=m;i++){OR(a[i],1);OR(b[i],1);}
	for(int i=0;i<=m;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<n;k++){
				c[i][k]=(c[i][k]+1ll*a[j][k]*b[i-j][k]%mod);
				if(c[i][k]>mod) c[i][k]-=mod;
			}
		}
		OR(c[i],-1);
	}
	for(int i=0;i<n;i++) {write(c[__builtin_popcount(i)][i]);putchar(' ');}
}

rt，差0.17s，怎么都调不出来了