import java.io.*;
import java.util.*;
 
public class SandBox
{
  public SandBox()
  {
    sand = new char[MAX];
    status = new int[MAX];
    statusReverse = new int[MAX];
    rangeBegin = MAX - 1;
    rangeEnd = 0;
    nWords = 0;
  }

  void addWord(String s, int loc)
  {
    if (loc < 0 || (loc + s.length() - 1) >= MAX) {
      System.out.println("PALINDROME TOO BIG\n");
      return;
    }
    // System.out.println("adding " + s + " at " + loc);

    nWords++;

    for (int i = 0; i < s.length(); i++) {
      int sandLoc = loc + i;
      if (sandLoc < rangeBegin || sandLoc > rangeEnd) {
	status[sandLoc] = TAKEN;
	statusReverse[sandLoc] = LOOSE;
	sand[sandLoc] = s.charAt(i);
      }
      else {
	if (sand[sandLoc] != s.charAt(i))
	  System.out.println("INTERNAL INCONSISTENCY spot1");
	if (status[sandLoc] != LOOSE)
	  System.out.println("INTERNAL INCONSISTENCY spot2");
	if (statusReverse[sandLoc] != TAKEN && 
	    statusReverse[sandLoc] != WORDSTART)
	  System.out.println("INTERNAL INCONSISTENCY spot3");
	status[sandLoc] = TAKEN;
      }
    }
    status[loc] = WORDSTART;

    if (rangeBegin > loc)
      rangeBegin = loc;
    if (rangeEnd < (loc + s.length() - 1))
      rangeEnd = (loc + s.length() - 1);
  }

  void addWordReverse(String s, int loc)
  {
    if (loc >= MAX || (loc - s.length() + 1) < 0) {
      System.out.println("PALINDROME TOO BIG\n");
      return;
    }
    // System.out.println("reverseadding " + s + " at " + loc);

    nWords++;

    for (int i = 0; i < s.length(); i++) {
      int sandLoc = loc - i;
      if (sandLoc < rangeBegin || sandLoc > rangeEnd) {
	statusReverse[sandLoc] = TAKEN;
	status[sandLoc] = LOOSE;
	sand[sandLoc] = s.charAt(i);
      }
      else {
	if (sand[sandLoc] != s.charAt(i))
	  System.out.println("INTERNAL INCONSISTENCY spot4 " + sand[sandLoc]
			     + " " + s.charAt(i) + " " + sandLoc + " " + i);
	if (statusReverse[sandLoc] != LOOSE)
	  System.out.println("INTERNAL INCONSISTENCY spot5");
	if (status[sandLoc] != TAKEN && status[sandLoc] != WORDSTART)
	  System.out.println("INTERNAL INCONSISTENCY spot6");
	statusReverse[sandLoc] = TAKEN;
      }
    }
    statusReverse[loc] = WORDSTART;

    if (rangeBegin > loc - s.length() + 1)
      rangeBegin = loc - s.length() + 1;
    if (rangeEnd < loc)
      rangeEnd = loc;
  }

  void print()
  {
    if (Complete()) {
      printComplete();
      if (CompleteReverse())    // if both, print both ways
	printCompleteReverse();
    }
    else if (CompleteReverse()) {
      printCompleteReverse();
    }
    else {  // not complete
      printIncomplete();
    }
  }

  void printIncomplete()
  {
    for (int i = rangeBegin; i <= rangeEnd; i++) {
      if (status[i] == LOOSE)
	System.out.print("[" + sand[i] + "] ");
      else if (status[i] == TAKEN)
	System.out.print(sand[i]);
      else if (status[i] == WORDSTART)
	System.out.print(" " + sand[i]);
      else
	System.out.println("\nINTERNAL INCONSISTENCY spot7");
    }

    System.out.print(" || ");

    for (int i = rangeEnd; i >= rangeBegin; i--) {
      if (statusReverse[i] == LOOSE)
	System.out.print("[" + sand[i] + "] ");
      else if (statusReverse[i] == TAKEN)
	System.out.print(sand[i]);
      else if (statusReverse[i] == WORDSTART)
	System.out.print(" " + sand[i]);
      else
	System.out.println("\nINTERNAL INCONSISTENCY spot8");
    }

    System.out.println("");
  }

