在一个n*m（n，m <= 150) 的网格上，有一些格子是障碍的，并且网格边界上的格子均是障碍的，另有一个非障碍的格子是出口。一个机器人可以根据程序在该网格上行走。一段程序是一个由UDLR四种指令组成的字符串，机器人会依次执行每个命令，一个指令会使机器人向指定的方向移动一格，如果对应的格子为障碍则不动，现在给定一格长度为l（l <= 1e5)的程序，求它的一个最短前缀p，使得对于一开始的网格上任意非障碍位置都是机器人，在执行完程序p之后都停在出口上。