#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;

using xy = pair<ll, ll>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;

using bs8 = bitset<8>;
using bs16 = bitset<16>;
using bs32 = bitset<32>;
using bs64 = bitset<64>;
using vbs8 = vector<bs8>;
using vbs16 = vector<bs16>;
using vbs32 = vector<bs32>;
using vbs64 = vector<bs64>;

using vs = vector<string>;
using vvs = vector<vs>;

using ull = unsigned long long;
using vul = vector<ull>;

using vd = vector<double>;
using vvd = vector<vd>;

using coord = pair<double, double>;
using vcoord = vector<coord>;

#define rep(var, n) for (ll var = 0; var < (n); var++)
#define cnt(var, n, m) for (ll var = (n); var <= (m); var++)
#define rcnt(var, n, m) for (ll var = (n); var >= (m); var--)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;

/////////////////////////////////////////////////
namespace zz_time {
/// @brief プログラム実行時のタイムポイント
std::chrono::_V2::system_clock::time_point START_TIME =
    std::chrono::system_clock::now();
/// @brief プログラム実行から経過時間をミリ秒で取得
/// @param st 経過開始時刻(基本引数指定する必要なし)
/// @return 経過時間ミリ秒
ll currentTime(std::chrono::_V2::system_clock::time_point st = START_TIME) {
  std::chrono::_V2::system_clock::time_point now =
      std::chrono::system_clock::now();
  return (ll)(std::chrono::duration_cast<std::chrono::milliseconds>(now - st)
                  .count());
};
/// @brief 実行時間が超過していないかの判定
/// @param mSec 実行時間制約ミリ秒
/// @return 実行時間制約以下であればtrue,その他はfalse
bool punctualityTime(const ll& mSec) { return (currentTime() < mSec); }

/// @brief 実行時間が超過しているかの判定
/// @param mSec 実行時間制約ミリ秒
/// @return 実行時間制約超過していればtrue,その他はfalse
bool spendTime(const ll& mSec) { return (currentTime() >= mSec); }
};  // namespace zz_time
using namespace zz_time;

namespace zz_random {
random_device seed_gen;
default_random_engine RANDOM_ENGINE(seed_gen());

/// @brief 整数閉区間[L,R]一様ランダム器生成
/// @param L 下限値 (default 0)
/// @param R 上限値 (default 1)
/// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成
uniform_int_distribution<> createIntCloseSegRandom(const ll& L = 0,
                                                   const ll& R = 1) {
  return uniform_int_distribution<>(L, R);
};

/// @brief 実数閉区間[L,R]一様ランダム器生成
/// @param L 下限値 (default 0.0)
/// @param R 上限値 (default 1.0)
/// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成
uniform_real_distribution<> createRealCloseSegRandom(const double& L = 0.0,
                                                     const double& R = 1.0) {
  return uniform_real_distribution<>(L, R);
};

/// @brief 正規表現ランダム器生成
/// @param average 平均値
/// @param s 標準偏差
/// @return ランダム生成器, RAMDOM_ENGINEを引数としてランダム生成
normal_distribution<> createNormalRandom(const double& average = 0.0,
                                         const double& s = 1.0) {
  return normal_distribution<>(average, s);
};

};  // namespace zz_random
using namespace zz_random;

namespace zz_mod {
class pp {
 public:
  ll val;
  ll mod;
  void recalc() {
    val %= mod;
    if (val < 0) val += mod;
  };

  /// @brief modint (+-*/ != exp ~ inv recalc )
  /// @param x value
  /// @param y mod (default= 998244353)
  pp(const ll& x = 0, const ll& y = 998244353) {
    val = x;
    mod = y;
    recalc();
  };

  friend pp operator+(const pp& x, const pp& y) {
    return pp(x.val + y.val, x.mod);
  };
  friend pp operator+(const pp&& x, const pp& y) {
    return pp(x.val + y.val, x.mod);
  };
  friend pp operator+(const pp& x, const pp&& y) {
    return pp(x.val + y.val, x.mod);
  };
  friend pp operator+(const pp&& x, const pp&& y) {
    return pp(x.val + y.val, x.mod);
  };