  void printComplete()
  {
    for (int i = rangeBegin; i <= rangeEnd-1; i++) {
      if (status[i] == LOOSE)
	System.out.println("\nINTERNAL INCONSISTENCY spot12");
      else if (status[i] == TAKEN)
	System.out.print(sand[i]);
      else if (status[i] == WORDSTART)
	System.out.print(" " + sand[i]);
    }

    if (status[rangeEnd] == TAKEN)
      System.out.print(sand[rangeEnd]);
    else if (status[rangeEnd] == WORDSTART)
      System.out.print(" " + sand[rangeEnd]);

    if (statusReverse[rangeEnd] != LOOSE)
      System.out.print(" " + sand[rangeEnd]);

    if (status[rangeEnd] == LOOSE && statusReverse[rangeEnd] == LOOSE)
	System.out.println("\nINTERNAL INCONSISTENCY spot18");

    for (int i = rangeEnd-1; i >= rangeBegin; i--) {
      if (statusReverse[i] == LOOSE)
	System.out.println("\nINTERNAL INCONSISTENCY spot13");
      else if (statusReverse[i] == TAKEN)
	System.out.print(sand[i]);
      else if (statusReverse[i] == WORDSTART)
	System.out.print(" " + sand[i]);
    }

    System.out.println("");
  }

  void printCompleteReverse()
  {
    for (int i = rangeEnd; i >= rangeBegin+1; i--) {
      if (statusReverse[i] == LOOSE)
	System.out.println("\nINTERNAL INCONSISTENCY spot14");
      else if (statusReverse[i] == TAKEN)
	System.out.print(sand[i]);
      else if (statusReverse[i] == WORDSTART)
	System.out.print(" " + sand[i]);
    }

    if (statusReverse[rangeBegin] == TAKEN)
      System.out.print(sand[rangeBegin]);
    else if (statusReverse[rangeBegin] == WORDSTART)
      System.out.print(" " + sand[rangeBegin]);

    if (status[rangeBegin] != LOOSE)
      System.out.print(" " + sand[rangeBegin]);

    if (status[rangeBegin] == LOOSE && statusReverse[rangeBegin] == LOOSE)
	System.out.println("\nINTERNAL INCONSISTENCY spot17");

    for (int i = rangeBegin+1; i <= rangeEnd; i++) {
      if (status[i] == LOOSE)
	System.out.println("\nINTERNAL INCONSISTENCY spot15");
      else if (status[i] == TAKEN)
	System.out.print(sand[i]);
      else if (status[i] == WORDSTART)
	System.out.print(" " + sand[i]);
    }

    System.out.println("");
  }

  String getString()
  {
    return new String(sand, rangeBegin, rangeEnd - rangeBegin + 1);
  }

  int length()
  {
    if (rangeBegin > rangeEnd)
      return 0;
    else
      return rangeEnd - rangeBegin + 1;
  }

  Vacancy Island()
  {
    int left, right;

    for(left=rangeBegin; left <= rangeEnd && status[left] == LOOSE; left++) ;
    if (left > rangeEnd) return new Vacancy("", 0);
    for(; left <= rangeEnd && status[left] != LOOSE; left++) ;
    if (left > rangeEnd) return new Vacancy("", 0);
    for(right=left; right <= rangeEnd && status[right] == LOOSE; right++) ;
    if (right > rangeEnd) return new Vacancy("", 0);
    // at this point, the island is from left to right-1
    String s = new String(sand, left, right-left);
    return new Vacancy(s, left);
  }

