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.
#ifdef LOCAL
    #define _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG_PEDANTIC
#endif
//#define Y_CONTEST
//#define TIMUS
#ifndef Y_CONTEST
    #pragma GCC target("avx2")
#else
    #pragma GCC target("sse4")
#endif
#ifndef LOCAL
    #pragma GCC optimize("Ofast,unroll-loops")
    #pragma GCC optimize("unroll-all-loops")
#endif
#include <bits/stdc++.h>
#include <immintrin.h>
#ifdef IACA
    #include <iacaMarks.h>
#endif
//#define FILENAME "parties"
#ifndef TIMUS
    #include <ext/rope>
    #include <ext/pb_ds/assoc_container.hpp>
#endif // TIMUS
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb emplace_back
#define pii pair<int, int>
#define unires(x) x.resize(unique(all(x)) - x.begin())
#define ll long long

typedef long double ld;

const int INF = INT_MAX / 2;
const ll LINF = (ll)2e18 + 666, M1 = 1e9 + 7, M2 = 1e9 + 9, M = 998244353;

#ifndef M_PI
    const ld M_PI = acos(-1);
#endif // M_PI

using namespace std;

#ifndef TIMUS
    using namespace __gnu_cxx;
    using namespace __gnu_pbds;

    template<class K, class T, class Cmp = less<K>>
    using ordered_map = tree<K, T, Cmp, rb_tree_tag, tree_order_statistics_node_update>;

    template<class T, class Cmp = less<T>>
    using ordered_set = ordered_map<T, null_type, Cmp>;
#endif

void run();

