#P4500. 矩阵

    ID: 3737 传统题 1000ms 512MiB 尝试: 631 已通过: 279 难度: 4 上传者: 标签>难度分类普及+/提高-数据结构带权并查集路径压缩按大小合并CF1600

矩阵

矩阵

题目描述

有一个 n×mn\times m 的矩阵,初始每个格子的权值都为 00。每次可以执行以下两种操作之一。

  1. 选择一行,将这一行每个格子的权值同时加 11 或同时减 11。
  2. 选择一列,将这一列每个格子的权值同时加 11 或同时减 11。

现在有 kk 个限制。每个限制 (x,y,c)(x,y,c) 要求矩阵第 xx 行第 yy 列的格子最终权值恰好为 cc。判断是否存在一串操作,使所有限制同时成立。

输入格式

第一行输入整数 TT,表示数据组数,满足 1≤T≤51\le T\le 5。

每组数据的第一行输入三个整数 n,m,kn,m,k,满足 1≤n,m,k≤10001\le n,m,k\le 1000。

接下来 kk 行,每行输入三个整数 x,y,cx,y,c,其中 1≤x≤n1\le x\le n,1≤y≤m1\le y\le m。cc 可以是负数。

输出格式

每组数据输出一行。若能满足所有限制,输出 Yes,否则输出 No。

样例

2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 1
Yes
No