import java.io.BufferedReader import scala.annotation.tailrec import scala.collection.{immutable, mutable} import scala.io.StdIn.readLine import scala.math.* import scala.annotation.tailrec import scala.io.{BufferedSource, StdIn} def readLine()(using reader: BufferedReader): String = reader.readLine() @main def main = given reader: BufferedReader = scala.io.Source.stdin.bufferedReader() 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) } val stack = mutable.ArrayDeque[Int]() val pair = Array.fill(n){-1} for (c, i) <- s.zipWithIndex do c match case '(' => stack.addOne(i) case ')' => val h = stack.removeLast() pair(i) = h pair(h) = i 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") )