  template <typename T>
  friend pp operator+(const pp& x, const T& y) {
    return pp(x.val + y, x.mod);
  };
  template <typename T>
  friend pp operator+(const pp&& x, const T& y) {
    return pp(x.val + y, x.mod);
  };
  template <typename T>
  friend pp operator+(const pp& x, const T&& y) {
    return pp(x.val + y, x.mod);
  };
  template <typename T>
  friend pp operator+(const pp&& x, const T&& y) {
    return pp(x.val + y, x.mod);
  };

  friend pp operator-(const pp& x) { return pp(-x.val, x.mod); };
  friend pp operator-(const pp&& x) { return pp(-x.val, x.mod); };

  friend pp operator-(const pp& x, const pp& y) {
    return pp(x.val - y.val, x.mod);
  };
  friend pp operator-(const pp&& x, const pp& y) {
    return pp(x.val - y.val, x.mod);
  };
  friend pp operator-(const pp& x, const pp&& y) {
    return pp(x.val - y.val, x.mod);
  };
  friend pp operator-(const pp&& x, const pp&& y) {
    return pp(x.val - y.val, x.mod);
  };

  template <typename T>
  friend pp operator-(const pp& x, const T& y) {
    return pp(x.val - y, x.mod);
  };
  template <typename T>
  friend pp operator-(const pp&& x, const T& y) {
    return pp(x.val - y, x.mod);
  };
  template <typename T>
  friend pp operator-(const pp& x, const T&& y) {
    return pp(x.val - y, x.mod);
  };
  template <typename T>
  friend pp operator-(const pp&& x, const T&& y) {
    return pp(x.val - y, x.mod);
  };

  friend pp operator*(const pp& x, const pp& y) {
    return pp(x.val * y.val, x.mod);
  };
  friend pp operator*(const pp&& x, const pp& y) {
    return pp(x.val * y.val, x.mod);
  };
  friend pp operator*(const pp& x, const pp&& y) {
    return pp(x.val * y.val, x.mod);
  };
  friend pp operator*(const pp&& x, const pp&& y) {
    return pp(x.val * y.val, x.mod);
  };

  template <typename T>
  friend pp operator*(const pp& x, const T& y) {
    return pp(x.val * y, x.mod);
  };
  template <typename T>
  friend pp operator*(const pp&& x, const T& y) {
    return pp(x.val * y, x.mod);
  };
  template <typename T>
  friend pp operator*(const pp& x, const T&& y) {
    return pp(x.val * y, x.mod);
  };
  template <typename T>
  friend pp operator*(const pp&& x, const T&& y) {
    return pp(x.val * y, x.mod);
  };

  friend pp operator~(const pp& x) { return x.exp(-1); }
  friend pp operator~(const pp&& x) { return x.exp(-1); }

  friend pp operator/(const pp& x, const pp& y) { return x * (~y); };
  friend pp operator/(const pp&& x, const pp& y) { return x * (~y); };
  friend pp operator/(const pp& x, const pp&& y) { return x * (~y); };
  friend pp operator/(const pp&& x, const pp&& y) { return x * (~y); };

  template <typename T>
  friend pp operator/(const pp& x, const T& y) {
    return x * pp(y, x.mod).inv();
  };
  template <typename T>
  friend pp operator/(const pp&& x, const T& y) {
    return x * pp(y, x.mod).inv();
  };
  template <typename T>
  friend pp operator/(const pp& x, const T&& y) {
    return x * pp(y, x.mod).inv();
  };
  template <typename T>
  friend pp operator/(const pp&& x, const T&& y) {
    return x * pp(y, x.mod).inv();
  };

