猫史档案馆

http://182.92.122.169:8765/work/jsp/showPRpage.jsp?pageId=0101

这题不会做！！！

序列

【题目描述】

小 D 有一个长度为 n 的整数序列 a_i（下标从 1 开始编号，下同），她想通过若干次操作把它变成序列 b_i。 
小 D 有 m种可选的操作，第 i 种操作可使用三元组 (t_i,u_i,v_i) 描述：若 t_i=1，则她可以使 a_ui 与 a_vi 都加一或都减一；若 t_i=2，则她可以使 a_ui-1、a_vi+1，或是 a_ui+1、a_vi-1，因此当 u_i=v_i 时，这种操作相当于没有操作。 
小 D 可以以任意顺序执行操作，且每种操作都可进行无限次。现在给定序列与所有操作，请你帮她判断是否存在一种方案能将 a_i 变为 b_i。题目保证两个序列长度都为 n。 若方案存在请输出 `YES`，否则输出 `NO`。

【输入格式】

从 sequence.in 读入数据。 

本题输入文件包含多组数据。 

第一行一个正整数 T 表示数据组数。对于每组数据： 

第一行两个整数 n,m，表示序列长度与操作种数。 

第二行 n 个整数表示序列 a_i。 

第三行 n 个整数表示序列 b_i。 

接下来 m 行每行三个整数 t_i,u_i,v_i，第 i 行描述操作 i。 

注意：同一个三元组 (t_i,u_i,v_i) 可能在输入中出现多次。 

【输出格式】

输出到文件 sequence.out 中。 

对于每组数据输出一行一个字符串 `YES` 或 `NO` 表示答案。

【样例1输入】

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

【样例1输出】

YES
YES
YES

【样例1解释】

第一组数据：使用一次操作 1。 第二组数据：使用三次操作 1。 第三组数据：使用三次操作 1，令 a₁,a₂ 都增加 3，再使用一次操作 2，令 a₁,a₃ 都增加 1。

【数据范围与提示】

对于测试点 1 - 5：n=2，m=1，a_i,b_i ≤ 99，u₁ ≠ v₁，t₁=1。
对于测试点 6 - 10：n=2，m=1，a_i,b_i ≤ 99，u₁ ≠ v₁，t₁=2。
对于测试点 11 - 12：n=2，a_i,b_i ≤ 99，u_i ≠ v_i。
对于测试点 13 - 16：t_i=2。
对于测试点 17：n,m ≤ 20。
对于测试点 18：n,m ≤ 1000。
对于所有测试点：1 ≤ T ≤ 10，1 ≤ n,m ≤ 10⁵，1 ≤ a_i,b_i ≤ 10⁹，t_i ∈ {1,2}，1≤ u_i,v_i≤ n。

 

【时间限制】

 

2.0s

 

【空间限制】

 

256MB