一个 行列的网格，其中左上角是 ，右下角是 。

某些位置上存在一些镜子，镜子能将某个方向射来的光线折射 再射出。

镜子只有以下两种状态。

镜子位于主对角线（两端位于左上和右下）。此时它可以产生如下效果：

1、将上方射来的光线从右侧射出

2、将右侧射来的光线从上方射出

3、将左侧射来的光线从下方射出

4、将下方射来的光线从左侧射出

镜子位于副对角线（两端位于左下和右上）。此时它可以产生如下效果：

1、将上方射来的光线从左侧射出

2、将左侧射来的光线从上方射出

3、将右侧射来的光线从下方射出

4、将下方射来的光线从右侧射出

如下图，黑线代表位于副对角线的镜子，蓝线代表光线。



你可以花费一个代价将某一面镜子向任意方向旋转 °。

现在从格点 左侧射入一条光线，我们希望它能从格点 的右侧射出，请问最少要花费多少代价？

假设多条光线相交互不干扰。

第一行三个整数  ，分别表示网格的行数、列数、镜子的数量。

接下来  行，每行三个整数 。

其中  表示第  个镜子所在的位置坐标为， 表示该镜子位于主对角线（两端位于左上和右下）， 表示该镜子位于副对角线（两端位于左下和右上）。

输出让从  左侧射入的光线最终从  右侧射出的最小代价。

如果无法实现，输出 。

3 5 2
1 3 0
3 3 1

1

样例一的初始状态：



样例一的最终状态：