Given a sequence of integers a of length n, a tuple (i,j,k) is called monotone triples if 

  * 1 ≤ i<j<k≤ n; 
  * a_i ≤ a_j ≤ a_k or a_i ≥ a_j ≥ a_k is satisfied. 



For example, a=[5,3,4,5], then (2,3,4) is monotone triples for sequence a while (1,3,4) is not.

Bob is given a sequence of integers a of length n in a math exam. The exams itself contains questions of form L, R, for each of them he is asked to find any subsequence b with size greater than 2 (i.e. |b| ≥ 3) of sequence a_L, a_{L+1},…, a_{R}.

Recall that an sequence b is a subsequence of sequence a if b can be obtained by deletion of several (possibly zero, or all) elements.

However, he hates monotone stuff, and he wants to find a subsequence free from monotone triples. Besides, he wants to find one subsequence with the largest length among all subsequences free from monotone triples for every query.

Please help Bob find out subsequences meeting the above constraints.

Input

The first line contains two integers n, q (3 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ q ≤ 2 ⋅ 10^5) — the length of sequence a and the number of queries.

The second line contains n integers a_1,a_2,…, a_n (1 ≤ a_i ≤ 10^{9}), representing the sequence a.

Then each of the following q lines contains two integers L, R (1 ≤ L,R ≤ n, R-L≥ 2).

Output

For each query, output 0 if there is no subsequence b satisfying the constraints mentioned in the legend. You can print the empty line after but that's not mandatory.

Otherwise, output one integer k (k > 2) denoting the length of sequence b, then output k integers i_1, i_2, …, i_k (L ≤ i_1 < i_2<…<i_k≤ R) satisfying that b_j = a_{i_j} for 1 ≤ j ≤ k.

If there are multiple answers with the maximum length, print any of them.

Example

Input


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


Output


3
1 2 3 
0

Note

For the first query, the given sequence itself is monotone triples free.

For the second query, it can be shown that there is no subsequence b with length greater than 2 such that b is monotone triples free.
#define MST(a, b) memset(a,b,sizeof(a))
#define ALL(v) (v).begin(),(v).end()
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL,LL> pll;
#include <ext/pb_ds/priority_queue.hpp>
#define rep(i,a,b) for(int i = a ; i <= b ; ++i)
#define per(i,a,b) for(int i = a ; i >= b ; --i)
#define fors(i,S) for(int i = S ; i ; i = (i-1)&S)
#define forn(i,n) for(int i = 0 ; i < n ; ++i)

using namespace __gnu_pbds;
//typedef __gnu_pbds::priority_queue<pii, greater<pii>, pairing_heap_tag> heap;
//typedef heap::point_iterator iter;
typedef unsigned long long ULL;
//typedef __int128 LL128;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

int system_const;
namespace fast_IO{
    const int maxbuff = 1<<17;
    char ibuff[maxbuff],obuff[maxbuff];
    inline char Getchar(){
        static char *p1=ibuff,*p2=ibuff;
        if(p1 == p2) {
            p1 = ibuff;
            p2 = ibuff+fread(ibuff,1,maxbuff,stdin);
            if(p1 == p2) return -1;
        }
        return *p1++;
    }

    int optr = 0;
    inline void Putchar(char c) {
        if(optr == maxbuff) {fwrite(obuff,1,optr,stdout);optr = 0;}
        obuff[optr++] = c;
    }

    inline void Flush() {
        fwrite(obuff,1,optr,stdout);
    }

    template<class T>
    void read_number(T &x) {
        x = 0;
        char c;int f = 0;
        for(c = Getchar() ; c != '-' && (c < '0' || c > '9') ; c = Getchar());
        if(c == '-') f = 1;
        else x = c-'0';
        for(c = Getchar() ; c >= '0' && c <= '9' ; c = Getchar()) x = x*10+c-'0';
        if(f) x = -x;
    }

    void read_string(string &s) {
        s.clear();
        char c;
        for(c = Getchar() ; c == ' ' || c == '\n' ; c = Getchar());
        s.push_back(c);
        for(c = Getchar() ; c != ' ' && c != '\n' ; c = Getchar())
            s.push_back(c);
    }

    template<class T>
    void write_number(T &x) {
        static int dec[20];int len = 0;
        if(x == 0) {Putchar('0');return ;}
        if(x < 0) {Putchar('-');x = -x;}
        while(x) {
            dec[++len] = x%10;
            x /= 10;
        }
        while(len) Putchar(dec[len--]+'0');
    }

    void write_string(const string &s) {
        for(int i = 0 ;i < s.size() ; ++i)
            Putchar(s[i]);
    }
}
void read(string &s) {
    if(system_const == 0) {
        using namespace fast_IO;
        read_string(s);
    }
    else cin >> s;
}
template<class T> void read(T &x) {
    if(system_const == 0) {
        using namespace fast_IO;
        read_number(x);
    }
    else cin >> x;
}
void write(const string &s) {
    if(system_const == 0) {
        fast_IO::write_string(s);
    }
    else cout << s;
}
template<class T> void write(T &x) {
    if(system_const == 0) {
        fast_IO::write_number(x);
    }
    else cout << x;
}
void writeln(const string &s) {
    write(s);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar('\n');
    }
    else cout << endl;
}
template<class T> void writeln(T x) {
    write(x);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar('\n');
    }
    else cout << '\n';
}
void writesp(const string &s) {
    write(s);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar(' ');
    }
    else cout << ' ';
}

