let S = getStringAsArray(maxLength: 500_000)
let N = S.count

let sa = S.suffixArray()
let lcp = S.lcpArray(suffixArray: sa)

let answer = N * (N+1) / 2 - lcp.reduce(0, +)
print(answer)




//=============================================================================
// MARK: - Array+suffixArray.swift
// code section by
// J Kärkkäinen, P Sanders. Simple linear work suffix array construction, 2003
// T Kasai, G Lee, H Arimura, S Arikawa, K Park. Linear-time longest-common-
//     prefix computation in suffix arrays and its applications, 2001
// Swift translation by Barry Fam

extension Array where Element: FixedWidthInteger {
    func suffixArray() -> [Int] {
        precondition(Element.bitWidth <= 16, "Alphabet size too large")
        assert(self.allSatisfy { $0 != 0 } )

        // Kärkkäinen-Sanders 2003
        // MARK: begin code -
        func leq(_ a1: Int, _ a2: Int,   _ b1: Int, _ b2: Int) -> Bool // lexicographic order
        { a1 < b1 || (a1 == b1 && a2 <= b2) }                                    // for pairs
        func leq(_ a1: Int, _ a2: Int, _ a3: Int,   _ b1: Int, _ b2: Int, _ b3: Int) -> Bool
        { a1 < b1 || (a1 == b1 && leq(a2,a3, b2,b3)) }                         // and triples

        /// stably sort `a[0...n-1]` to `b[0...n-1]` with keys in `0...K` from `r`
        func radixPass(_ a: [Int], _ b: inout [Int], _ r: ArraySlice<Int>, _ n: Int, _ K: Int)
        { // count occurrences
            var c = [Int](repeating: 0, count: K+1)                                // counter array
            for i in 0 ..< n { c[r[r.startIndex + a[i]]] += 1 }                // count occurrences
            var sum = 0;  for i in 0 ... K                                 // exclusive prefix sums
            { let t = c[i];  c[i] = sum;  sum += t }
            for i in 0 ..< n { let ci=r[r.startIndex + a[i]];  b[c[ci]] = a[i];  c[ci]+=1 } // sort
        }

        /// find the suffix array `SA` of `s[0...n-1] ` in {`1...K`}^n
        /// require `s[n]`=`s[n+1]`=`s[n+2]`=`0`, `n >=2`
        func suffixArray(_ s: [Int], _ SA: inout [Int], _ n: Int, _ K: Int) {
            let n0=(n+2)/3, n1=(n+1)/3, n2=n/3, n02=n0+n2
            var s12  = [Int](repeating: 0, count: n02 + 3)
            var SA12 = [Int](repeating: 0, count: n02 + 3)
            var s0   = [Int](repeating: 0, count: n0)
            var SA0  = [Int](repeating: 0, count: n0)

            // generate positions of mod 1 and mod 2 suffixes
            // the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
            var j=0;  for i in 0 ..< n+(n0-n1) { if i%3 != 0 { s12[j] = i;  j+=1 } }

            // lsb radix sort the mod 1 and mod 2 triples
            radixPass(s12 , &SA12, s[2...], n02, K)
            radixPass(SA12, &s12 , s[1...], n02, K)
            radixPass(s12 , &SA12, s[...] , n02, K)

            // find lexicographic names of triples
            var name = 0, c0 = -1, c1 = -1, c2 = -1
            for i in 0 ..< n02 {
                if s[SA12[i]] != c0 || s[SA12[i]+1] != c1 || s[SA12[i]+2] != c2
                { name+=1; c0 = s[SA12[i]]; c1 = s[SA12[i]+1]; c2 = s[SA12[i]+2] }
                if (SA12[i] % 3 == 1) { s12[SA12[i]/3]      = name } // left half
                else                  { s12[SA12[i]/3 + n0] = name } // right half
            }

            // recurse if names are not yet unique
            if name < n02 {
                suffixArray(s12, &SA12, n02, name)
                // store unique names in s12 using the suffix array
                for i in 0 ..< n02 { s12[SA12[i]] = i + 1 }
            } else // generate the suffix array of s12 directly
                { for i in 0 ..< n02 { SA12[s12[i] - 1] = i } }

            // stably sort the mod 0 suffixes from SA12 by their first character
            j=0;  for i in 0 ..< n02 { if SA12[i] < n0 { s0[j] = 3*SA12[i];  j+=1 } }
            radixPass(s0, &SA0, s[...], n0, K)

            // merge sorted SA0 suffixes and sorted SA12 suffixes
            var p=0,  t=n0-n1,  k=0;  while k < n { defer { k+=1 }
                func GetI() -> Int { (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2) }
                let i = GetI() // pos of current offset 12 suffix
                let j = SA0[p] // pos of current offset 0 suffix
                if SA12[t] < n0 ? // different compares for mod 1 and mod 2 suffixes
                   leq(s[i], s12[SA12[t] + n0], s[j], s12[j/3]) :
                   leq(s[i],s[i+1],s12[SA12[t]-n0+1], s[j],s[j+1],s12[j/3+n0])
                {        // suffix from SA12 is smaller
                    SA[k] = i;  t+=1;
                    if t == n02 // done --- only SA0 suffixes left
                        { k+=1;  while p < n0 { SA[k] = SA0[p];  p+=1;  k+=1 } }
                } else { // suffix from SA0 is smaller
                    SA[k] = j;  p+=1;
                    if p == n0  // done --- only SA12 suffixes left
                        { k+=1;  while t < n02 { SA[k] = GetI();  t+=1;  k+=1 } }
                }
            }
        }
        // MARK: - end code

        let s = self.map(Int.init) + [0, 0, 0]
        var SA = [Int](repeating: 0, count: count)
        suffixArray(s, &SA, count, 1 << Element.bitWidth - 1)
        return SA
    }

