练习1-div3-805-C

C. Train and Queries

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Along the railroad there are stations indexed from 11 to 109109. An express train always travels along a route consisting of nn stations with indices u1,u2,…,unu1,u2,…,un, where (1≤ui≤1091≤ui≤109). The train travels along the route from left to right. It starts at station u1u1, then stops at station u2u2, then at u3u3, and so on. Station unun — the terminus.

It is possible that the train will visit the same station more than once. That is, there may be duplicates among the values u1,u2,…,unu1,u2,…,un.

You are given kk queries, each containing two different integers ajaj and bjbj (1≤aj,bj≤1091≤aj,bj≤109). For each query, determine whether it is possible to travel by train from the station with index ajaj to the station with index bjbj.

For example, let the train route consist of 66 of stations with indices [3,7,1,5,1,43,7,1,5,1,4] and give 33 of the following queries:

• a1=3a1=3, b1=5b1=5

  It is possible to travel from station 33 to station 55 by taking a section of the route consisting of stations [3,7,1,53,7,1,5]. Answer: YES.

• a2=1a2=1, b2=7b2=7

  You cannot travel from station 11 to station 77 because the train cannot travel in the opposite direction. Answer: NO.

• a3=3a3=3, b3=10b3=10

  It is not possible to travel from station 33 to station 1010 because station 1010 is not part of the train's route. Answer: NO.

Input

The first line of the input contains an integer tt (1≤t≤1041≤t≤104) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case is empty.

The second line of each test case contains two integers: nn and kk (1≤n≤2⋅105,1≤k≤2⋅1051≤n≤2⋅105,1≤k≤2⋅105) —the number of stations the train route consists of and the number of queries.

The third line of each test case contains exactly nn integers u1,u2,…,unu1,u2,…,un (1≤ui≤1091≤ui≤109). The values u1,u2,…,unu1,u2,…,un are not necessarily different.

The following kk lines contain two different integers ajaj and bjbj (1≤aj,bj≤1091≤aj,bj≤109) describing the query with index jj.

It is guaranteed that the sum of nn values over all test cases in the test does not exceed 2⋅1052⋅105. Similarly, it is guaranteed that the sum of kk values over all test cases in the test also does not exceed 2⋅1052⋅105

Output

For each test case, output on a separate line:

• YES, if you can travel by train from the station with index ajaj to the station with index bjbj
• NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

Example

input

Copy

3

6 3
3 7 1 5 1 4
3 5
1 7
3 10

3 3
1 2 1
2 1
1 2
4 5

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

output

Copy

YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES

Note

The first test case is explained in the problem statement.

//双map记录坐标

#include
using namespace std;
const int N = 1e6;
int a[N];
int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int m;
        int k;
        cin >> m>>k;
        mapmp1,mp2;
        for (int i = 1; i <= m; i ++ )
        {
            cin >> a[i];
            if(!mp1[a[i]])
            {
                mp1[a[i]]=i;
            }
            mp2[a[i]]=i;
        }
        while (k -- )
        {
            int l,r;
            cin >> l>>r;
            if(mp1[l]==0||mp2[r]==0)
            cout << "NO"<