(
 nOrLeaves: number | ArrayLike<E>,
 operations: {
   /**
    * 线段树维护的值的幺元.
    */
   e: () => E

   /**
    * 更新操作/懒标记的幺元.
    */
   id: () => Id

   /**
    * 合并左右区间的值.
    */
   op: (e1: E, e2: E) => E

   /**
    * 父结点的懒标记更新子结点的值.
    */
   mapping: (lazy: Id, data: E) => E

   /**
    * 父结点的懒标记更新子结点的懒标记(合并).
    */
   composition: (parentLazy: Id, childLazy: Id) => Id
 }
)

class SegmentTreePointUpdateRangeQuery<E = number> {
  private readonly _n: number
  private readonly _size: number
  private readonly _data: E[]
  private readonly _e: () => E
  private readonly _op: (a: E, b: E) => E

  /**
   * 单点更新,区间查询的线段树.
   * @param nOrLeaves 大小或叶子节点的值.
   * @param e 幺元.
   * @param op 结合律.
   */
  constructor(nOrLeaves: number | ArrayLike<E>, e: () => E, op: (a: E, b: E) => E) {
    const n = typeof nOrLeaves === 'number' ? nOrLeaves : nOrLeaves.length
    let size = 1
    while (size < n) size <<= 1
    const data = Array(size << 1)
    for (let i = 0; i < data.length; i++) data[i] = e()

    this._n = n
    this._size = size
    this._data = data
    this._e = e
    this._op = op

    if (typeof nOrLeaves !== 'number') this.build(nOrLeaves)
  }

  set(index: number, value: E): void {
    if (index < 0 || index >= this._n) return
    index += this._size
    this._data[index] = value
    while ((index >>= 1)) {
      this._data[index] = this._op(this._data[index << 1], this._data[(index << 1) | 1])
    }
  }

  get(index: number): E {
    if (index < 0 || index >= this._n) return this._e()
    return this._data[index + this._size]
  }

  /**
   * 将`index`处的值与作用素`value`结合.
   */
  update(index: number, value: E): void {
    if (index < 0 || index >= this._n) return
    index += this._size
    this._data[index] = this._op(this._data[index], value)
    while ((index >>= 1)) {
      this._data[index] = this._op(this._data[index << 1], this._data[(index << 1) | 1])
    }
  }

  /**
   * 查询区间`[start,end)`的聚合值.
   * 0 <= start <= end <= n.
   */
  query(start: number, end: number): E {
    if (start < 0) start = 0
    if (end > this._n) end = this._n
    if (start >= end) return this._e()

    let leftRes = this._e()
    let rightRes = this._e()
    for (start += this._size, end += this._size; start < end; start >>= 1, end >>= 1) {
      if (start & 1) leftRes = this._op(leftRes, this._data[start++])
      if (end & 1) rightRes = this._op(this._data[--end], rightRes)
    }
    return this._op(leftRes, rightRes)
  }

  queryAll(): E {
    return this._data[1]
  }

  /**
   * 树上二分查询最大的`end`使得`[start,end)`内的值满足`predicate`.
   * @alias findFirst
   */
  maxRight(start: number, predicate: (value: E) => boolean): number {
    if (start < 0) start = 0
    if (start >= this._n) return this._n
    start += this._size
    let res = this._e()
    while (true) {
      while (!(start & 1)) start >>= 1
      if (!predicate(this._op(res, this._data[start]))) {
        while (start < this._size) {
          start <<= 1
          if (predicate(this._op(res, this._data[start]))) {
            res = this._op(res, this._data[start])
            start++
          }
        }
        return start - this._size
      }
      res = this._op(res, this._data[start])
      start++
      if ((start & -start) === start) break
    }
    return this._n
  }

  /**
   * 树上二分查询最小的`start`使得`[start,end)`内的值满足`predicate`
   * @alias findLast
   */
  minLeft(end: number, predicate: (value: E) => boolean): number {
    if (end > this._n) end = this._n
    if (end <= 0) return 0
    end += this._size
    let res = this._e()
    while (true) {
      end--
      while (end > 1 && end & 1) end >>= 1
      if (!predicate(this._op(this._data[end], res))) {
        while (end < this._size) {
          end = (end << 1) | 1
          if (predicate(this._op(this._data[end], res))) {
            res = this._op(this._data[end], res)
            end--
          }
        }
        return end + 1 - this._size
      }
      res = this._op(this._data[end], res)
      if ((end & -end) === end) break
    }
    return 0
  }