  friend pp& operator+=(pp& x, const pp& y) {
    x.val += y.val;
    x.recalc();
    return x;
  };
  friend pp& operator+=(pp& x, const pp&& y) {
    x.val += y.val;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator+=(pp& x, const T& y) {
    x.val += y;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator+=(pp& x, const T&& y) {
    x.val += y;
    x.recalc();
    return x;
  };

  friend pp& operator-=(pp& x, const pp& y) {
    x.val -= y.val;
    x.recalc();
    return x;
  };
  friend pp& operator-=(pp& x, const pp&& y) {
    x.val -= y.val;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator-=(pp& x, const T& y) {
    x.val -= y;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator-=(pp& x, const T&& y) {
    x.val -= y;
    x.recalc();
    return x;
  };

  friend pp& operator*=(pp& x, const pp& y) {
    x.val *= y.val;
    x.recalc();
    return x;
  };
  friend pp& operator*=(pp& x, const pp&& y) {
    x.val *= y.val;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator*=(pp& x, const T& y) {
    x.val *= y;
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator*=(pp& x, const T&& y) {
    x.val *= y;
    x.recalc();
    return x;
  };

  friend pp& operator/=(pp& x, const pp& y) {
    x *= pp(y.val, x.mod).inv();
    x.recalc();
    return x;
  };
  friend pp& operator/=(pp& x, const pp&& y) {
    x *= pp(y.val, x.mod).inv();
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator/=(pp& x, const T& y) {
    x *= pp(y, x.mod).inv();
    x.recalc();
    return x;
  };
  template <typename T>
  friend pp& operator/=(pp& x, const T&& y) {
    x *= pp(y, x.mod).inv();
    x.recalc();
    return x;
  };

  pp exp(ll x) const {
    if (x == 0) {
      return pp(1, this->mod);
    }
    pp y = *this;

    if (x > 0) {
      vl Vec;
      while (x > 0) {
        Vec.push_back(x & 1);
        x >>= 1;
      }
      pp ans(1, this->mod);
      each(ite, Vec) {
        if (*ite) ans = ans * y;
        y = y * y;
      }

      return ans;
    }

    return y.exp(y.mod - 2).exp(-x);
  };

  pp inv() const {
    return ~(*this);
    return pp(this->val, this->mod).exp(-1);
  }
};

class factorial {
 public:
  const ll size;
  vector<pp> vec;
  /// @brief mod! (operator[] comb)
  /// @param x max! [0,x]  (default 1000000)
  /// @param y mod (default 998244353)
  factorial(const ll&& x = 1000000, const ll&& y = 998244353) : size(x + 1) {
    vec = vector<pp>(x + 1, pp(1, y));
    cnt(i, 2, x) vec[i] *= (vec[i - 1] * pp(i, y));
  };

  /// @brief mod factorial
  /// @return x! mod
  pp operator[](const ll& x) const { return vec[x]; };

  /// @brief mod factorial
  /// @return x! mod
  pp operator[](const ll&& x) const { return vec[x]; };

  /// @brief mod combination
  /// @param n
  /// @param m
  /// @return nCm
  pp comb(const ll n, const ll m) const {
    return (vec[n] / (vec[m] * vec[n - m]));
  };
};

}  // namespace zz_mod
using namespace zz_mod;

namespace zz_print {

namespace elm {
template <typename Arg>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const Arg&& arg) {
  cout << "[" << arg << "| " << Indent << " " << Space << " ]" << endl;
};

void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const ll& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const int& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const ull& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const unsigned int& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};

template <typename Elm1, typename Elm2>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const pair<Elm1, Elm2>& pr) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "< " << pr.first << " , " << pr.second << " >" << string(Space, ' ');
};

void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space, const pp& pr) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "{ " << pr.val << " | " << pr.mod << " }" << string(Space, ' ');
};

void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const double& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const float& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};

void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const char& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const string& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};

void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const bs8& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const bs16& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const bs32& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const bs64& elm) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << elm << string(Space, ' ');
};

template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const vector<Elm>& Vec) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, Vec) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const list<Elm>& Lst) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, Lst) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};

template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const set<Elm>& SET) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const multiset<Elm>& SET) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const unordered_set<Elm>& SET) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const unordered_multiset<Elm>& SET) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, SET) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};

