#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long OO = 1LL << 62;
const int mod = 1e9 + 7;
int qpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = 1LL * ans * x % mod;
    x = 1LL * x * x % mod;
    y >>= 1;
  }
  return ans;
}
int gi() {
  int w = 0;
  bool q = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') q = 0, c = getchar();
  while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar();
  return q ? w : -w;
}
namespace io {
const int L = (1 << 21) + 1;
char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, st[55];
int f, tp;
inline char getc() {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <class I>
inline bool gi(I &x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == -1)
      return false;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
  return true;
}
template <class I>
inline void print(I x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) st[++tp] = x % 10 + '0', x /= 10;
  while (tp) putc(st[tp--]);
}
inline bool gs(char *s, int &l) {
  for (c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == -1) return false;
  for (l = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    s[l++] = c;
  s[l] = 0;
  return true;
}
inline void printld(double x, int digit) {
  if (x < 0) putc('-'), x = -x;
  x += 0.5 * pow(0.1, digit);
  print((long long)x), putc('.');
  for (x -= (long long)x; digit; --digit)
    x = x * 10, putc((int)x + '0'), x -= (int)x;
}
inline void ps(const char *s) {
  for (int i = 0, n = strlen(s); i < n; i++) putc(s[i]);
}
struct IOFLUSHER {
  ~IOFLUSHER() { flush(); }
} _ioflusher_;
};  // namespace io
using io::getc;
using io::gi;
using io::gs;
using io::print;
using io::printld;
using io::ps;
using io::putc;
const int N = 21;
const long long odd = 5864062014805;
const long long even = odd << 1;
unsigned int ax[1 << N | 2], ay[1 << N | 2], bx[1 << N | 2], by[1 << N | 2],
    cx[1 << N | 2], cy[1 << N | 2];
int siz[1 << N | 2];
char str[1 << N | 2];
void add(unsigned int &ax, unsigned int &ay, unsigned int bx, unsigned int by) {
  ay ^= by ^ (ax & bx);
  ax ^= bx;
}
void dec(unsigned int &ax, unsigned int &ay, unsigned int &bx,
         unsigned int &by) {
  ay ^= by ^ (~ax & bx);
  ax ^= bx;
}
int main() {
  int n, i, s;
  gi(n);
  gs(str, s);
  for (s = 0; s < 1 << n; s++) {
    siz[s] = siz[s >> 1] + (s & 1);
    ax[s] = ((str[s] - '0') & 1) << siz[s];
    ay[s] = ((str[s] - '0') >> 1 & 1) << siz[s];
  }
  gs(str, s);
  for (s = 0; s < 1 << n; s++) {
    bx[s] = ((str[s] - '0') & 1) << siz[s];
    by[s] = ((str[s] - '0') >> 1 & 1) << siz[s];
  }
  for (i = 0; i < n; i++)
    for (s = 0; s < 1 << n; s++)
      if (!(s >> i & 1)) {
        add(ax[s | 1 << i], ay[s | 1 << i], ax[s], ay[s]);
        add(bx[s | 1 << i], by[s | 1 << i], bx[s], by[s]);
      }
  for (s = 0; s < 1 << n; s++) {
    for (i = 0; i <= n; i++) {
      if (ax[s] >> i & 1) add(cx[s], cy[s], bx[s] << i, by[s] << i);
      if (ay[s] >> i & 1) cy[s] ^= bx[s] << i;
    }
  }
  for (i = 0; i < n; i++)
    for (s = 0; s < 1 << n; s++)
      if (!(s >> i & 1)) dec(cx[s | 1 << i], cy[s | 1 << i], cx[s], cy[s]);
  for (s = 0; s < 1 << n; s++)
    print((cx[s] >> siz[s] & 1) | (cy[s] >> siz[s] & 1) << 1);
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Little C loves number «3» very much. He loves all things about it.

Now he is interested in the following problem:

There are two arrays of 2^n intergers a_0,a_1,...,a_{2^n-1} and b_0,b_1,...,b_{2^n-1}.

The task is for each i (0 ≤ i ≤ 2^n-1), to calculate c_i=∑ a_j ⋅ b_k (j|k=i and j\&k=0, where "|" denotes [bitwise or operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR) and "\&" denotes [bitwise and operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND)).

It's amazing that it can be proved that there are exactly 3^n triples (i,j,k), such that j|k=i, j\&k=0 and 0 ≤ i,j,k ≤ 2^n-1. So Little C wants to solve this excellent problem (because it's well related to 3) excellently.

