結果
| 問題 | No.2410 Nine Numbers |
| ユーザー |
 warabi0906
|
| 提出日時 | 2023-08-14 16:46:10 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 61 ms / 2,000 ms |
| コード長 | 37,788 bytes |
| コンパイル時間 | 3,042 ms |
| コンパイル使用メモリ | 227,836 KB |
| 実行使用メモリ | 86,272 KB |
| 最終ジャッジ日時 | 2024-11-22 15:46:36 |
| 合計ジャッジ時間 | 3,885 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
コンパイルメッセージ
main.cpp: In member function 'std::pair<long long int, long long int> Warabi::diameter::dfs(long long int, long long int, long long int)':
main.cpp:426:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
426 | auto [to,cost]=e;
| ^
main.cpp:428:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
428 | auto [crrv,crrd]=dfs(to,v,d+1);
| ^
main.cpp: In member function 'std::tuple<long long int, long long int, long long int> Warabi::diameter::get()':
main.cpp:445:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
445 | auto [s,xxx]=dfs(0,-1,0);
| ^
main.cpp:446:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
446 | auto [t,D]=dfs(s,-1,0);
| ^
main.cpp: In function 'bool Warabi::bellman_ford(const std::vector<std::tuple<long long int, long long int, long long int> >&, long long int, long long int, std::vector<long long int>&)':
main.cpp:907:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
907 | for(auto [from,to,cost]:E){
| ^
ソースコード
/*
Hi,I am warabi.
Welcome to my coding space.
Let me give you a great word of advice.
"The pen is mightier than the sword"
-by Edward Bulwer-Lytton
_,,....,,_ ＿人人人人人人人人人人人人人人人人人人＿
-''":::::::::::::｀''＞ ゆっくりできるとでも? ＜
ヽ:::::::::::::::::::::￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ￣
|::::::;ノ´￣＼:::::::::::＼_,. -‐ｧ ＿_ _____ ＿_____
|::::ﾉ ヽ､ヽr-r'"´ （.__ ,´ _,, '-´￣￣｀-ゝ 、_ イ、
_,.!イ_ _,.ﾍｰｧ'二ﾊ二ヽ､へ,_7 'r ´ ヽ、ﾝ、
::::::rｰ''7ｺ-‐'"´ ; ', ｀ヽ/｀7 ,'＝=─- -─=＝', i
r-'ｧ'"´/ /! ﾊ ハ ! iヾ_ﾉ i ｲ iゝ、ｲ人レ／_ルヽｲ i |
!イ´ ,' | /__,.!/ V ､!__ﾊ ,' ,ゝ ﾚﾘｲi (ﾋ_] ﾋ_ﾝ ).| .|、i .||
`! !/ﾚi' (ﾋ_] ﾋ_ﾝ ﾚ'i ﾉ !Y!"" ,＿__, "" 「 !ﾉ i |
,' ﾉ !'" ,＿__, "' i .ﾚ' L.',. ヽ _ﾝ L」 ﾉ| .|
（ ,ﾊ ヽ _ﾝ 人! | ||ヽ、 ,ｲ| ||ｲ| /
,.ﾍ,）､ ）＞,､ _____, ,.イ ハ レ ル｀ ー--─ ´ルﾚ ﾚ´
Take your time.
GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define V vector
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define brep(i,a,b) for(ll i=a;i>=b;i--)
#define reph(i,vec) for(auto &i:vec)
#define FI first
#define SE second
#define P pair
#define PB push_back
#define EB emplace_back
#define INS insert
#define all(vec) vec.begin(),vec.end()
#define in(name) ll name;cin >> name
#define ins(name) string name;cin >> name;
#define inc(name) char name;cin >> name
#define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);}
#define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);}
#define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});}
#define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i
#define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i;
#define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE
#define out(n) cout << (n) << endl
#define _out(n) cout << " " << (n) << endl;
#define notout(n) cout << (n)
#define out_(n) cout << (n) << " "
#define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " ";
#define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl;
#define nel cout<<endl;
#define getbit(n,k) (((1LL<<(k))&(n))>0)
#define g_t(t,a) get<a>(t)
#define INF 1000000000000000000ll
#define MOD 1000000007
#define MOD2 998244353
#define CMOD MOD2
#define EPS 0.00000001
//debug
#define bug assert(false);
#define debug cout<<"OK Line "<<__LINE__<<endl;
//
//constexpr long double PI=3.14159265358979323846;
//template
template<typename T>
inline bool chmax(T& a, const T b) { if (a < b) { a = b; return true; }return false; }
template<typename T>
inline bool chmin(T& a, const T b) { if (a > b) { a = b; return true; }return false; }
//
namespace Warabi {
//常備変数のコーナー
V<bool> primes(1e7+5, true);
V<ll> prime_list;
V<ll> prime_rui(1e7+5, 0LL);
V<bool> visiteded(300100);
V<bool> afed(300100, false);
V<ll> k1(200100, 0ll);
V<ll> k2(200100, 0ll);
//
//常備構造体宣言のコーナー
class UnionFind {
private:
ll NumberOfElements;
ll Not1NumberOfelements;
public:
vector<ll> par;
vector<ll> SIZE;
void init(ll sz) {
par.resize(sz, -1LL);
SIZE.resize(sz, 1LL);
NumberOfElements = sz;
Not1NumberOfelements = 0ll;
}
ll root(ll pos) {
if (par[pos] == -1) return pos;
par[pos] = root(par[pos]);
return par[pos];
}
bool same(ll u, ll v) {
if (root(u) == root(v)) return true;
return false;
}
ll SZ(ll u) {
return SIZE[root(u)];
}
ll noe() {
return NumberOfElements;
}
ll nnoe() {
return Not1NumberOfelements;
}
bool unite(ll u, ll v) {
//頂点番号が大きいほうに統合する
u = root(u); v = root(v);
if (u == v) {
return false;
}
if (SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++;
if (u > v)swap(u, v);
par[u] = v;
SIZE[v] += SIZE[u];
NumberOfElements--;
return true;
}
};
class SCC {
public:
V<V<ll>> G;
V<V<ll>> UG;
V<ll> order;
V<ll> GROUP;
V<bool> visited;
ll sz_count;
V<ll> groupsize;
void init(ll sz) {
G.resize(sz, V<ll>(0));
UG.resize(sz, V<ll>(0));
GROUP.resize(sz, -1ll);
visited.resize(sz, false);
sz_count = 0LL;
return;
}
void dfs(ll now) {
visited[now] = true;
reph(i, G[now]) {
if (visited[i])continue;
dfs(i);
}
order.PB(now);
return;
}
void dfs2(ll now, ll group) {
GROUP[now] = group;
sz_count++;
reph(i, UG[now]) {
if (GROUP[i] != -1ll and GROUP[i] != group)continue;
if (GROUP[i] != -1ll)continue;
dfs2(i, group);
}
return;
}
void make_group(V<V<ll>> Graph_function) {
G = Graph_function;
rep(i, 0, (ll)G.size()) {
reph(j, G[i]) {
UG[j].PB(i);
}
}
rep(i, 0, (ll)G.size()) {
if (visited[i])continue;
dfs(i);
}
reverse(all(order));
ll now_group = 0LL;
reph(i, order) {
if (GROUP[i] != -1)continue;
ll prev = sz_count;
dfs2(i, now_group);
now_group++;
groupsize.PB(sz_count - prev);
}
return;
}
};
template<typename X, typename M>
class SegmentTree {
public:
long long sz;
using FX = function<X(X, X)>;
using FA = function<X(X, M)>;
using FM = function<M(M, M)>;
const FX fx;
const FA fa;
const FM fm;
const X ex;
const M em;
vector<X> node;
vector<M> lazy;
SegmentTree(long long sz_, FX fx_, FA fa_, FM fm_, X ex_, M em_) :sz(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_) {
long long n = 1LL;
while (n < sz_)n *= 2;
sz = n;
node.resize(sz * 2 - 1, ex);
lazy.resize(sz * 2 - 1, em);
}
void set(long long index, X x) {
node[index + sz - 1] = x;
return;
}
void build() {
for (int i = sz - 2; i >= 0; i--)node[i] = fx(node[i * 2 + 1], node[i * 2 + 2]);
return;
}
void eval(long long k) {
if (lazy[k] == em)return;
if (k < sz - 1) {
lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
}
node[k] = fa(node[k], lazy[k]);
lazy[k] = em;
}
void update_sub(long long a, long long b, M x, long long k, long long l, long long r) {
//cout << " " << a << " " << b << " " << l << " " << r << endl;
eval(k);
if (a <= l and r <= b) {
lazy[k] = fm(lazy[k], x);
//cout<<" "<<lazy[k]<<endl;
eval(k);
return;
}
else if (a < r and l < b) {
update_sub(a, b, x, k * 2 + 1, l, (l + r) / 2);
update_sub(a, b, x, k * 2 + 2, (l + r) / 2, r);
node[k] = fx(node[k * 2 + 1], node[k * 2 + 2]);
return;
}
return;
}
void update(long long a, long long b, M x) {
update_sub(a, b, x, 0LL, 0LL, sz);
return;
}
void add_sub(long long a, X x, long long k, long long l, long long r) {
eval(k);
node[k] += x;
if (k < sz - 1) {
long long mid = (l + r) / 2;
if (a < mid)add_sub(a, x, k * 2 + 1, l, mid);
else add_sub(a, x, k * 2 + 2, mid, r);
}
return;
}
void add(long long a, X x) {
add_sub(a, x, 0LL, 0LL, sz);
}
X query_sub(long long a, long long b, long long k, long long l, long long r) {
eval(k);
if (r <= a or b <= l)return ex;
else if (a <= l and r <= b)return node[k];
else {
X Xl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X Xr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
//cout<<" / "<<Xl<<" "<<Xr<<endl;
return fx(Xl, Xr);
}
}
X query(long long a, long long b) {
return query_sub(a, b, 0LL, 0LL, sz);
}
inline X operator [] (long long index) {
return query(index, index + 1);
}
};
template<typename T>
class multimap {
private:
map<T, ll> mp;
public:
void add(ll x) {
mp[x]++;
return;
}
void del(ll x) {
mp[x]--;
if (mp[x] < 1)mp.erase(x);
return;
}
T maximum() {
return mp.rbegin()->first;
}
T minimum() {
return mp.begin()->first;
}
};
class LCA {
public:
vector<vector<long long>> parent;
vector<long long> dist;
vector<vector<long long>> G;
LCA(const vector<vector<long long>>& gr) { init(gr); }
void dfs(long long v, long long p, long long d) {
parent[0][v] = p;
dist[v] = d;
for (long long next : G[v]) {
if (next == p)continue;
dfs(next, v, d + 1);
}
return;
}
void init(const vector<vector<long long>>& gr) {
G = gr;
parent.assign(33, vector<long long>(G.size(), -1LL));
dist.assign(G.size(), -1LL);
dfs(0LL, -1LL, 0LL);
for (int i = 0; i < 32; i++) {
for (int j = 0; j < (int)G.size(); j++) {
if (parent[i][j] < 0LL) {
parent[i + 1][j] = -1LL;
}
else {
parent[i + 1][j] = parent[i][parent[i][j]];
}
}
}
return;
}
long long lca(long long u, long long v) {
if (dist[u] < dist[v])swap(u, v);
long long between = dist[u] - dist[v];
for (int i = 0; i < 33; i++) {
if (between & (1LL << i)) { u = parent[i][u]; }
}
if (u == v)return u;
for (int i = 32; i >= 0; i--) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
assert(parent[0][u] == parent[0][v]);
return parent[0][u];
}
long long get_dist(long long u, long long v) {
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
bool on_path(long long u, long long v, long long a) {
return get_dist(u, v) == get_dist(u, a) + get_dist(v, a);
}
};
class nCk {
public:
const long long m;
const long long MAXIMUM = 2000005;
vector<long long> fac, facinv, inv;
nCk(long long m_);
~nCk();
long long com(long long n, long long k)const;
};
nCk::nCk(long long m_) :m(m_) {
fac.resize(MAXIMUM + 3);
facinv.resize(MAXIMUM + 3);
inv.resize(MAXIMUM + 3);
fac[0] = fac[1] = 1;
facinv[0] = facinv[1] = 1;
inv[1] = 1;
for (long long i = 2; i < MAXIMUM + 2; i++) {
fac[i] = fac[i - 1] * i % m;
inv[i] = m - inv[m % i] * (m / i) % m;
facinv[i] = facinv[i - 1] * inv[i] % m;
}
}
nCk::~nCk() {}
long long nCk::com(long long n, long long k)const {
if (k == 0)return 1;
assert(!(n < 0 || k < 0));
return fac[n] * (facinv[k] * facinv[n - k] % m) % m;
}
//
//常備構造体宣言のコーナー
//
//常備関数のコーナー
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
//木の直径を求める
class diameter{
private:
long long N;
vector<vector<pair<long long,long long>>> G;
pair<long long,long long> dfs(long long v,long long p,long long d){
long long Max_v=v,Max_dist=d;
for(const pair<long long,long long> &e:G[v]){
auto [to,cost]=e;
if(to==p)continue;
auto [crrv,crrd]=dfs(to,v,d+1);
if(Max_dist<crrd){
Max_dist=crrd;
Max_v=crrv;
}
}
return make_pair(Max_v,Max_dist);
}
public:
diameter(long long n_):N(n_){
G.resize(N);
}
void Add_edge(long long u,long long v,long long c=1){
G[u].emplace_back(v,c);G[v].emplace_back(u,c);
return;
}
tuple<long long,long long,long long> get(){
auto [s,xxx]=dfs(0,-1,0);
auto [t,D]=dfs(s,-1,0);
return make_tuple(s,t,D);
}
};
//素数の取得
void prime_init(const long long Limit) {
V<bool> at(Limit, true);
primes = at;
primes[0] = primes[1] = false;
rep(i, 2, Limit) {
if (!primes[i])continue;
for (ll j = i * 2; j <= Limit; j += i)primes[j] = false;
}
rep(i, 1, Limit) {
if (primes[i]) {
prime_list.PB(i);
prime_rui[i] = prime_rui[i - 1] + 1;
}
else {
prime_rui[i] = prime_rui[i - 1];
}
}
return;
}
//modpow
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 63; i++) {
if ((b & (1LL << i)) != 0) {
p *= q;
p %= m;
}
q *= q;
q %= m;
}
return p;
}
//逆元
long long Div(long long a, long long b, long long m) {
return (a * modpow(b, m - 2, m)) % m;
}
//点と点の距離を返す
long double Dis(ll ax, ll ay, ll bx, ll by) {
return sqrt(pow(ax - bx, 2) + pow(ay - by, 2));
}
//二つのベクトルから平行四辺形の面積を返す
ll he(ll x0, ll y0, ll x1, ll y1, ll x2, ll y2) {//外積を二で割る
return abs((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0));
}
//
template<typename T>
ll Lis_size(V<T> arr, ll sz) {
const T TINF = numeric_limits<T>::max();
V<T> DP(sz + 1, TINF);
DP[0] = -TINF;
rep(i, 0, sz) {
*lower_bound(all(DP), arr[i]) = arr[i];
}
ll ans = 0LL;
rep(i, 1, sz + 1) {
if (DP[i] != TINF)ans = i;
}
return ans;
}
string toBinary(ll n) {
string r;
while (n != 0LL) {
r += (n % 2LL == 0LL ? "0" : "1");
n /= 2LL;
}
return r;
}
template<typename T>
V<ll> press(V<T> arr) {
V<T> X = arr;
sort(all(X));
X.erase(unique(all(X)), X.end());
V<ll> ans(arr.size());
rep(i, 0LL, (ll)arr.size()) {
ans[i] = lower_bound(all(X), arr[i]) - X.begin();
}
return ans;
}
P<V<V<ll>>, V<V<P<ll, ll>>>> warshall_floyd(ll N, V<V<P<ll, ll>>> G) {
V<V<ll>> DP(N, V<ll>(N, INF));
rep(i, 0, N)DP[i][i] = 0LL;
V<V<P<ll, ll>>> prev(N, V<P<ll, ll>>(N, { INF,INF }));
rep(i, 0, N) {
reph(j, G[i]) {
DP[i][j.FI] = j.SE;
prev[i][j.FI] = { i,j.FI };
}
}
rep(k, 0, N) {
rep(i, 0, N) {
rep(j, 0, N) {
if (chmin(DP[i][j], DP[i][k] + DP[k][j])) {
prev[i][j] = prev[k][j];
}
}
}
}
return { DP,prev };
}
template<typename T>
void to_sum(V<T>& arr) {
rep(i, 0, (ll)arr.size() - 1LL) {
arr[i + 1] += arr[i];
}
return;
}
template<typename T>
void including_map(ll H, ll W, V<V<T>>& G, T c) {
V<V<T>> new_G(H + 2, V<T>(W + 2));
rep(i, 0, W + 2)new_G[0][i] = c;
rep(i, 1, H + 1) {
new_G[i][0] = c;
new_G[i][W + 1] = c;
rep(j, 1, W + 1) {
new_G[i][j] = G[i - 1][j - 1];
}
}
rep(i, 0, W + 2)new_G[H + 1][i] = c;
G = new_G;
return;
}
template<typename T> class BIT {
private:
int n;
vector<T> bit;
public:
// 0_indexed で i 番目の要素に x を加える
void add(int i, T x){
i++;
while(i < n){
bit[i] += x, i += i & -i;
}
}
// 0_indexed で [0,i] の要素の和(両閉区間！！)
T sum(int i){
i++;
T s = 0;
while(i > 0){
s += bit[i], i -= i & -i;
}
return s;
}
BIT(){}
//初期値がすべて0の場合
BIT(int sz) : n(sz+1), bit(n, 0){}
BIT(const vector<T>& v) : n((int)v.size()+1), bit(n, 0){
for(int i = 0; i < n-1; i++){
add(i,v[i]);
}
}
void print(){
for(int i = 0; i < n-1; i++){
cout << sum(i) - sum(i-1) << " ";
}
cout << "\n";
}
//-1スタート
void print_sum(){
for(int i = 0; i < n; i++){
cout << sum(i-1) << " ";
}
cout << "\n";
}
};
// u を昇順にソートするのに必要な交換回数(転倒数) (u は {0,..., n-1} からなる重複を許した長さ n の数列)
long long inv_count(const vector<long long>& u,const int Max)
{
int n=u.size();
int m=Max;
BIT<long long> bt(m);
long long ans = 0;
for(int i = 0; i < n; i++){
ans += i - bt.sum(u[i]);
bt.add(u[i], 1);
}
return ans;
}
set<ll> factor(ll N) {
set<ll> ans;
for (ll i = 1LL; i * i <= N; i++) {
if (N % i)continue;
ans.INS(i);
ans.INS(N / i);
}
return ans;
}
V<ll> dijkstra(ll sz, V<V<P<ll, ll>>> G, ll s) {
V<ll> ans(sz, INF); ans[s] = 0LL;
priority_queue<P<ll, ll>, vector<P<ll, ll>>, greater<P<ll, ll>>> examine;
examine.push({ 0LL,s });
while (examine.size()) {
P<ll, ll> p = examine.top();
examine.pop();
ll now = p.SE, dist = p.FI;
if (ans[now] < dist)continue;
reph(i, G[now]) {
ll next = i.FI, c = i.SE;
if (chmin(ans[next], dist + c)) {
examine.push({ dist + c,next });
}
}
}
return ans;
}
V<ll> pass(const V<V<ll>>& G, ll s, ll t) {
V<ll> ans, res;
function<void(ll,ll)> dfs = [&](ll now,ll p) {
res.PB(now);
if (now == t) {
ans = res;
}
reph(next, G[now]) {
if (next==p)continue;
dfs(next,now);
}
res.pop_back();
return;
};
dfs(s,-1);
return ans;
}
// 負の数にも対応した mod (a = -11 とかでも OK)
inline long long mod(long long a, long long m) {
long long res = a % m;
if (res < 0) res += m;
return res;
}
// 拡張 Euclid の互除法
long long extGCD(long long a, long long b, long long& p, long long& q) {
if (b == 0) { p = 1; q = 0; return a; }
long long d = extGCD(b, a % b, q, p);
q -= a / b * p;
return d;
}
long long extGcd(long long a, long long b, long long& p, long long& q) {
if (b == 0) { p = 1; q = 0; return a; }
long long d = extGcd(b, a % b, q, p);
q -= a / b * p;
return d;
}
// 逆元計算 (ここでは a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
long long x, y;
extGCD(a, m, x, y);
return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}
// Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
// for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"
// coeffs[k] = m[0]m[1]...m[k-1]
// constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]
long long Garner(vector<long long> b, vector<long long> m, long long Mmod) {
m.push_back(Mmod); // banpei
vector<long long> coeffs((int)m.size(), 1);
vector<long long> constants((int)m.size(), 0);
for (int k = 0; k < (int)b.size(); ++k) {
long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
for (int i = k + 1; i < (int)m.size(); ++i) {
(constants[i] += t * coeffs[i]) %= m[i];
(coeffs[i] *= m[k]) %= m[i];
}
}
return constants.back();
}
pair<long long, long long> ChineseRem(const vector<long long>& b, const vector<long long>& m) {
long long r = 0, M = 1;
for (int i = 0; i < (int)b.size(); ++i) {
long long p, q;
long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
if ((b[i] - r) % d != 0) return make_pair(0, -1);
long long tmp = (b[i] - r) / d * p % (m[i] / d);
r += M * tmp;
M *= m[i] / d;
}
return make_pair(mod(r, M), M);
}
map<ll, ll> bunkai(ll n) {
map<ll, ll> ans;
ll Nn = n;
for (int i = 2; i * i <= Nn; i++) {
while (n % i == 0) {
n /= i;
ans[i]++;
}
}
if (n > 1) { ans[n]++; }
return ans;
}
template<typename T>
void RLE(vector<T>& arr) {
vector<T> res;
res.push_back(arr[0]);
for (const T t : arr) {
if (res.back() != t)res.push_back(t);
}
arr = res;
return;
}
vector<pair<long long, long long>> EulerTour(const vector<vector<long long>>& G) {
long long N = (long long)G.size();
vector<pair<long long, long long>> res(N);
long long now = 0ll;
function<void(long long, long long)> dfs = [&](long long v, long long p) {
res[v].first = now;
++now;
for (const long long next : G[v]) {
if (next == p)continue;
dfs(next, v);
}
res[v].second = now;
++now;
return;
};
dfs(0, -1ll);
return res;
}
template <typename T>
struct BIT2D {
int H, W;
vector<vector<T>> bit; // データの格納先
BIT2D(int H_, int W_) { init(H_, W_); }
void init(int H_, int W_) {
H = H_ + 1;
W = W_ + 1;
bit.assign(H, vector<T>(W, 0));
}
void add(int h, int w, T x) {
for (int i = h; i < H; i += (i & -i)) {
for (int j = w; j < W; j += (j & -j)) {
bit[i][j] += x;
}
}
}
// 1≦i≦h かつ 1≦j≦w
T sum(int h, int w) {
T s(0);
for (int i = h; i > 0; i -= (i & -i)) {
for (int j = w; j > 0; j -= (j & -j)) {
s += bit[i][j];
}
}
return s;
}
// h1≦i<h2 かつ w1≦j<w2
T query(int h1, int w1, int h2, int w2) {
return sum(h2 - 1, w2 - 1) - sum(h2 - 1, w1 - 1) - sum(h1 - 1, w2 - 1) + sum(h1 - 1, w1 - 1);
}
};
template<typename T>
struct Matrix {
vector<vector<T>>A;
Matrix() {}
Matrix(size_t n,size_t m):A(n,vector<T>(m,0)){}
Matrix(size_t n):A(n,vector<T>(n,0)){};
size_t height(){
return (A.size());
}
size_t width(){
return (A[0].size());
}
inline const vector<T>&operator[](int k)const{
return (A.at(k));
}
inline vector<T>&operator[](int k){
return (A.at(k));
}
static Matrix E(size_t n){
Matrix mat(n);
for(int i=0;i<n;i++)mat[i][i]=1;
return (mat);
}
Matrix &operator+=(Matrix&B){
size_t n=height(),m=width();
for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]+=B[i][j];
return (*this);
}
Matrix &operator-=(Matrix&B){
size_t n=height(),m=width();
for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]-=B[i][j];
return (*this);
}
Matrix &operator*=(Matrix&B) {
size_t n=height(),m=B.width(),p=width();
vector<vector<T>> C(n,vector<T>(m,0));
for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<p;k++)C[i][j]+=(*this)[i][k]*B[k][j];
A.swap(C);
return (*this);
}
Matrix &operator^=(long long k){
Matrix B=Matrix::E(height());
while(k>0){
if(k&1)B*=*this;
*this*=*this;
k>>=1LL;
}
A.swap(B.A);
return (*this);
}
Matrix operator+(Matrix&B){
return (Matrix(*this)+=B);
}
Matrix operator-(Matrix &B){
return (Matrix(*this)-=B);
}
Matrix operator*(Matrix&B){
return (Matrix(*this)*=B);
}
Matrix operator^(long long k){
return (Matrix(*this)^=k);
}
};
long long BGstep(long long a,long long b,long long p){
//solve a^x≡b(mod p) O(√p)
long long m=ceil(sqrt(p));
map<long long,long long> power;
for(int i=m-1;0<=i;i--){
power[modpow(a,i,p)]=i;
}
long long c=Div(1ll,modpow(a,m,p),p);
for(int i=0;i<m;i++){
long long d=(b*modpow(c,i,p))%p;
if(power.count(d))return i*m+power[d];
}
return -1;
}
bool bellman_ford(const vector<tuple<long long,long long,long long>> &E,long long N,long long S,vector<long long> &dist){
const long long inf=1e9;
dist.resize(N,inf);
dist[S]=0ll;
for(int i=0;i<N;i++){
bool end=true;
for(auto [from,to,cost]:E){
if(dist[from]==inf)continue;
if(dist[from]+cost<dist[to]){
dist[to]=dist[from]+cost;
end=false;
}
}
if(end)return false;
}
return true;
}
class TopologicalSort{
private:
int N;
vector<vector<int>> G;
public:
TopologicalSort(const vector<vector<int>> &g):G(g){};
vector<int> order;
bool sort(function<bool(int,int)> compare=[](int a,int b){return a<b;}){
N=G.size();
priority_queue<int,vector<int>,function<bool(int,int)>> pq(compare);
vector<int> in_edge(N,0);
for(int i=0;i<N;i++){
for(const int &nxt:G[i]){
in_edge[nxt]++;
}
}
for(int i=0;i<N;i++)if(!in_edge[i])pq.push(i);
while(pq.size()){
int v=pq.top();pq.pop();
order.push_back(v);
for(const int &nxt:G[v]){
if(--in_edge[nxt])continue;
pq.push(nxt);
}
}
return N==(ll)order.size();
}
};
class Doubling{
private:
const vector<int> G;
const int Max;
vector<vector<int>> doubling;
public:
Doubling(const vector<int> g,int m):G(g),Max(m){
//2^Max-1
int N=G.size();
doubling.resize(N);
for(int i=0;i<N;i++)doubling[i].resize(Max,-1);
for(int i=0;i<N;i++)doubling[i][0]=G[i];
for(int i=0;i<Max-1;i++){
for(int j=0;j<N;j++)doubling[j][i+1]=doubling[doubling[j][i]][i];
}
return;
};
int get(int v,long long K){
int ans=v;
for(int i=0;i<Max;i++){
if(K&(1ll<<i))ans=doubling[ans][i];
}
return ans;
}
};
//from https://algo-logic.info/tree-dp/#
struct Rerooting {
/* start 問題ごとに書き換え */
struct DP { // DP の型
long long black,white;// 全部black/一つでもwhiteを含む
DP(long long b,long long w) : black(b),white(w) {}
};
const DP identity = DP(0,-1e9); // 単位元(末端の値は add_root(identity) になるので注意)
function<DP(DP, DP)> merge = [](DP dp_cum, DP d) -> DP {
return DP(dp_cum.black+d.black,max(dp_cum.white+max(d.black,d.white),dp_cum.black+d.white));
};
function<DP(DP)> add_root = [](DP d) -> DP {
return DP(d.white+1,max(d.white,d.black));
};
/* end 問題ごとに書き換え */
// グラフの定義
struct Edge {
int to;
};
using Graph = vector<vector<Edge>>;
vector<vector<DP>> dp; // dp[v][i]: vから出るi番目の有向辺に対応する部分木のDP
vector<DP> ans; // ans[v]: 頂点vを根とする木の答え
Graph G;
Rerooting(int N) : G(N) {
dp.resize(N);
ans.assign(N, identity);
}
void add_edge(int a, int b) {
G[a].push_back({b});
}
void build() {
dfs(0); // 普通に木DP
bfs(0, identity); // 残りの部分木に対応するDPを計算
}
DP dfs(int v, int p = -1) { // 頂点v, 親p
DP dp_cum = identity;
int deg = G[v].size();
dp[v] = vector<DP>(deg, identity);
for (int i = 0; i < deg; i++) {
int u = G[v][i].to;
if (u == p) continue;
dp[v][i] = dfs(u, v);
dp_cum = merge(dp_cum, dp[v][i]);
}
//DP dp_=add_root(dp_cum);
//printf("%d\n",v);
//printf("{%lld,%lld}\n",dp_.black,dp_.white);
return add_root(dp_cum);
}
void bfs(int v, const DP& dp_p, int p = -1) { // bfs だが、実装が楽なので中身は dfs になっている
int deg = G[v].size();
for (int i = 0; i < deg; i++) { // 前のbfsで計算した有向辺に対応する部分木のDPを保存
if (G[v][i].to == p) dp[v][i] = dp_p;
}
vector<DP> dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積merge
for (int i = 0; i < deg; i++) {
dp_l[i + 1] = merge(dp_l[i], dp[v][i]);
}
for (int i = deg - 1; i >= 0; i--) {
dp_r[i] = merge(dp_r[i + 1], dp[v][i]);
}
ans[v] = add_root(dp_l[deg]); // 頂点 v の答え
for (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算
int u = G[v][i].to;
if (u == p) continue;
bfs(u, add_root(merge(dp_l[i], dp_r[i + 1])), v);
}
}
};
}
namespace Guest {
const int MAX_VAL = 300000;
int a[MAX_VAL]; //要素
int cnt[MAX_VAL]; //区間内のiの個数
int res; //区間内の種類の数
class Mo {
private:
vector<int> left, right;
const int width;
void add(const int id);
void del(const int id);
public:
vector<int> ans;
Mo(const int n) : width((int)sqrt(n)) {}
//クエリ[l,r)
void insert(const int l, const int r) {
left.push_back(l), right.push_back(r);
}
void solve() {
const int sz = (int)left.size();
int nl = 0, nr = 0;
vector<int> ord(sz);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](const int a, const int b) {
const int c = left[a] / width, d = left[b] / width;
return (c == d) ? ((c & 1) ? (right[b] < right[a]) : (right[a] < right[b])) : (c < d);
});
ans.resize(sz);
for (const int id : ord) {
while (nl > left[id]) add(--nl);
while (nr < right[id]) add(nr++);
while (nl < left[id]) del(nl++);
while (nr > right[id]) del(--nr);
ans[id] = res;
}
}
};
//idは元の配列のインデックス
void Mo::add(const int id)
{
res -= cnt[a[id]] / 2;
res += (++cnt[a[id]]) / 2;
}
void Mo::del(const int id)
{
res -= cnt[a[id]] / 2;
res += (--cnt[a[id]]) / 2;
}
constexpr long long mod=MOD2;
class mint {
long long x;
public:
mint(long long x=0) : x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint& a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint& a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint& a) {
(x *= a.x) %= mod;
return *this;
}
bool operator==(const mint a){
return x==a.x;
}
mint operator+(const mint& a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint& a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint& a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint& a) {
return (*this) *= a.inv();
}
mint operator/(const mint& a) const {
mint res(*this);
return res/=a;
}
friend ostream& operator<<(ostream& os, const mint& m){
os << m.x;
return os;
}
};
struct RollingHash {
static const int base1 = 1007, base2 = 2009;
static const int mod1 = 1000000007, mod2 = 1000000009;
vector<long long> hash1, hash2, power1, power2;
// construct
RollingHash(const vector<long long> &S) {
int n = (int)S.size();
hash1.assign(n+1, 0);
hash2.assign(n+1, 0);
power1.assign(n+1, 1);
power2.assign(n+1, 1);
for (int i = 0; i < n; ++i) {
hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
power1[i+1] = (power1[i] * base1) % mod1;
power2[i+1] = (power2[i] * base2) % mod2;
}
}
// get hash of S[left:right]
inline pair<long long, long long> get(int l, int r) const {
long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
if (res1 < 0) res1 += mod1;
long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
if (res2 < 0) res2 += mod2;
return {res1, res2};
}
// get lcp of S[a:] and S[b:]
inline int getLCP(int a, int b) const {
int len = min((int)hash1.size()-a, (int)hash1.size()-b);
int low = 0, high = len;
while (high - low > 1) {
int mid = (low + high) >> 1;
if (get(a, a+mid) != get(b, b+mid)) high = mid;
else low = mid;
}
return low;
}
// get lcp of S[a:] and T[b:]
inline int getLCP(const RollingHash &T, int a, int b) const {
int len = min((int)hash1.size()-a, (int)hash1.size()-b);
int low = 0, high = len;
while (high - low > 1) {
int mid = (low + high) >> 1;
if (get(a, a+mid) != T.get(b, b+mid)) high = mid;
else low = mid;
}
return low;
}
};
}
//
long long gcd(long long a, long long b) {
if (b == 0LL)return a;
return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
return a * b / gcd(a, b);
}
signed main() {
/*
文章を読み落としていませんか?
制約も隅々まで読んでいますか?
注意
・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を
rは含みません
・BITって1-indexedなんだぜ
イケてるよな
・using namespace Warabi??
*/
//using namespace Warabi;
//mintのMODは確認した?
rep(i,0,9)out_(pow(3,i));nel;
}