template <typename Elm1, typename Elm2>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const map<Elm1, Elm2>& MAP) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm1, typename Elm2>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const multimap<Elm1, Elm2>& MAP) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm1, typename Elm2>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const unordered_map<Elm1, Elm2>& MAP) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm1, typename Elm2>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const unordered_multimap<Elm1, Elm2>& MAP) {
  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "[" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  each(ite, MAP) ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0),
                      Space, *ite);
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};

template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const stack<Elm>& Sta) {
  stack<Elm> Datas = Sta;

  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "(" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  while (!Datas.empty()) {
    Elm Data = Datas.top();
    Datas.pop();
    ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space,
         Data);
  }
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const queue<Elm>& Que) {
  queue<Elm> Datas = Que;

  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "(" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  while (!Datas.empty()) {
    Elm Data = Datas.front();
    Datas.pop();
    ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space,
         Data);
  }
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const priority_queue<Elm>& Que) {
  priority_queue<Elm> Datas = Que;

  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "(" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  while (!Datas.empty()) {
    Elm Data = Datas.top();
    Datas.pop();
    ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space,
         Data);
  }
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};
template <typename Elm>
void ZOUT(const ll& FlatHier, const ll& Indent, const ll& Space,
          const deque<Elm>& Que) {
  deque<Elm> Datas = Que;

  if (FlatHier > 0 && Indent > 0) cout << endl << string(Indent, ' ');
  cout << "(" << string(Space, ' ');
  if (FlatHier == 1) cout << endl << string(Indent + (1 + Space), ' ');
  while (!Datas.empty()) {
    Elm Data = Datas.front();
    Datas.pop_front();
    ZOUT(max<ll>(0, FlatHier - 1), Indent + (FlatHier > 0 ? 3 : 0), Space,
         Data);
  }
  if (FlatHier >= 1) cout << endl << string(Indent, ' ');
  cout << "]" << string(Space, ' ');
};

}  // namespace elm

namespace branch {
void ZOUT_branch(const ll& FlatHier, const ll& Indent, const ll& Space) {};
template <typename HeadArg, typename... Args>
void ZOUT_branch(const ll& FlatHier, const ll& Indent, const ll& Space,
                 HeadArg&& headArg, Args&&... args) {
  zz_print::elm::ZOUT(FlatHier, Indent, Space, headArg);
  ZOUT_branch(FlatHier, Indent, Space, std::forward<Args>(args)...);
};
template <typename HeadArg, typename... Args>
void ZOUT_branch(const ll& FlatHier, const ll& Indent, const ll& Space,
                 HeadArg& headArg, Args&... args) {
  zz_print::elm::ZOUT(FlatHier, Indent, Space, headArg);
  ZOUT_branch(FlatHier, Indent, Space, std::forward<Args>(args)...);
};
}  // namespace branch

/// @brief プリント関数
/// @tparam FlatHier 改行による階層表示数 (default 0　改行なし)
/// @tparam Space 表示スペース間隔 (default 2)
/// @tparam InitIndent インデント間隔 (default 0)
/// @tparam ...Args 可変引数型 (指定する必要なし)
/// @param ...args 可変引数
template <ll FlatHier = 0, ll Space = 2, ll InitIndent = 0, typename... Args>
void zout(Args&&... args) {
  cout << flush;
  branch::ZOUT_branch(FlatHier, InitIndent, Space, std::forward<Args>(args)...);
  cout << endl;
};
};  // namespace zz_print
using namespace zz_print;

/////////////////////////////////////////////////
namespace lazeSegment {

template <class S, class F>
class lazySeg {
 private:
 public:
  vector<S> A;
  vector<F> B;
  vxy Rng;

 public:
  const ll N;
  const ll Size;

  lazySeg(ll n = 300000)
      : N([&n] {
          ll x = 1;
          while (x < n) x *= 2;
          return x;
        }()),
        Size(2 * N - 1) {
    A = vector<S>(Size, S::e());
    B = vector<F>(Size, F::id());
    Rng = vxy(Size);
    Rng[0] = make_pair(0, N);
    cnt(i, 1, Size - 1) {
      if (i % 2 == 1) {
        Rng[i] =
            make_pair(Rng[(i - 1) / 2].first,
                      (Rng[(i - 1) / 2].first + Rng[(i - 1) / 2].second) / 2);
      } else {
        Rng[i] =
            make_pair((Rng[(i - 1) / 2].first + Rng[(i - 1) / 2].second) / 2,
                      Rng[(i - 1) / 2].second);
      }
    }
  };

