#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
long long max(long long a, int b){return std::max(a, (long long)b);}
long long max(int a, long long b){return std::max((long long)a, b);}
long long min(long long a, int b){return std::min(a, (long long)b);}
long long min(int a, long long b){return std::min((long long)a, b);}
long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;}

template<typename T>
struct safe_vector : std::vector<T>{
  using std::vector<T>::vector;
  T& operator [](size_t i){return this->at(i);}
};

template<typename T, int N>
struct safe_array : std::array<T, N>{
  using std::array<T, N>::array;
  T& operator [](size_t i){return this->at(i);}
};
ll ceil_div(ll x, ll y){
  assert(y > 0);
  return (x + (x > 0 ? y - 1 : 0)) / y;
}
ll floor_div(ll x, ll y){
  assert(y > 0);
  return (x + (x > 0 ? 0 : -y + 1)) / y;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}






std::vector<char> stovector(const std::string &s){
  int n = s.size();
  std::vector<char> res(n);
  for(int i = 0; i < n; i++) res[i] = s[i];
  return res;
}
// cを0としてintに直す
std::vector<int> stovector_int(const std::string &s, char c = 'a'){
  int n = s.size();
  std::vector<int> res(n);
  for(int i = 0; i < n; i++) res[i] = s[i] - c;
  return res;
}
#include <sstream>
std::vector<std::string> split(const std::string &s, char delim){
  std::vector<std::string> elems;
  std::stringstream ss(s);
  std::string item;
  while(std::getline(ss, item, delim)){
    if(!item.empty()) elems.push_back(item);
  }
  return elems;
}

template<typename T>
std::vector<std::pair<T, int>> runlength(const std::vector<T> &v){
  std::vector<std::pair<T, int>> ret;
  int n = v.size();
  for(int i = 0; i < n; i++){
    if(ret.empty() || ret.back().first != v[i]){
      ret.push_back({v[i], 1});
    }else{
      ret.back().second++;
    }
  }
  return ret;
}
// 全ての要素が [0, NUM_VAL)
template<int NUM_VAL = 26>
struct string_processor{
private:
  static constexpr int s = 64, sdiv = 6, smod = 63;
  using Z = uint64_t;
  int N;
  std::vector<std::array<int, NUM_VAL>> B;
  std::vector<std::array<Z, NUM_VAL>> S;
  std::vector<std::vector<int>> V;
public:
  string_processor(){}
  string_processor(const std::vector<int> &v): N(v.size()){
    int M = (N + s - 1) / s;
    V.resize(NUM_VAL, std::vector<int>());
    std::array<int, NUM_VAL> pop;
    std::array<Z, NUM_VAL> pop_small;
    pop.fill(0);
    pop_small.fill(0);
    B.resize(M + 1, pop);
    S.resize(M, pop_small);
    for(int i = 0, t = 0, sz = 0; i < N; i++, t++){
      int x = v[i];
      assert(0 <= x && x < NUM_VAL);
      V[x].push_back(i);
      pop[x]++, pop_small[x] |= (Z(1) << t);
      if(t == s - 1 || i == N - 1){
        for(int j = 0; j < NUM_VAL; j++){
          if(j) pop[j] += pop[j - 1], pop_small[j] |= pop_small[j - 1];
          B[sz + 1][j] = pop[j] + B[sz][j];
          S[sz][j] = pop_small[j];
        }
        pop.fill(0);
        pop_small.fill(0);
        t = -1;
        sz++;
      }
    }
  }
  // count c, i < r, O(1)
  int rank(int r, int c){
    if(c == 0) return rank_lower(r, c);
    assert(0 <= r && r <= N);
    assert(0 <= c && c < NUM_VAL);
    int rq = r >> sdiv, rm = r & smod;
    int ret = B[rq][c] - B[rq][c - 1];
    if(rm) ret += __builtin_popcountll((S[rq][c] ^ S[rq][c - 1]) << (s - rm));
    return ret;
  }
  // count [0, c], i < r, O(1)
  int rank_lower(int r, int c){
    assert(0 <= r && r <= N);
    assert(0 <= c && c < NUM_VAL);
    int rq = r >> sdiv, rm = r & smod;
    int ret = B[rq][c];
    if(rm) ret += __builtin_popcountll(S[rq][c] << (s - rm));
    return ret;
  }
  // k番目のc, ない場合は-1 O(1)
  int select(int k, int c){
    assert(0 <= c && c < NUM_VAL);
    return (k < 0 || V[c].size() <= k) ? -1 : V[c][k];
  }
  // k番目のc以下, ない場合は-1 O(logN)
  int select_lower(int k, int c){
    assert(0 <= c && c < NUM_VAL);
    int l = 0, r = N + 1;
    while(r - l > 1){
      int mid = (l + r) >> 1;
      if(rank_lower(mid, c) <= k) l = mid;
      else r = mid;
    }
    return r == N + 1 ? -1 : l;
  }
  // [i, n)で最も左のc
  int find_next(int i, int c){
    return select(rank(i, c), c);
  }
  // [0, i]で最も右のc
  int find_prev(int i, int c){
    return select(rank(i + 1, c) - 1, c);
  }
};



unsigned long long random_once(){
  static std::random_device seed_gen;
  static std::mt19937_64 engine(seed_gen());
  static unsigned long long ret = engine();
  return ret;
}

unsigned long long random_number(){
  static std::random_device seed_gen;
  static std::mt19937_64 engine(seed_gen());
  return engine();
}

// [low, high]
unsigned long long random_number(unsigned long long low, unsigned long long high){
  static std::random_device seed_gen;
  static std::mt19937_64 engine(seed_gen());
  assert(high >= low);
  unsigned long long diff = high - low + 1;
  return engine() % diff + low;
}



#include <cstdint>
#include <limits>

// ak + b のl <= k < rにおける和
template<typename T = long long>
T arithmetic_sum(T a, T b, T l, T r){
  return a * (r * (r - 1) - l * (l - 1)) / 2 + b * (r - l);
}
// a * k^2の　l <= k < rにおける和
template<typename T = long long>
T square_sum(T a, T l, T r){
  return (r * (r - 1) * (2 * r - 1) - l * (l - 1) * (2 * l - 1)) / 6 * a;
}
// a^k * b のl <= k < rにおける和
// b * (a^r - a^l) / (a - 1)
template<typename T>
T geometric_sum(T a, T b, T l, T r){
  if(a == 1) return 0;
  return b * (a.pow(r) - a.pow(l)) / (a - 1);
}
// @param 0 <= b, a^bがオーバーフローしない
long long llpow(long long a, long long b){
  assert(0 <= b);
  long long ret = 1;
  while(b){
    if(b & 1) ret *= a;
    a *= a;
    b >>= 1;
  }
  return ret;
}
// a^b, オーバーフローする場合numeric_limits<ull>
// @param 0 <= a, b
unsigned long long ullpow_of(unsigned long long a, unsigned long long b){
  static constexpr unsigned long long inf = std::numeric_limits<unsigned long long>::max();
  unsigned long long ret = 1;
  while(b){
    if(b & 1){
      if(ret >= inf / a) return inf;
      ret *= a;
    }
    a = (a >= inf / a ? inf : a * a);
    b >>= 1;
  }
  return ret;
}

