#pragma region watasou /* the pen is mightier than the sword. -エドワード・ブルワー=リットン- KCLC44TH watasou1543. */ #include //#include using namespace std; //using namespace atcoder; //マクロ宣言 #define rep(i, a, b) for (ll i = a; i < b; i++) using ll = long long; using ld = long double; using pii = pair; using pli = pair; using pll = pair; using Graph = vector>; using V = vector; const ll mod=998244353; const ll MOD=1000000007; const ll INF=1000000000000000000; const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string abc="abcdefghijklmnopqrstuvwxyz"; string Y = "Yes"; string N = "No"; #define gcd __gcd #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define fi first #define se second #define fix(n) fixed << setprecision(n) #define print(n) cout << n << endl #define si size() #define in(n) insert(n) //関数宣言 template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } ll jou(ll N,ll k){ ll i=0; ll p=N; ll Ans=0; while(k>=(1<>Gra; mapvisited;// false=not visited, true=visited void DFS(int pos){ visited[pos]=true; for(int i : Gra[pos]){ if(visited[i]==false){ DFS(i); } } } vector > pri(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } const vectordx = {0, 1, 0, -1}; const vectordy = {1, 0, -1, 0}; vector> BFS(int H, int W, const vector &G, pair s) { vector> dist(H, vector(W, -1)); //すべての頂点を未訪問に初期化 queue> que; //初期条件 (頂点sを初期頂点とする) dist[s.first][s.second] = 0; que.push(s); // sを探索済み頂点に // BFS開始 while (!que.empty()) { pair v = que.front(); que.pop(); //頂点vからたどれる頂点を全て調べる for (int i = 0; i < 4; i++) { int X = dx[i] + v.first; int Y = dy[i] + v.second; if (X < 0 || X >= H || Y < 0 || Y >= W) continue; //すでに発見済みの頂点は探索しない if (dist[X][Y] != -1 || G[X][Y] == '#') continue; //新たな未探索点xについて距離情報を更新してキューに挿入 dist[X][Y] = dist[v.first][v.second] + 1; que.push(make_pair(X, Y)); } } return dist; } vectorsosuu(long long n){ vector isprime(n+1, true); // 0, 1 は予めふるい落としておく isprime[0] = isprime[1] = false; // ふるい for (int p = 2; p <= n; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p 以外の p の倍数から素数ラベルを剥奪 for (int q = p * 2; q <= n; q += p) { isprime[q] = false; } } return isprime; } // a^n mod を計算する long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // Union-Find struct UnionFind { vector par, rank, siz; // 構造体の初期化 UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { } // 根を求める int root(int x) { if (par[x]==-1) return x; // x が根の場合は x を返す else return par[x] = root(par[x]); // 経路圧縮 } // x と y が同じグループに属するか (= 根が一致するか) bool same(int x, int y) { return root(x)==root(y); } // x を含むグループと y を含むグループを併合する bool unite(int x, int y) { int rx = root(x), ry = root(y); // x 側と y 側の根を取得する if (rx==ry) return false; // すでに同じグループのときは何もしない // union by rank if (rank[rx]P; struct edge{int to;ll cost;}; vector dijkstra(vector> graph, int n, int start, ll INF){ priority_queue,greater

>que; vectordst(n,INF); dst[start]=0; que.push(P(0,start)); while(que.size()){ ll d=que.top().first; int u=que.top().second; que.pop(); if(dst[u]d+cost){ dst[v]=d+cost; que.push(P(dst[v],v)); } } } return dst; } // グラフ、頂点の入次数、頂点数を受け取り、そのトポロジカルソートを記録した配列を返す関数 vector topological_sort(vector> &G, vector &indegree, int V) { // トポロジカルソートを記録する配列 vector sorted_vertices; // 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する queue que; for (int i = 0; i < V; i++) { if (indegree[i] == 0) { que.push(i); } } // キューが空になるまで、操作1~3を繰り返す while (que.empty() == false) { // キューの先頭の頂点を取り出す int v = que.front(); que.pop(); if(que.size()!=1){ print(N); exit(0); } // その頂点と隣接している頂点の入次数を減らし、0になればキューに追加 for (int i = 0; i < (int)G[v].size(); i++) { int u = G[v][i]; indegree[u] -= 1; if (indegree[u] == 0) que.push(u); } // 頂点vを配列の末尾に追加する sorted_vertices.push_back(v); } // トポロジカルソートを返す return sorted_vertices; } template struct RMQ { const T INF = numeric_limits::max(); int n; // 葉の数 vector dat; // 完全二分木の配列 RMQ(int n_):n(),dat(n_*4,INF) { // 葉の数は 2^x の形 int x = 1; while (n_>x) { x*=2; } n=x; } void update(int i,T x) { i+=n-1; dat[i]=x; while(i>0){ i=(i-1)/2;//parent dat[i]=min(dat[i*2+1],dat[i*2+2]); } } // the minimum element of [a,b) T query(int a, int b) { return query_sub(a, b, 0, 0, n); } T query_sub(int a, int b, int k, int l, int r) { if (r <= a || b <= l) { return INF; } else if (a <= l && r <= b) { return dat[k]; } else { T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } }; int op(int a,int b){ return (a^b); } int e(){ return 0; } //using mint =modint998244353; #define debug cout << "OK" << endl; #pragma region template template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << "," << p.second << ")"; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } template ostream &operator<<(ostream &os, const vector> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << endl; } return os; } template ostream &operator<<(ostream &os, const vector>> &v) { for (int i = 0; i < (int)v.size(); i++) { os << "i = " << i << endl; os << v[i]; } return os; } template istream &operator>>(istream &is, vector &v) { for (T &in : v) is >> in; return is; } // template // ostream &operator<<(ostream &os, const map &mp) // { // for ((auto &[key, val]) : mp) // { // os << key << ":" << val << " "; // } // return os; // } template ostream &operator<<(ostream &os, const set &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, const multiset &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, queue q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; } template ostream &operator<<(ostream &os, deque q) { while (q.size()) { os << q.front() << " "; q.pop_front(); } return os; } template ostream &operator<<(ostream &os, stack st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; } template ostream &operator<<(ostream &os, priority_queue pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; } #pragma endregion template //-------------- ----------------------------------------------------------- #pragma endregion watasou /* 切り上げは(a+b-1)/bでできる cin忘れに注意 制約を見よう ヒントが多分ある N<=100だとO(N^3)かもしれない N<=10だとO(2^N)かもO(!N)かもしれない N<=9*(10^18)だとO(√N)の場合通らないことがある わかんなくなったら問題文を読み直そう */ /* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体 update(i,x): i 番目の要素を x に更新。O(log(n)) query(a,b): [a,b) での最小の要素を取得。O(log(n)) */ #include int main(){ print(1); }