  template <typename... Arg>
  S s(Arg... arg) {
    return S(arg...);
  };
  template <typename... Arg>
  F f(Arg... arg) {
    return F(arg...);
  };

  S get(ll L, ll R, bool dbg = false) {
    S s = S::e();
    if (R <= L) return s;
    L = max<ll>(0, L);
    R = min<ll>(R, N);
    if (N <= L) return s;
    if (R <= 0) return s;
    function<void(const ll&)> Func = [this, &L, &R, &dbg, &s,
                                      &Func](const ll& at) {
      if (at < (N - 1)) {
        B[at * 2 + 1] = B[at] * B[at * 2 + 1];
        B[(at + 1) * 2] = B[at] * B[(at + 1) * 2];
      }
      A[at] = B[at] * A[at];
      B[at] = F::id();

      if ((R <= Rng[at].first) || (Rng[at].second <= L)) {
        if (dbg) cout << " 1 return" << endl;
        return;
      }
      if ((L <= Rng[at].first) && (Rng[at].second <= R)) {
        if (dbg) cout << " 2 in" << endl;
        s = A[at] * s;
      } else {
        if (dbg) cout << " 3 cross" << endl;
        Func((at + 1) * 2);
        Func(at * 2 + 1);
        A[at] = A[at * 2 + 1] * A[(at + 1) * 2];
      }
    };
    Func(0);

    return s;
  };

  void set(ll L, ll R, F Act, bool dbg = false) {
    if (dbg)
      cout << "set(" << L << " " << R << " " << Act.str() << " " << dbg << ")"
           << endl;
    if (R <= L) return;
    L = max<ll>(0, L);
    R = min<ll>(R, N);
    if (N <= L) return;
    if (R <= 0) return;

    function<void(const ll&)> Func = [this, &L, &R, &Act, &dbg,
                                      &Func](const ll& at) {
      if ((L <= Rng[at].first) && (Rng[at].second <= R)) {
        B[at] = Act * B[at];
      }
      if (at < (N - 1)) {
        B[at * 2 + 1] = B[at] * B[at * 2 + 1];
        B[(at + 1) * 2] = B[at] * B[(at + 1) * 2];
      }
      A[at] = B[at] * A[at];
      B[at] = F::id();

      if (dbg)
        cout << "@=" << at << " [" << L << "," << R << ")  Rng=["
             << Rng[at].first << "," << Rng[at].second << ") S=" << A[at].str()
             << " F=" << B[at].str() << endl;

      if ((R <= Rng[at].first) || (Rng[at].second <= L)) {
        if (dbg) cout << " 1 return" << endl;
        return;
      }
      if ((L <= Rng[at].first) && (Rng[at].second <= R)) {
        if (dbg) cout << " 2 in" << endl;
      } else {
        if (dbg) cout << " 3 cross" << endl;

        Func((at + 1) * 2);
        Func(at * 2 + 1);
        A[at] = A[at * 2 + 1] * A[(at + 1) * 2];
      }
    };
    Func(0);
  };

  S operator[](const ll& at) { return get(at, at + 1); };

