arthalter 正在游玩《生化危机 9：安魂曲》，并扮演格蕾丝在一座疗养院中寻找逃生路线。
疗养院内部不仅有封锁区域与权限门，还存在会改变局部通行条件的电源装置。
疗养院可以看作一个 的网格。
你初始位于起点 S，目标是到达终点 T。每一步你可以向上、下、左、右四个方向移动一格，前提是目标格子在网格内，且当前可以进入。
地图中可能出现以下类型的格子：
S：起点。
T：终点。
.：空地，可以进入。
#：墙，不能进入。
a ~ e：权限卡。
A ~ E：权限门，只有在已经获得对应小写字母权限卡后才能进入。
0：仅在断电状态下才能进入。
1：仅在通电状态下才能进入。
P：电源切换器。每次进入该格子后，当前的供电状态会立刻翻转一次。
疗养院初始处于断电状态。
初始时你不持有任何权限卡。若你进入一个权限卡格子，则会立刻获得对应权限卡，并在之后永久持有。获得权限卡后，该格子仍可重复经过，但不会产生额外效果。
需要注意的是：
0 或 1。
P 本身始终可以进入；当你进入 P 后，供电状态才会翻转。
S、T、.、权限卡格子均不受供电状态影响。
请输出从 S 到 T 的最少步数。如果无法到达，输出 -1。
第一行包含三个整数 n,m,k，分别表示网格的行数、列数，以及地图中可能出现的权限卡种类数。
接下来 n 行，每行一个长度为 m 的字符串，表示疗养院地图。
保证：
输出一个整数，表示从 S 到 T 的最少步数。
如果无法到达，输出 -1。