    func lcpArray(suffixArray: [Int]) -> [Int] {
        // Kasai 2001
        // MARK: begin code -
        let SA = suffixArray
        var ISA: [Int]
        let T = self
        let n = count
        var LCP: [Int]

        ISA = [Int](repeating: 0, count: n)
        for i in 0..<n { ISA[SA[i]] = i }
        LCP = [Int](repeating: 0, count: n-1)

        var h = 0
        for i in 0..<n {
            if ISA[i] > 0 {
                let j = SA[ISA[i]-1]
                while i+h < n && j+h < n,
                      T[i+h] == T[j+h]
                {
                    h += 1
                }
                LCP[ISA[i]-1] = h
                if h > 0 { h -= 1 }
            }
        }
        // MARK: - end code

        return LCP
    }
}

//=============================================================================
// MARK: - contestIO.swift
// code section by Barry Fam

#if os(Linux)
import Glibc
#else
import Darwin.C
#endif

struct IO {
    static var INPUT = stdin
    fileprivate static var buffer: UnsafeMutablePointer<CChar>?
    fileprivate static var bufferCapacity: Int32 = 0
}

fileprivate func getsToBuffer(size: Int32) -> UnsafeMutablePointer<CChar> {
    if IO.bufferCapacity < size {
        IO.buffer?.deallocate()
        IO.buffer = UnsafeMutablePointer.allocate(capacity: Int(size))
        IO.bufferCapacity = size
    }
    return fgets(IO.buffer!, size, IO.INPUT)
}
fileprivate func getIntFromBuffer(_ ptr: inout UnsafeMutablePointer<CChar>) -> Int {
    var minus = false
    var x: Int?
    while true {
        switch ptr.pointee {
        case 0x2D:
            assert(!minus && x == nil)
            minus = true
        case let d where 0x30...0x39 ~= d:
            x = (x ?? 0)*10 + Int(d)-0x30
        case 0x00:
            x ??= 0
            fallthrough
        default:
            if x != nil { return minus ? -x! : x! }
        }
        ptr += 1
    }
}