  string str(const ll& at, const ll rngShow = true, const ll sShow = true,
             const ll fShow = true, const ll length = 0) {
    // S s = get(at, s + 1);
    string T(1, '_');

    if (rngShow)
      T += "[" + to_string(Rng[at].first) + "," + to_string(Rng[at].second) +
           ")";
    if (sShow) {
      if (*T.rbegin() != '_') T.push_back(' ');
      T += A[at].str();
    }
    if (fShow) {
      if (*T.rbegin() != '_') T.push_back(' ');
      T += B[at].str();
    }
    T.push_back('_');
    if (length > 0) {
      while (T.size() < length) T.push_back('_');
    }
    return T;
  }
  void show(const bool Hier = false, const ll rngShow = true,
            const ll sShow = true, const ll fShow = true, const ll length = 0) {
    if (Hier) {
      rep(i, Size) {
        cout << str(i, rngShow, sShow, fShow, length) << flush;
        if (Rng[i].second == N) cout << endl;
      }
    } else {
      rep(i, Size) cout << str(i, rngShow, sShow, fShow, length) << endl;
    }
  }
};

class S_sum {
 public:
  ll e_sum;
  ll len;
  S_sum(const ll& x, const ll& y) : e_sum(x), len(y) {};
  static S_sum e() { return S_sum(0, 1); };
  friend S_sum operator*(const S_sum& l, const S_sum& r) {
    return S_sum(l.e_sum + r.e_sum, l.len + r.len);
  }
  string str() { return "<" + to_string(e_sum) + "," + to_string(len) + ">"; };
  friend string str(S_sum x) { return x.str(); }
};
class F_sum {
 public:
  ll a;
  ll b;
  F_sum(const ll& x, const ll& y) : a(x), b(y) {};
  static F_sum id() { return F_sum(1, 0); };
  friend F_sum operator*(const F_sum& l, const F_sum& r) {
    return F_sum(l.a * r.a, l.a * r.b + l.b);
  };
  friend S_sum operator*(const F_sum& l, const S_sum& r) {
    return S_sum(l.a * r.e_sum + l.b * r.len, r.len);
  };
  string str() { return ("<" + to_string(a) + "," + to_string(b) + ">"); };
  friend string str(F_sum x) { return x.str(); }
};

class S_01 {
 public:
  ll len;
  ll zero;
  ll one;
  ll full;
  ll lft0;
  ll lft1;
  ll rgt0;
  ll rgt1;

  S_01(const ll& b, const ll& x, const ll& y, const ll& z, const ll& a1,
       const ll& a2, const ll& a3, const ll& a4)
      : len(b),
        zero(x),
        one(y),
        full(z),
        lft0(a1),
        lft1(a2),
        rgt0(a3),
        rgt1(a4) {};
  static S_01 e() { return S_01(0, 0, 0, 0, 0, 0, 0, 0); };
  friend S_01 operator*(const S_01& l, const S_01& r) {
    if (l.len == 0) {
      return r;
    }
    if (r.len == 0) {
      return l;
    }

    ll Zero = ((l.full ^ r.full) ? 1 : 0) + l.zero + r.zero +
              (l.full ? r.lft1 : r.lft0) + (r.full ? l.lft1 : l.lft0);
    ll One = ((l.full ^ r.full) ? 0 : 1) + l.one + r.one +
             (l.full ? r.lft0 : r.lft1) + (r.full ? l.lft0 : l.lft1);

    ll L0 = l.lft0 + (l.full == 0 ? r.lft0 : r.lft1) + (l.full ? 0 : 1);
    ll L1 = l.lft1 + (l.full == 0 ? r.lft1 : r.lft0) + (l.full ? 1 : 0);
    ll R0 = r.rgt0 + (r.full == 0 ? l.rgt0 : l.rgt1) + (r.full ? 0 : 1);
    ll R1 = r.rgt1 + (r.full == 0 ? l.rgt1 : l.rgt0) + (r.full ? 1 : 0);
    return S_01(l.len + r.len, Zero, One, (l.full ^ r.full), L0, L1, R0, R1);
  }
  string str() {
    return ("<" + to_string(len) + "|" + to_string(zero) + "|" +
            to_string(one) + " [" + to_string(full) + "] " + to_string(lft0) +
            " " + to_string(lft1) + " | " + to_string(rgt0) + " " +
            to_string(rgt1) + ">");
  };
  friend string str(S_01 x) { return x.str(); }
};
class F_01 {
 public:
  ll len;
  ll zero;
  ll one;
  ll full;
  ll lft0;
  ll lft1;
  ll rgt0;
  ll rgt1;
  F_01(const ll& b, const ll& x, const ll& y, const ll& z, const ll& a1,
       const ll& a2, const ll& a3, const ll& a4)
      : len(b),
        zero(x),
        one(y),
        full(z),
        lft0(a1),
        lft1(a2),
        rgt0(a3),
        rgt1(a4) {};
  static F_01 id() { return F_01(0, 0, 0, 0, 0, 0, 0, 0); };

