seuOJ290 - 格雷矩阵

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2020

题目描述

Grey 是一个聪明的小姑娘，热爱思考的她有一天发明了一个奇妙的矩阵并命名为 Grey 矩阵。Grey 矩阵满足在矩阵中每一行和每一列都是等差数列。

这样的矩阵有很多奇妙的性质，她发现了 $10086$ 条奇妙的性质里，有这样几条奇妙的性质：(相信聪明的你也早已发现了这几条性质)

1. 某一行或者某一列中如果知道了两个位置的元素的值，则这一行或者这一列的每一个位置的值就完全确定了。
2. 如果一个矩阵中有两行(列)都确定了，则每一列(行)已经确定了至少两个元素，每一列(行)也可以确定，则整个矩阵也可以确定了。

啊，聪明的 Grey 发现，运用上面这两条规律，如果可以选择位置，只需要用知道四个元素的值就可以确定整个矩阵每一个位置的值，特别地，如果这个矩阵其中行数和列数中的较小值为 $1$，则可以用小于 $4$ 个元素的值得到。

但聪明的 Grey 自然不会让你如愿地这么轻易解决这个问题，所以并不能给你选择位置，而是随机告诉你矩阵中四个位置的值。

那么，根据 Grey 给定的四个位置的值你可以确定这个矩阵每个位置的值吗？

输入格式

第一行一个整数 $T(1\leq T\leq 10^5)$ 表示测试数据组数。

每组测试数据有 $5$ 行信息：

• 第一行共两个整数 $n,m(1\leq n,m\leq 10^9,nm\geq 4)$ 表示矩阵的大小。
• 接下来 $4$ 行中第 $i$ 行有三个整数 $x_i,y_i,num_i(1\leq x_i\leq n,1\leq y_i\leq m,0<num_i<10^9)$ 其中 $x_i,y_i$ 为整数表示第 $i$ 个给定元素的位置下标，$num_i$ 表示该元素的值。

输出格式

对于每一组数据输出一行一个整数，不能确定所有位置的值是请输出 $0$，否则请输出 $1$。

样例

样例输入

2
2 2
1 1 1
1 2 1
2 1 2
2 2 2
2 4
1 1 1
1 2 2
1 3 3
1 4 4 

样例输出

1
0

补充说明

给定的四个点中可能出现重复的点