#include <bits/stdc++.h>
using namespace std;
int inf;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T, class T2>
int chkmin(T &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class T2>
int chkmax(T &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T, class T2>
T mmin(T a, T2 b) {
  return a < b ? a : b;
}
template <class T, class T2>
T mmax(T a, T2 b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
int dcmp(T a, T b) {
  return a > b;
}
template <int *a>
int cmp_a(int first, int second) {
  return a[first] < a[second];
}
struct __INIT__ {
  __INIT__() { memset(&inf, 0x3f, sizeof(inf)); }
} __INIT___;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  while ((first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)) == ' ' ||
         first == '\n' || first == '\r')
    ;
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    ;
  if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
template <typename A>
inline bool write(A first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
int a[200005], b[200005], m;
int xl[200005], xr[200005], yl[200005], yr[200005], xyl[200005], xyr[200005];
struct smt {
  pair<int, int> mx, mn;
  int ls, rs;
  smt *l, *r;
  smt(int la, int ra) {
    ls = la;
    rs = ra;
    if (ls == rs) {
      mx = mn = make_pair(a[ls], ls);
      l = r = 0;
      return;
    }
    int mid = (ls + rs) >> 1;
    l = new smt(ls, mid);
    r = new smt(mid + 1, rs);
    mx = mmax(l->mx, r->mx);
    mn = mmin(l->mn, r->mn);
  }
  void qry(int la, int ra, pair<int, int> &Mx, pair<int, int> &Mn) {
    if (la <= ls && rs <= ra) {
      chkmax(Mx, mx);
      chkmin(Mn, mn);
      return;
    }
    if (la <= l->rs) l->qry(la, ra, Mx, Mn);
    if (r->ls <= ra) r->qry(la, ra, Mx, Mn);
  }
};
smt *xrt;
struct smt2 {
  int ls, rs;
  smt2 *l, *r;
  int mxs, mns;
  smt2(int la, int ra) {
    ls = la;
    rs = ra;
    mxs = mns = 0;
    if (ls == rs) {
      l = r = 0;
      return;
    }
    int mid = (ls + rs) >> 1;
    l = new smt2(ls, mid);
    r = new smt2(mid + 1, rs);
  }
  void set_mx(int first) {
    ++mxs;
    if (ls == rs) return;
    if (first <= l->rs)
      l->set_mx(first);
    else
      r->set_mx(first);
  }
  void unset_mx(int first) {
    --mxs;
    if (ls == rs) return;
    if (first <= l->rs)
      l->unset_mx(first);
    else
      r->unset_mx(first);
  }
  void set_mn(int first) {
    ++mns;
    if (ls == rs) return;
    if (first <= l->rs)
      l->set_mn(first);
    else
      r->set_mn(first);
  }
  void unset_mn(int first) {
    --mns;
    if (ls == rs) return;
    if (first <= l->rs)
      l->unset_mn(first);
    else
      r->unset_mn(first);
  }
  void fnd(int atl, int hmx, int hmn, int &ans) {
    if ((hmx ? mxs : 0) + (hmn ? mns : 0) == rs - ls + 1) return;
    if (rs < atl) return;
    if (ls == rs) {
      ans = ls;
      return;
    }
    l->fnd(atl, hmx, hmn, ans);
    if (!ans) r->fnd(atl, hmx, hmn, ans);
  }
};
smt2 *rt;
int mxs[200005], mxat[200005], mxt;
int mns[200005], mnat[200005], mnt;
int smxs[200005], smxat[200005], smxt;
int smns[200005], smnat[200005], smnt;
signed main() {
  int n, q;
  read(n, q);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    b[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  m = unique(b + 1, b + n + 1) - b - 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
  }
  xrt = new smt(1, n);
  rt = new smt2(1, n);
  xyr[n + 1] = xr[n + 1] = yr[n + 1] = n + 1;
  for (int i = n; i; --i) {
    while (mxt && a[i] > mxs[mxt]) {
      rt->unset_mx(mxat[mxt]);
      --mxt;
    }
    mxs[++mxt] = a[i];
    mxat[mxt] = i;
    rt->set_mx(mxat[mxt]);
    while (mnt && a[i] < mns[mnt]) {
      rt->unset_mn(mnat[mnt]);
      --mnt;
    }
    mns[++mnt] = a[i];
    mnat[mnt] = i;
    rt->set_mn(mnat[mnt]);
    while (smxt && a[i] >= smxs[smxt]) --smxt;
    int mxl = smxt ? smxat[smxt] : n + 1;
    smxs[++smxt] = a[i];
    smxat[smxt] = i;
    while (smnt && a[i] <= smns[smnt]) --smnt;
    int mnl = smnt ? smnat[smnt] : n + 1;
    smns[++smnt] = a[i];
    smnat[smnt] = i;
    int w;
    w = 0;
    rt->fnd(mxl, 1, 0, w);
    if (w)
      xr[i] = w;
    else
      xr[i] = n + 1;
    xl[i] = i;
    w = 0;
    rt->fnd(mnl, 0, 1, w);
    if (w)
      yr[i] = w;
    else
      yr[i] = n + 1;
    yl[i] = i;
    rt->unset_mn(i);
    w = 0;
    rt->fnd(mmax(mxl, mnl), 1, 1, w);
    rt->set_mn(i);
    if (w)
      xyr[i] = w;
    else
      xyr[i] = n + 1;
    xyl[i] = i;
    if (chkmin(xr[i], xr[i + 1])) xl[i] = xl[i + 1];
    if (chkmin(yr[i], yr[i + 1])) yl[i] = yl[i + 1];
    if (chkmin(xyr[i], xyr[i + 1])) xyl[i] = xyl[i + 1];
  }
  for (; q; --q) {
    int l, r;
    read(l, r);
    if (xyr[l] <= r) {
      r = xyr[l];
      l = xyl[l];
      pair<int, int> first = make_pair(-inf, 0), second = make_pair(inf, 0);
      xrt->qry(l, r, first, second);
      if (first.second > second.second) swap(first.second, second.second);
      write(4, '\n', l, ' ', first.second, ' ', second.second, ' ', r, '\n');
    } else if (xr[l] <= r) {
      r = xr[l];
      l = xl[l];
      pair<int, int> first = make_pair(-inf, 0), second = make_pair(inf, 0);
      xrt->qry(l, r, first, second);
      write(3, '\n', l, ' ', first.second, ' ', r, '\n');
    } else if (yr[l] <= r) {
      r = yr[l];
      l = yl[l];
      pair<int, int> first = make_pair(-inf, 0), second = make_pair(inf, 0);
      xrt->qry(l, r, first, second);
      write(3, '\n', l, ' ', second.second, ' ', r, '\n');
    } else
      write(0, '\n', '\n');
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int inf;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T, class T2>
int chkmin(T &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class T2>
int chkmax(T &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T, class T2>
T mmin(T a, T2 b) {
  return a < b ? a : b;
}
template <class T, class T2>
T mmax(T a, T2 b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
int dcmp(T a, T b) {
  return a > b;
}
template <int *a>
int cmp_a(int first, int second) {
  return a[first] < a[second];
}
struct __INIT__ {
  __INIT__() { memset(&inf, 0x3f, sizeof(inf)); }
} __INIT___;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  while ((first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)) == ' ' ||
         first == '\n' || first == '\r')
    ;
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    ;
  if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
template <typename A>
inline bool write(A first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
int a[200005], b[200005], m;
int xl[200005], xr[200005], yl[200005], yr[200005], xyl[200005], xyr[200005];
struct smt {
  pair<int, int> mx, mn;
  int ls, rs;
  smt *l, *r;
  smt(int la, int ra) {
    ls = la;
    rs = ra;
    if (ls == rs) {
      mx = mn = make_pair(a[ls], ls);
      l = r = 0;
      return;
    }
    int mid = (ls + rs) >> 1;
    l = new smt(ls, mid);
    r = new smt(mid + 1, rs);
    mx = mmax(l->mx, r->mx);
    mn = mmin(l->mn, r->mn);
  }
  void qry(int la, int ra, pair<int, int> &Mx, pair<int, int> &Mn) {
    if (la <= ls && rs <= ra) {
      chkmax(Mx, mx);
      chkmin(Mn, mn);
      return;
    }
    if (la <= l->rs) l->qry(la, ra, Mx, Mn);
    if (r->ls <= ra) r->qry(la, ra, Mx, Mn);
  }
};
smt *xrt;
struct smt2 {
  int ls, rs;
  smt2 *l, *r;
  int mxs, mns;
  smt2(int la, int ra) {
    ls = la;
    rs = ra;
    mxs = mns = 0;
    if (ls == rs) {
      l = r = 0;
      return;
    }
    int mid = (ls + rs) >> 1;
    l = new smt2(ls, mid);
    r = new smt2(mid + 1, rs);
  }
  void set_mx(int first) {
    ++mxs;
    if (ls == rs) return;
    if (first <= l->rs)
      l->set_mx(first);
    else
      r->set_mx(first);
  }
  void unset_mx(int first) {
    --mxs;
    if (ls == rs) return;
    if (first <= l->rs)
      l->unset_mx(first);
    else
      r->unset_mx(first);
  }
  void set_mn(int first) {
    ++mns;
    if (ls == rs) return;
    if (first <= l->rs)
      l->set_mn(first);
    else
      r->set_mn(first);
  }
  void unset_mn(int first) {
    --mns;
    if (ls == rs) return;
    if (first <= l->rs)
      l->unset_mn(first);
    else
      r->unset_mn(first);
  }
  void fnd(int atl, int hmx, int hmn, int &ans) {
    if ((hmx ? mxs : 0) + (hmn ? mns : 0) == rs - ls + 1) return;
    if (rs < atl) return;
    if (ls == rs) {
      ans = ls;
      return;
    }
    l->fnd(atl, hmx, hmn, ans);
    if (!ans) r->fnd(atl, hmx, hmn, ans);
  }
};
smt2 *rt;
int mxs[200005], mxat[200005], mxt;
int mns[200005], mnat[200005], mnt;
int smxs[200005], smxat[200005], smxt;
int smns[200005], smnat[200005], smnt;
signed main() {
  int n, q;
  read(n, q);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    b[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  m = unique(b + 1, b + n + 1) - b - 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
  }
  xrt = new smt(1, n);
  rt = new smt2(1, n);
  xyr[n + 1] = xr[n + 1] = yr[n + 1] = n + 1;
  for (int i = n; i; --i) {
    while (mxt && a[i] > mxs[mxt]) {
      rt->unset_mx(mxat[mxt]);
      --mxt;
    }
    mxs[++mxt] = a[i];
    mxat[mxt] = i;
    rt->set_mx(mxat[mxt]);
    while (mnt && a[i] < mns[mnt]) {
      rt->unset_mn(mnat[mnt]);
      --mnt;
    }
    mns[++mnt] = a[i];
    mnat[mnt] = i;
    rt->set_mn(mnat[mnt]);
    while (smxt && a[i] >= smxs[smxt]) --smxt;
    int mxl = smxt ? smxat[smxt] : n + 1;
    smxs[++smxt] = a[i];
    smxat[smxt] = i;
    while (smnt && a[i] <= smns[smnt]) --smnt;
    int mnl = smnt ? smnat[smnt] : n + 1;
    smns[++smnt] = a[i];
    smnat[smnt] = i;
    int w;
    w = 0;
    rt->fnd(mxl, 1, 0, w);
    if (w)
      xr[i] = w;
    else
      xr[i] = n + 1;
    xl[i] = i;
    w = 0;
    rt->fnd(mnl, 0, 1, w);
    if (w)
      yr[i] = w;
    else
      yr[i] = n + 1;
    yl[i] = i;
    rt->unset_mn(i);
    w = 0;
    rt->fnd(mmax(mxl, mnl), 1, 1, w);
    rt->set_mn(i);
    if (w)
      xyr[i] = w;
    else
      xyr[i] = n + 1;
    xyl[i] = i;
    if (chkmin(xr[i], xr[i + 1])) xl[i] = xl[i + 1];
    if (chkmin(yr[i], yr[i + 1])) yl[i] = yl[i + 1];
    if (chkmin(xyr[i], xyr[i + 1])) xyl[i] = xyl[i + 1];
  }
  for (; q; --q) {
    int l, r;
    read(l, r);
    if (xyr[l] <= r) {
      r = xyr[l];
      l = xyl[l];
      pair<int, int> first = make_pair(-inf, 0), second = make_pair(inf, 0);
      xrt->qry(l, r, first, second);
      if (first.second > second.second) swap(first.second, second.second);
      write(4, '\n', l, ' ', first.second, ' ', second.second, ' ', r, '\n');
    } else if (xr[l] <= r) {
      r = xr[l];
      l = xl[l];
      pair<int, int> first = make_pair(-inf, 0), second = make_pair(inf, 0);
      xrt->qry(l, r, first, second);
      write(3, '\n', l, ' ', first.second, ' ', r, '\n');
    } else if (yr[l] <= r) {
      r = yr[l];
      l = yl[l];
      pair<int, int> first = make_pair(-inf, 0), second = make_pair(inf, 0);
      xrt->qry(l, r, first, second);
      write(3, '\n', l, ' ', second.second, ' ', r, '\n');
    } else
      write(0, '\n', '\n');
  }
  return 0;
}

```