  friend F_01 operator*(const F_01& l, const F_01& r) {
    return F_01(l.len + r.len, l.zero + r.zero, l.one + r.one, l.full + r.full,
                l.lft0 + r.lft0, l.lft1 + r.lft1, l.rgt0 + r.rgt0,
                l.rgt1 + r.rgt1);
  };
  friend S_01 operator*(const F_01& l, const S_01& r) {
    return S_01(l.len + r.len, l.zero + r.zero, l.one + r.one, l.full + r.full,
                l.lft0 + r.lft0, l.lft1 + r.lft1, l.rgt0 + r.rgt0,
                l.rgt1 + r.rgt1);
  };
  string str() {
    return ("<" + to_string(len) + "|" + to_string(zero) + "|" +
            to_string(one) + " [" + to_string(full) + "] " + to_string(lft0) +
            " " + to_string(lft1) + " | " + to_string(rgt0) + " " +
            to_string(rgt1) + ">");
  };
  friend string str(F_01 x) { return x.str(); }
};

class S_sum998244353 {
 public:
  ll e_sum;
  ll len;
  S_sum998244353(const ll& x, const ll& y) : e_sum(x), len(y) {};
  static S_sum998244353 e() { return S_sum998244353(0, 1); };
  friend S_sum998244353 operator*(const S_sum998244353& l,
                                  const S_sum998244353& r) {
    return S_sum998244353((l.e_sum + r.e_sum) % 998244353,
                          (l.len + r.len) % 998244353);
  }
  string str() { return "<" + to_string(e_sum) + "," + to_string(len) + ">"; };
  friend string str(S_sum998244353 x) { return x.str(); }
};
class F_sum998244353 {
 public:
  ll a;
  ll b;
  F_sum998244353(const ll& x, const ll& y) : a(x), b(y) {};
  static F_sum998244353 id() { return F_sum998244353(1, 0); };
  friend F_sum998244353 operator*(const F_sum998244353& l,
                                  const F_sum998244353& r) {
    return F_sum998244353((l.a * r.a) % 998244353,
                          (((l.a * r.b) % 998244353) + l.b) % 998244353);
  };
  friend S_sum998244353 operator*(const F_sum998244353& l,
                                  const S_sum998244353& r) {
    return S_sum998244353(
        (((l.a * r.e_sum) % 998244353) + ((l.b * r.len) % 998244353)) %
            998244353,
        r.len);
  };
  string str() { return ("<" + to_string(a) + "," + to_string(b) + ">"); };
  friend string str(F_sum998244353 x) { return x.str(); }
};

class S_func998244353 {
 public:
  ll a;
  ll b;
  S_func998244353(const ll& x, const ll& y) : a(x), b(y) {};
  static S_func998244353 e() { return S_func998244353(1, 0); };
  friend S_func998244353 operator*(const S_func998244353& l,
                                   const S_func998244353& r) {
    return S_func998244353((r.a * l.a) % 998244353,
                           (((r.a * l.b) % 998244353) + r.b) % 998244353);
  }
  string str() { return "<" + to_string(a) + "," + to_string(b) + ">"; };
  friend string str(S_func998244353 x) { return x.str(); }
};
struct F_func998244353 {
 public:
  ll a;
  ll b;
  ll c;
  ll d;
  F_func998244353(const ll& x, const ll& y, const ll& z, const ll& w)
      : a(x), b(y), c(z), d(w) {};
  static F_func998244353 id() { return F_func998244353(1, 0, 1, 0); };
  friend F_func998244353 operator*(const F_func998244353& l,
                                   const F_func998244353& r) {
    return F_func998244353(
        (r.a * l.a) % 998244353, (((r.a * l.b) % 998244353) + r.b) % 998244353,
        (r.c * l.c) % 998244353, (((r.c * l.d) % 998244353) + r.d) % 998244353);
  };
  friend S_func998244353 operator*(const F_func998244353& l,

                                   const S_func998244353& r) {
    return S_func998244353((((l.a * r.a) % 998244353) + l.b) % 998244353,
                           (((l.c * r.b) % 998244353) + l.d) % 998244353);
  };
  string str() {
    return ("<" + to_string(a) + "," + to_string(b) + "," + to_string(c) + "," +
            to_string(d) + ">");
  };
  friend string str(F_func998244353 x) { return x.str(); }
};

class S_bitflp {
 public:
  ll zero;
  ll one;
  ll zo;
  ll oz;
  S_bitflp(const ll& x, const ll& y, const ll& z, const ll& w)
      : zero(x), one(y), zo(z), oz(w) {};
  static S_bitflp e() { return S_bitflp(0, 0, 0, 0); };
  friend S_bitflp operator*(const S_bitflp& l, const S_bitflp& r) {
    return S_bitflp(l.zero + r.zero, l.one + r.one,
                    l.zo + r.zo + l.zero * r.one, l.oz + r.oz + l.one * r.zero);
  }

