题目背景

小L开着TA的小掘金机，在广袤的平原上行驶着......

突然，TA发现了一个黄金矿洞！

题目描述

小L所在的这块土地，横截面共有 n*m 个土块。她现在位于（1,1）的位置，要去黄金的位置（ x,y ）。

在这个横截面上，有石块 ‘ s ’ ,这是小掘金机挖不开的。也有土壤，这是TA能挖开的，不过土壤是有不同类型的，它上面标的数值越高说明越难挖。小掘金机的初始电量为 t ，这个数值是随着挖掉的土壤的数值而不断减少的，也就是说，小掘金机的初始电量为50，挖掉一个数值为10的土块，电量就变成40了。

小L决定走一条耗电最少的路线，可是面对错综复杂的地形，TA无从下手。因此，TA来找你帮忙了。现在请你帮帮TA，为TA指明一条耗电最少的路线，走过的地方用“*”表示，并告诉她最终的剩余电量。

如果无论如何都到不了黄金的位置，就输出 “QwQ” 。

注意：如果在到达黄金的时候电量正好用完了，则算作小L到达了宝藏，不输出 “QwQ” 。

输入格式

输入共 n+1 行：

第一行输入5个正整数： n,m,x,y,t ;

随后 n 行，每行输入 m 个字符或数字。

输出格式

第一种情况

输出共 n+1 行： 第 1~n 行，每行输出 m 个字符或数字，表示耗电最少的路线； 第 n+1 行，输出一个正整数，表示最终电量。

第二种情况：

输出一个字符串： QwQ 。

样例 #1

3 3 3 3 50
1 s 2 
3 4 5 
s 2 3

* s 2
* * 5
s * *
37

样例 #2

3 3 3 3 50
1 s s
s s s
s s s

QwQ

提示

对于100%的数据，所有输入数据均<=1000。