CF241F Race

老城是一个矩形城市，表示为m×n块网格。这座城市包含许多建筑物、笔直的双向街道和路口。每个路口和每个建筑物都恰好是一个街区。所有的街道都有一个街区的宽度，可以是垂直的，也可以是水平的。每条街的两边都有一个路口。当且仅当它们共享一个公共边时，我们才称两个块相邻。没有两个不同街道的街区是相邻的，也没有两个路口是相邻的。 每年都有一个节日，作为节日的一部分，Peykan 沿着城市的一条特殊路径走。这条路径从街道的一个街区开始，经过许多交叉路口，并在某个街道的一个街区结束。对于每个街区，我们知道 Peykan 从这个街区到相邻街区需要多长时间。此外，Peykan 可以在一分钟内从每个路口到达其相邻的街区。 我们知道 Peykan 的初始位置以及它到达目的地所经过的路口序列。经过所有的路口，到达目的地后，它会永远停留在那里。你的任务是找出 Peykan 开始移动 k 分钟后会在哪里。 考虑到 Peykan 总是遵循通过给定交叉路口序列并到达目的地的最短路径。 请注意，Peykan 可能会多次访问某些街区。

输入的第一行包含三个整数 m , n 和 k (3

一行,输出2个整数$ r_{f} $ 和 $ c_{f} $ — ( $ r_{f},c_{f} $ )正好是 Peykan 第k分钟的位置。 ## 样例 #1 ### 样例输入 #1 ``` 3 10 12 ########## #z1a1111b# ########## 2 3 ab 2 8 ``` ### 样例输出 #1 ``` 2 8 ``` ## 样例 #2 ### 样例输入 #2 ``` 10 3 5 ### #w# #1# #a# #1# #1# #1# #1# #b# ### 3 2 abababababababab 6 2 ``` ### 样例输出 #2 ``` 8 2 ``` ## 样例 #3 ### 样例输入 #3 ``` 3 10 6 ########## #z1a1311b# ########## 2 3 ab 2 8 ``` ### 样例输出 #3 ``` 2 7 ```