  Vacancy IslandReverse()
  {
    int left, right;

    for(right=rangeEnd; right >= rangeBegin && 
	  statusReverse[right] == LOOSE; right--) ;
    if (right < rangeBegin) return new Vacancy("", 0);
    for(; right >= rangeBegin && statusReverse[right] != LOOSE; right--) ;
    if (right < rangeBegin) return new Vacancy("", 0);
    for(left=right; left >= rangeBegin && 
	  statusReverse[left] == LOOSE; left--) ;
    if (left < rangeBegin) return new Vacancy("", 0);
    // at this point, the island is from right down to left+1
    String s = new String(sand, left+1, right-left);
    s = new String(new StringBuffer(s).reverse());
    return new Vacancy(s, right);
  }

  Vacancy RightEdge()
  {
    int right, left;
    left = right = rangeEnd;
    for (; left >= rangeBegin && status[left] == LOOSE; left--) ;
    // at this point, the edge is from left+1 to right
    String s = new String(sand, left+1, right-left) ;
    return new Vacancy(s, left+1);
  }

  Vacancy RightEdgeReverse()
  {
    int right, left;
    left = right = rangeBegin;
    for (; right <= rangeEnd && statusReverse[right] == LOOSE; right++) ;
    // at this point, the edge is from right-1 down to left
    String s = new String(sand, left, right-left) ;
    s = new String(new StringBuffer(s).reverse());
    return new Vacancy(s, right-1);
  }

  Vacancy LeftEdge()
  {
    int right, left;
    left = right = rangeBegin;
    for (; right <= rangeEnd && status[right] == LOOSE; right++) ;
    // at this point, the edge is from left to right-1
    String s = new String(sand, left, right-left);
    return new Vacancy(s, right-1);
  }

  Vacancy LeftEdgeReverse()
  {
    int right, left;
    left = right = rangeEnd;
    for (; left >= rangeBegin && statusReverse[left] == LOOSE; left--) ;
    // at this point, the edge is from right down to left+1 
    String s = new String(sand, left+1, right-left);
    s = new String(new StringBuffer(s).reverse());
    return new Vacancy(s, left+1);
  }

  int numwords()
  {
    return nWords;
  }

  // check completed palindrome
  //	both directions
  //	allow for missing edge letter
  boolean Complete()
  {
    return (Island().length() == 0 &&
	    IslandReverse().length() == 0 &&
	    LeftEdge().length() == 0 &&
	    RightEdgeReverse().length() == 0 &&
	    ((RightEdge().length() < 2 &&
	      LeftEdgeReverse().length() == 0) ||
	     (RightEdge().length() == 0 &&
	      LeftEdgeReverse().length() < 2)));
  }

  boolean CompleteReverse()
  {
    return (Island().length() == 0 &&
	    IslandReverse().length() == 0 &&
	    RightEdge().length() == 0 &&
	    LeftEdgeReverse().length() == 0 &&
	    ((LeftEdge().length() < 2 &&
	      RightEdgeReverse().length() == 0) ||
	     (LeftEdge().length() == 0 &&
	      RightEdgeReverse().length() < 2)));
  }

  SandBox copy()
  {
    // note: only spend time copying characters between rangeBegin and rangeEnd

    SandBox dup = new SandBox();
    dup.rangeBegin = rangeBegin;
    dup.rangeEnd = rangeEnd;
    dup.nWords = nWords;
    for (int i=rangeBegin; i <= rangeEnd; i++) {
      dup.sand[i] = sand[i];
      dup.status[i] = status[i];
      dup.statusReverse[i] = statusReverse[i];
    }

    return dup;
  }

  char getLetter(int i)
  {
    return( sand[rangeBegin + i] );
  }

  boolean used(int i)
  {
    return status[rangeBegin + i] != LOOSE;
  }

  boolean usedReverse(int i)
  {
    return statusReverse[rangeBegin + i] != LOOSE;
  }

  private char[] sand;
  private int[] status;   // LOOSE, TAKEN or WORDSTART
  private int[] statusReverse;
  private int rangeBegin, rangeEnd; // Where characters have been added
  private int nWords;

  final static int MAX = 300;
  final static int LOOSE = 1;      // not part of a word
  final static int TAKEN = 2;      // part of a word
  final static int WORDSTART = 3;  // first letter of a word
}