#include <bits/stdc++.h>
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace std::chrono {
long long get_time_ms() {
  return duration_cast<milliseconds>(system_clock::now().time_since_epoch())
      .count();
}
};  // namespace std::chrono
namespace typedefs {}
namespace numbers_operation {
template <class T>
T floor_mod(T a, T b) {
  if (a % b == 0) return 0;
  if (a >= 0 && b >= 0) return a % b;
  if (a <= 0 && b <= 0) return a % b;
  return abs(b) - (abs(a) % abs(b));
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
int n;
vector<int> v;
vector<vector<int>> rez;
void act(int a, int b, int c) {
  assert(a < n && b < n && c < n);
  rez.push_back({a, b, c});
  v[a] ^= 1;
  v[b] ^= 1;
  v[c] ^= 1;
}
vector<vector<int>> resolve(vector<int> big) {
  auto make = [&big](int st, int k) {
    if (st < ((int)big.size())) {
      big[st] ^= 1;
    }
    if (st + k < ((int)big.size())) {
      big[st + k] ^= 1;
    }
    if (st + k + k < ((int)big.size())) {
      big[st + k + k] ^= 1;
    }
  };
  for (int a = 0; a < ((int)big.size()); a++) {
    for (int k = 1; a + k <= ((int)big.size()); k++) {
      for (int b = 0; b < ((int)big.size()); b++) {
        for (int t = 1; b + t <= ((int)big.size()); t++) {
          make(a, k);
          make(b, t);
          bool fail = false;
          for (int first : big) {
            if (first != 0) {
              fail = true;
            }
          }
          if (!fail) {
            vector<vector<int>> rez;
            rez.push_back({a, a + k, a + 2 * k});
            rez.push_back({b, b + t, b + 2 * t});
            return rez;
          }
          make(a, k);
          make(b, t);
        }
      }
    }
  }
  assert(false);
}
vector<int> dist;
vector<int> pref;
void dijkstra(int m) {
  int M = (1 << m);
  dist.resize(M, 1e9);
  pref.resize(M, -1);
  dist[0] = 0;
  deque<int> deq{0};
  while (!deq.empty()) {
    int v = deq[0];
    deq.pop_front();
    for (int i = 0; i < m; i++) {
      for (int k = 1; k * 2 + i < m; k++) {
        int sub = v;
        sub ^= (1 << i);
        sub ^= (1 << (i + k));
        sub ^= (1 << (i + k + k));
        if (dist[sub] > dist[v] + 1) {
          dist[sub] = dist[v] + 1;
          pref[sub] = v;
          deq.push_back(sub);
        }
      }
    }
  }
}
signed main(signed argc, char *argv[]) {
  cin, n;
  v.resize(n);
  cin, v;
  for (int i = 0; i < (n - 13); i++) {
    if (v[i] == 0) continue;
    vector<int> small = {v[i], v[i + 1], v[i + 2]};
    vector<int> big = {v[i], v[i + 1], v[i + 2], v[i + 3], v[i + 4], v[i + 5]};
    if (true) {
      vector<vector<int>> __t = resolve(big);
      for (vector<int> t : __t) {
        act(i + t[0], i + t[1], i + t[2]);
      }
    } else {
      int cnt = small[0] + small[1] + small[2];
      vector<int> ones;
      for (int j = 0; j < (3); j++) {
        if (small[j] == 1) {
          ones.push_back(j);
        }
      }
      if (cnt == 1) {
        act(i + ones[0], i + ones[0] + 3, i + ones[0] + 6);
      } else if (cnt == 2) {
        act(i + ones[0], i + ones[1], i + ones[1] + 2);
      } else if (cnt == 3) {
        act(i, i + 1, i + 2);
      }
    }
  }
  int k = min(13, ((int)v.size()));
  vector<int> end(v.end() - k, v.end());
  int mask = 0;
  for (int i = 0; i < (((int)end.size())); i++) {
    mask = (mask | (end[i] << i));
  }
  dijkstra(k);
  if (dist[mask] == 1e9) {
    smart_io::precall_print();
    cout, "NO";
    return 0;
  }
  while (mask) {
    int next = pref[mask];
    int diff = (next ^ mask);
    vector<int> pos;
    for (int i = 0; i < (k); i++) {
      if ((1 << i) & diff) {
        pos.push_back(i + ((int)v.size()) - k);
      }
    }
    act(pos[0], pos[1], pos[2]);
    mask = next;
  }
  for (int first : v) {
    if (first != 0) {
      smart_io::precall_print();
      cout, "NO";
      return 0;
    }
  }
  smart_io::precall_print();
  cout, "YES";
  smart_io::precall_print();
  cout, ((int)rez.size());
  for (vector<int> sub : rez) {
    smart_io::precall_print();
    cout, sub[0] + 1, sub[1] + 1, sub[2] + 1;
  }
}

### Prompt

Construct a CPP code solution to the problem outlined:

You are given an array a of length n that consists of zeros and ones.

You can perform the following operation multiple times. The operation consists of two steps: 

  1. Choose three integers 1 ≤ x < y < z ≤ n, that form an arithmetic progression (y - x = z - y). 
  2. Flip the values a_x, a_y, a_z (i.e. change 1 to 0, change 0 to 1). 



Determine if it is possible to make all elements of the array equal to zero. If yes, print the operations that lead the the all-zero state. Your solution should not contain more than (⌊ n/3 ⌋ + 12) operations. Here ⌊ q ⌋ denotes the number q rounded down. We can show that it is possible to make all elements equal to zero in no more than this number of operations whenever it is possible to do so at all.

Input

The first line contains a single integer n (3 ≤ n ≤ 10^5) — the length of the array.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 1) — the elements of the array.

Output

Print "YES" (without quotes) if the answer exists, otherwise print "NO" (without quotes). You can print each letter in any case (upper or lower).

If there is an answer, in the second line print an integer m (0 ≤ m ≤ (⌊ n/3 ⌋ + 12)) — the number of operations in your answer.

After that in (i + 2)-th line print the i-th operations — the integers x_i, y_i, z_i. You can print them in arbitrary order.

Examples

Input

5
1 1 0 1 1


Output

YES
2
1 3 5
2 3 4


Input

3
0 1 0


Output

NO

Note

In the first sample the shown output corresponds to the following solution: 

