import java.io.*;
import java.util.*;
import java.awt.*;
import java.math.*;

public class Main {
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out) );
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st = new StringTokenizer("");
	static String next() throws Exception {

		while (!st.hasMoreTokens()) {
			String s = br.readLine();
			if (s == null)
				return null;
			st = new StringTokenizer(s);
		}
		return st.nextToken();
	}

	public static void main(String[] asda) throws Exception {
		
		String s = "ABCBCAB$";
		s = "abaabbaaa$".toUpperCase();
		
	//	s = "ABAA$";
	//	s = "AAAB$";
	//	s = "ALEXXELA$";
		SuffixArray sa = new SuffixArray(s);
		SuffixTree st = new SuffixTree(s, sa.pos, sa.LCP);
		
		// tests if all suffixes are in tree
		for (int i = 0; i < s.length(); i++)	{
			String sub = s.substring(i);
			out.println( sub + " in tree?: " + st.contains(sub) );
		}
		
		//
		out.flush();
		System.exit(0);
	}

	static class SuffixTree	{
		
		static final int ALPH_SIZE = 26 + 26 + 1;	// how many symbols are admitted? + terminator symbol ($)
		
		// given a character, returns its index for suffix node
		// this function should be updated if we change the alphabet
		static int char2id(char ch)	{
			if	( ch == '$' )	return	0;	// end symbol
			if	( ch <= 'Z' )	return	ch - 'A' + 1;	// upper case
			return	ch - 'a' + 26 + 1;	// lower case
		}
		
		/**
		 * Node for suffix tree
		**/
		class SuffixNode	{
			SuffixNode sons [];	// who are sons of this node?
			SuffixNode dad;		// who is dad of this node?, null if this node is root
			int startIndex;		// where this suffix starts? substring(index)	- inclusive
			int endIndex = -1;	// where this suffix ends? substring(index, len + 1)	- inclusive
			int chars = 0;	// how many chars are between root and dad?
			
			// create a node given his dad
			SuffixNode(SuffixNode dad)	{
				sons = new SuffixNode [ ALPH_SIZE ];
				this.dad = dad;
			}
			
			/*
			 * insert idx-suffix ( TEXT.substring(idx) )
			 * only useful if the new node doesn't exists
			**/
			SuffixNode insert(int idx)	{
				if	( idx >= TEXT.length() )	return	null;	// avoid bad indexes
				
				int ch = char2id( TEXT.charAt(idx) );	// id of new node
				SuffixNode node = sons[ch];
				if	( node == null )	{
					// if node doesn't exists, insert the whole range only
					node = sons[ch] = new SuffixNode(this);
					
					// insert TEXT.substring(idx)
					node.startIndex = idx;
					node.endIndex = TEXT.length() - 1;
					
					// update char count between root and dad
					node.chars = this.chars + size();
				}
				return	node;
			}

			/**
			 * insert a new node ( TEXT.substring(idx) )
			 * lcp is the longest common prefix between this and idx-th suffix
			**/
			SuffixNode insert(int idx, int lcp)	{
				// update lcp and idx (if need it)
				lcp -= chars;
				idx += chars;
				
				// trim right part and add it like a son of this node (if need it)
				if	( startIndex + lcp <= endIndex )	{
					// right suffix trimmed
					int id = char2id( TEXT.charAt( startIndex + lcp ) );

					// like inesrt(idx)
					SuffixNode node = new SuffixNode(this);
					node.startIndex = startIndex + lcp;
					node.endIndex = endIndex;	// only changed this
					node.chars = chars + lcp;
					
					if	( sons[id] == null )	{
						// if node doesn't overlap with a son, only add it
						if	( node.size() != 0 )	{
							SuffixNode [] aux = node.sons;
							node.sons = sons;
							sons = aux;
							
							sons[id] = node;
						}
					}
					else	{
						// the node overlap with a son
						// replace that son with an intermediate node (node)
						SuffixNode [] aux = node.sons;
						node.sons = sons;
						sons = aux;
						
						sons[id] = node;
					}
				}
				
				// trim this node to lcp
				endIndex = startIndex + lcp - 1;
				
				// insert left suffix
				return	insert(lcp + idx);
			}
			
			
			/**
			 * compute longest common prefix between TEXT.substring(i) and TEXT.substring(k, kk + 1)
			**/
			int lcp(int i, int k, int kk)	{
				int ans = 0;
				
				while	( i < TEXT.length() && k <= kk && TEXT.charAt(i++) == TEXT.charAt(k++) )
					ans++;
				
				return	ans;
			}
			
			/**
			 * size of this suffix
			**/
			int size()	{
				return	endIndex - startIndex + 1;
			}
			
			
			/*
			 * String representation of this suffix (empty if root)
			**/
			public String toString()	{
				String s = TEXT.substring(startIndex, endIndex + 1);
				return	s;
			}
			
		}
		
		// root of suffix tree
		SuffixNode	root;
		
		// text for this suffix tree
		final String TEXT;
		
		/**
		 * create suffix tree for string str using its suffix array and longest common prefix array
		 * O(N logN)
		 * @author Alexis Hernández
		 */
		SuffixTree(String str, Integer [] sa, int [] LCP)	{
			int N = LCP.length;
			this.TEXT = str;
			
			root = new SuffixNode(null);
			
			// insert $
			SuffixNode node = root.insert( sa[0] );
			
			// test
			int i = 1;
			while	( i < N )	{
				
				if	( LCP[i] == 0 )	{
					// here starts a new bucket, insert it into root only
					node = root.insert( sa[i++] );
					continue;
				}
				
				// find node with sharing part of LCP
				while	( node.chars >= LCP[i]	)	{
					node = node.dad;
				}
				
				// insert this suffix into found node
				node = node.insert( sa[i], LCP[i] );
				
				i++;
			}
		}
		
		/**
		 * tests if this suffix tree contains s
		**/
		public boolean contains(String s)	{
			SuffixNode node = root;
			int i = 0;
			while	( i < s.length() )	{
				node = node.sons[ char2id( s.charAt(i) ) ];
				if	( node == null )
					return	false;
				
				for (int k = node.startIndex; i < s.length() && k <= node.endIndex; k++, i++)
					if	( s.charAt(i) != TEXT.charAt(k) )
						return	false;
			}
			return	true;
		}
	}
	
	
	static class SuffixArray {
		final String str; // input
		int N;
		Integer [] pos;	// output
		int [] rank;	// output
		int LCP [];		// LCP[i] = Longest common prefix of suffix pos[i] and suffix pos[i - 1]

		public SuffixArray(final String str) {
			this.str = str;
			N = str.length();

			pos = new Integer[N];
			rank = new int[N];
			int [] cnt = new int[N];
			int [] next = new int[N];
			boolean [] bh = new boolean[N];
			boolean [] b2h = new boolean[N];

			// sort suffixes according to their first characters
			for (int i = 0; i < N; i++)
				pos[i] = i;

			Arrays.sort(pos, new Comparator<Integer>() {
				public int compare(Integer a, Integer b) {
					return str.charAt(a) - str.charAt(b);
				}
			});
			// {pos contains the list of suffixes sorted by their first
			// character}

			bh[0] = true;
			for (int i = 1; i < N; ++i) {
				bh[i] = str.charAt(pos[i]) != str.charAt(pos[i - 1]);
			}

			for (int h = 1; h < N; h <<= 1) {
				// {bh[i] == false if the first h characters of pos[i-1] == the
				// first h characters of pos[i]}
				int buckets = 0;
				for (int i = 0, j; i < N; i = j) {
					j = i + 1;
					while (j < N && !bh[j])
						j++;
					next[i] = j;
					buckets++;
				}
				if (buckets == N)
					break; // We are done! Lucky bastards!
				// {suffixes are separted in buckets containing strings starting
				// with the same h characters}

				for (int i = 0; i < N; i = next[i]) {
					cnt[i] = 0;
					for (int j = i; j < next[i]; ++j) {
						rank[pos[j]] = i;
					}
				}

				cnt[rank[N - h]]++;
				b2h[rank[N - h]] = true;
				for (int i = 0; i < N; i = next[i]) {
					for (int j = i; j < next[i]; ++j) {
						int s = pos[j] - h;
						if (s >= 0) {
							int head = rank[s];
							rank[s] = head + cnt[head]++;
							b2h[rank[s]] = true;
						}
					}
					for (int j = i; j < next[i]; ++j) {
						int s = pos[j] - h;
						if (s >= 0 && b2h[rank[s]]) {
							for (int k = rank[s] + 1; k < N && !bh[k] && b2h[k]; k++)
								b2h[k] = false;
						}
					}
				}
				for (int i = 0; i < N; ++i) {
					pos[rank[i]] = i;
					bh[i] |= b2h[i];
				}
			}
			

			// compute inverse of suffix array
			for (int i = 0; i < N; ++i)
				rank[ pos[i] ] = i;
			
			/**
			 * Begin of the O(n) longest common prefix algorithm
			 * Refer to "Linear-Time Longest-Common-Prefix Computation in Suffix
			 * Arrays and Its Applications" by Toru Kasai, Gunho Lee, Hiroki
			 * Arimura, Setsuo Arikawa, and Kunsoo Park
			**/

			LCP = new int [N];
			LCP[0] = 0;
			for (int i = 0, h = 0; i < N; ++i)	{
				if ( rank[i] > 0 )	{
					int j = pos[ rank[i] - 1 ];
					while ( i + h < N && j + h < N && str.charAt(i+h) == str.charAt(j+h) )
						h++;
					LCP[ rank[i] ] = h;
					if ( h > 0 )
						h--;
				}
			}
		}

	}
}