  string str() {
    return "<" + to_string(zero) + "," + to_string(one) + "," + to_string(zo) +
           "," + to_string(oz) + ">";
  };
  friend string str(S_bitflp x) { return x.str(); }
};

class F_bitflp {
 public:
  ll flp;
  ll set_a;
  ll set_b;
  F_bitflp(const ll& x, const ll& y, const ll& z)
      : flp(x), set_a(y), set_b(z) {};
  static F_bitflp id() { return F_bitflp(0, 1, 0); };
  friend F_bitflp operator*(const F_bitflp& l, const F_bitflp& r) {
    return F_bitflp((l.flp + r.flp) % 2, l.set_a, l.set_b);
  };
  friend S_bitflp operator*(const F_bitflp& l, const S_bitflp& r) {
    if (l.flp == 0) {
      if (l.set_a != 1) {
        return S_bitflp(l.set_b == 0, l.set_b == 1, 0, 0);
      }
      return r;
    }
    return S_bitflp(r.one, r.zero, r.oz, r.zo);
  };
  string str() { return ("<" + to_string(flp) + ">"); };
  friend string str(F_bitflp x) { return x.str(); }
};

using sum = lazySeg<lazeSegment::S_sum, lazeSegment::F_sum>;

using zz01 = lazySeg<lazeSegment::S_01, lazeSegment::F_01>;

using sum998244353 =
    lazySeg<lazeSegment::S_sum998244353, lazeSegment::F_sum998244353>;

using func998244353 =
    lazySeg<lazeSegment::S_func998244353, lazeSegment::F_func998244353>;

using bitflip =
    lazeSegment::lazySeg<lazeSegment::S_bitflp, lazeSegment::F_bitflp>;
};  // namespace lazeSegment

int main() {
  ll N, Q;
  cin >> N >> Q;
  vl A(N);
  rep(i, N) cin >> A[i];

  vxy Query(N);
  rep(i, N) cin >> Query[i].first >> Query[i].second;

  vector<lazeSegment::zz01> SEGvec(27, lazeSegment::zz01(N));
  rep(i, N) {
    ll X = A[i];
    // zout(i, bs32(A[i]));
    rep(j, 27) {
      if (X & (1 << j)) {
        SEGvec[j].set(i, i + 1, SEGvec[j].f(1, 1, 0, 1, 1, 0, 1, 0));
      }
      X >>= 1;
    }
  }
  rep(i, Q) {
    // zout("@=", i);
    ll Cnt = 0;
    rep(j, 27) {
      // zout("- j=", j);
      // SEGvec[i].show(true);

      Cnt +=
          (1LL << j) * SEGvec[j].get(Query[i].first, Query[i].second + 1).one;
    }
    cout << Cnt << endl;
  }

  return 0;
}