import scala.collection.mutable

object Main extends App {
  import scala.io.StdIn._


  val Array(h, w, l) = readLine.trim.split(' ').map(_.toInt)
  val state = Array.tabulate(h){_ ⇒ readLine.trim}
  val stage = new Stage(h, w, state)
  val start = new Stand(l, (0 until w).flatMap(x ⇒ (0 until h).find(y ⇒ state(y)(x) == 'S').map(y ⇒ Coordinate(x, y))).head)
  val switches = new Switches
  val minCost = Array.tabulate(h){_ ⇒ Array.tabulate(w){_ ⇒ Array.tabulate(3){_ ⇒ Array.tabulate(1 << 5){_ ⇒ Int.MaxValue}}}}
  val queue = mutable.PriorityQueue()(Ordering.by[(Block, Switches, Int), Int](_._3).reverse)
  minCost(start.position.y)(start.position.x)(start.typeId)(switches.toInt) = 0
  queue.enqueue((start, switches, 0))

  while(queue.nonEmpty && !stage.isGoal(queue.head._1)) {
    val (block, switch, cost) = queue.dequeue()
    if (minCost(block.position.y)(block.position.x)(block.typeId)(switch.toInt) == cost) {
      for (next ← block.neighbor if stage.canPut(next, switch)){
        val nextS = stage.put(next, switch)
        if (minCost(next.position.y)(next.position.x)(next.typeId)(nextS.toInt) > cost + 1){
          minCost(next.position.y)(next.position.x)(next.typeId)(nextS.toInt) = cost + 1
          queue.enqueue((next, nextS, cost + 1))
        }
      }
    }
  }
  println(
    if (queue.isEmpty) -1
    else queue.head._3
  )

  class Stage(val height: Int, val width: Int, private[this] val state: Array[String]) {
    def canPut(block: Block, switches: Switches): Boolean = {
      block.indices.forall{c ⇒
        (0 until width).contains(c.x) && (0 until height).contains(c.y) &&
          (state(c.y)(c.x) match {
          case '#' ⇒ false
          case '^' ⇒ !block.isStand
          case 'S' | 'G' ⇒ true
          case c if c.isLower ⇒ switches.isOn(c)
          case _ ⇒ true
        })
      }
    }
    def put(block: Block, switches: Switches): Switches = {
      if (block.isStand)
        state(block.position.y)(block.position.x) match {
          case 'S' | 'G' ⇒ switches
          case s if s.isUpper ⇒ switches.pushSwitch(s)
          case _ ⇒ switches
        }
      else switches
    }
    def isGoal(block: Block): Boolean = block.isStand && (0 until width).contains(block.position.x) && (0 until height).contains(block.position.y) && state(block.position.y)(block.position.x) == 'G'
  }
  class Switches(private[this] val flag: Int = 0) {
    def toInt = flag
    def pushSwitch(char: Char): Switches = new Switches(flag ^ (1 << (char - 'A')))
    def isOn(char: Char): Boolean = (flag & (1 << (char - 'a'))) != 0
  }
  sealed trait Block {
    def right: Block
    def left: Block
    def up: Block
    def down: Block
    def indices: Iterable[Coordinate]
    def isStand: Boolean = false
    def position: Coordinate
    def typeId: Int
    def neighbor: Iterable[Block] = List(right, left, up, down)
  }
  class Stand(private[this] val length: Int, val position: Coordinate) extends Block {
    override def right: Block = new Horizontal(length, position + Coordinate(1, 0))
    override def left: Block = new Horizontal(length, position - Coordinate(length, 0))
    override def up: Block = new Vertical(length, position - Coordinate(0, 1))
    override def down: Block = new Vertical(length, position + Coordinate(0, length))
    override def indices: Iterable[Coordinate] = Some(position)
    override def isStand: Boolean = true
    override def typeId: Int = 0
  }
  class Vertical(private[this] val length: Int, val position: Coordinate) extends Block {
    override def right: Block = new Vertical(length, position + Coordinate(1, 0))
    override def left: Block = new Vertical(length, position - Coordinate(1, 0))
    override def up: Block = new Stand(length, position - Coordinate(0, length))
    override def down: Block = new Stand(length, position + Coordinate(0, 1))
    override def indices: Iterable[Coordinate] = (0 until length).map(y ⇒ position - Coordinate(0, y))
    override def typeId: Int = 1
  }
  class Horizontal(private[this] val length: Int, val position: Coordinate) extends Block {
    override def right: Block = new Stand(length, position + Coordinate(length, 0))
    override def left: Block = new Stand(length, position - Coordinate(1, 0))
    override def up: Block = new Horizontal(length, position - Coordinate(0, 1))
    override def down: Block = new Horizontal(length, position + Coordinate(0, 1))
    override def indices: Iterable[Coordinate] = (0 until length).map(x ⇒ position + Coordinate(x, 0))
    override def typeId: Int = 2
  }
  case class Coordinate(x: Int, y: Int) {
    def +(that: Coordinate): Coordinate = Coordinate(x + that.x, y + that.y)
    def -(that: Coordinate): Coordinate = Coordinate(x - that.x, y - that.y)
  }
  implicit class Scope[T](val value: T) extends AnyVal{
    @inline
    def also(@inline func: T ⇒ Unit): T = {
      func(value)
      value
    }
    @inline
    def let[A](func: T ⇒ A): A = func(value)
  }
}


Measured memory_bytes: 119428