  build(arr: ArrayLike<E>): void {
    if (arr.length !== this._n) throw new RangeError(`length must be equal to ${this._n}`)
    for (let i = 0; i < arr.length; i++) {
      this._data[i + this._size] = arr[i] // 叶子结点
    }
    for (let i = this._size - 1; i > 0; i--) {
      this._data[i] = this._op(this._data[i << 1], this._data[(i << 1) | 1])
    }
  }

  toString(): string {
    const sb: string[] = []
    sb.push('SegmentTreePointUpdateRangeQuery(')
    for (let i = 0; i < this._n; i++) {
      if (i) sb.push(', ')
      sb.push(String(this.get(i)))
    }
    sb.push(')')
    return sb.join('')
  }
}

type E = {
  size: number
  preMax: number
  sufMax: number
  max: number
  leftChar: string
  rightChar: string
}

function longestRepeating(s: string, queryCharacters: string, queryIndices: number[]): number[] {
  const n = s.length
  const leaves: E[] = Array(n)
  for (let i = 0; i < n; i++) {
    leaves[i] = { size: 1, preMax: 1, sufMax: 1, max: 1, leftChar: s[i], rightChar: s[i] }
  }

  const seg = new SegmentTreePointUpdateRangeQuery<E>(
    leaves,
    () => ({
      size: 0,
      preMax: 0,
      sufMax: 0,
      max: 0,
      leftChar: '',
      rightChar: ''
    }),
    (a, b) => {
      const res = {
        size: a.size + b.size,
        leftChar: a.leftChar,
        rightChar: b.rightChar,
        preMax: 0,
        sufMax: 0,
        max: 0
      }
      if (a.rightChar === b.leftChar) {
        res.preMax = a.preMax
        if (a.preMax === a.size) res.preMax += b.preMax
        res.sufMax = b.sufMax
        if (b.sufMax === b.size) res.sufMax += a.sufMax
        res.max = Math.max(a.max, b.max, a.sufMax + b.preMax)
      } else {
        res.preMax = a.preMax
        res.sufMax = b.sufMax
        res.max = Math.max(a.max, b.max)
      }
      return res
    }
  )

  const res: number[] = Array(queryIndices.length)
  for (let i = 0; i < queryIndices.length; i++) {
    const pos = queryIndices[i]
    const char = queryCharacters[i]
    seg.set(pos, { size: 1, preMax: 1, sufMax: 1, max: 1, leftChar: char, rightChar: char })
    res[i] = seg.queryAll().max
  }
  return res
}

class SegmentTreeRangeUpdatePointGet<Id = number> {
  private readonly _n: number
  private readonly _size: number
  private readonly _height: number
  private readonly _lazy: Id[]
  private readonly _id: () => Id
  private readonly _composition: (f: Id, g: Id) => Id
  private readonly _equalsToId: (o: Id) => boolean
  private readonly _commutative: boolean

  /**
   * 区间修改,单点查询的线段树.
   * @param n 线段树的大小.
   * @param id 单位元.
   * @param composition 父结点`f`与子结点`g`的结合函数.
   * @param equals 判断两个值是否相等的函数.比较方式默认为`===`.
   * @param commutative 群的结合是否可交换顺序.默认为`false`.为'true'时可以加速区间修改.
   *
   * @alias DualSegmentTree
   */
  constructor(
    n: number,
    id: () => Id,
    composition: (f: Id, g: Id) => Id,
    equals: (a: Id, b: Id) => boolean = (a, b) => a === b,
    commutative = false
  ) {
    if (!equals(id(), id())) {
      throw new Error('equals must be provided when id() returns an non-primitive value')
    }

    let size = 1
    let height = 0
    while (size < n) {
      size <<= 1
      height++
    }
    const lazy = Array(size << 1)
    for (let i = 0; i < lazy.length; i++) lazy[i] = id()
    this._n = n
    this._size = size
    this._height = height
    this._lazy = lazy
    this._id = id
    this._composition = composition

    const identity = id()
    this._equalsToId = equals ? (o: Id) => equals(o, identity) : (o: Id) => o === identity
    this._commutative = commutative
  }