long long gcd(long long _a, long long _b){
  uint64_t a = abs(_a), b = abs(_b);
  if(a == 0) return b;
  if(b == 0) return a;
  int shift = __builtin_ctzll(a | b);
  a >>= __builtin_ctzll(a);
  do{
    b >>= __builtin_ctzll(b);
    if(a > b) std::swap(a, b);
    b -= a;
  }while(b);
  return (a << shift);
}
// 64bitに収まらない可能性あり
template<typename T>
long long lcm(T a, T b){
  return __int128_t(a) * b / gcd(a, b);
}

// min(lcm(a, b), inf)
template<typename T>
T lcm_limited(T a, T b, T inf){
  if(a >= inf || b >= inf) return inf;
  b /= gcd(a, b);
  return (inf / a) < b ? inf : a * b;
}

std::tuple<long long, long long, long long> extgcd(long long a, long long b){
  long long x, y;
  for(long long u = y = 1, v = x = 0; a;){
    long long q = b / a;
    std::swap(x -= q * u, u);
    std::swap(y -= q * v, v);
    std::swap(b -= q * a, a);
  }
  return {x, y, b};//return {x, y, gcd(a, b)} s.t. ax + by = gcd(a, b)
}
constexpr long long __safe_mod(long long x, long long m){
  x %= m;
  if (x < 0) x += m;
  return x;
}
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_ext_gcd(long long a, long long b) {
  a = __safe_mod(a, b);
  if (a == 0) return {b, 0};
  long long s = b, t = a;
  long long m0 = 0, m1 = 1;
  while (t){
    long long u = s / t;
    s -= t * u;
    m0 -= m1 * u;
    auto tmp = s;
    s = t;
    t = tmp;
    tmp = m0;
    m0 = m1;
    m1 = tmp;
  }
  if (m0 < 0) m0 += b / s;
  return {s, m0};
}
// {lcm, ans}
std::pair<long long, long long> crt(const std::vector<long long>& r, const std::vector<long long>& m){
  assert(r.size() == m.size());
  int n = int(r.size());
  // Contracts: 0 <= r0 < m0
  long long r0 = 0, m0 = 1;
  for(int i = 0; i < n; i++){
    assert(1 <= m[i]);
    long long r1 = __safe_mod(r[i], m[i]), m1 = m[i];
    if(m0 < m1){
      std::swap(r0, r1);
      std::swap(m0, m1);
    }
    if(m0 % m1 == 0){
      if(r0 % m1 != r1) return {0, 0};
      continue;
    }
    long long g, im;
    std::tie(g, im) = inv_ext_gcd(m0, m1);
    long long u1 = (m1 / g);
    if ((r1 - r0) % g) return {0, 0};
    long long x = (r1 - r0) / g % u1 * im % u1;
    r0 += x * m0;
    m0 *= u1;
    if (r0 < 0) r0 += m0;
  }
  return {r0, m0};
}

// ai + bj = cの li <= i < ri かつ lj <= j < rjを満たす整数解
// 制約: a, b, c, li, ri, lj, riの絶対値が10^18以下(負でもいい)
//      a, b != 0
long long count_solution(long long a, long long b, long long c, long long li, long long ri, long long lj, long long rj){
  if(li >= (ri--) || lj >= (rj--)) return 0;
  if(a < 0){
    a *= -1, li *= -1, ri *= -1;
    std::swap(li, ri);
  }
  if(b < 0){
    b *= -1, lj *= -1, rj *= -1;
    std::swap(lj, rj);
  }
  assert(a && b);
  auto [i, j, g] = extgcd(a, b);
  if(c % g != 0) return 0;
  a /= g, b /= g, c /= g;
  __int128_t i2 = (__int128_t)i * c;
  __int128_t j2 = (__int128_t)j * c;
  // 任意の整数kに対してa(i2 + bk) + b(j2 - ak) = cを満たす
  __int128_t lk1 = i2 >= li ? -(i2 - li) / b : (li - i2 + b - 1) / b;
  __int128_t rk1 = i2 >= ri ? -(i2 - ri + b - 1) / b : (ri - i2) / b;
  __int128_t lk2 = j2 >= rj ? (j2 - rj + a - 1) / a : -(rj - j2) / a;
  __int128_t rk2 = j2 >= lj ? (j2 - lj) / a : -(lj - j2 + a - 1) / a;
  lk1 = std::max(lk1, lk2);
  rk1 = std::min(rk1, rk2);
  if(lk1 > rk1) return 0;
  return rk1 - lk1 + 1;
}

// 2^k >= xとなる最小の2^k
uint64_t ceil_2_pow(uint64_t x){
  static uint64_t INF = std::numeric_limits<uint64_t>::max();
  uint64_t ret = uint64_t(1) << (63 - __builtin_clzll(x));
  if(ret == x) return x;
  assert(ret <= (INF >> 1));
  return ret << 1;
}