func getString(maxLength: Int) -> String {
    var s = String(cString: getsToBuffer(size: Int32(maxLength + 3)))
    if s.last == "\n" { s.removeLast() }
    if s.last == "\r" { s.removeLast() }
    return s
}
func getStringAsArray(maxLength: Int) -> [UInt8] {
    let ptr = getsToBuffer(size: Int32(maxLength + 3))
    var s = [UInt8]()
    for ptr in ptr ..< ptr + maxLength {
        let c = UInt8(ptr.pointee)
        if c == 0x00 || c == 0x0A || c == 0x0D { break }
        s.append(c)
    }
    return s
}
func getInt() -> Int {
    var xPtr = getsToBuffer(size: 24)
    return getIntFromBuffer(&xPtr)
}
func getIntPair() -> (Int, Int) {
    var xPtr = getsToBuffer(size: 2*24)
    let x1 = getIntFromBuffer(&xPtr)
    let x2 = getIntFromBuffer(&xPtr)
    return (x1, x2)
}
func getIntTriplet() -> (Int, Int, Int) {
    var xPtr = getsToBuffer(size: 3*24)
    let x1 = getIntFromBuffer(&xPtr)
    let x2 = getIntFromBuffer(&xPtr)
    let x3 = getIntFromBuffer(&xPtr)
    return (x1, x2, x3)
}
func getIntQuadruplet() -> (Int, Int, Int, Int) {
    var xPtr = getsToBuffer(size: 4*24)
    let x1 = getIntFromBuffer(&xPtr)
    let x2 = getIntFromBuffer(&xPtr)
    let x3 = getIntFromBuffer(&xPtr)
    let x4 = getIntFromBuffer(&xPtr)
    return (x1, x2, x3, x4)
}
func getIntQuintuplet() -> (Int, Int, Int, Int, Int) {
    var xPtr = getsToBuffer(size: 5*24)
    let x1 = getIntFromBuffer(&xPtr)
    let x2 = getIntFromBuffer(&xPtr)
    let x3 = getIntFromBuffer(&xPtr)
    let x4 = getIntFromBuffer(&xPtr)
    let x5 = getIntFromBuffer(&xPtr)
    return (x1, x2, x3, x4, x5)
}
func getIntSextuplet() -> (Int, Int, Int, Int, Int, Int) {
    var xPtr = getsToBuffer(size: 6*24)
    let x1 = getIntFromBuffer(&xPtr)
    let x2 = getIntFromBuffer(&xPtr)
    let x3 = getIntFromBuffer(&xPtr)
    let x4 = getIntFromBuffer(&xPtr)
    let x5 = getIntFromBuffer(&xPtr)
    let x6 = getIntFromBuffer(&xPtr)
    return (x1, x2, x3, x4, x5, x6)
}
func getInts(count: Int) -> [Int] {
    var xPtr = getsToBuffer(size: Int32(count) * 24)
    var a = [Int]()
    a.reserveCapacity(count)
    for _ in 0..<count { a.append(getIntFromBuffer(&xPtr)) }
    return a
}

//=============================================================================
// MARK: - operators.swift
// code section by Barry Fam

infix operator <?= : AssignmentPrecedence
infix operator >?= : AssignmentPrecedence
func <?= <T: Comparable>(lhs: inout T, rhs: T) {
    if lhs < rhs { lhs = rhs }
}
func >?= <T: Comparable>(lhs: inout T, rhs: T) {
    if lhs > rhs { lhs = rhs }
}

infix operator ??= : AssignmentPrecedence
func ??= <T>(lhs: inout T?, rhs: T?) {
    if lhs == nil { lhs = rhs }
}

func ^ (lhs: Bool, rhs: Bool) -> Bool {
    lhs != rhs
}

