import scala collection mutable class SuffixTree Seq ps val inf 666666

import scala.collection.mutable
class SuffixTree[T, S <: Seq[T]](ps:S) {
  val inf = 666666
  private class Node(pl: Int = 0, pr: Int = 0, ppar: Int = -1) {
    var l = pl
    var r = pr
    var par = ppar
    var link = -1
    var next: mutable.Map[T, Int] = mutable.Map()
    def len(): Int = r - l
    def get(c:T): Int = if (next.contains(c)) next(c) else {next(c) = -1; next(c)}
  }
  private class State(pv: Int, ppos: Int) {
    var v = pv
    var pos = ppos
  }
  private var s : Seq[T] = ps
  private val t: mutable.Map[Int, Node] = mutable.Map()
  private var sz = 1
  private var ptr = new State(0,0)
  private def go(pst:State, pl:Int, pr:Int) : State  = {
    var st = pst
    var l = pl
    while (l < pr)
      if (st.pos == t.getOrElseUpdate(st.v, new Node()).len()) {
        st = new State(t(st.v).get(s(l)), 0)
        if (st.v == -1) return st
      } else {
        if (s(t(st.v).l + st.pos) != s(l)) return new State(-1, -1)
        if (pr - l < t(st.v).len() - st.pos) return new State(st.v, st.pos + pr - l)
        l += t(st.v).len() - st.pos
        st.pos = t(st.v).len()
      }
    st
  }
  private def split(st:State): Int = {
    val func : (State) => Int = {
      case (st1) if st1.pos == t(st1.v).len() => st.v
      case (st2) if st2.pos == 0 => t(st2.v).par
      case (st3) =>
        val v = t(st3.v)
        val id = sz
        sz = sz + 1
        t(id) = new Node(v.l, v.l + st.pos, v.par)
        t(v.par).next(s(v.l)) = id
        t(id).next(s(v.l + st.pos)) = st.v
        t(st.v).par = id
        t(st.v).l += st.pos
        id
    }
    func(st)
  }
  private def get_link(v:Int): Int = {
    val func : (Int) => Int = {
      case (v1) if t(v1).link != -1 => t(v1).link
      case (v2) if t(v2).par == -1 => 0
      case (v3) =>
        val to = get_link(t(v3).par)
        val e =  if (t(v3).par==0)  1 else 0
        val lst = new State(to,t(to).len())
        t(v3).link = split (go(lst, t(v3).l+e, t(v).r))
        t(v3).link
    }
    func(v)
  }
  private def tree_extend(pos:Int): Unit = {
    var cond = true
    while(cond) {
      val nptr = go (ptr, pos, pos+1)
      if (nptr.v != -1) {
        ptr = nptr
        return
      }
      val mid = split (ptr)
      val leaf = sz
      sz = sz + 1
      t(leaf) = new Node (pos, inf, mid)
      t(mid).next(s(pos)) = leaf
      ptr.v = get_link (mid)
      ptr.pos = t(ptr.v).len()
      if (mid==0)  cond=false
    }
  }
  def exist(f:S): Boolean = {
    var st = new State(0,0)
    val r = f.length
    var l = 0
    while (l < r)
      if (st.pos == t(st.v).len()) {
        st = new State(t(st.v).get(f(l)),0)
        if (st.v == -1) return false
      } else {
        if (s(t(st.v).l + st.pos) != f(l)) return false
        l+=1
        st.pos+=1
      }
    true
  }
  def find(f:S): Int = {
    var st = new State(0,0)
    var index = 0
    val r = f.length
    var l = 0
    while (l < r)
      if (st.pos == t(st.v).len()) {
        val pr = t(st.v).r
        st = new State(t(st.v).get(f(l)),0)
        if (st.v == -1) return -1
        index += t(st.v).l - pr
      } else {
        if (s(t(st.v).l + st.pos) != f(l)) return -1
        l += 1
        st.pos += 1
      }
    index
  }
  private var i = 0
  while (i<s.length) {
    tree_extend(i)
    i = i + 1
  }
  def add(f:S): Unit = {
    s = s ++ f
    while (i<s.length) {
      tree_extend(i)
      i = i + 1
    }
  }
}