struct barrett_reduction{
  unsigned int mod;
  unsigned long long m;
  barrett_reduction(unsigned int _mod) : mod(_mod){
    m = ((__uint128_t)1 << 64) / mod;
  }
  unsigned int reduce(unsigned int a){
    unsigned long long q = ((__uint128_t)a * m) >> 64;
    a -= q * mod; // 0 <= a < 2 * mod
    // return a;
    return a >= mod ? a - mod : a;
  }
  unsigned int mul(unsigned int a, unsigned int b){
    return reduce((unsigned long long)a * b);
  }
  // {gcd(a, mod), x}, such that a * x ≡ gcd(a, mod)
  std::pair<unsigned int, unsigned int> inv(unsigned int a){
    if(a >= mod) a = reduce(a);
    if(a == 0) return {mod, 0};
    unsigned int s = mod, t = a;
    long long m0 = 0, m1 = 1;
    while(t){
      int u = s / t;
      s -= t * u;
      m0 -= m1 * u;
      std::swap(m0, m1);
      std::swap(s, t);
    }
    if(m0 < 0) m0 += mod / s;
    return {s, m0};
  }
};
// 64bit mod対応
// R = 2^64
// 偶数modだと壊れる
struct montgomery_reduction_64bit{
private:
  // [0, 2 * MOD)
  inline uint64_t reduce_unsafe(__uint128_t x) const{
    x = (x + ((uint64_t)x * (uint64_t)NEG_INV) * MOD) >> 64;
    return x;
  }
  void _set_mod(uint64_t mod){
    assert((mod < (1ULL << 63)) && (mod & 1));
    MOD = mod;
    NEG_INV = 0;
    __uint128_t s = 1, t = 0;
    for(int i = 0; i < 64; i++){
      if (~t & 1) {
        t += MOD;
        NEG_INV += s;
      }
      t >>= 1;
      s <<= 1;
    }
    R2 = ((__uint128_t)1 << 64) % MOD;
    R2 = R2 * R2 % MOD;
    ONE = generate(1);
  }
  __uint128_t MOD, NEG_INV, R2;
  uint64_t ONE;
public:
  montgomery_reduction_64bit(){}
  montgomery_reduction_64bit(uint64_t mod){_set_mod(mod);}
  void set_mod(uint64_t mod){
    _set_mod(mod);
  }
  uint64_t mod()const{
    return MOD;
  }
  inline uint64_t one()const{
    return ONE;
  }
  inline uint64_t generate(uint64_t x)const{
    return reduce((__uint128_t)x * R2);
  }
  inline uint64_t reduce(__uint128_t x)const{
    x = (x + ((uint64_t)x * (uint64_t)NEG_INV) * MOD) >> 64;
    return x < MOD ? x : x - MOD;
  }
  inline uint64_t fix(uint64_t x)const{
    return x < MOD ? x : x - MOD;
  }
  // [0, 2MOD)
  inline uint64_t mul(uint64_t mx, uint64_t my)const{
    return reduce_unsafe((__uint128_t)mx * my);
  }
  inline uint64_t mul_safe(uint64_t mx, uint64_t my)const{
    return reduce((__uint128_t)mx * my);
  }
  // [0, 2MOD)
  inline uint64_t add(uint64_t mx, uint64_t my)const{
    return (mx >= MOD ? mx - MOD : mx) + (my >= MOD ? my - MOD : my);
  }
  inline uint64_t add_safe(uint64_t mx, uint64_t my)const{
    uint64_t res = (mx >= MOD ? mx - MOD : mx) + (my >= MOD ? my - MOD : my);
    return res >= MOD ? res - MOD : res;
  }
  // [0, 2MOD)
  inline uint64_t sub(uint64_t mx, uint64_t my)const{
    if(my >= MOD) my -= MOD;
    return mx >= my ? mx - my : mx + MOD - my;
  }
  inline uint64_t sub_safe(uint64_t mx, uint64_t my)const{
    if(my >= MOD) my -= MOD;
    uint64_t res = mx >= my ? mx - my : mx + MOD - my;
    return res >= MOD ? res - MOD : res;
  }
  inline uint64_t pow(uint64_t ma, uint64_t b)const{
    uint64_t ret = one();
    while(b){
      if(b & 1) ret = mul(ret, ma);
      ma = mul(ma, ma);
      b >>= 1;
    }
    return ret;
  }
  inline uint64_t pow_safe(uint64_t ma, uint64_t b)const{
    return fix(pow(ma, b));
  }
};
unsigned long long mod_pow_mr(unsigned long long a, unsigned long long b, unsigned long long m){
  montgomery_reduction_64bit mr(m);
  return mr.reduce(mr.pow(mr.generate(a), b));
}

namespace prime_sieve{
  std::vector<int> primes, min_factor;// 素数, 各数を割り切る最小の素数
  // O(MAX_N loglog MAX_N)
  // [1, MAX_N]を扱えるように初期化
  void init(int MAX_N){
    min_factor.resize(MAX_N + 1, -1);
    for(int i = 2; i <= MAX_N; i++){
      if(min_factor[i] == -1){
        primes.push_back(i);
        min_factor[i] = i;
      }
      for(int p : primes){
        if((long long)p * i > MAX_N || p > min_factor[i]) break;
        min_factor[p * i] = p;
      }
    }
  }
  bool is_prime(int n){
    assert(n < min_factor.size());
    return n == min_factor[n];
  }
  // {{素因数, 数}}, O(log n)
  std::vector<std::pair<int, int>> factorize(int n){
    assert(n < min_factor.size());
    std::vector<std::pair<int, int>> ret;
    while(n > 1){
      int cnt = 0, f = min_factor[n];
      while(n % f == 0){
        n /= f;
        cnt++;
      }
      ret.push_back({f, cnt});
    }
    return ret;
  }
  // 約数列挙, O(√n)
  std::vector<int> divisor(int n){
    auto p = factorize(n);
    std::vector<std::vector<int>> x;
    for(int i = 0; i < p.size(); i++){
      x.push_back(std::vector<int>{1});
      for(int j = 0; j < p[i].second; j++) x[i].push_back(x[i][j] * p[i].first);
    }
    int l = 0, r = 1;
    std::vector<int> ret{1};
    for(int i = 0; i < x.size(); i++){
      for(auto e : x[i]){
        for(int j = l; j < r; j++){
          ret.push_back(ret[j] * e);
        }
      }
      l = r;
      r = ret.size();
    }
    return std::vector<int>(ret.begin() + l, ret.end());
  }
  // O(logN)
  unsigned long long totient_function(unsigned long long n){
    unsigned long long res = n;
    int prev = -1;
    while(n > 1){
      if(min_factor[n] > prev){
        res -= res / min_factor[n];
        prev = min_factor[n];
      }
      n /= min_factor[n];
    }
    return res;
  }
  int mobius_function(int x){
    int pcnt = 0;
    while(x > 1){
      int y = x / min_factor[x];
      if(min_factor[x] == min_factor[y]) return 0;
      x = y;
      pcnt++;
    }
    return pcnt % 2 == 0 ? 1 : -1;
  }
};

