由于震惊海内外的 “愤怒门投毒事件” 的发生，部落为了对抗皇家药剂师协会的叛乱，所有的外交工作完成后，部落大酋长萨尔带领着小 A 穿过传送门到达幽暗城平叛。
幽暗城的地图是一个 的 串。 时表示 的位置是障碍，无法通过； 时表示 的位置可以进入。
小 A 与萨尔的初始位置是 ，而恐惧魔王的初始位置是 。小 A 的目标就是到达恐惧魔王的位置。
萨尔会按照一个特定的路线行走，该路线是一个数字串，由 组成。
第 秒，若数字串第（数字串的长度）位等于 ，则表示这一秒萨尔将会原地不动； 等于 ，则表示这一秒萨尔会向上走一格； 等于 ，则表示这一秒萨尔会向下走一格； 等于 ，则表示这一秒萨尔会向左走一格； 等于 ，则表示这一秒萨尔会向右走一格。
若萨尔将要移动的位置是墙或者超出迷宫的范围，则萨尔会原地不动。恐惧魔王也是这样。（换句话说，你可以认为如果将数字串是重复无限次，第 秒就是字符串第 位）
小 A 每秒可以选择从上下左右四个方向中选择一个方向，朝那个方向走一格，前提是那个位置不是墙并且没有超出迷宫的范围；或者原地不动。不过，由于幽暗城的诡异环境，小 A 只能持续脱离萨尔的光环 秒，若超过 秒小 A 则会死亡。光环的有效半径为 ，表示当小 A 与萨尔之间的距离 小于等于 时小 A 才能受到萨尔光环的效果。若小 A 脱离萨尔的光环又重新进入光环有效区域，则再次离开光环时持续时间归零重记。
小 A 想知道最少需要几秒他才能到达恐惧魔王所在的位置。
第一行四个数 。
接下来的 行，每行 个数（ 或 ），之间没有空格，表示幽暗城的地图。
接下来的一行四个整数，（，）。
接下来的一行是一个数字串，表示萨尔的移动方式。
接下来的一行是一个数字串，表示恐惧魔王的移动方式。
一行一个整数，表示需要最少的时间。
3 4 7 3 1010 0000 0101 1 2 3 3 0132401 12131
3
【题目来源】
kiro 原创
【数据范围】
对于 的数据，，，， 数字串长度 ， 答案 。
