import scala.annotation.tailrec import scala.collection.{immutable, mutable} import scala.io.StdIn.readLine import scala.math.* import scala.annotation.tailrec @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 result = Array.fill(q){"-1"} val set = mutable.TreeSet[Int]() var last = 0 for ((x, y), i) <- queries.zipWithIndex.sortBy(_._1) do while last <= x do if s(last) == '(' then set.addOne(pair(last)) last += 1 set.minAfter(y) match case Some(right) => result(i) = s"${pair(right) + 1} ${right + 1}" case None => println( result.mkString("\n") )