Desserts at Magnan

Mr. Blind and Stefano are best friends and they both study at the same university.

There are mainly two student canteens they can choose from: $\textcolor{red}{Crous}$ or $\textcolor{blue}{Magnan}$. Mr. Blind usually eats at $\textcolor{red}{Crous}$ while Stefano $-$ at $\textcolor{blue}{Magnan}$.

In this problem we will focus on Magnan, known for its friendly staff and delicious fruit-based desserts.

Mr. Blind and Stefano decided to eat at Magnan (to Blind's distress, as the $2$€ difference in price is tremendous) and have come to pick their desserts.

Like in Figure above, there are $N$ desserts given on a line.

For each dessert, we only care about its sweetness $S$ and its primary fruit ingredient $F$ (i.e. $S_i$ and $F_i$, for the $i$-th dessert on the line).

Stefano is pretty unpredictable when choosing his desserts but Mr. Blind found out there are exactly $Q$ preferences he will choose from.

A preference is given by the tuple $(l, r, k)$, where $[l, r]$ is the interval of how sweet the desserts must be, and $k$ is the amount of desserts that must be based on his favourite fruit, denoted by $P$.

Task

Given $N$, $P$, arrays $S$ and $F$ and the $Q$ preferences, find out for each one of them whether Mr. Blind can get an order that satisfies it.

Input data

The first line of the input file contains integers $N$ and $P$, the number of desserts and Stefano's favourite dessert.

The second line contains $N$ integers $S_0, S_1, \cdots, S_{N-1}$, representing the sweetness of each dessert.

The third line contains $N$ integers $F_0, F_1, \cdots, F_{N-1}$, representing the main fruit ingredient of each dessert.

The fourth line contains a single integer $Q$, the number of preferences.

Each of the following $Q$ lines contain three integers, $l_i$, $r_i$, $k_i$, with their meaning explained above.

Output data

The output file must contain $Q$ lines, each consisting of a single string: the $i$-th line must be YES if Mr. Blind can find a suitable order for the $i$-th preference, and NO otherwise.

Constraints and clarifications

• $1 \leq N \leq 10^5$.
• $1 \leq P \leq 10^9$.
• $\vert S_i \vert \leq 10^6$ for each $i = 0, \cdots, N - 1$.
• $1 \leq F_i \leq 10^9$, for each $i = 0, \cdots, N - 1$.
• $1 \leq Q \leq 10^5$.
• $-10^6 \leq l \leq r \leq 10^6$, for each preference.
• $1 \leq k \leq N$, for each preference.

Example 1

stdin

7 3
4 5 7 4 5 3 3
3 2 3 1 6 5 3
3
1 9 2
3 6 2
3 6 3

stdout

YES
YES
NO

Explanation

In the first sample case, we know that $N = 7$, $P = 3$, $S = [4, 5, 7, 4, 5, 3, 2]$ and $F = [3, 2, 3, 1, 6, 5, 3]$.

For the first preference, because $l = 1$ and $r = 9$, we notice that any order that has $k = 2$ desserts which use $P$ as an ingredient is a valid order. As such, for example, the orders given by indices $\{0, 2\}$, $\{0, 5, 6\}$ and $\{1, 2, 6\}$ are all suitable orders for this preference, so the answer is YES. These are not the only valid orders.

For the second preference, one possible order is $\{0, 1, 3, 6\}$.

For the third preference, one can notice that there are only $3$ desserts that use $P$, one of them being too sweet. Thus, there are no orders, so the answer is NO.

Example 2

stdin

10 9
10 -2 -8 -6 -7 5 0 3 -8 -5
9 9 9 13 9 9 9 9 12 12
5
-4 -3 6
-5 0 4
-7 -4 3
-9 -7 4
0 4 2

stdout

NO
NO
NO
NO
YES

Explanation

In the second sample case, notice that the sweetness of desserts can also be negative.