#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long n;
long long a[200020];
long long ans[200020][3];
long long ans1[200020][2];
long long ans2[200020][2];
struct Segmin {
 private:
 public:
  long long cor = (1 << 18);
  vector<pair<long long, long long> > vec;
  void shoki1() {
    vec.resize(2 * cor + 3, make_pair(1000000007, 0));
    for (long long i = cor; i < 2 * cor; i++) vec[i].second = i - cor;
  }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--) {
      if (vec[2 * i].first <= vec[2 * i + 1].first)
        vec[i] = vec[2 * i];
      else
        vec[i] = vec[2 * i + 1];
    }
  }
  void updadd(long long x, long long w) {
    x += cor;
    vec[x].first += w;
    while (1) {
      x /= 2;
      if (x == 0) break;
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
    }
  }
  void updchan(long long x, long long w) {
    x += cor;
    vec[x].first = w;
    while (1) {
      x /= 2;
      if (x == 0) break;
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
    }
  }
  pair<long long, long long> segmin(long long a, long long b, long long k = 1,
                                    long long l = 0, long long r = -10) {
    if (r < 0) r = cor;
    if (a <= l && r <= b) {
      return vec[k];
    }
    if (r <= a || b <= l) {
      return make_pair((1ll << 31) - 1, -1);
    }
    pair<long long, long long> v1 = segmin(a, b, k * 2, l, (l + r) / 2),
                               v2 = segmin(a, b, k * 2 + 1, (l + r) / 2, r);
    if (v1.first <= v2.first)
      return v1;
    else
      return v2;
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long q;
  cin >> n >> q;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  set<long long> se, se1, se2;
  deque<pair<long long, long long> > d1, d2;
  vector<long long> f(n, 0);
  d1.push_back(make_pair(n, 0));
  d2.push_back(make_pair(n + 1, 0));
  a[n] = 1000000007;
  a[n + 1] = -1000000007;
  for (long long i = n - 1; i >= 0; i--) {
    while (a[d1[0].first] < a[i]) {
      pair<long long, long long> z = d1[0];
      d1.pop_front();
      f[z.first]++;
      if (f[z.first] == 2) se.insert(z.first);
      se1.insert(z.first);
    }
    if (a[d1[0].first] > a[i])
      d1.push_front(make_pair(i, 1));
    else
      d1.push_front(make_pair(i, d1[0].second + 1));
    while (a[d2[0].first] > a[i]) {
      pair<long long, long long> z = d2[0];
      d2.pop_front();
      f[z.first]++;
      if (f[z.first] == 2) se.insert(z.first);
      se2.insert(z.first);
    }
    if (a[d2[0].first] < a[i])
      d2.push_front(make_pair(i, 1));
    else
      d2.push_front(make_pair(i, d2[0].second + 1));
    long long it1 = d1[d1[0].second].first;
    long long it2 = d2[d2[0].second].first;
    auto fg = se.lower_bound(max(it1, it2));
    if (fg != se.end() && it1 < n && it2 < n) {
      ans[i][2] = *fg;
    } else {
      ans[i][0] = 1000000007;
      ans[i][1] = 1000000007;
      ans[i][2] = 1000000007;
    }
    fg = se1.lower_bound(it1);
    if (fg != se1.end() && it1 < n) {
      ans1[i][0] = it1;
      ans1[i][1] = *fg;
    } else {
      ans1[i][0] = 1000000007;
      ans1[i][1] = 1000000007;
    }
    fg = se2.lower_bound(it2);
    if (fg != se2.end() && it2 < n) {
      ans2[i][0] = it2;
      ans2[i][1] = *fg;
    } else {
      ans2[i][0] = 1000000007;
      ans2[i][1] = 1000000007;
    }
  }
  Segmin ss1, ss2, ss3, sa, sb;
  ss1.shoki1();
  ss2.shoki1();
  ss3.shoki1();
  sa.shoki1();
  sb.shoki1();
  for (long long i = 0; i < n; i++) {
    sb.vec[sb.cor + i].first = a[i];
    sa.vec[sa.cor + i].first = -a[i];
  }
  sb.shoki2();
  sa.shoki2();
  for (long long i = 0; i < n; i++)
    if (ans[i][2] < 1000000007) {
      ans[i][0] = sa.segmin(i + 1, ans[i][2]).second;
      ans[i][1] = sb.segmin(i + 1, ans[i][2]).second;
    }
  for (long long i = 0; i < n; i++)
    if (ans1[i][1] < 1000000007) {
      ans1[i][0] = sa.segmin(i + 1, ans1[i][1]).second;
    }
  for (long long i = 0; i < n; i++)
    if (ans2[i][1] < 1000000007) {
      ans2[i][0] = sb.segmin(i + 1, ans2[i][1]).second;
    }
  for (long long i = 0; i < n; i++) {
    ss1.vec[ss1.cor + i].first = ans[i][2];
    ss2.vec[ss1.cor + i].first = ans1[i][1];
    ss3.vec[ss1.cor + i].first = ans2[i][1];
  }
  ss1.shoki2();
  ss2.shoki2();
  ss3.shoki2();
  for (long long i = 0; i < q; i++) {
    long long l, r;
    cin >> l >> r;
    l--, r--;
    pair<long long, long long> z = ss1.segmin(l, r + 1);
    if (z.first <= r) {
      long long it1 = z.second;
      long long it4 = ans[it1][2];
      long long it2 = ans[it1][1];
      long long it3 = ans[it1][0];
      if (it2 > it3) swap(it2, it3);
      cout << 4 << "\n";
      cout << it1 + 1 << " " << it2 + 1 << " " << it3 + 1 << " " << it4 + 1
           << "\n";
      continue;
    }
    z = ss2.segmin(l, r + 1);
    if (z.first <= r) {
      cout << 3 << "\n";
      cout << z.second + 1 << " " << ans1[z.second][0] + 1 << " "
           << ans1[z.second][1] + 1 << "\n";
      continue;
    }
    z = ss3.segmin(l, r + 1);
    if (z.first <= r) {
      cout << 3 << "\n";
      cout << z.second + 1 << " " << ans2[z.second][0] + 1 << " "
           << ans2[z.second][1] + 1 << "\n";
      continue;
    }
    cout << 0 << "\n";
    cout << "\n";
  }
  return 0;
}