  get(index: number): Id {
    if (index < 0 || index >= this._n) return this._id()
    index += this._size
    for (let i = this._height; i > 0; i--) this._propagate(index >> i)
    return this._lazy[index]
  }

  /**
   * 将区间`[left, right)`的值与`lazy`作用.
   */
  update(start: number, end: number, lazy: Id): void {
    if (start < 0) start = 0
    if (end > this._n) end = this._n
    if (start >= end) return
    start += this._size
    end += this._size
    if (!this._commutative) {
      for (let i = this._height; i > 0; i--) {
        if ((start >> i) << i !== start) this._propagate(start >> i)
        if ((end >> i) << i !== end) this._propagate((end - 1) >> i)
      }
    }
    while (start < end) {
      if (start & 1) {
        this._lazy[start] = this._composition(lazy, this._lazy[start])
        start++
      }
      if (end & 1) {
        end--
        this._lazy[end] = this._composition(lazy, this._lazy[end])
      }
      start >>= 1
      end >>= 1
    }
  }

  toString(): string {
    const sb: string[] = []
    sb.push('SegmentTreeRangeUpdatePointGet(')
    for (let i = 0; i < this._size; i++) {
      this._propagate(i)
    }
    for (let i = this._size; i < this._size + this._n; i++) {
      if (i !== this._size) sb.push(',')
      sb.push(String(this._lazy[i]))
    }
    sb.push(')')
    return sb.join('')
  }

  private _propagate(k: number): void {
    if (this._equalsToId(this._lazy[k])) return
    this._lazy[k << 1] = this._composition(this._lazy[k], this._lazy[k << 1])
    this._lazy[(k << 1) | 1] = this._composition(this._lazy[k], this._lazy[(k << 1) | 1])
    this._lazy[k] = this._id()
  }
}

const BIGMOD = BigInt(1e9 + 7)

class Fancy {
  private readonly _seg: SegmentTreeRangeUpdatePointGet<[mul: bigint, add: bigint]> =
    new SegmentTreeRangeUpdatePointGet(
      1e5 + 10,
      () => [1n, 0n],
      (f, g) => [(f[0] * g[0]) % BIGMOD, (f[0] * g[1] + f[1]) % BIGMOD],
      (a, b) => a[0] === b[0] && a[1] === b[1]
    )
  private _length = 0

  append(val: number): void {
    this._seg.update(this._length, this._length + 1, [1n, BigInt(val)])
    this._length++
  }

  addAll(inc: number): void {
    this._seg.update(0, this._length, [1n, BigInt(inc)])
  }

  multAll(m: number): void {
    this._seg.update(0, this._length, [BigInt(m), 0n])
  }

  getIndex(idx: number): number {
    if (idx >= this._length) return -1
    return Number(this._seg.get(idx)[1])
  }
}

class SegmentTreeRangeUpdateRangeQuery<E = number, Id = number> {
  private readonly _n: number
  private readonly _size: number
  private readonly _height: number
  private readonly _data: E[]
  private readonly _lazy: Id[]
  private readonly _e: () => E
  private readonly _id: () => Id
  private readonly _op: (a: E, b: E) => E
  private readonly _mapping: (id: Id, data: E) => E
  private readonly _composition: (id1: Id, id2: Id) => Id
  private readonly _equalsToId: (o: Id) => boolean