template<class T> void writesp(T x) {
    write(x);
    if(system_const == 0) {
        using namespace fast_IO;
        Putchar(' ');
    }
    else cout << ' ';
}
void set_program_type(int t = 0) {
    system_const = t;
    if(t) {
        ios::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
    }
}
void finish_program(int t = 0) {
    if(!t) fast_IO::Flush();
}

void init_all(int t = 0,string s = "output") {
#ifdef LOCAL
    if ((t >> 1) & 1) freopen("input", "r", stdin);
    if ((t >> 2) & 1) freopen(s.c_str(), "w", stdout);
#endif
}

template <int MOD=998244353, class T = int> struct Modular {
    T value;
    static const T MOD_value = MOD;

    Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
    Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

    Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
    Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
    Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

    friend Modular mexp(Modular a, long long e) {
        Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
        return res;
    }
    friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

    Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
    friend Modular operator+(Modular a, Modular const &b) { return a += b; }
    friend Modular operator-(Modular a, Modular const &b) { return a -= b; }
    friend Modular operator-(Modular const &a) { return 0 - a; }
    friend Modular operator*(Modular a, Modular const &b) { return a *= b; }
    friend Modular operator/(Modular a, Modular const &b) { return a /= b; }
    friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
    friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
    friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};



int pre_ask_time;
void show_time() {
    int now = clock();
    cout << now-pre_ask_time << endl;
    pre_ask_time = now;
}

template<class T> void cmin(T &x,const T&y) {if(x > y) x = y;}
template<class T> void cmax(T &x,const T&y) {if(x < y) x = y;}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

const int N = 2e5+19;

int a[N],n,q,vis[N];
int s1[N],s2[N],t1,t2;
int l3[N],l4[N],m3[N],m4[N],p1[N],p2[N];
vector<int> four[N],three[N];
set<int> st;

int find1(int x) {
    int l = -1 , r = t1;
    for(int mid = l+r>>1 ; l < r-1 ; mid = l+r>>1)
        if(a[s1[mid]] > x) l = mid;
        else r = mid;
    return l;
}

int find2(int x) {
    int l = -1 , r = t2;
    for(int mid = l+r>>1 ; l < r-1 ; mid = l+r>>1)
        if(a[s2[mid]] < x) l = mid;
        else r = mid;
    return l;
}

void push1(int p) {
    while(t1 && a[s1[t1-1]] < a[p]) {
        --vis[s1[t1-1]];
        if(!vis[s1[t1-1]]) st.insert(s1[t1-1]);
        --t1;
    }
    s1[t1++] = p;
    ++vis[p];
}

void push2(int p) {
    while(t2 && a[s2[t2-1]] > a[p]) {
        --vis[s2[t2-1]];
        if(!vis[s2[t2-1]]) st.insert(s2[t2-1]);
        --t2;
    }
    s2[t2++] = p;
    ++vis[p];
}

void solve() {
    read(n);read(q);
    rep(i,1,n) read(a[i]);
    p1[0] = p2[0] = -1;
    rep(i,1,n) {
        int x = find1(a[i]),y = find2(a[i]);
        p1[i] = x != -1 ? s1[x] : -1;p2[i] = y != -1 ? s2[y] : -1;
        if(x != -1 && y != -1) {
            int X = s1[x],Y = s2[y];
            auto p = st.lower_bound(min(X,Y));
            if(p != st.begin()) {
                four[i].push_back(*p);
                four[i].push_back(min(X,Y));
                four[i].push_back(max(X,Y));
                four[i].push_back(i);
                l4[i] = *p;
            }
        }
        if(x != -1 || y != -1) {
            if(x != -1) {
                int X = s1[x];
                if(p2[X] != -1) {
                    l3[i] = p2[X];
                    three[i].push_back(p2[X]);
                    three[i].push_back(X);
                    three[i].push_back(i);
                }
            }
            if(y != -1) {
                int Y = s2[y];
                if(p1[Y] != -1 && l3[i] < p1[Y]) {
                    l3[i] = p1[Y];
                    three[i].push_back(p1[Y]);
                    three[i].push_back(Y);
                    three[i].push_back(i);
                }
            }
        }
        push1(i);push2(i);
    }
    rep(i,1,n) {
        m3[i] = m3[i-1];
        m4[i] = m4[i-1];
        if(l3[i] && l3[i] >= l3[m3[i]]) m3[i] = i;
        if(l4[i] && l4[i] >= l4[m4[i]]) m4[i] = i;
    }
    rep(i,1,q) {
        int l,r;
        read(l);read(r);
        int p = m4[r];
        if(l4[p] >= l) {
            writeln(4);
            for(auto v : four[p]) writesp(v);
            fast_IO::Putchar('\n');
            continue;
        }
        p = m3[r];
        if(l3[p] >= l) {
            writeln(3);
            for(auto v : three[p]) writesp(v);
            fast_IO::Putchar('\n');
            continue;
        }
        writeln(0);
    }
}

signed main() {
    //srand((int)time(0));
    pre_ask_time = clock();
    init_all(3);
    //init();
    set_program_type(0);
//tmp::main();
//return 0;
    int T = 1;
    //read(T);
    //scanf("%d",&T);
    rep(i,1,T) {
        //printf("Case #%d: ",i);
        solve();
    }

    finish_program(0);

    return 0;
}