  * 1 1 0 1 1 (initial state); 
  * 0 1 1 1 0 (the flipped positions are the first, the third and the fifth elements); 
  * 0 0 0 0 0 (the flipped positions are the second, the third and the fourth elements). 



Other answers are also possible. In this test the number of operations should not exceed ⌊ 5/3 ⌋ + 12 = 1 + 12 = 13.

In the second sample the only available operation is to flip all the elements. This way it is only possible to obtain the arrays 0 1 0 and 1 0 1, but it is impossible to make all elements equal to zero.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace std::chrono {
long long get_time_ms() {
  return duration_cast<milliseconds>(system_clock::now().time_since_epoch())
      .count();
}
};  // namespace std::chrono
namespace typedefs {}
namespace numbers_operation {
template <class T>
T floor_mod(T a, T b) {
  if (a % b == 0) return 0;
  if (a >= 0 && b >= 0) return a % b;
  if (a <= 0 && b <= 0) return a % b;
  return abs(b) - (abs(a) % abs(b));
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
int n;
vector<int> v;
vector<vector<int>> rez;
void act(int a, int b, int c) {
  assert(a < n && b < n && c < n);
  rez.push_back({a, b, c});
  v[a] ^= 1;
  v[b] ^= 1;
  v[c] ^= 1;
}
vector<vector<int>> resolve(vector<int> big) {
  auto make = [&big](int st, int k) {
    if (st < ((int)big.size())) {
      big[st] ^= 1;
    }
    if (st + k < ((int)big.size())) {
      big[st + k] ^= 1;
    }
    if (st + k + k < ((int)big.size())) {
      big[st + k + k] ^= 1;
    }
  };
  for (int a = 0; a < ((int)big.size()); a++) {
    for (int k = 1; a + k <= ((int)big.size()); k++) {
      for (int b = 0; b < ((int)big.size()); b++) {
        for (int t = 1; b + t <= ((int)big.size()); t++) {
          make(a, k);
          make(b, t);
          bool fail = false;
          for (int first : big) {
            if (first != 0) {
              fail = true;
            }
          }
          if (!fail) {
            vector<vector<int>> rez;
            rez.push_back({a, a + k, a + 2 * k});
            rez.push_back({b, b + t, b + 2 * t});
            return rez;
          }
          make(a, k);
          make(b, t);
        }
      }
    }
  }
  assert(false);
}
vector<int> dist;
vector<int> pref;
void dijkstra(int m) {
  int M = (1 << m);
  dist.resize(M, 1e9);
  pref.resize(M, -1);
  dist[0] = 0;
  deque<int> deq{0};
  while (!deq.empty()) {
    int v = deq[0];
    deq.pop_front();
    for (int i = 0; i < m; i++) {
      for (int k = 1; k * 2 + i < m; k++) {
        int sub = v;
        sub ^= (1 << i);
        sub ^= (1 << (i + k));
        sub ^= (1 << (i + k + k));
        if (dist[sub] > dist[v] + 1) {
          dist[sub] = dist[v] + 1;
          pref[sub] = v;
          deq.push_back(sub);
        }
      }
    }
  }
}
signed main(signed argc, char *argv[]) {
  cin, n;
  v.resize(n);
  cin, v;
  for (int i = 0; i < (n - 13); i++) {
    if (v[i] == 0) continue;
    vector<int> small = {v[i], v[i + 1], v[i + 2]};
    vector<int> big = {v[i], v[i + 1], v[i + 2], v[i + 3], v[i + 4], v[i + 5]};
    if (true) {
      vector<vector<int>> __t = resolve(big);
      for (vector<int> t : __t) {
        act(i + t[0], i + t[1], i + t[2]);
      }
    } else {
      int cnt = small[0] + small[1] + small[2];
      vector<int> ones;
      for (int j = 0; j < (3); j++) {
        if (small[j] == 1) {
          ones.push_back(j);
        }
      }
      if (cnt == 1) {
        act(i + ones[0], i + ones[0] + 3, i + ones[0] + 6);
      } else if (cnt == 2) {
        act(i + ones[0], i + ones[1], i + ones[1] + 2);
      } else if (cnt == 3) {
        act(i, i + 1, i + 2);
      }
    }
  }
  int k = min(13, ((int)v.size()));
  vector<int> end(v.end() - k, v.end());
  int mask = 0;
  for (int i = 0; i < (((int)end.size())); i++) {
    mask = (mask | (end[i] << i));
  }
  dijkstra(k);
  if (dist[mask] == 1e9) {
    smart_io::precall_print();
    cout, "NO";
    return 0;
  }
  while (mask) {
    int next = pref[mask];
    int diff = (next ^ mask);
    vector<int> pos;
    for (int i = 0; i < (k); i++) {
      if ((1 << i) & diff) {
        pos.push_back(i + ((int)v.size()) - k);
      }
    }
    act(pos[0], pos[1], pos[2]);
    mask = next;
  }
  for (int first : v) {
    if (first != 0) {
      smart_io::precall_print();
      cout, "NO";
      return 0;
    }
  }
  smart_io::precall_print();
  cout, "YES";
  smart_io::precall_print();
  cout, ((int)rez.size());
  for (vector<int> sub : rez) {
    smart_io::precall_print();
    cout, sub[0] + 1, sub[1] + 1, sub[2] + 1;
  }
}

```