  /**
   * 区间修改区间查询的懒标记线段树.维护幺半群.
   * @param nOrLeaves 大小或叶子节点的值.
   * @param operations 线段树的操作.
   */
  constructor(
    nOrLeaves: number | ArrayLike<E>,
    operations: {
      /**
       * 线段树维护的值的幺元.
       */
      e: () => E

      /**
       * 更新操作/懒标记的幺元.
       */
      id: () => Id

      /**
       * 合并左右区间的值.
       */
      op: (e1: E, e2: E) => E

      /**
       * 父结点的懒标记更新子结点的值.
       */
      mapping: (lazy: Id, data: E) => E

      /**
       * 父结点的懒标记更新子结点的懒标记(合并).
       */
      composition: (f: Id, g: Id) => Id

      /**
       * 判断两个懒标记是否相等.比较方式默认为`===`.
       */
      equalsId?: (id1: Id, id2: Id) => boolean
    } & ThisType<void>
  ) {
    const n = typeof nOrLeaves === 'number' ? nOrLeaves : nOrLeaves.length
    const { e, id, op, mapping, composition, equalsId } = operations
    if (!equalsId && !SegmentTreeRangeUpdateRangeQuery._isPrimitive(id())) {
      throw new Error('equalsId must be provided when id() returns an non-primitive value')
    }

    let size = 1
    let height = 0
    while (size < n) {
      size <<= 1
      height++
    }
    const data = Array(size << 1)
    for (let i = 0; i < data.length; i++) data[i] = e()
    const lazy = Array(size)
    for (let i = 0; i < lazy.length; i++) lazy[i] = id()
    this._n = n
    this._size = size
    this._height = height
    this._data = data
    this._lazy = lazy
    this._e = e
    this._id = id
    this._op = op
    this._mapping = mapping
    this._composition = composition

    const identity = id()
    this._equalsToId = equalsId ? (o: Id) => equalsId(o, identity) : (o: Id) => o === identity

    if (typeof nOrLeaves !== 'number') this.build(nOrLeaves)
  }

  set(index: number, value: E): void {
    if (index < 0 || index >= this._n) return
    index += this._size
    for (let i = this._height; i > 0; i--) this._pushDown(index >> i)
    this._data[index] = value
    for (let i = 1; i <= this._height; i++) this._pushUp(index >> i)
  }

  get(index: number): E {
    if (index < 0 || index >= this._n) return this._e()
    index += this._size
    for (let i = this._height; i > 0; i--) this._pushDown(index >> i)
    return this._data[index]
  }

  /**
   * 区间`[start,end)`的值与`lazy`进行作用.
   * 0 <= start <= end <= n.
   */
  update(start: number, end: number, lazy: Id): void {
    if (start < 0) start = 0
    if (end > this._n) end = this._n
    if (start >= end) return
    start += this._size
    end += this._size
    for (let i = this._height; i > 0; i--) {
      if ((start >> i) << i !== start) this._pushDown(start >> i)
      if ((end >> i) << i !== end) this._pushDown((end - 1) >> i)
    }
    let start2 = start
    let end2 = end
    for (; start < end; start >>= 1, end >>= 1) {
      if (start & 1) this._propagate(start++, lazy)
      if (end & 1) this._propagate(--end, lazy)
    }
    start = start2
    end = end2
    for (let i = 1; i <= this._height; i++) {
      if ((start >> i) << i !== start) this._pushUp(start >> i)
      if ((end >> i) << i !== end) this._pushUp((end - 1) >> i)
    }
  }

  /**
   * 查询区间`[start,end)`的聚合值.
   * 0 <= start <= end <= n.
   */
  query(start: number, end: number): E {
    if (start < 0) start = 0
    if (end > this._n) end = this._n
    if (start >= end) return this._e()
    start += this._size
    end += this._size
    for (let i = this._height; i > 0; i--) {
      if ((start >> i) << i !== start) this._pushDown(start >> i)
      if ((end >> i) << i !== end) this._pushDown((end - 1) >> i)
    }
    let leftRes = this._e()
    let rightRes = this._e()
    for (; start < end; start >>= 1, end >>= 1) {
      if (start & 1) leftRes = this._op(leftRes, this._data[start++])
      if (end & 1) rightRes = this._op(this._data[--end], rightRes)
    }
    return this._op(leftRes, rightRes)
  }

  queryAll(): E {
    return this._data[1]
  }