Help him calculate all c_i. Little C loves 3 very much, so he only want to know each c_i \& 3.

Input

The first line contains one integer n (0 ≤ n ≤ 21).

The second line contains 2^n integers in [0,3] without spaces — the i-th of them is a_{i-1}.

The third line contains 2^n integers in [0,3] without spaces — the i-th of them is b_{i-1}.

Output

Print one line contains 2^n integers in [0,3] without spaces — the i-th of them is c_{i-1}\&3. (It's obvious that c_{i}\&3 is in [0,3]).

Examples

Input

1
11
11


Output

12

Input

2
0123
3210


Output

0322

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long OO = 1LL << 62;
const int mod = 1e9 + 7;
int qpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = 1LL * ans * x % mod;
    x = 1LL * x * x % mod;
    y >>= 1;
  }
  return ans;
}
int gi() {
  int w = 0;
  bool q = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') q = 0, c = getchar();
  while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar();
  return q ? w : -w;
}
namespace io {
const int L = (1 << 21) + 1;
char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, st[55];
int f, tp;
inline char getc() {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <class I>
inline bool gi(I &x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == -1)
      return false;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
  return true;
}
template <class I>
inline void print(I x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) st[++tp] = x % 10 + '0', x /= 10;
  while (tp) putc(st[tp--]);
}
inline bool gs(char *s, int &l) {
  for (c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == -1) return false;
  for (l = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    s[l++] = c;
  s[l] = 0;
  return true;
}
inline void printld(double x, int digit) {
  if (x < 0) putc('-'), x = -x;
  x += 0.5 * pow(0.1, digit);
  print((long long)x), putc('.');
  for (x -= (long long)x; digit; --digit)
    x = x * 10, putc((int)x + '0'), x -= (int)x;
}
inline void ps(const char *s) {
  for (int i = 0, n = strlen(s); i < n; i++) putc(s[i]);
}
struct IOFLUSHER {
  ~IOFLUSHER() { flush(); }
} _ioflusher_;
};  // namespace io
using io::getc;
using io::gi;
using io::gs;
using io::print;
using io::printld;
using io::ps;
using io::putc;
const int N = 21;
const long long odd = 5864062014805;
const long long even = odd << 1;
unsigned int ax[1 << N | 2], ay[1 << N | 2], bx[1 << N | 2], by[1 << N | 2],
    cx[1 << N | 2], cy[1 << N | 2];
int siz[1 << N | 2];
char str[1 << N | 2];
void add(unsigned int &ax, unsigned int &ay, unsigned int bx, unsigned int by) {
  ay ^= by ^ (ax & bx);
  ax ^= bx;
}
void dec(unsigned int &ax, unsigned int &ay, unsigned int &bx,
         unsigned int &by) {
  ay ^= by ^ (~ax & bx);
  ax ^= bx;
}
int main() {
  int n, i, s;
  gi(n);
  gs(str, s);
  for (s = 0; s < 1 << n; s++) {
    siz[s] = siz[s >> 1] + (s & 1);
    ax[s] = ((str[s] - '0') & 1) << siz[s];
    ay[s] = ((str[s] - '0') >> 1 & 1) << siz[s];
  }
  gs(str, s);
  for (s = 0; s < 1 << n; s++) {
    bx[s] = ((str[s] - '0') & 1) << siz[s];
    by[s] = ((str[s] - '0') >> 1 & 1) << siz[s];
  }
  for (i = 0; i < n; i++)
    for (s = 0; s < 1 << n; s++)
      if (!(s >> i & 1)) {
        add(ax[s | 1 << i], ay[s | 1 << i], ax[s], ay[s]);
        add(bx[s | 1 << i], by[s | 1 << i], bx[s], by[s]);
      }
  for (s = 0; s < 1 << n; s++) {
    for (i = 0; i <= n; i++) {
      if (ax[s] >> i & 1) add(cx[s], cy[s], bx[s] << i, by[s] << i);
      if (ay[s] >> i & 1) cy[s] ^= bx[s] << i;
    }
  }
  for (i = 0; i < n; i++)
    for (s = 0; s < 1 << n; s++)
      if (!(s >> i & 1)) dec(cx[s | 1 << i], cy[s | 1 << i], cx[s], cy[s]);
  for (s = 0; s < 1 << n; s++)
    print((cx[s] >> siz[s] & 1) | (cy[s] >> siz[s] & 1) << 1);
  return 0;
}

```