Description

Given an integer sequence $h_i$ of length $n$, along with $n$ pairs $(a_i, b_i)$ and a positive integer $k$.

For each position $p$, you can perform one of the following operations:

• Activate position $p$: Choose a position $j$ satisfying $1 \le j - p \le k$, then update $h_p \leftarrow h_p + a_p$ and $h_j \leftarrow h_j - b_p$. Each position can be activated at most once.
• Do not activate position $p$.

There are $q$ queries $(l_i, r_i, x_i)$. For each query, under the constraints that only positions $p \in [l_i, r_i]$ can be activated and the corresponding $j$ must lie within $[p+1, \min(p+k, r_i)]$, determine whether there exists a way to activate positions such that $\max_{t=l_i}^{r_i} h_t \le x_i$.

Queries are independent: the sequence $h$ is restored to its original state at the start of each query, and no activation choices are retained between queries.

Input Format

Multiple test cases.
The first line contains two integers $c$ and $T$, representing the subtask number and the number of test cases, respectively. Sample inputs satisfy $c=0$.

For each test case:

• The first line contains three integers $n, q, k$, representing the sequence length, number of queries, and activation range parameter.
• The second line contains $n$ integers $h_1, h_2, \ldots, h_n$.
• The third line contains $n$ integers $a_1, a_2, \ldots, a_n$.
• The fourth line contains $n$ integers $b_1, b_2, \ldots, b_n$.
• The next $q$ lines each contain three integers $l_i, r_i, x_i$, describing the $i$-th query.

Output Format

For each query, output Yes or No indicating whether a valid activation scheme exists.

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

Yes
No

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

Hint

Explanation #1

Sample 1 Explanation:

For the query $(2, 3, 1)$, activating position $2$ updates $h_2$ to $0 + a_2 = 1$ and $h_3$ to $2 - b_2 = 2 - 8 = -6$. The maximum value in $[2, 3]$ is $1$, satisfying the condition.

For the query $(1, 3, 1)$, no valid activation exists.

Constraints

This problem uses subtask scoring.

For all test data: $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$.

• Special Property A: For all queries, $l_i = 1$ and $r_i = n$.
• Special Property B: For all queries, $x_i = x_j$ for any $i, j$.

Note: Be mindful of the problem's time limits.

Translated by DeepSeek R1