func + <T: AdditiveArithmetic>(u: (T, T), v: (T, T)) -> (T, T) {
    (u.0+v.0, u.1+v.1)
}
func + <T: AdditiveArithmetic>(u: (T, T, T), v: (T, T, T)) -> (T, T, T) {
    (u.0+v.0, u.1+v.1, u.2+v.2)
}
func + <T: AdditiveArithmetic>(u: (T, T, T, T), v: (T, T, T, T)) -> (T, T, T, T) {
    (u.0+v.0, u.1+v.1, u.2+v.2, u.3+v.3)
}
func + <T: AdditiveArithmetic>(u: (T, T, T, T, T), v: (T, T, T, T, T)) -> (T, T, T, T, T) {
    (u.0+v.0, u.1+v.1, u.2+v.2, u.3+v.3, u.4+v.4)
}
func + <T: AdditiveArithmetic>(u: (T, T, T, T, T, T), v: (T, T, T, T, T, T)) -> (T, T, T, T, T, T) {
    (u.0+v.0, u.1+v.1, u.2+v.2, u.3+v.3, u.4+v.4, u.5+v.5)
}

func - <T: AdditiveArithmetic>(u: (T, T), v: (T, T)) -> (T, T) {
    (u.0-v.0, u.1-v.1)
}
func - <T: AdditiveArithmetic>(u: (T, T, T), v: (T, T, T)) -> (T, T, T) {
    (u.0-v.0, u.1-v.1, u.2-v.2)
}
func - <T: AdditiveArithmetic>(u: (T, T, T, T), v: (T, T, T, T)) -> (T, T, T, T) {
    (u.0-v.0, u.1-v.1, u.2-v.2, u.3-v.3)
}
func - <T: AdditiveArithmetic>(u: (T, T, T, T, T), v: (T, T, T, T, T)) -> (T, T, T, T, T) {
    (u.0-v.0, u.1-v.1, u.2-v.2, u.3-v.3, u.4-v.4)
}
func - <T: AdditiveArithmetic>(u: (T, T, T, T, T, T), v: (T, T, T, T, T, T)) -> (T, T, T, T, T, T) {
    (u.0-v.0, u.1-v.1, u.2-v.2, u.3-v.3, u.4-v.4, u.5-v.5)
}

infix operator *+ : MultiplicationPrecedence
func *+ <T: Numeric>(u: (T, T), v: (T, T)) -> T {
    var x = u.0 * v.0
    x += u.1 * v.1
    return x
}
func *+ <T: Numeric>(u: (T, T, T), v: (T, T, T)) -> T {
    var x = u.0 * v.0
    x += u.1 * v.1
    x += u.2 * v.2
    return x
}
func *+ <T: Numeric>(u: (T, T, T, T), v: (T, T, T, T)) -> T {
    var x = u.0 * v.0
    x += u.1 * v.1
    x += u.2 * v.2
    x += u.3 * v.3
    return x
}
func *+ <T: Numeric>(u: (T, T, T, T, T), v: (T, T, T, T, T)) -> T {
    var x = u.0 * v.0
    x += u.1 * v.1
    x += u.2 * v.2
    x += u.3 * v.3
    x += u.4 * v.4
    return x
}
func *+ <T: Numeric>(u: (T, T, T, T, T, T), v: (T, T, T, T, T, T)) -> T {
    var x = u.0 * v.0
    x += u.1 * v.1
    x += u.2 * v.2
    x += u.3 * v.3
    x += u.4 * v.4
    x += u.5 * v.5
    return x
}

extension BinaryInteger {
    func ceilDiv(by d: Self) -> Self {
        assert(self >= 0)
        return (self + d-1) / d
    }
}

func gcd<T: BinaryInteger>(_ a: T, _ b: T) -> T {
    b == 0 ? a : gcd(b, a%b)
}
func lcm<T: BinaryInteger>(_ a: T, _ b: T) -> T {
    a / gcd(a, b) * b
}

extension FixedWidthInteger {
    var bitLength: Int {
        assert(self >= 0)
        return self.bitWidth - self.leadingZeroBitCount
    }
}


Measured memory_bytes: 38420