/* version 2007.09.24, D. J. Bernstein; public domain */

dagbitn::dagbitn()
{
  for (int i = 0;i < N;++i) b[i] = 0;
}

dagbitn::dagbitn(int x)
{
  for (int i = 0;i < N;++i) b[i] = x >> i;
}

dagbitn& dagbitn::operator=(int x)
{
  for (int i = 0;i < N;++i) b[i] = x >> i;
  return *this;
}

dagbitn& dagbitn::operator=(const dagbitn& x)
{
  for (int i = 0;i < N;++i) b[i] = x.b[i];
  return *this;
}

void dagbitn::key(long long i,int x)
{
  for (int j = 0;j < N;++j) {
    b[j].key(i,x & 1); x >>= 1; ++i;
  }
}

void dagbitn::input(long long i,int x)
{
  for (int j = 0;j < N;++j) {
    b[j].input(i,x & 1); x >>= 1; ++i;
  }
}

void dagbitn::output(long long i)
{
  for (int j = 0;j < N;++j) {
    b[j].output(i); ++i; 
  }
}

dagbitn operator~(dagbitn x)
{
  dagbitn result;
  for (int i = 0;i < N;++i) result.b[i] = ~x.b[i];
  return result;
}

dagbitn operator&(dagbitn x,dagbitn y)
{
  dagbitn result;
  for (int i = 0;i < N;++i) result.b[i] = x.b[i] & y.b[i];
  return result;
}

dagbitn operator|(dagbitn x,dagbitn y)
{
  dagbitn result;
  for (int i = 0;i < N;++i) result.b[i] = x.b[i] | y.b[i];
  return result;
}

dagbitn operator^(dagbitn x,dagbitn y)
{
  dagbitn result;
  for (int i = 0;i < N;++i) result.b[i] = x.b[i] ^ y.b[i];
  return result;
}

dagbitn operator+(dagbitn x,dagbitn y)
{
  dagbitn result;
  dagbit c[N - 1];
  c[0] = x.b[0] & y.b[0];
  for (int i = 1;i < N - 1;++i) c[i] = majority(x.b[i],y.b[i],c[i - 1]);
  result.b[0] = x.b[0] ^ y.b[0];
  for (int i = 1;i < N;++i) result.b[i] = xorthree(x.b[i],y.b[i],c[i - 1]);
  return result;
}

dagbitn operator-(dagbitn x,dagbitn y)
{
  dagbitn result;
  dagbit c[N - 1];
  c[0] = y.b[0] & ~x.b[0];
  for (int i = 1;i < N - 1;++i) c[i] = belowsum(x.b[i],y.b[i],c[i - 1]);
  result.b[0] = x.b[0] ^ y.b[0];
  for (int i = 1;i < N;++i) result.b[i] = xorthree(x.b[i],y.b[i],c[i - 1]);
  return result;
}

dagbitn operator<<(dagbitn x,int n)
{
  dagbitn result;
  for (int i = 0;i < N;++i)
    if (i - n >= 0 && i - n < N) result.b[i] = x.b[i - n];
    else result.b[i] = 0;
  return result;
}

dagbitn operator>>(dagbitn x,int n)
{
  dagbitn result;
  for (int i = 0;i < N;++i)
    if (i + n >= 0 && i + n < N) result.b[i] = x.b[i + n];
    else result.b[i] = 0;
  return result;
}