题目背景

「興味がないこと本気じゃないもの全部後回しで」

「知ってることは知らんぷり 私は終わってる」

「恥ずかしい過去知ってるやつらの記憶消させて」

「迷惑かけてごめんってば ねえ誰か助けて」

题目描述

给定一个长为 $n$ 的整数序列 $h_i$，再给定 $n$ 个二元组 $(a_i,b_i)$，和一个正整数 $k$。

对于每个位置 $p$，你可以进行如下操作之一：

• 激活位置 $p$，选择一个位置 $j$ 满足 $1\le j-p\le k$，然后令 $h_p \leftarrow h_p + a_p$、$h_j \leftarrow h_j - b_p$。每个位置最多激活一次。

• 不激活位置 $p$。

有 $q$ 次询问 $(l_i,r_i,x_i)$，表示在只能激活位置 $p\in[l_i,r_i]$，且对应的 $j\in [p+1,\min(p+k,r_i)]$ 的条件下，可以选择多个位置激活，问此时是否存在一种激活方式使得 $\max_{t=l_i}^{r_i}h_t\le x_i$。

询问之间互相独立，即每次询问开始时序列 $h$ 被恢复到原始状态，每个位置均未选择操作方式。

输入格式

本题有多组测试数据。输入的第一行两个整数 $c,T$，分别表示子任务编号和测试数据组数，接下来输入每组测试数据。样例满足 $c=0$。

对于每组测试数据：

• 第一行，三个整数 $n,q,k$，分别表示序列长度、询问次数和激活的限制参数。
• 第二行，$n$ 个整数 $h_1,h_2,\ldots,h_n$。
• 第三行，$n$ 个整数 $a_1,a_2,\ldots,a_n$。
• 第四行，$n$ 个整数 $b_1,b_2,\ldots,b_n$。
• 接下来 $q$ 行，第 $i$ 行三个整数 $l_i,r_i,x_i$，分别表示询问的区间和最大值限制。

输出格式

对于每个询问输出 Yes 或 No，表示是否存在一种方案满足要求。

样例

0 1
3 2 1
2 0 2
4 1 1
0 8 0
2 3 1
1 3 1

Yes
No

样例 1 解释

对于询问 $(2,3,1)$，可以激活位置 $2$，令 $h_2 \leftarrow h_2 + a_2$、$h_3 \leftarrow h_3 - b_2$，最后的 $h$ 的区间 $[2,3]$ 为 $1,-6$，最大值为 $1$，符合要求。

对于询问 $(1,3,1)$，可以证明没有合法的操作方案。

0 2
7 7 3
4 1 2 2 3 2 2
4 1 4 0 3 2 1
3 3 4 1 3 3 0
5 5 4
3 4 5
1 4 3
2 5 0
1 2 3
1 4 5
1 3 4
7 7 3
5 2 1 5 2 5 2
4 2 1 4 3 1 2
1 5 3 4 1 5 1
6 7 5
1 4 5
2 4 5
5 7 5
1 2 5
3 4 5
2 6 5

Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

数据范围

本题使用子任务捆绑。

对于所有测试数据，$1 \le T \le 3$，$1 \le n \le 2 \times 10^4$，$1\le q \le 10^5$，$0\le h_i,a_i,b_i,x_i \le 10^6$，$1\le l_i \le r_i \le n$，$1\le k \le 5$。

子任务编号	$n\le$	$q \le$	$k \le$	$T \le$	特殊性质	分值	时限
$1$	$10$		$5$	$3$	无	$5$	1.5 s
$2$	$1000$			$1$		$10$
$3$	$2\times 10^4$	$10^5$		$3$	A		6 s
$4$	$10^4$		$3$	$1$	B	$5$	1.5 s
$5$					无	$10$
$6$	$2\times 10^4$	$2\times 10^4$	$4$		B	$5$
$7$					无	$10$
$8$		$4\times 10^4$		$2$	B	$5$
$9$					无	$10$
$10$		$10^5$	$5$	$3$		$30$	6 s

• 特殊性质 A：$\forall 1 \le i \le q,l_i=1,r_i = n$。
• 特殊性质 B：$\forall 1 \le i,j \le q,x_i = x_j$。

提示

请注意本题特别的时间限制。