Bag(){
  this.size = 0;
  this.impl = Monoid();
}

void BagInsert(Bag S, int item){
  int k = 0;
  pennant x = pennant(item);
  while(S.p[k] != NULL){
    x = pennantUnion((S.p[k],x);
    S.p[k++] = NULL;
  }
  S.p[k] = x;
}

Bag Bagplit(Bag S1){
  Bag S2;
  pennant y = S1.p[0];
  S1.p[0] = NULL;
  for (int i = 1; i < S1.size; i++){
    if (S1.p[i] != NULL){
      S2.p[i-1] = pennantSplit(S1.p[i]);
      S1.p[i-1] = S1.p[i];
      S1.p[i] = NULL;
    }
  }

  if (y != NULL){
    Bag Insert(S1, y);
  }
  return S2;
}


void Union(Bag S1, Bag S2){
    pennant y = NULL;
    for (int i = 0; i < MAXSIZE; i++){
      if(S1->p[i] == NULL && y == NULL && S2->p[i] == NULL){
    S1->p[i] = NULL;
    y = NULL;
      }

      else if(S1->p[i] != NULL && y == NULL && S2->p[i] == NULL){
    y = NULL;
      }

      else if(S1->p[i] == NULL && y != NULL && S2->p[i] == NULL){
    S1->p[i] = y;
    y = NULL;
      }

      else if(S1->p[i] == NULL && y == NULL && S2->p[i] != NULL){
    S1->p[i] = S2->p[i];
    y = NULL;
      }

      else if(S1->p[i] != NULL && y != NULL && S2->p[i] == NULL){
    S1->p[i] = NULL;
    y = pennantUnion(S1->p[i], y);
      }

      else if(S1->p[i] != NULL && y == NULL && S2->p[i] != NULL){
    S1->p[i] = NULL;
    y = pennantUnion(S1->p[i], S2->p[i]);
      }

      else if(S1->p[i] == NULL && y != NULL && S2->p[i] != NULL){
    S1->p[i] = NULL;
    y = pennantUnion(y, S2->p[i]);
      }

      else if(S1->p[i] != NULL && y != NULL && S2->p[i] != NULL){
    y = pennantUnion(y, S2->p[i]);
      }

}