#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline bool setmin(T &a, T b) {
  if (a > b) return a = b, 1;
  return 0;
}
template <class T>
inline bool setmax(T &a, T b) {
  if (a < b) return a = b, 1;
  return 0;
}
template <class T>
inline T fast(T a, T b, T mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
template <class T>
istream &operator>>(istream &os, vector<T> &container) {
  for (auto &u : container) os >> u;
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &container) {
  for (auto &u : container) os << u << " ";
  return os;
}
template <class T>
inline T gcd(T a, T b) {
  while (b) swap(a %= b, b);
  return a;
}
const long long INF = 1e9 + 7;
const long long mod = 998244353;
const long long BIG_INF = 1e18 + 7;
const long long N = 1e6 + 7;
const long long T = 1 << 20;
const long double inf = 1e18;
long long n, m, q;
int ile[N];
int tab[N];
int ans[N];
set<int> trojki;
int tree[T * 2];
vector<vector<int> > siema(N);
int ask(int pocz, int kon) {
  pocz += T - 1;
  kon += T + 1;
  int ret = INF;
  while (pocz >> 1 != kon >> 1) {
    if (!(pocz & 1)) ret = min(ret, tree[pocz + 1]);
    if (kon & 1) ret = min(ret, tree[kon - 1]);
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void add(int poz, int val) {
  poz += T;
  tree[poz] = val;
  poz /= 2;
  while (poz) {
    tree[poz] = min(tree[poz + poz], tree[poz + poz + 1]);
    poz /= 2;
  }
}
pair<int, int> tree_maxi[T * 2];
pair<int, int> tree_mini[T * 2];
int podaj_maxa(int pocz, int kon) {
  pocz += T - 1;
  kon += T + 1;
  int ret = -INF;
  int val = -INF;
  while (pocz >> 1 != kon >> 1) {
    if (!(pocz & 1)) {
      if (val < tree_maxi[pocz + 1].first) {
        val = tree_maxi[pocz + 1].first;
        ret = tree_maxi[pocz + 1].second;
      }
    }
    if (kon & 1)
      if (val < tree_maxi[kon - 1].first) {
        val = tree_maxi[kon - 1].first;
        ret = tree_maxi[kon - 1].second;
      }
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void add_maxi(int poz, pair<int, int> val) {
  poz += T;
  tree_maxi[poz] = val;
  poz /= 2;
  while (poz) {
    if (tree_maxi[poz + poz].first > tree_maxi[poz + poz + 1].first)
      tree_maxi[poz] = tree_maxi[poz + poz];
    else
      tree_maxi[poz] = tree_maxi[poz + poz + 1];
    poz /= 2;
  }
}
int podaj_mini(int pocz, int kon) {
  pocz += T - 1;
  kon += T + 1;
  int ret = INF;
  int val = INF;
  while (pocz >> 1 != kon >> 1) {
    if (!(pocz & 1)) {
      if (val > tree_mini[pocz + 1].first) {
        val = tree_mini[pocz + 1].first;
        ret = tree_mini[pocz + 1].second;
      }
    }
    if (kon & 1) {
      if (val > tree_mini[kon - 1].first) {
        val = tree_mini[kon - 1].first;
        ret = tree_mini[kon - 1].second;
      }
    }
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void add_mini(int poz, pair<int, int> val) {
  poz += T;
  tree_mini[poz] = val;
  poz /= 2;
  while (poz) {
    if (tree_mini[poz + poz].first > tree_mini[poz + poz + 1].first)
      tree_mini[poz] = tree_mini[poz + poz + 1];
    else
      tree_mini[poz] = tree_mini[poz + poz];
    poz /= 2;
  }
}
void update(vector<int> xd) {
  if ((int)(siema[xd[3]]).size() == 0 || siema[xd[3]][0] < xd[0])
    siema[xd[3]] = xd;
}
int nast[N];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> tab[i];
    add_maxi(i, {tab[i], i});
    add_mini(i, {tab[i], i});
  }
  for (int i = n; i >= 1; i--) {
    if (tab[i] != tab[i + 1])
      nast[i] = i + 1;
    else
      nast[i] = nast[i + 1];
  }
  for (int i = 1; i <= n - 2; i++) {
    int a = i;
    int b = nast[a];
    int c = nast[b];
    if (b > n or c > n) continue;
    if (tab[a] != tab[b] and tab[b] != tab[c]) {
      if ((tab[a] < tab[b] and tab[b] > tab[c]) or
          (tab[a] > tab[b] and tab[b] < tab[c]))
        trojki.insert(a);
    }
  }
  vector<pair<int, int> > maxi, mini;
  set<int> zdjete;
  for (int i = n; i >= 1; i--) {
    while ((int)(maxi).size() and maxi.back().first < tab[i]) {
      int v = maxi.back().second;
      ile[v]++;
      if (ile[v] == 1) {
      }
      if (ile[v] == 2) {
        zdjete.insert(v);
      }
      maxi.pop_back();
    }
    while ((int)(mini).size() and mini.back().first > tab[i]) {
      int v = mini.back().second;
      ile[v]++;
      if (ile[v] == 1) {
      }
      if (ile[v] == 2) {
        zdjete.insert(v);
      }
      mini.pop_back();
    }
    auto it_maxi = lower_bound(
        (maxi).begin(), (maxi).end(), make_pair(tab[i], -(int)INF),
        [](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });
    auto it_mini =
        lower_bound((mini).begin(), (mini).end(), make_pair(tab[i], -(int)INF));
    ans[i] = INF;
    if (it_mini == mini.begin() or it_maxi == maxi.begin()) {
      maxi.push_back({tab[i], i});
      mini.push_back({tab[i], i});
      continue;
    }
    it_mini = prev(it_mini);
    it_maxi = prev(it_maxi);
    int a = (*it_maxi).second;
    int b = (*it_mini).second;
    int najw = max(a, b);
    maxi.push_back({tab[i], i});
    mini.push_back({tab[i], i});
    if (tab[i] == tab[i + 1]) {
      ans[i] = ans[i + 1];
      continue;
    }
    set<int>::iterator it = zdjete.upper_bound(najw);
    if (it != zdjete.end()) {
      int A = podaj_maxa(i, *it);
      int B = podaj_mini(i, *it);
      if (A > B) swap(A, B);
      if (tab[i] == tab[A] or tab[B] == tab[i] or tab[*it] == tab[A] or
          tab[B] == tab[*it])
        continue;
      ans[i] = *it;
      update({i, A, B, *it});
    }
  }
  for (int i = 1; i <= n; i++) {
    add(i, ans[i]);
  }
  for (int i = 0; i < (m); i++) {
    int a, b;
    cin >> a >> b;
    int poz = ask(a, b);
    if (poz <= b) {
      cout << 4 << '\n';
      cout << siema[poz] << '\n';
    } else {
      auto it = trojki.lower_bound(a);
      if (it != trojki.end() and nast[(*it)] <= b and nast[nast[(*it)]] <= b) {
        cout << 3 << '\n';
        cout << (*it) << ' ' << nast[(*it)] << ' ' << nast[nast[(*it)]] << '\n';
      } else {
        cout << 0 << '\n';
        cout << '\n';
      }
    }
  }
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline bool setmin(T &a, T b) {
  if (a > b) return a = b, 1;
  return 0;
}
template <class T>
inline bool setmax(T &a, T b) {
  if (a < b) return a = b, 1;
  return 0;
}
template <class T>
inline T fast(T a, T b, T mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
template <class T>
istream &operator>>(istream &os, vector<T> &container) {
  for (auto &u : container) os >> u;
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &container) {
  for (auto &u : container) os << u << " ";
  return os;
}
template <class T>
inline T gcd(T a, T b) {
  while (b) swap(a %= b, b);
  return a;
}
const long long INF = 1e9 + 7;
const long long mod = 998244353;
const long long BIG_INF = 1e18 + 7;
const long long N = 1e6 + 7;
const long long T = 1 << 20;
const long double inf = 1e18;
long long n, m, q;
int ile[N];
int tab[N];
int ans[N];
set<int> trojki;
int tree[T * 2];
vector<vector<int> > siema(N);
int ask(int pocz, int kon) {
  pocz += T - 1;
  kon += T + 1;
  int ret = INF;
  while (pocz >> 1 != kon >> 1) {
    if (!(pocz & 1)) ret = min(ret, tree[pocz + 1]);
    if (kon & 1) ret = min(ret, tree[kon - 1]);
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void add(int poz, int val) {
  poz += T;
  tree[poz] = val;
  poz /= 2;
  while (poz) {
    tree[poz] = min(tree[poz + poz], tree[poz + poz + 1]);
    poz /= 2;
  }
}
pair<int, int> tree_maxi[T * 2];
pair<int, int> tree_mini[T * 2];
int podaj_maxa(int pocz, int kon) {
  pocz += T - 1;
  kon += T + 1;
  int ret = -INF;
  int val = -INF;
  while (pocz >> 1 != kon >> 1) {
    if (!(pocz & 1)) {
      if (val < tree_maxi[pocz + 1].first) {
        val = tree_maxi[pocz + 1].first;
        ret = tree_maxi[pocz + 1].second;
      }
    }
    if (kon & 1)
      if (val < tree_maxi[kon - 1].first) {
        val = tree_maxi[kon - 1].first;
        ret = tree_maxi[kon - 1].second;
      }
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void add_maxi(int poz, pair<int, int> val) {
  poz += T;
  tree_maxi[poz] = val;
  poz /= 2;
  while (poz) {
    if (tree_maxi[poz + poz].first > tree_maxi[poz + poz + 1].first)
      tree_maxi[poz] = tree_maxi[poz + poz];
    else
      tree_maxi[poz] = tree_maxi[poz + poz + 1];
    poz /= 2;
  }
}
int podaj_mini(int pocz, int kon) {
  pocz += T - 1;
  kon += T + 1;
  int ret = INF;
  int val = INF;
  while (pocz >> 1 != kon >> 1) {
    if (!(pocz & 1)) {
      if (val > tree_mini[pocz + 1].first) {
        val = tree_mini[pocz + 1].first;
        ret = tree_mini[pocz + 1].second;
      }
    }
    if (kon & 1) {
      if (val > tree_mini[kon - 1].first) {
        val = tree_mini[kon - 1].first;
        ret = tree_mini[kon - 1].second;
      }
    }
    pocz >>= 1;
    kon >>= 1;
  }
  return ret;
}
void add_mini(int poz, pair<int, int> val) {
  poz += T;
  tree_mini[poz] = val;
  poz /= 2;
  while (poz) {
    if (tree_mini[poz + poz].first > tree_mini[poz + poz + 1].first)
      tree_mini[poz] = tree_mini[poz + poz + 1];
    else
      tree_mini[poz] = tree_mini[poz + poz];
    poz /= 2;
  }
}
void update(vector<int> xd) {
  if ((int)(siema[xd[3]]).size() == 0 || siema[xd[3]][0] < xd[0])
    siema[xd[3]] = xd;
}
int nast[N];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> tab[i];
    add_maxi(i, {tab[i], i});
    add_mini(i, {tab[i], i});
  }
  for (int i = n; i >= 1; i--) {
    if (tab[i] != tab[i + 1])
      nast[i] = i + 1;
    else
      nast[i] = nast[i + 1];
  }
  for (int i = 1; i <= n - 2; i++) {
    int a = i;
    int b = nast[a];
    int c = nast[b];
    if (b > n or c > n) continue;
    if (tab[a] != tab[b] and tab[b] != tab[c]) {
      if ((tab[a] < tab[b] and tab[b] > tab[c]) or
          (tab[a] > tab[b] and tab[b] < tab[c]))
        trojki.insert(a);
    }
  }
  vector<pair<int, int> > maxi, mini;
  set<int> zdjete;
  for (int i = n; i >= 1; i--) {
    while ((int)(maxi).size() and maxi.back().first < tab[i]) {
      int v = maxi.back().second;
      ile[v]++;
      if (ile[v] == 1) {
      }
      if (ile[v] == 2) {
        zdjete.insert(v);
      }
      maxi.pop_back();
    }
    while ((int)(mini).size() and mini.back().first > tab[i]) {
      int v = mini.back().second;
      ile[v]++;
      if (ile[v] == 1) {
      }
      if (ile[v] == 2) {
        zdjete.insert(v);
      }
      mini.pop_back();
    }
    auto it_maxi = lower_bound(
        (maxi).begin(), (maxi).end(), make_pair(tab[i], -(int)INF),
        [](pair<int, int> a, pair<int, int> b) { return a.first > b.first; });
    auto it_mini =
        lower_bound((mini).begin(), (mini).end(), make_pair(tab[i], -(int)INF));
    ans[i] = INF;
    if (it_mini == mini.begin() or it_maxi == maxi.begin()) {
      maxi.push_back({tab[i], i});
      mini.push_back({tab[i], i});
      continue;
    }
    it_mini = prev(it_mini);
    it_maxi = prev(it_maxi);
    int a = (*it_maxi).second;
    int b = (*it_mini).second;
    int najw = max(a, b);
    maxi.push_back({tab[i], i});
    mini.push_back({tab[i], i});
    if (tab[i] == tab[i + 1]) {
      ans[i] = ans[i + 1];
      continue;
    }
    set<int>::iterator it = zdjete.upper_bound(najw);
    if (it != zdjete.end()) {
      int A = podaj_maxa(i, *it);
      int B = podaj_mini(i, *it);
      if (A > B) swap(A, B);
      if (tab[i] == tab[A] or tab[B] == tab[i] or tab[*it] == tab[A] or
          tab[B] == tab[*it])
        continue;
      ans[i] = *it;
      update({i, A, B, *it});
    }
  }
  for (int i = 1; i <= n; i++) {
    add(i, ans[i]);
  }
  for (int i = 0; i < (m); i++) {
    int a, b;
    cin >> a >> b;
    int poz = ask(a, b);
    if (poz <= b) {
      cout << 4 << '\n';
      cout << siema[poz] << '\n';
    } else {
      auto it = trojki.lower_bound(a);
      if (it != trojki.end() and nast[(*it)] <= b and nast[nast[(*it)]] <= b) {
        cout << 3 << '\n';
        cout << (*it) << ' ' << nast[(*it)] << ' ' << nast[nast[(*it)]] << '\n';
      } else {
        cout << 0 << '\n';
        cout << '\n';
      }
    }
  }
}

```