結果
| 問題 |
No.2715 Unique Chimatagram
|
| コンテスト | |
| ユーザー |
 tonegawa
|
| 提出日時 | 2024-04-05 21:30:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 32 ms / 2,000 ms |
| コード長 | 48,984 bytes |
| コンパイル時間 | 3,191 ms |
| コンパイル使用メモリ | 188,656 KB |
| 最終ジャッジ日時 | 2025-02-20 20:53:44 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
#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';
}