import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;
// from https://gist.github.com/bicepjai/3355993#file-gistfile1-java-L147

/*
 * Copyright (c) 2016 Sergey Makagonov
 * 
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 * 
 */
 
class main {

static class UkkonenSuffixTree {
  static final int oo = Integer.MAX_VALUE/2; // TODO: Why /2?
  Node [] nodes;
  char [] text;
  int root, position = -1, currentNode, needSuffixLink, remainder;

  int active_node, active_length, active_edge;

  static class Node {
    int start, end = oo, link;
    public TreeMap<Character, Integer> next = new TreeMap<Character, Integer>();

    Node(int start, int end) {
  this.end = end;
  this.start = start;}

    public int edgeLength(UkkonenSuffixTree tree) {
      return Math.min(end, tree.position + 1) - start;
    }
  }

  UkkonenSuffixTree(int length) {
    nodes = new Node[2*length+2];
    text = new char[length];
    root = active_node = newNode(-1, -1);
  }

  private void addSuffixLink(int node) {
      if (needSuffixLink > 0)
          nodes[needSuffixLink].link = node;
      needSuffixLink = node;
  }

  char active_edge() {
      return text[active_edge];
  }

  boolean walkDown(int next) {
      if (active_length >= nodes[next].edgeLength(this)) {
          active_edge += nodes[next].edgeLength(this);
          active_length -= nodes[next].edgeLength(this);
          active_node = next;
          return true;
      }
      return false;
  }

  int newNode(int start, int end) {
      nodes[++currentNode] = new Node(start, end);
      return currentNode;
  }

  public void addChar(char c) {
      text[++position] = c;
      needSuffixLink = -1;
      remainder++;
      while(remainder > 0) {
          if (active_length == 0) active_edge = position;
          if (!nodes[active_node].next.containsKey(active_edge())){
              int leaf = newNode(position, oo);
              nodes[active_node].next.put(active_edge(), leaf);
              addSuffixLink(active_node); //rule 2
          } else {
              int next = nodes[active_node].next.get(active_edge());
              if (walkDown(next)) continue;   //observation 2
              if (text[nodes[next].start + active_length] == c) { //observation 1
                  active_length++;
                  addSuffixLink(active_node); // observation 3
                  break;
              }
              int split = newNode(nodes[next].start, nodes[next].start + active_length);
              nodes[active_node].next.put(active_edge(), split);
              int leaf = newNode(position, oo);
              nodes[split].next.put(c, leaf);
              nodes[next].start += active_length;
              nodes[split].next.put(text[nodes[next].start], next);
              addSuffixLink(split); //rule 2
          }
          remainder--;

          if (active_node == root && active_length > 0) {  //rule 1
              active_length--;
              active_edge = position - remainder + 1;
          } else
              active_node = nodes[active_node].link > 0 ? nodes[active_node].link : root; //rule 3
      }
  }
}}