  /**
   * 树上二分查询最大的`end`使得`[start,end)`内的值满足`predicate`.
   * @alias findFirst
   */
  maxRight(start: number, predicate: (value: E) => boolean): number {
    if (start < 0) start = 0
    if (start >= this._n) return this._n
    start += this._size
    for (let i = this._height; i > 0; i--) this._pushDown(start >> i)
    let res = this._e()
    while (true) {
      while (!(start & 1)) start >>= 1
      if (!predicate(this._op(res, this._data[start]))) {
        while (start < this._size) {
          this._pushDown(start)
          start <<= 1
          if (predicate(this._op(res, this._data[start]))) {
            res = this._op(res, this._data[start])
            start++
          }
        }
        return start - this._size
      }
      res = this._op(res, this._data[start])
      start++
      if ((start & -start) === start) break
    }
    return this._n
  }

  /**
   * 树上二分查询最小的`start`使得`[start,end)`内的值满足`predicate`
   * @alias findLast
   */
  minLeft(end: number, predicate: (value: E) => boolean): number {
    if (end > this._n) end = this._n
    if (end <= 0) return 0
    end += this._size
    for (let i = this._height; i > 0; i--) this._pushDown((end - 1) >> i)
    let res = this._e()
    while (true) {
      end--
      while (end > 1 && end & 1) end >>= 1
      if (!predicate(this._op(this._data[end], res))) {
        while (end < this._size) {
          this._pushDown(end)
          end = (end << 1) | 1
          if (predicate(this._op(this._data[end], res))) {
            res = this._op(this._data[end], res)
            end--
          }
        }
        return end + 1 - this._size
      }
      res = this._op(this._data[end], res)
      if ((end & -end) === end) break
    }
    return 0
  }

  build(leaves: ArrayLike<E>): void {
    if (leaves.length !== this._n) throw new RangeError(`length must be equal to ${this._n}`)
    for (let i = 0; i < this._n; i++) this._data[this._size + i] = leaves[i]
    for (let i = this._size - 1; i > 0; i--) this._pushUp(i)
  }

  toString(): string {
    const sb: string[] = []
    sb.push('SegmentTreeRangeUpdateRangeQuery(')
    for (let i = 0; i < this._n; i++) {
      if (i) sb.push(', ')
      sb.push(String(this.get(i)))
    }
    sb.push(')')
    return sb.join('')
  }

  private _pushUp(index: number): void {
    this._data[index] = this._op(this._data[index << 1], this._data[(index << 1) | 1])
  }

  private _pushDown(index: number): void {
    const lazy = this._lazy[index]
    if (this._equalsToId(lazy)) return
    this._propagate(index << 1, lazy)
    this._propagate((index << 1) | 1, lazy)
    this._lazy[index] = this._id()
  }

  private _propagate(index: number, lazy: Id): void {
    this._data[index] = this._mapping(lazy, this._data[index])
    if (index < this._size) this._lazy[index] = this._composition(lazy, this._lazy[index])
  }

  private static _isPrimitive(
    o: unknown
  ): o is number | string | boolean | symbol | bigint | null | undefined {
    return o === null || (typeof o !== 'object' && typeof o !== 'function')
  }
}

const BIGMOD = BigInt(1e9 + 7)

class Fancy {
  private readonly _seg = new SegmentTreeRangeUpdateRangeQuery<
    [size: bigint, sum: bigint],
    [mul: bigint, add: bigint]
  >(1e5 + 10, {
    e() {
      return [1n, 0n]
    },
    id() {
      return [1n, 0n]
    },
    op(e1, e2) {
      return [e1[0] + e2[0], (e1[1] + e2[1]) % BIGMOD]
    },
    mapping(lazy, data) {
      return [data[0], (data[1] * lazy[0] + data[0] * lazy[1]) % BIGMOD]
    },
    composition(f, g) {
      return [(f[0] * g[0]) % BIGMOD, (f[0] * g[1] + f[1]) % BIGMOD]
    },
    equalsId(id1, id2) {
      return id1[0] === id2[0] && id1[1] === id2[1]
    }
  })

  private _length = 0

  append(val: number): void {
    this._seg.update(this._length, this._length + 1, [1n, BigInt(val)])
    this._length++
  }

  addAll(inc: number): void {
    this._seg.update(0, this._length, [1n, BigInt(inc)])
  }

  multAll(m: number): void {
    this._seg.update(0, this._length, [BigInt(m), 0n])
  }

  getIndex(idx: number): number {
    if (idx >= this._length) return -1
    return Number(this._seg.get(idx)[1])
  }
}