时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
转眼间，旅行者的异世界之旅已经进行了
天，终于即将踏入须弥的土地。众所周知，须弥是一个智慧的国度，旅行者觉得自己智商有点不够用（应急食品派蒙也帮不上什么忙）。于是拜托摩拉克斯联系到了小吉祥草王，希望能提前得到更多的锻炼。在得知今天是5月29日是丘丘人的某传统节日后，小吉祥草王决定用丘丘人庆祝活动中的一个游戏来考查旅行者。小吉祥草王寄来的描述丘丘人庆祝活动中的信如下（似乎有很多嘈杂的声音）：
Eleka mimi-a-Domu,Mita domu-a-dada,La-la-la,La-la-la...Mimi mosi ye mita.
Mi muhe mita nye,Mi muhe mita nye,Muhe nye,Muhe nye,Gusha,Biat, gusha.
Nini movo muhe yoyo,Nini movo mimi tomo,Lata movo mosi yoyo,Celi movo celi yoyo.
Mimi movo,Mimi sada,Mimi domu,Domu upa,Gusha dada.
（以下省略
个字）
读完这封信，旅行者得知了游戏的玩法：裁判丘丘萨满给出了一个 
的方格矩阵，每名丘丘人需要从矩阵的左上角出发，到达右下角（左上角坐标为)
，右下角坐标为)
），丘丘人智商很低，它只会朝着终点前进（也就是说只会向下或向右走）。每个方格都有一个得分，到达该方格的丘丘人会将该得分累计到总得分中，最终总得分最高的丘丘人获胜。由于该游戏过于单调无趣，小吉祥草王决定在上面矩阵中增加两种特殊的方格：
- 第一种特殊格子会先加上当前位置得分，然后总得分减半(向下取整)。
- 第二种特殊格子会使得当前格子的得分变为当前格子权值乘以走过的格子数（走过的格子数包括当前格子）
由于上述格子过于特殊，小吉祥草王规定每种特殊格子只能经过一次。如果多走了特殊格子，那么会直接输掉游戏！
该游戏是轮流制，每名丘丘人有且仅有一次机会，最终得分最多的那个丘丘人可以赢得超级大奖。小吉祥草王要求旅行者混入丘丘群尽最大可能去赢得游戏，拿走超级大奖——十枚日落果。旅行者需要屏幕前你的帮助！
输入描述:
第一行两个整数，代表矩阵的行数和列数。
第二行到第行，每行
个整数，代表每个位置的分数
，以空格隔开。
第行一个整数
代表特殊格子的个数。
接下来行，每行三个整数
，分别代表特殊格子的种类以及该特殊方格的位置，以空格隔开。
输出描述:
如果旅行者能够成功到达终点，则输出他能够得到的最大分数；否则输出"gusha!"。
备注:
题目保证每个位置要么是普通方格，要么只属于一种特殊方格。