bool _miller_rabin_mr(unsigned long long n, const montgomery_reduction_64bit &mr){
  static std::vector<int> small_p{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
  static std::vector<unsigned long long> A{2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  static std::vector<unsigned long long> B{2, 7, 61};
  if(n <= 1) return false;
  if(n <= 50){
    for(int l = n < 20 ? 0 : 8, r = n < 20 ? 8 : 15; l < r; l++) if(small_p[l] == n) return true;
    return false;
  }
  if(!(n & 1)) return false;
  unsigned long long d = n - 1;
  unsigned long long one = mr.one(), mone = mr.generate(n - 1);
  d >>= __builtin_ctzll(d);
  for(unsigned long long a : (n >> 32) ? A : B){
    if(a % n == 0) continue;
    unsigned long long d2s = d; // d * 2^s, 0 <= s <= (n - 1)が2で割れる回数
    unsigned long long y = mr.pow_safe(mr.generate(a), d);
    while(d2s != n - 1 && y != one && y != mone){
      y = mr.mul_safe(y, y);
      d2s <<= 1;
    }
    if(y != mone && !(d2s & 1)) return false;
  }
  return true;
}
bool miller_rabin_mr(unsigned long long n){
  if(n % 2 == 0) return n == 2 ? true : false;
  montgomery_reduction_64bit mr(n);
  return _miller_rabin_mr(n, mr);
}
// https://en.wikipedia.org/wiki/Binary_GCD_algorithm
unsigned long long binary_gcd(unsigned long long a, unsigned long long b){
  if(!a || !b) return !a ? b : a;
  int shift = __builtin_ctzll(a | b); // [1] gcd(2a', 2b') = 2 * gcd(a', b')
  a >>= __builtin_ctzll(a);
  do{
    // if b is odd
    // gcd(2a', b) = gcd(a', b), if a = 2a'(a is even)
    // gcd(a, b) = gcd(|a - b|, min(a, b)), if a is odd
    b >>= __builtin_ctzll(b); // make b odd
    if(a > b) std::swap(a, b);
    b -= a;
  }while(b); // gcd(a, 0) = a
  return a << shift; // [1]
}
unsigned long long generate_random_prime(unsigned long long min_n = 2, unsigned long long max_n = ~0ULL){
  std::random_device seed_gen;
  std::mt19937_64 engine(seed_gen());
  __uint128_t len = max_n - min_n + 1;
  // https://en.wikipedia.org/wiki/Prime_number_theorem
  while(true){
    unsigned long long a = engine() % len + min_n;
    if(miller_rabin_mr(a)){
      return a;
    }
  }
}
namespace rho_factorization{
  unsigned long long rho(unsigned long long n){
    static std::vector<int> small_p{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

    for(int sp : small_p) if(n % sp == 0) return sp; // n < 50

    montgomery_reduction_64bit mr(n);
    if(_miller_rabin_mr(n, mr)) return n;

    auto try_factorize = [n, mr](unsigned long long c){
      c = mr.generate(c);
      auto f = [mr, c](unsigned long long mx){
        return mr.add(mr.mul(mx, mx), c);
      };
      unsigned long long m = 1LL << ((64 - __builtin_clzll(n)) / 8);
      unsigned long long y = n, r = 1, q = 1;
      unsigned long long x, g, k, ys;
      do{
        x = y;
        y = mr.generate(y);
        for(int i = 0; i < r; i++) y = f(y);
        y = mr.reduce(y);

        k = 0;
        while(k < r && g == 1){
          q = mr.generate(q);
          y = mr.generate(y);
          ys = y;
          for(int i = 0; i < std::min(m, r - k); i++){
            y = f(y);
            unsigned long long z = mr.reduce(y);
            q = mr.mul(q, mr.generate(x > z ? x - z : z - x));
          }
          y = mr.reduce(y);
          g = binary_gcd(mr.reduce(q), n);
          k += m;
        }
        r <<= 1;
      }while(g == 1);
      if(g == n){
        do{
          ys = f(ys);
          unsigned long long z = mr.reduce(ys);
          g = binary_gcd(x > z ? x - z : z - x, n);
        }while(g == 1);
      }
      return g; // g == n when failure
    };
    unsigned long long c = 1, res = n;
    do{
      res = try_factorize(c);
      // c = generate_random_prime(2, n - 1);
      c = (c + 1) % n;
    }while(res == n);
    return res;
  }
  std::vector<unsigned long long> factorize(unsigned long long n){
    if(n <= 1) return {};
    unsigned long long x = rho(n);
    if(x == n) return {x};
    auto l = factorize(x);
    auto r = factorize(n / x);
    l.insert(l.end(), r.begin(), r.end());
    return l;
  }
  // {素数, 個数}の形で返す
  std::vector<std::pair<unsigned long long, int>> factorize2(unsigned long long n){
    auto p = factorize(n);
    sort(p.begin(), p.end());
    std::vector<std::pair<unsigned long long, int>> ret;
    for(int i : p){
      if(ret.empty() || ret.back().first != i) ret.push_back({i, 1});
      else ret.back().second++;
    }
    return ret;
  }
  // 素因数の集合(重複なし, ソート済)を返す
  std::vector<unsigned long long> prime_factor(unsigned long long n){
    auto p = factorize(n);
    std::sort(p.begin(), p.end());
    p.erase(std::unique(p.begin(), p.end()), p.end());
    return p;
  }
  // 10^18以下の高度合成数 897612484786617600の約数が103680個なので全列挙して良さそう
  std::vector<unsigned long long> divisor(unsigned long long n){
    auto p = factorize(n);
    std::sort(p.begin(), p.end());

    std::vector<std::pair<unsigned long long, int>> x;

    for(int i = 0; i < p.size(); i++){
      if(!i || p[i] != p[i - 1]) x.push_back({p[i], 1});
      else x.back().second++;
    }
    int sz = 1;
    for(auto [p_cur, cnt] : x) sz *= cnt + 1;

    std::vector<unsigned long long> res(sz);
    res[0] = 1;
    int r_prev = 1, r = 1;
    for(auto [p_cur, cnt] : x){
      unsigned long long ppow = 1;
      for(int c = 0; c < cnt; c++){
        ppow *= p_cur;
        for(int i = 0; i < r_prev; i++){
          res[r++] = res[i] * ppow;
        }
      }
      r_prev = r;
    }
    return res;
  }
  int mobius_function(long long x){
    auto P = rho_factorization::factorize(x);
    for(long long p : P) if((x / p) % p == 0) return 0;
    return P.size() % 2 == 0 ? 1 : -1;
  }
  unsigned long long totient_function(unsigned long long n){
    unsigned long long res = n;
    auto prims = rho_factorization::prime_factor(n);
    for(auto p : prims) res -= res / p;
    return res;
  }
};
// p: 素数
unsigned long long find_primitive_root(unsigned long long p){
  static std::random_device seed_gen;
  static std::mt19937_64 engine(seed_gen());
  //assert(miller_rabin_mr(p));
  auto primes = rho_factorization::prime_factor(p - 1);
  while(true){
    bool f = true;
    unsigned long long a = engine() % (p - 1) + 1;
    for(unsigned long long pk : primes){
      // a ^ (p - 1) / pk ≡ 1 (mod p) -> no
      if(mod_pow_mr(a, (p - 1) / pk, p) == 1){
        f = false;
        break;
      }
    }
    if(f) return a;
  }
}

struct bigint_prime_factor{
  int sq, max_x;
  std::vector<int> low;
  std::unordered_map<int, int> high;
  bigint_prime_factor(int max_x): sq(sqrt(max_x)), max_x(max_x), low(sq + 1, 0){
    // 篩が初期化済か
    assert(prime_sieve::min_factor.size() > max_x);
  }
  // O(log(x))
  // x^kを掛ける
  void mul(int x, int k = 1){
    assert(0 < x && x <= max_x);
    while(x > 1){
      int p = prime_sieve::min_factor[x];
      if(p <= sq) low[p] += k;
      else{
        auto [itr, f] = high.emplace(x, k);
        if(!f) itr->second += k;
      }
      x /= p;
    }
  }
  // O(log(x))
  // x^kで割る(割り切れない場合エラー)
  void div(int x, int k = 1){
    assert(0 < x && x <= max_x);
    while(x > 1){
      int p = prime_sieve::min_factor[x];
      if(p <= sq){
        assert(low[p] >= k);
        low[p] -= k;
      }else{
        auto itr = high.find(p);
        assert(itr != high.end() && itr->second >= k);
        itr->second -= k;
        if(itr->second == 0) high.erase(itr);
      }
      x /= p;
    }
  }
  // 素数pで何回割れるか, O(1)
  // pが素数でない場合0
  int k_divisible_prime(int p){
    if(p > max_x || !prime_sieve::is_prime(p)) return 0;
    if(p > sq){
      auto itr = high.find(p);
      return itr == high.end() ? 0 : itr->second;
    }
    return low[p];
  }
  // xで何回割れるか, O(log(x))
  // x = 1のときinf回割れる
  // @param 0 < x <= 篩の最大値
  int k_divisible(int x){
    assert(x > 0);
    static constexpr int inf = std::numeric_limits<int>::max();
    int ans = inf;
    for(auto [p, num] : prime_sieve::factorize(x)){
      if(p > sq){
        auto itr = high.find(p);
        if(itr == high.end()) return 0;
        ans = std::min(ans, itr->second / num);
      }else{
        ans = std::min(ans, low[p] / num);
      }
    }
    return ans;
  }
  // rで何回割り切れるか, O(sqrt(r.max_x)以下の素数 + rの素因数の種類)
  int k_divisible(const bigint_prime_factor &r){
    static constexpr int inf = std::numeric_limits<int>::max();
    int ans = inf;
    
    for(int i = 0; prime_sieve::primes[i] <= r.sq; i++){
      int p = prime_sieve::primes[i];
      if(!r.low[p]) continue;
      if(p <= sq){
        if(low[p] < r.low[p]) return 0;
        ans = std::min(ans, low[p] / r.low[p]);
      }else{
        auto itr = high.find(p);
        if(itr->second < r.low[p]) return 0;
        ans = std::min(ans, itr->second / r.low[p]);
      }
    }
    for(auto [p, num] : r.high){
      assert(num);
      if(p <= sq){
        if(low[p] < num) return 0;
        ans = std::min(ans, low[p] / num);
      }else{
        auto itr = high.find(p);
        if(itr->second < num) return 0;
        ans = std::min(ans, itr->second / num);
      }
    }
    return ans;
  }
};
// res[i] := v[i]の位数
template<typename mint>
std::vector<long long> multiplicative_order_many(const std::vector<mint> &v){
  int n = v.size();
  std::vector<long long> res(n, 1);
  for(auto [p, q] : rho_factorization::factorize2(mint::mod() - 1)){
    long long x = mint(p).pow(q).val(), y = (mint::mod() - 1) / x;
    for(int i = 0; i < n; i++){
      long long z = x;
      for(int j = 0; j < q; j++){
        z /= p;
        if(v[i].pow(y * z).val() != 1){
          res[i] *= z * p;
          break;
        }
      }
    }
  }
  return res;
}


// 要素はモンゴメリ表現に変換せずに演算する
struct montgomery_rolling_hash{
  using ull = unsigned long long;
  using ulll = __uint128_t;
  static ull r, rinv, mod;
  static std::vector<ull> rpow, rinvpow, run_inv;
  static montgomery_reduction_64bit mr;
  
  // run関数をO(1)で使いたい場合はuse_run = true
  static void init(int max_n, bool use_run = false){
    assert(0 < max_n || rpow.empty()); // 2回呼び出されると壊れる
    mod = generate_random_prime(1ULL << 58, 1ULL << 63); // 小さすぎず, 足してもullでオーバーフローしない
    mr.set_mod(mod);
    r = random_number(1, mod - 1);
    ull g;
    std::tie(g, rinv) = inv_ext_gcd(r, mod);
    assert(g == 1); // r != 0 && is_prime(mod) -> gcd(r, mod) == 1
    r = mr.generate(r);
    rinv = mr.generate(rinv);
    rpow.resize(max_n + 1);
    rinvpow.resize(max_n + 1);
    run_inv.resize(max_n + 1);
    rpow[0] = rinvpow[0] = run_inv[0] = mr.generate(1);
    ull one = mr.generate(1);

    for(int i = 1; i <= max_n; i++){
      rpow[i] = mr.mul_safe(rpow[i - 1], r);
      rinvpow[i] = mr.mul_safe(rinvpow[i - 1], rinv);
      if(use_run) run_inv[i] = mr.pow_safe(mr.sub_safe(rpow[i], one), mod - 2); // 1 / (rpow[i] - 1)のモンゴメリ表現, i != 0
    }
  }
  template<typename T>
  static ull __mod(T x){
    x %= mod;
    return x < 0 ? mod + x : x;
  }
  static ull hash(const std::string &s){
    assert(s.size() <= rpow.size());
    ull res = 0;
    for(int i = 0; i < s.size(); i++) res = mr.add(res, mr.mul(rpow[i], s[i]));
    return mr.fix(res);
  }
  // 要素aが負の場合やaがmod以上の場合, aとa + modが同一視される
  template<typename T>
  static ull hash(const std::vector<T> &s){
    assert(s.size() <= rpow.size());
    ull res = 0;
    for(int i = 0; i < s.size(); i++) res = mr.add(res, mr.mul(rpow[i], __mod(s[i])));
    return mr.fix(res);
  }
  // table[i] = [0, i)のハッシュテーブル
  template<typename T>
  static std::vector<ull> hash_table(const std::vector<T> &s){
    assert(s.size() <= rpow.size());
    std::vector<ull> res(s.size() + 1);
    res[0] = 0;
    for(int i = 0; i < s.size(); i++){
      res[i + 1] = mr.add_safe(res[i], mr.mul(rpow[i], __mod(s[i])));
    }
    return res;
  }
  // xがk文字目にあった時のハッシュ
  template<typename T>
  static ull get(int k, T x){
    assert(k < rpow.size());
    return mr.mul_safe(rpow[k], __mod(x));
  }
  static ull mul(ull a, ull b){
    return mr.mul_safe(a, b);
  }
  static ull add(ull a, ull b){
    return mr.add_safe(a, b);
  }
  static ull sub(ull a, ull b){
    return mr.sub_safe(a, b);
  }
  // a^b
  static ull pow(ull a, ull b){
    return mr.pow_safe(a, b);
  }
  // 長さalenのハッシュがaの文字の末尾にハッシュがbの文字を結合する
  // O(1)またはO(log alen)
  static ull concat(ull a, ull alen, ull b){
    if(alen < rpow.size()) return add(a, mul(rpow[alen], b));
    return add(a, mul(pow(r, alen), b));
  }
  // 長さalenのハッシュがaの文字をk回繰り返す
  // a + a * rpow[alen] + a * rpow[2 * alen] ...
  // = a * (rpow[k * alen] - 1) / (rpow[alen] - 1)
  static ull run(ull a, ull alen, ull k){
    if(alen == 0) return 0;
    if(k <= 1) return k ? a : 0;
    __uint128_t K = k * alen;
    if(K < (int)rpow.size()) return mul(a, mul(sub(rpow[K], run_inv[0]), run_inv[alen]));

    // rpow[alen]
    unsigned long long r_alen = (alen < rpow.size() ? rpow[alen] : mr.pow_safe(r, alen));

    // rpow[k * alen]
    unsigned long long r_K = mr.pow_safe(r_alen, k);

    // 1 / (rpow[alen] - 1)
    r_alen = mr.pow_safe(sub(r_alen, run_inv[0]), mod - 2);
    return mul(a, mul(sub(r_K, run_inv[0]), r_alen));
  }
};
unsigned long long montgomery_rolling_hash::r = 0;
unsigned long long montgomery_rolling_hash::rinv = 0;
unsigned long long montgomery_rolling_hash::mod = 0;
std::vector<unsigned long long> montgomery_rolling_hash::rpow;
std::vector<unsigned long long> montgomery_rolling_hash::rinvpow;
std::vector<unsigned long long> montgomery_rolling_hash::run_inv;
montgomery_reduction_64bit montgomery_rolling_hash::mr;
// モンゴメリ乗算の方が早い
/* 
struct rolling_hash61{
  using ull = unsigned long long;
  static constexpr ull mod = (1UL << 61) - 1;
  static constexpr ull mod4 = (mod << 2);
  static constexpr ull mask30 = (1UL << 30) - 1;
  static constexpr ull mask31 = (1UL << 31) - 1;
  static constexpr ull mask61 = mod;

  static ull r, rinv;
  static std::vector<ull> rpow, rinvpow, run_inv;

  template<typename T>
  static ull __mod(T x){
    x %= mod;
    return x < 0 ? mod + x : x;
  }
  static ull calc_mod(ull a){
    ull au = a >> 61, ad = a & mask61;
    ull b = au + ad;
    return b >= mod ? b - mod : b;
  }
  static ull add(ull a, ull b){
    ull c = a + b;
    return c >= mod ? c - mod : c;
  }
  static ull sub(ull a, ull b){
    return a < b ? a + mod - b : a - b;
  }
  static ull mul(ull a, ull b){
    ull au = a >> 31, ad = a & mask31;
    ull bu = b >> 31, bd = b & mask31;
    ull c = ad * bu + au * bd;
    ull cu = c >> 30, cd = c & mask30;
    return calc_mod(au * bu * 2 + cu + (cd << 31) + ad * bd);
  }
  // a^b
  static ull pow(ull a, ull b){
    ull c = 1;
    while(b){
      if(b & 1) c = mul(c, a);
      a = mul(a, a);
      b >>= 1;
    }
    return c;
  }
  
  static void init(int max_n, bool use_run = false){
    assert(0 < max_n || rpow.empty()); // 2回呼び出されると壊れる
    r = random_number(2, mod - 1);
    ull g;
    std::tie(g, rinv) = inv_ext_gcd(r, mod);
    rpow.resize(max_n + 1);
    rinvpow.resize(max_n + 1);
    run_inv.resize(max_n + 1);
    rpow[0] = rinvpow[0] = run_inv[0] = 1;
    for(int i = 1; i <= max_n; i++){
      rpow[i] = mul(rpow[i - 1], r);
      rinvpow[i] = mul(rinvpow[i - 1], rinv);
      if(use_run) run_inv[i] = pow(sub(rpow[i], 1), mod - 2); // 1 / (rpow[i] - 1)
    }
  }
  static ull hash(const std::string &s){
    assert(s.size() <= rpow.size());
    ull res = 0;
    for(int i = 0; i < s.size(); i++) res = add(res, mul(rpow[i], s[i]));
    return res;
  }
  // 要素aが負の場合やaがmod以上の場合, aとa + modが同一視される
  template<typename T>
  static ull hash(const std::vector<T> &s){
    assert(s.size() <= rpow.size());
    ull res = 0;
    for(int i = 0; i < s.size(); i++) res = add(res, mul(rpow[i], __mod(s[i])));
    return res;
  }
  // table[i] = [0, i)のハッシュテーブル
  template<typename T>
  static std::vector<ull> hash_table(const std::vector<T> &s){
    assert(s.size() <= rpow.size());
    std::vector<ull> res(s.size() + 1);
    res[0] = 0;
    for(int i = 0; i < s.size(); i++) res[i + 1] = add(res[i], mul(rpow[i], __mod(s[i])));
    return res;
  }
  // xがk文字目にあった時のハッシュ
  template<typename T>
  static ull get(int k, T x){
    assert(k < rpow.size());
    return mul(rpow[k], __mod(x));
  }

  // 長さalenのハッシュがaの文字の末尾にハッシュがbの文字を結合する
  // O(1)またはO(log alen)
  static ull concat(ull a, ull alen, ull b){
    if(alen < rpow.size()) return add(a, mul(rpow[alen], b));
    return add(a, mul(pow(r, alen), b));
  }
  // 長さalenのハッシュがaの文字をk回繰り返す
  // a + a * rpow[alen] + a * rpow[2 * alen] ...
  // = a * (rpow[k * alen] - 1) / (rpow[alen] - 1)
  static ull run(ull a, ull alen, ull k){
    if(alen == 0) return 0;
    if(k <= 1) return k ? a : 0;
    __uint128_t K = k * alen;
    if(K < (int)rpow.size()) return mul(a, mul(sub(rpow[K], run_inv[0]), run_inv[alen]));
    // rpow[alen]
    unsigned long long r_alen = (alen < rpow.size() ? rpow[alen] : pow(r, alen));
    // rpow[k * alen]
    unsigned long long r_K = pow(r_alen, k);
    // 1 / (rpow[alen] - 1)
    r_alen = pow(sub(r_alen, run_inv[0]), mod - 2);
    return mul(a, mul(sub(r_K, run_inv[0]), r_alen));
  }
};
unsigned long long rolling_hash61::r = 0;
unsigned long long rolling_hash61::rinv = 0;
std::vector<unsigned long long> rolling_hash61::rpow;
std::vector<unsigned long long> rolling_hash61::rinvpow;
std::vector<unsigned long long> rolling_hash61::run_inv;

*/

struct rolling_hash_string{
  using ull = unsigned long long;
  using rh = montgomery_rolling_hash;
private:
  int n;
  std::vector<ull> sum;
public:
  template<typename T>
  rolling_hash_string(const std::vector<T> &_v): n(_v.size()), sum(rh::hash_table(_v)){}
  int size() const{
    return n;
  }
  ull get(int k) const{
    assert(k < n);
    return rh::mul(rh::sub(sum[k + 1], sum[k]), rh::rinvpow[k]);
  }
  template<typename T>
  void push_back(T x){
    ull h = rh::add(sum.back(), rh::mul(rh::__mod(x), rh::rpow[n]));
    sum.push_back(h);
    n++;
  }
  void pop_back(){
    assert(n);
    sum.pop_back();
    n--;
  }
  // 全体のハッシュ
  ull hash_all() const{
    return sum.back();
  }
  // [l, r)のハッシュ
  // l == rなら0
  ull hash_range(int l, int r) const{
    assert(0 <= l && l <= r && r <= n);
    if(!l) return sum[r];
    return rh::mul(rh::sub(sum[r], sum[l]), rh::rinvpow[l]);
  }
  // 結合後のサイズがmontgomeryテーブルのサイズを超えない
  void concat(const rolling_hash_string &b){
    int m = b.size();
    assert(n + m < rh::rpow.size());
    unsigned long long x = rh::rpow[n], y = sum.back();
    for(int i = 1; i <= m; i++) sum.push_back(rh::add(y, rh::mul(b.sum[i], x)));
    n += m;
  }
  // aの[l1...]とbの[l2...]のlcp
  static int lcp(const rolling_hash_string &a, const rolling_hash_string &b, int l1, int l2){
    int L = 0, R = std::min(a.size() - l1, b.size() - l2) + 1;
    while(R - L > 1){
      int mid = (L + R) >> 1;
      if(a.hash_range(l1, l1 + mid) == b.hash_range(l2, l2 + mid)) L = mid;
      else R = mid;
    }
    return L;
  }
  // これの[l1...]とbの[l2...]のlcp
  int lcp(const rolling_hash_string &b, int l1, int l2) const{
    return lcp(*this, b, l1, l2);
  }
};

struct dynamic_rolling_hash_string{
  using ull = unsigned long long;
  using rh = montgomery_rolling_hash;
private:
  int n, h;
  std::vector<ull> sum, point;
  void __init(std::vector<ull> &v){
    sum.resize(1, 0);
    sum.insert(sum.begin() + 1, v.begin(), v.end());
    for(int i = 1; i <= n; i++){
      int nxt = i + (i & (-i));
      if(nxt <= n) sum[nxt] = rh::add(sum[nxt], sum[i]);
    }
    if(n) h = 31 - __builtin_clz(n);
  }
  void __update(int k, ull x){
    for(int i = k + 1; i <= n; i += (i & (-i))){
      sum[i] = rh::add(sum[i], x);
    }
  }
  ull __query(int r) const{
    ull res = 0;
    for(int k = r; k > 0; k -= (k & (-k))){
      res = rh::mr.add(res, sum[k]);
    }
    return rh::mr.fix(res);
  }
  ull __query(int l, int r) const{
    ull a = __query(r), b = __query(l);
    return rh::sub(a, b);
  }
  ull __query_all() const{
    return __query(n);
  }
public:
  template<typename T>
  dynamic_rolling_hash_string(const std::vector<T> &_v): n(_v.size()){
    std::vector<ull> table(n);
    point.resize(n);
    for(int i = 0; i < n; i++){
      table[i] = rh::get(i, _v[i]);
      point[i] = rh::__mod(_v[i]);
    }
    __init(table);
  }
  int size() const{
    return n;
  }
  template<typename T>
  void set(int k, T x){
    ull _x = rh::__mod(x), _y = get(k);
    point[k] = _x;
    __update(k, rh::mul(rh::sub(_x, _y), rh::rpow[k]));
  }
  ull get(int k) const{
    assert(0 <= k && k < n);
    return point[k];
  }
  // 全体のハッシュ
  ull hash_all() const{
    return __query_all();
  }
  // [0, r)のハッシュ
  ull hash_range(int r) const{
    return __query(r);
  }
  // [l, r)のハッシュ
  // l == rなら0
  ull hash_range(int l, int r) const{
    assert(0 <= l && l <= r && r <= n);
    if(l == 0) return __query(r);
    return rh::mul(__query(l, r), rh::rinvpow[l]);
  }
  static int lcp(const dynamic_rolling_hash_string &a, const dynamic_rolling_hash_string &b, int l1, int l2){
    int v = 1 << a.h, H = a.h;
    ull s = rh::sub(0, a.__query(l1));
    ull hash_b = b.__query(l2);
    while(H--){
      int len = v - l1;
      if(a.n < v || l2 + len > b.size()){
        v -= 1 << H;
        continue;
      }
      ull hash_tmp = rh::add(s, a.sum[v]);
      if(v <= l1){
        s = hash_tmp;
        v += 1 << H;
        continue;
      }
      bool f = rh::mul(rh::sub(b.__query(l2 + len), hash_b), rh::rinvpow[l2]) != rh::mul(hash_tmp, rh::rinvpow[l1]);
      if(f){
        v -= 1 << H;
      }else{
        s = hash_tmp;
        v += 1 << H;
      }
    }
    if(v == a.n + 1) return a.n - l1;
    int len = v - l1;
    bool f = l2 + len > b.size() || b.hash_range(l2, l2 + len) != rh::mul(rh::add(s, a.sum[v]), rh::rinvpow[l1]);
    return f ? v - 1 - l1 : v - l1;
  }
  // len(a) == len(b)かつ0からのlcp O(loglen(a))
  static int lcp_same_size(const dynamic_rolling_hash_string &a, const dynamic_rolling_hash_string &b){
    assert(a.size() == b.size());
    int v = 1 << a.h, H = a.h;
    while(H--){
      if(a.n < v) v -= 1 << H;
      else if(a.sum[v] != b.sum[v]) v -= 1 << H;
      else v += 1 << H;
    }
    if(v == a.n + 1) return a.n;
    return a.sum[v] != b.sum[v] ? v - 1 : v;
  }
  static int lcp(const dynamic_rolling_hash_string &a, const rolling_hash_string &b, int l1, int l2){
    int v = 1 << a.h, H = a.h;
    ull s = rh::sub(0, a.__query(l1));
    while(H--){
      int len = v - l1;
      if(a.n < v || l2 + len > b.size()){
        v -= 1 << H;
        continue;
      }
      ull hash_tmp = rh::add(s, a.sum[v]);
      if(v <= l1){
        s = hash_tmp;
        v += 1 << H;
        continue;
      }
      bool f = b.hash_range(l2, l2 + len) != rh::mul(hash_tmp, rh::rinvpow[l1]);
      if(f){
        v -= 1 << H;
      }else{
        s = hash_tmp;
        v += 1 << H;
      }
    }
    if(v == a.n + 1) return a.n - l1;
    int len = v - l1;
    bool f = l2 + len > b.size() || b.hash_range(l2, l2 + len) != rh::mul(rh::add(s, a.sum[v]), rh::rinvpow[l1]);
    return f ? v - 1 - l1 : v - l1;
  }
  static int lcp(const rolling_hash_string &a, const dynamic_rolling_hash_string &b, int l1, int l2){
    return lcp(b, a, l2, l1);
  }
};

struct dynamic_rolling_hash_string_persistent{
  using ull = unsigned long long;
  using rh = montgomery_rolling_hash;
private:
  struct node{
    node *l, *r;
    int sz;
    ull val;
    node(ull x): l(nullptr), r(nullptr), sz(1), val(x){}
    node(node *l, node *r): l(l), r(r), sz(l->sz + r->sz), val(rh::add(l->val, rh::mul(r->val, rh::rpow[l->sz]))){}
  };
  template<typename T>
  static node *__build(const std::vector<T> &v, int l, int r){
    if(l + 1 == r) return new node(v[l]);
    int mid = (l + r) / 2;
    return new node(__build(v, l, mid), __build(v, mid, r));
  }
  static node *__set(node *v, int k, ull x, int l, int r){
    if(r - l == 1) return new node(x);
    int mid = (l + r) / 2;
    if(k < mid){
      return new node(__set(v->l, k, x, l, mid), v->r);
    }else{
      return new node(v->l, __set(v->r, k, x, mid, r));
    }
  }
  static ull __get(node *v, int k, int l, int r){
    if(r - l == 1) return v->val;
    int mid = (l + r) / 2;
    if(k < mid) return __get(v->l, k, l, mid);
    else return __get(v->r, k, mid, r);
  }
  static ull __hash_range(node *v, int b){
    int l = 0, r = v->sz;
    b = std::min(b, r);
    int lsz = 0;
    ull res = 0;
    while(v){
      if(b <= l) return res;
      if(b >= r) return rh::add(res, rh::mul(v->val, rh::rpow[lsz]));
      int mid = (l + r) / 2;
      if(b <= mid){
        r = mid;
        v = v->l;
      }else{
        res = rh::add(res, rh::mul(v->l->val, rh::rpow[lsz]));
        lsz += mid - l;
        l = mid;
        v = v->r;
      }
    }
    return res;
  }
  static ull __hash_range(node *v, int a, int b, int l, int r){
    if(!v || b <= l || r <= a) return 0;
    if(a <= l && r <= b) return v->val;
    int mid = (l + r) / 2;
    return rh::add(__hash_range(v->l, a, b, l, mid), rh::mul(__hash_range(v->r, a, b, mid, r), rh::rpow[mid - l]));
  }
public:
  dynamic_rolling_hash_string_persistent(){}
  template<typename T>
  static node *build(const std::vector<T> &v){
    int n = v.size();
    return __build(v, 0, n);
  }
  static int size(node *v){
    return v ? v->sz : 0;
  }
  static node *set(node *v, int k, ull x){
    assert(k < size(v));
    return __set(v, k, x, 0, v->sz);
  }
  static ull get(node *v, int k){
    assert(k < size(v));
    return __get(v, k, 0, v->sz);
  }
  static ull hash_range(node *v, int r){
    assert(0 <= r && r <= size(v));
    if(r == 0) return 0;
    return __hash_range(v, r);
  }
  static ull hash_range(node *v, int l, int r){
    if(l >= r) return 0;
    assert(0 <= l && r <= size(v));
    return __hash_range(v, l, r, 0, v->sz);
  }
  static int __lcp(node *v, const rolling_hash_string &b, int l1, int l2){
    if(!v || l2 >= b.size()) return 0;
    if(l1 == 0 && l2 + v->sz <= b.size() && v->val == b.hash_range(l2, l2 + v->sz)) return v->sz;
    int szl = v->l ? v->l->sz : 0;
    if(szl <= l1) return __lcp(v->r, b, l1 - szl, l2);
    int left_cross = szl - l1, L = __lcp(v->l, b, l1, l2);
    if(L != left_cross) return L;
    l2 += left_cross;
    return L + __lcp(v->r, b, 0, l2);
  }
  static int __lcp(node *v, const dynamic_rolling_hash_string &b, int l1, int l2, int &oksz, ull &ok){
    if(!v || l2 >= b.size()) return 0;
    if(l1 == 0 && l2 + v->sz <= b.size()){
      ull rh = rh::mul(rh::sub(b.hash_range(l2 + v->sz), ok), rh::rinvpow[l2]);
      if(v->val == rh){
        ok = rh::add(ok, rh::mul(v->val, rh::rpow[oksz]));
        oksz += v->sz;
        return v->sz;
      }
    }
    int szl = v->l ? v->l->sz : 0;
    if(szl <= l1) return __lcp(v->r, b, l1 - szl, l2, oksz, ok);
    int left_cross = szl - l1, L = __lcp(v->l, b, l1, l2, oksz, ok);
    if(L != left_cross) return L;
    l2 += left_cross;
    return L + __lcp(v->r, b, 0, l2, oksz, ok);
  }
  static int __lcp(node *v, node *u, int l1, int l2, int &oksz, ull &ok){
    if(!v || l2 >= size(u)) return 0;
    if(l1 == 0 && l2 + v->sz <= size(u)){
      ull rh = rh::mul(rh::sub(hash_range(u, l2 + v->sz), ok), rh::rinvpow[l2]);
      if(v->val == rh){
        ok = rh::add(ok, rh::mul(v->val, rh::rpow[oksz]));
        oksz += v->sz;
        return v->sz;
      }
    }
    int szl = v->l ? v->l->sz : 0;
    if(szl <= l1) return __lcp(v->r, u, l1 - szl, l2, oksz, ok);
    int left_cross = szl - l1, L = __lcp(v->l, u, l1, l2, oksz, ok);
    if(L != left_cross) return L;
    l2 += left_cross;
    return L + __lcp(v->r, u, 0, l2, oksz, ok);
  }
  static int lcp(node *v, const rolling_hash_string &b, int l1, int l2){
    if(!v) return 0;
    return __lcp(v, b, l1, l2);
  }
  static int lcp(const rolling_hash_string &b, node *v, int l1, int l2){
    if(!v) return 0;
    return __lcp(v, b, l2, l1);
  }
  static int lcp(node *v, const dynamic_rolling_hash_string &b, int l1, int l2){
    int oksz = l2;
    ull ok = b.hash_range(l2);
    return __lcp(v, b, l1, l2, oksz, ok);
  }
  static int lcp(const dynamic_rolling_hash_string &a, node *v, int l1, int l2){
    return lcp(v, a, l2, l1);
  }
  static int lcp(node *v, node *u, int l1, int l2){
    int oksz = l2;
    ull ok = hash_range(u, 0, l2);
    return __lcp(v, u, l1, l2, oksz, ok);
  }
};


int main(){
  io_init();
  int n;
  std::cin >> n;
  using H = montgomery_rolling_hash;
  H::init(100000);
  using ull = unsigned long long;
  map<ull, int> mp;

  vector<string> S(n);
  range(i, 0, n){
    vector<int> cnt(26, 0);
    string s;
    std::cin >> s;
    S[i] = s;
    
    range(j, 0, s.size()) cnt[s[j] - 'a']++;
    range(j, 0, 26){
      cnt[j]++;
      auto h = H::hash(cnt);
      auto itr = mp.find(h);
      if(itr == mp.end()) mp.emplace(h, 1);
      else itr->second++;
      cnt[j]--;
    }
  }

  range(i, 0, n){
    vector<int> cnt(26, 0);
    string s = S[i];
    range(j, 0, s.size()) cnt[s[j] - 'a']++;

    range(j, 0, 26){
      cnt[j]++;
      auto h = H::hash(cnt);
      auto itr = mp.find(h);
      if(itr != mp.end() && itr->second == 1){
        string ans = "";
        range(k, 0, 26) ans += string(cnt[k], 'a' + k);
        std::cout << ans << '\n';
        return 0;
      }
      cnt[j]--;
    }
  }
  std::cout << -1 << '\n';
}