Echoes Under New Names

Time limit: 2500 msMemory limit: 256 MB

An archive contains a row of $N$ plaques. Plaque $i$ carries the integer emblem $A_i$ . The actual numbers assigned to emblems are arbitrary; only their pattern of repetition matters.

Two sequences of equal length,

$X_1, X_2, \ldots, X_k$

and

$Y_1, Y_2, \ldots, Y_k,$

are relabel-equivalent if there is a bijection $f$ between the distinct values occurring in the first sequence and the distinct values occurring in the second sequence such that

$f(X_i)=Y_i \quad \text{for every } 1 \le i \le k.$

In other words, every occurrence of one emblem must be renamed consistently, and different emblems must receive different new names.

For each query, you are given $x$ , $y$ , and $k$ . Determine whether the segments

$A_x, A_{x+1}, \ldots, A_{x+k-1}$

and

$A_y, A_{y+1}, \ldots, A_{y+k-1}$

are relabel-equivalent. The two segments may overlap, and a new bijection may be chosen independently for each query.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N,Q \le 2 \times 10^5$ ), the number of plaques and the number of queries.

Output

For each of the $Q$ queries, print YES if the two specified length- $k$ segments are relabel-equivalent. Otherwise, print NO.

Samples

Sample 1

Input

10 6
10 20 10 30 7 8 7 9 9 7
1 5 4
2 5 4
5 7 3
6 8 2
2 6 3
8 9 2

Output

YES
NO
NO
NO
YES
NO

The first and fifth queried pairs are relabel-equivalent. For the first pair, the renaming $10 \mapsto 7$ , $20 \mapsto 8$ , and $30 \mapsto 9$ is valid. In the fifth pair, both segments contain three distinct emblems. Each remaining pair has positions that are equal in one segment but unequal in the other.

Echoes Under New Names

Input

Output

Samples

Sample 1

Submit

Submissions