module AcLibraryRb

# File lib_lock/ac-library-rb/inv_mod.rb, line 10
def _inv_gcd(a, b)
  a %= b # safe_mod

  s, t = b, a
  m0, m1 = 0, 1

  while t > 0
    u = s / t
    s -= t * u
    m0 -= m1 * u

    s, t = t, s
    m0, m1 = m1, m0
  end

  m0 += b / s if m0 < 0
  [s, m0]
end

# File lib_lock/ac-library-rb/convolution.rb, line 128
def convolution(a, b, mod: 998244353, k: 35, z: 99)
  n = a.size
  m = b.size
  return [] if n == 0 || m == 0

  raise ArgumentError if a.min < 0 || b.min < 0

  format = "%0#{k}x" # "%024x"
  sa = ""
  sb = ""
  a.each{ |x| sa << (format % x) }
  b.each{ |x| sb << (format % x) }

  zero = '0'
  s = zero * z + ("%x" % (sa.hex * sb.hex))
  i = -(n + m - 1) * k - 1

  Array.new(n + m - 1){ (s[i + 1..i += k] || zero).hex % mod }
end

# File lib_lock/ac-library-rb/crt.rb, line 3
def crt(r, m)
  unless r.size == m.size
    raise ArgumentError.new("size of r and m must be equal for crt(r, m)")
  end

  n = r.size
  r0, m0 = 0, 1
  n.times do |i|
    raise ArgumentError if m[i] < 1

    r1, m1 = r[i] % m[i], m[i]
    if m0 < m1
      r0, r1 = r1, r0
      m0, m1 = m1, m0
    end

    if m0 % m1 == 0
      return [0, 0] if r0 % m1 != r1

      next
    end

    g, im = inv_gcd(m0, m1)
    u1 = m1 / g
    return [0, 0] if (r1 - r0) % g != 0

    x = (r1 - r0) / g * im % u1
    r0 += x * m0
    m0 *= u1
    r0 += m0 if r0 < 0
  end

  return [r0, m0]
end

# File lib_lock/ac-library-rb/floor_sum.rb, line 2
def floor_sum(n, m, a, b)
  raise ArgumentError if n < 0 || m < 1

  res = 0

  if a < 0
    a2 = a % m
    res -= n * (n - 1) / 2 * ((a2 - a) / m)
    a = a2
  end

  if b < 0
    b2 = b % m
    res -= n * ((b2 - b) / m)
    b = b2
  end

  res + floor_sum_unsigned(n, m, a, b)
end

# File lib_lock/ac-library-rb/floor_sum.rb, line 22
def floor_sum_unsigned(n, m, a, b)
  res = 0

  while true
    if a >= m
      res += n * (n - 1) / 2 * (a / m)
      a %= m
    end

    if b >= m
      res += n * (b / m)
      b %= m
    end

    y_max = a * n + b
    break if y_max < m

    n = y_max / m
    b = y_max % m
    m, a = a, m
  end

  res
end

# File lib_lock/ac-library-rb/crt.rb, line 40
def inv_gcd(a, b)
  a %= b
  return [b, 0] if a == 0

  s, t = b, a
  m0, m1 = 0, 1
  while t > 0
    u, s = s.divmod(t)
    m0 -= m1 * u
    s, t = t, s
    m0, m1 = m1, m0
  end
  m0 += b / s if m0 < 0

  return [s, m0]
end

# File lib_lock/ac-library-rb/inv_mod.rb, line 3
def inv_mod(x, m)
  z = _inv_gcd(x, m)
  raise ArgumentError unless z.first == 1

  z[1]
end

# File lib_lock/ac-library-rb/lcp_array.rb, line 3
def lcp_array(s, sa)
  s = s.bytes if s.is_a?(String)

  n = s.size
  rnk = [0] * n
  sa.each_with_index{ |sa, id|
    rnk[sa] = id
  }

  lcp = [0] * (n - 1)
  h = 0
  n.times{ |i|
    h -= 1 if h > 0
    next if rnk[i] == 0

    j = sa[rnk[i] - 1]
    h += 1 while j + h < n && i + h < n && s[j + h] == s[i + h]
    lcp[rnk[i] - 1] = h
  }

  return lcp
end

# File lib_lock/ac-library-rb/pow_mod.rb, line 3
def pow_mod(x, n, m)
  return 0 if m == 1

  r, y = 1, x % m
  while n > 0
    r = r * y % m if n.odd?
    y = y * y % m
    n >>= 1
  end

  r
