import scala.annotation.tailrec import scala.collection.immutable import scala.collection.immutable.TreeSet import scala.io.StdIn.readLine import scala.math.* import scala.annotation.tailrec object Patricia: private sealed trait Node: val prefix: Int private object Node: private def leftMostOne(value: Int): Int = var result = 0 for i <- Array(4, 3, 2, 1, 0) do if value >>> (result + (1 << i)) > 0 then result += 1 << i 1 << result private def apply(left: Node, right: Node): Node = val mask = -leftMostOne(left.prefix ^ right.prefix) val prefix = (left.prefix | right.prefix) & mask assert(mask == -(prefix & -prefix)) assert(left.prefix < right.prefix) assert(((left.prefix ^ right.prefix) & (mask << 1)) == 0 && ((left.prefix ^ right.prefix) & mask) != 0) Branch(prefix, left, right) def insert(node: Node, newValue: Int): Node = node match case Branch(prefix, left, right) => val mask = -(prefix & -prefix) << 1 assert(((left.prefix ^ right.prefix) & mask) == 0 && ((left.prefix ^ right.prefix) & -(prefix & -prefix)) != 0, s"prefix: ${prefix.toBinaryString}, left: ${left.prefix.toBinaryString}, right: ${right.prefix.toBinaryString}") if (prefix & mask) != (newValue & mask) then if prefix < newValue then Node(node, Leaf(newValue)) else Node(Leaf(newValue), node) else if newValue < (prefix & right.prefix) then val newLeft = insert(left, newValue) if newLeft eq left then node else Branch(prefix, newLeft, right) else val newRight = insert(right, newValue) if newRight eq right then node else Branch(prefix, left, newRight) case Leaf(prefix) => if prefix == newValue then node else if prefix < newValue then Node(node, Leaf(newValue)) else Node(Leaf(newValue), node) def erase(node: Node, value: Int): Option[Node] = node match case Branch(prefix, left, right) => val mask = -(prefix & -prefix) << 1 if (prefix & mask) != (value & mask) then Some(node) else if value < (right.prefix & prefix) then erase(left, value) match case Some(newLeft) => if newLeft eq left then Some(node) else Some(Node(newLeft, right)) case None => Some(right) else erase(right, value) match case Some(newRight) => if newRight eq right then Some(node) else Some(Node(left, newRight)) case None => Some(left) case Leaf(oldValue) => if oldValue == value then None else Some(node) @tailrec def minValue(node: Node): Int = node match case Branch(_, left, _) => minValue(left) case Leaf(prefix) => prefix def lowerBound(node: Node, value: Int): Option[Int] = node match case Branch(prefix, left , right) => val mask = -(prefix & -prefix) << 1 if (prefix & mask) < (value & mask) then None if (value & mask) < (prefix & mask) then Some(minValue(left)) else if value < (right.prefix & prefix) then Some(lowerBound(left, value).getOrElse(minValue(right))) else lowerBound(right, value) case Leaf(prefix) => if prefix < value then None else Some(prefix) def upperBound(node: Node, value: Int): Option[Int] = node match case Branch(prefix, left , right) => val mask = -(prefix & -prefix) << 1 if (prefix & mask) < (value & mask) then None else if (value & mask) < (prefix & mask) then Some(minValue(left)) else if value < (right.prefix & prefix) then Some(upperBound(left, value).getOrElse(minValue(right))) else upperBound(right, value) case Leaf(prefix) => if prefix <= value then None else Some(prefix) def copyToArray(node: Node, dest: Array[Int], position: Int): Int = node match case Branch(prefix, left, right) => copyToArray(right, dest, copyToArray(left, dest, position)) case Leaf(prefix) => dest(position) = prefix position + 1 private case class Branch(override val prefix: Int, val left: Node, val right: Node) extends Node private case class Leaf(override val prefix: Int) extends Node class Patricia private(private val root: Option[Patricia.Node], val size: Int): import Patricia.Node.* import Patricia.* def this() = this(None, 0) def inserted(value: Int): Patricia = root match case Some(r) => val newRoot = insert(r, value) if newRoot eq r then this else Patricia(Some(newRoot), size + 1) case None => Patricia(Some(Patricia.Leaf(value)), 1) def erased(value: Int): Patricia = root match case Some(r) => erase(r, value) match case Some(newRoot) => if newRoot eq r then this else Patricia(Some(newRoot), size - 1) case None => Patricia(None, 0) case None => this def lowerBound(value: Int): Option[Int] = root.flatMap(Node.lowerBound(_, value)) def upperBound(value: Int): Option[Int] = root.flatMap(Node.upperBound(_, value)) def toArray: Array[Int] = root match case Some(r) => val result = Array.fill(size){0} copyToArray(r, result, 0) result case None => Array() def +(value: Int): Patricia = inserted(value) def minAfter(value: Int): Option[Int] = lowerBound(value) @main def main = val Array(n, q) = readLine().split(' ').map(_.toInt) val s = readLine() val queries = Array.fill(q){ val Array(x, y) = readLine().split(' ').map(_.toInt - 1) min(x, y) -> max(x, y) } var stack = Nil: List[Int] val pair = Array.fill(n){-1} for (c, i) <- s.zipWithIndex do c match case '(' => stack ::= i case ')' => val h::t = stack pair(i) = h pair(h) = i stack = t val set = Array.fill(n){Patricia()} for i <- 0 until n do if i > 0 then set(i) = set(i - 1) if s(i) == '(' then set(i) = set(i) + pair(i) for (x, y) <- queries do val result = set(x).minAfter(y).map(right => s"${pair(right) + 1} ${right + 1}").getOrElse("-1") println(result)