### Prompt

Generate a CPP solution to 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>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long n;
long long a[200020];
long long ans[200020][3];
long long ans1[200020][2];
long long ans2[200020][2];
struct Segmin {
 private:
 public:
  long long cor = (1 << 18);
  vector<pair<long long, long long> > vec;
  void shoki1() {
    vec.resize(2 * cor + 3, make_pair(1000000007, 0));
    for (long long i = cor; i < 2 * cor; i++) vec[i].second = i - cor;
  }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--) {
      if (vec[2 * i].first <= vec[2 * i + 1].first)
        vec[i] = vec[2 * i];
      else
        vec[i] = vec[2 * i + 1];
    }
  }
  void updadd(long long x, long long w) {
    x += cor;
    vec[x].first += w;
    while (1) {
      x /= 2;
      if (x == 0) break;
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
    }
  }
  void updchan(long long x, long long w) {
    x += cor;
    vec[x].first = w;
    while (1) {
      x /= 2;
      if (x == 0) break;
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
    }
  }
  pair<long long, long long> segmin(long long a, long long b, long long k = 1,
                                    long long l = 0, long long r = -10) {
    if (r < 0) r = cor;
    if (a <= l && r <= b) {
      return vec[k];
    }
    if (r <= a || b <= l) {
      return make_pair((1ll << 31) - 1, -1);
    }
    pair<long long, long long> v1 = segmin(a, b, k * 2, l, (l + r) / 2),
                               v2 = segmin(a, b, k * 2 + 1, (l + r) / 2, r);
    if (v1.first <= v2.first)
      return v1;
    else
      return v2;
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long q;
  cin >> n >> q;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  set<long long> se, se1, se2;
  deque<pair<long long, long long> > d1, d2;
  vector<long long> f(n, 0);
  d1.push_back(make_pair(n, 0));
  d2.push_back(make_pair(n + 1, 0));
  a[n] = 1000000007;
  a[n + 1] = -1000000007;
  for (long long i = n - 1; i >= 0; i--) {
    while (a[d1[0].first] < a[i]) {
      pair<long long, long long> z = d1[0];
      d1.pop_front();
      f[z.first]++;
      if (f[z.first] == 2) se.insert(z.first);
      se1.insert(z.first);
    }
    if (a[d1[0].first] > a[i])
      d1.push_front(make_pair(i, 1));
    else
      d1.push_front(make_pair(i, d1[0].second + 1));
    while (a[d2[0].first] > a[i]) {
      pair<long long, long long> z = d2[0];
      d2.pop_front();
      f[z.first]++;
      if (f[z.first] == 2) se.insert(z.first);
      se2.insert(z.first);
    }
    if (a[d2[0].first] < a[i])
      d2.push_front(make_pair(i, 1));
    else
      d2.push_front(make_pair(i, d2[0].second + 1));
    long long it1 = d1[d1[0].second].first;
    long long it2 = d2[d2[0].second].first;
    auto fg = se.lower_bound(max(it1, it2));
    if (fg != se.end() && it1 < n && it2 < n) {
      ans[i][2] = *fg;
    } else {
      ans[i][0] = 1000000007;
      ans[i][1] = 1000000007;
      ans[i][2] = 1000000007;
    }
    fg = se1.lower_bound(it1);
    if (fg != se1.end() && it1 < n) {
      ans1[i][0] = it1;
      ans1[i][1] = *fg;
    } else {
      ans1[i][0] = 1000000007;
      ans1[i][1] = 1000000007;
    }
    fg = se2.lower_bound(it2);
    if (fg != se2.end() && it2 < n) {
      ans2[i][0] = it2;
      ans2[i][1] = *fg;
    } else {
      ans2[i][0] = 1000000007;
      ans2[i][1] = 1000000007;
    }
  }
  Segmin ss1, ss2, ss3, sa, sb;
  ss1.shoki1();
  ss2.shoki1();
  ss3.shoki1();
  sa.shoki1();
  sb.shoki1();
  for (long long i = 0; i < n; i++) {
    sb.vec[sb.cor + i].first = a[i];
    sa.vec[sa.cor + i].first = -a[i];
  }
  sb.shoki2();
  sa.shoki2();
  for (long long i = 0; i < n; i++)
    if (ans[i][2] < 1000000007) {
      ans[i][0] = sa.segmin(i + 1, ans[i][2]).second;
      ans[i][1] = sb.segmin(i + 1, ans[i][2]).second;
    }
  for (long long i = 0; i < n; i++)
    if (ans1[i][1] < 1000000007) {
      ans1[i][0] = sa.segmin(i + 1, ans1[i][1]).second;
    }
  for (long long i = 0; i < n; i++)
    if (ans2[i][1] < 1000000007) {
      ans2[i][0] = sb.segmin(i + 1, ans2[i][1]).second;
    }
  for (long long i = 0; i < n; i++) {
    ss1.vec[ss1.cor + i].first = ans[i][2];
    ss2.vec[ss1.cor + i].first = ans1[i][1];
    ss3.vec[ss1.cor + i].first = ans2[i][1];
  }
  ss1.shoki2();
  ss2.shoki2();
  ss3.shoki2();
  for (long long i = 0; i < q; i++) {
    long long l, r;
    cin >> l >> r;
    l--, r--;
    pair<long long, long long> z = ss1.segmin(l, r + 1);
    if (z.first <= r) {
      long long it1 = z.second;
      long long it4 = ans[it1][2];
      long long it2 = ans[it1][1];
      long long it3 = ans[it1][0];
      if (it2 > it3) swap(it2, it3);
      cout << 4 << "\n";
      cout << it1 + 1 << " " << it2 + 1 << " " << it3 + 1 << " " << it4 + 1
           << "\n";
      continue;
    }
    z = ss2.segmin(l, r + 1);
    if (z.first <= r) {
      cout << 3 << "\n";
      cout << z.second + 1 << " " << ans1[z.second][0] + 1 << " "
           << ans1[z.second][1] + 1 << "\n";
      continue;
    }
    z = ss3.segmin(l, r + 1);
    if (z.first <= r) {
      cout << 3 << "\n";
      cout << z.second + 1 << " " << ans2[z.second][0] + 1 << " "
           << ans2[z.second][1] + 1 << "\n";
      continue;
    }
    cout << 0 << "\n";
    cout << "\n";
  }
  return 0;
}

```