题目描述

天顶星人设下了无数的陷阱,魔法世界的一支侦察小分队就落到了一个 迷宫陷阱之中,现在，小分队要从一个$\red{m}$列$\red{n}$行的迷宫中逃走,有$\red{p}$个石柱,另有$\red{b}$ 只吸血蝙蝠。

蝙蝠分三种类型:

$\red{(1)}$当蝙蝠前方遇到石柱或墙,向左转。

$\red{(2)}$当編蝠前方遇到石柱或墙,向后转。

$\red{(3) }$当蝙蝠前方遇到石柱或墙,向右转。

人可以向上、下、左、右四个方向移动或在原位置等待,人运动一格或等待,都 花费一个单位时间。在一个单位时间内,蝙蝠和人可以同时移动,蝙蝠也可以向上、 下、左、右四个方向移动或旋转，注意旋转不花时间,也就是说蝙蝠和人都可以先旋 转再移动。同一时刻,人和蝙蝠在同一地点时,人死亡。人和蝙蝠可以互相穿过， 且蝙蝠可以重叠。

现在从$\red{(1,1)}$逃到$\red{(m,n),}$仅有$\red{(m+n- 1)}$单位时间，问在该时间内共有几种 逃亡路线。

注:在第$\red{1}$个时刻,人进入$\red{(1,1),}$蝙蝠赋初始状态，在第$\red{(m+n-1)}$时刻,人要到 达$\red{(m,n)}$。

若初始状态中蝙蝠与石柱重合，则认为蝙蝠在石柱上休息,不会动。

输入格式

输入文件第$\red{1}$行为$\red{m,n}$;

第$\red{2}$行为石柱个数$\red{p}$;以下$\red{p}$行,每行两个整数,分别为 石柱的横、纵坐标，

第$\red{p+3}$行,为蝙蝠数$\red{b,}$以下$\red{b}$行，每行四个整数,分别为蝙蝠的 横、纵坐标,蝙蝠方向$\red{d(}$上为$\red{1,}$左为$\red{2,}$下为$\red{3,}$右为$\red{4)}$。以及煽蝠类型$\red{t}$用$\red{1,2,3}$表示。

$\red{2≤}$$\red{m≤}$$\red{100}$; $\red{2≤}$$\red{n≤}$$\red{100}$; $\red{0≤}$$\red{p≤}$$\red{100}$; $\red{0≤}$$\red{b≤}$$\red{100}$

输出格式

仅一行,为逃脱的方法数,若无解则输出$\red{0}$。

样例

输入样例

3 3
1
1 2
1
2 3 1 1

输出样例

3