end

# File lib_lock/ac-library-rb/suffix_array.rb, line 37
def sa_is(s, upper)
  n = s.size

  return [] if n == 0
  return [0] if n == 1

  ls = [false] * n
  (n - 2).downto(0){ |i|
    ls[i] = (s[i] == s[i + 1] ? ls[i + 1] : s[i] < s[i + 1])
  }

  sum_l = [0] * (upper + 1)
  sum_s = [0] * (upper + 1)
  n.times{ |i|
    if ls[i]
      sum_l[s[i] + 1] += 1
    else
      sum_s[s[i]] += 1
    end
  }
  0.upto(upper){ |i|
    sum_s[i] += sum_l[i]
    sum_l[i + 1] += sum_s[i] if i < upper
  }

  lms = (1 ... n).select{ |i| !ls[i - 1] && ls[i] }
  m = lms.size
  lms_map = [-1] * (n + 1)
  lms.each_with_index{ |lms, id| lms_map[lms] = id }

  sa = sa_is_induce(s, ls, sum_l, sum_s, lms)

  return sa if m == 0

  sorted_lms = sa.select{ |sa| lms_map[sa] != -1 }
  rec_s = [0] * m
  rec_upper = 0
  rec_s[lms_map[sorted_lms[0]]] = 0
  1.upto(m - 1) do |i|
    l, r = sorted_lms[i - 1, 2]
    end_l = lms[lms_map[l] + 1] || n
    end_r = lms[lms_map[r] + 1] || n
    same = true
    if end_l - l == end_r - r
      while l < end_l
        break if s[l] != s[r]

        l += 1
        r += 1
      end
      same = false if l == n || s[l] != s[r]
    else
      same = false
    end
    rec_upper += 1 if not same
    rec_s[lms_map[sorted_lms[i]]] = rec_upper
  end

  sa_is(rec_s, rec_upper).each_with_index{ |rec_sa, id|
    sorted_lms[id] = lms[rec_sa]
  }

  return sa_is_induce(s, ls, sum_l, sum_s, sorted_lms)
end

# File lib_lock/ac-library-rb/suffix_array.rb, line 3
def sa_is_induce(s, ls, sum_l, sum_s, lms)
  n = s.size
  sa = [-1] * n

  buf = sum_s.dup
  lms.each{ |lms|
    if lms != n
      sa[buf[s[lms]]] = lms
      buf[s[lms]] += 1
    end
  }

  buf = sum_l.dup
  sa[buf[s[-1]]] = n - 1
  buf[s[-1]] += 1
  sa.each{ |v|
    if v >= 1 && !ls[v - 1]
      sa[buf[s[v - 1]]] = v - 1
      buf[s[v - 1]] += 1
    end
  }

  buf = sum_l.dup
  sa.reverse_each{ |v|
    if v >= 1 && ls[v - 1]
      buf[s[v - 1] + 1] -= 1
      sa[buf[s[v - 1] + 1]] = v - 1
    end
  }

  return sa
end

# File lib_lock/ac-library-rb/suffix_array.rb, line 103
def suffix_array(s, upper = nil)
  if upper
    s.each{ |s|
      raise ArgumentError if s < 0 || upper < s
    }
  else
    case s
    when Array
      # compression
      n = s.size
      idx = (0 ... n).sort_by{ |i| s[i] }
      t = [0] * n
      upper = 0
      t[idx[0]] = 0
      1.upto(n - 1){ |i|
        upper += 1 if s[idx[i - 1]] != s[idx[i]]
        t[idx[i]] = upper
      }
      s = t
    when String
      upper = 255
      s = s.bytes
    end
  end

  return sa_is(s, upper)
end

# File lib_lock/ac-library-rb/z_algorithm.rb, line 7
def z_algorithm(s)
  n = s.size
  return [] if n == 0

  s = s.codepoints if s.is_a?(String)

  z = [0] * n
  z[0] = n
  i, j = 1, 0
  while i < n
    j += 1 while i + j < n && s[j] == s[i + j]
    z[i] = j
    if j == 0
      i += 1
      next
    end
    k = 1
    while i + k < n && k + z[k] < j
      z[i + k] = z[k]
      k += 1
    end
    i += k
    j -= k
  end

  return z
end