template<class T1, class T2>
inline bool mini(T1 &a, T2 b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

template<class T1, class T2>
inline bool maxi(T1 &a, T2 b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

mt19937 rnd(0);

signed main() {
    #if defined FILENAME && !defined STDIO && !defined LOCAL
        freopen(FILENAME".in", "r", stdin);
        freopen(FILENAME".out", "w", stdout);
    #endif // FILENAME
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef LOCAL
        int temp, *ptr = new int;
        rnd.seed(time(0) ^ hash<string>()(__FILE__) ^ hash<string>()(__TIME__) ^
        temp ^ reinterpret_cast<size_t>(ptr) ^ 
        hash<string>()(
            string("ksdhfkshdfkshdfhdfkshdf") +
            "fdskhjfhsdkfhsdkfhsdkfjfsdhkjfhksdfhskdfhskdhfksdhfksdhfddjff" +
            "Hack my random, if you can!"));
    #endif
    cout << setprecision(11) << fixed;
    #ifdef PRINTTIME
        auto start = clock();
    #endif
    run();
    #ifdef PRINTTIME
        cout << "\ntime = " << (double)(clock() - start) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

#define rand rnd

template<ll Mod = M, class T = ll>
struct mod {
    T operator()(T x, T y) {
        return x * y % Mod;
    }
};

template<class T, ll Mod>
inline T identity_element(mod<Mod, T>) {
    return T(1);
}

template<class T>
struct is_continer {
 private:
    static void detect(...);
    template<class U>
    static decltype(declval<U>().begin()) detect(const U&);
 public:
    static const bool value = !is_same<decltype(detect(declval<T>())), void>::value;
};

template<class T>
struct is_std_array {
    static const bool value = 0;
};

template<class T, size_t sz>
struct is_std_array<array<T, sz>> {
    static const bool value = 1;
};

template<class T>
typename enable_if<is_continer<T>::value && !is_same<T, string>::value, ostream>::type&
operator<<(ostream &out, const T &arr) {
    for (const auto &x : arr)
        out << x << " ";
    return out;
}

template<class T>
typename enable_if<is_continer<T>::value && !is_same<T, string>::value, istream>::type&
operator>>(istream &in, T &arr) {
    for (auto &x : arr)
        in >> x;
    return in;
}

template<class T, size_t pos>
void read_tuple(istream &in, T &x) {
    if constexpr (pos == tuple_size<T>::value)
        return;
    else {
        in >> get<pos>(x);
        read_tuple<T, pos + 1>(in, x);
    }
}

template<class T, size_t pos = 0>
typename enable_if<(bool)tuple_size<T>::value && !is_std_array<T>::value, istream>::type&
operator>>(istream &in, T &x) {
    read_tuple<T, 0>(in, x);
    return in;
}

template<class T, size_t pos>
void write_tuple(ostream &out, const T &x) {
    if constexpr (pos == tuple_size<T>::value)
        return;
    else {
        if constexpr (pos != 0)
            out << " ";
        out << get<pos>(x);
        write_tuple<T, pos + 1>(out, x);
    }
}

template<class T>
typename enable_if<(bool)tuple_size<T>::value && !is_std_array<T>::value, ostream>::type&
operator<<(ostream &out, const T &x) {
    write_tuple<T, 0>(out, x);
    return out;
}

#define DEBUG
#if defined DEBUG && defined LOCAL
    #define debugdo(x) x
#else
    #define debugdo(x)
#endif

#define debug(x) debugdo(cout << x << endl)
#define debug2(x, s) debugdo(cout << x << s)
#define debugs(x) debug2(x, ' ')
#define named(x) #x << " = " << x

// ---SOLUTION--- //

struct SegTree {
    int n;
    vector<pair<pii, pii>> a;
    SegTree(const vector<int> &arr): n(arr.size()), a(arr.size() * 4) {
        build(arr, 0, 0, n);
    }
    void build(const vector<int> &arr, int v, int l, int r) {
        if (r - l == 1) {
            a[v] = {{arr[l], l}, {arr[l], l}};
            return;
        }
        int c = (l + r) / 2;
        build(arr, v * 2 + 1, l, c);
        build(arr, v * 2 + 2, c, r);
        a[v].F = max(a[v * 2 + 1].F, a[v * 2 + 2].F);
        a[v].S = min(a[v * 2 + 1].S, a[v * 2 + 2].S);
    }
    pair<pii, pii> get(int ql, int qr, int v = 0, int l = 0, int r = -1) {
        if (r == -1) {
            r = n;
        }
        if (l >= qr || ql >= r) {
            return {{-INF, 0}, {INF, 0}};
        }
        if (l >= ql && r <= qr) {
            //debug(ql << " " << qr << " " << a[v]);
            return a[v];
        }
        int c = (l + r) / 2;
        auto la = get(ql, qr, v * 2 + 1, l, c);
        auto ra = get(ql, qr, v * 2 + 2, c, r);
        return {max(la.F, ra.F), min(la.S, ra.S)};
    }
};

const int N = 2e5 + 128;

alignas(32) int a[N], nr[N];

//#define TEST

void run() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        #ifndef TEST
        cin >> a[i];
        #else
        a[i] = i + 1;
        #endif
    }
    vector<int> d(n);
    d[0] = a[0];
    for (int i = 1; i < n; ++i) {
        d[i] = a[i] - a[i - 1];
    }
    SegTree t(d);
    // debug(t.a);
    SegTree ta(vector<int>(a, a + n));
    for (int i = 0; i < n; ++i) {
        int l = i + 1, r = n;
        while (r - l > 1) {
            int m = (l + r) / 2;
            auto res = ta.get(i, m);
            if (res.F.F > a[i] && res.S.F < a[i]) {
                r = m;
            } else {
                l = m;
            }
        }
        nr[i] = r;
    }
    debug(vector<int>(nr, nr + n));
    SegTree t2(vector<int>(nr, nr + n));
    while (q--) {
        int l, r;
        #ifdef TEST
        l = 1, r = n;
        #else
        cin >> l >> r;
        #endif
        --l;
        auto res = t.get(l + 1, r);
        auto res2 = t2.get(l, r);
        if (res.F.F <= 0 || res.S.F >= 0) {
            cout << "0\n";
        } else if (res2.S.F < r) {
            l = res2.S.S;
            r = res2.S.F;
            auto resa = ta.get(l + 1, r);
            int mn = resa.F.S;
            int mx = resa.S.S;
            if (mn > mx)
                swap(mn, mx);
            cout << "4\n";
            cout << l + 1 << " " << mn + 1 << " " << mx + 1 << " " << r + 1 << "\n";
        } else {
            debug(res);
            int k = res.F.S;
            if (res.F.S > res.S.S) {
                swap(res.F, res.S);
                k = res.F.S;
                if (a[res.S.S - 1] < a[k])
                    k = res.S.S - 1;
            } else {
                if (a[res.S.S - 1] > a[k])
                    k = res.S.S - 1;
            }
            cout << "3\n";
            cout << res.F.S << " " << k + 1 << " " << res.S.S + 1 << "\n";
        }
    }
}