結果
| 問題 | No.809 かけ算 |
| ユーザー |
 sakaki_tohru
|
| 提出日時 | 2019-09-06 19:09:45 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 32,622 bytes |
| コンパイル時間 | 3,504 ms |
| コンパイル使用メモリ | 211,428 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-24 09:05:17 |
| 合計ジャッジ時間 | 4,141 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 3 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,944 KB |
| testcase_04 | AC | 2 ms
6,940 KB |
| testcase_05 | AC | 2 ms
6,940 KB |
| testcase_06 | AC | 2 ms
6,944 KB |
ソースコード
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include<unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include<functional>
#include<queue>
#include<regex>
#include<time.h>
#include<type_traits>
#include<cstdlib>
#include<utility>
#include<numeric>
#include<iterator>
#include<random>
using namespace std;
using ll = long long;
using grid = vector<vector<char>>;
/*
メモ書き
cout << setw(5) << setfill('0') << 〇〇 << endl;
は5つ右寄せで0埋め出力
*/
constexpr ll MOD = 1000000007;//良く出てくるMOD
constexpr ll INF = 1050000000;//intで使うでかい数
constexpr ll LONGINF = 1050000000000000000;//longlongで使うでかい数
struct all_init{
//初期化のためだけの構造体
//コンストラクタが呼ばれ、cin,cout高速化がされる
//ついでに少数も出力できるようにしている
all_init() {
cout.tie(nullptr);
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
};
}ALL_INIT;
struct edge {
//辺の重みを管理できるような構造体
//フローで使う容量を意味するcapaも追加
//コンストラクタによって簡単に値を入れられるようにしている
//operatorは辺の重みでソート出来るようにしている(主に最小全域木用)
int from, to;
ll cost;
ll capa;
edge(int s, int d) : from(s), to(d) {
cost = 0; capa = 0;
}
edge(int s, int d, ll w) : from(s), to(d), cost(w) { capa = 0; }
edge(int s, int d, ll x, ll y) :from(s), to(d), cost(x), capa(y) { }
bool operator < (const edge& x) const {
return cost < x.cost;
}
};
using graph = vector<vector<edge>>;
using graph_bool = vector<vector<bool>>;
#define CIN(vector_array_etc,n) for(int loop=0;loop<n;loop++){cin>>vector_array_etc[loop];}
#define COUT(vector_array_etc,n) for(int LOOP=0;LOOP<n;LOOP++){cout<<vector_array_etc[LOOP]<<(LOOP == n-1 ?'\n':' ');}
#define VC(Type_name) vector<Type_name>//1次元ならあまり意味ないかも
#define SORT(vector_etc) sort(vector_etc.begin(),vector_etc.end())
#define ALL(vec_etc) vec_etc.begin(),vec_etc.end()
#define VCVC(Type_name) vector<vector<Type_name>>//2次元配列定義怠過ぎ問題
#define WARSHALL vector<vector<ll>> g(n,vector<ll>(n,LONGINF))
#define endl '\n'
template<class T>bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}//aに最大値が入る
template<class T>bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}//aに最小値が入る
template<typename T>istream& operator >> (istream& is, vector<T>& Vec) {
for (T& x : Vec) { is >> x; }
return is;
}
template<typename V, typename H>void resize(vector<V>& vec, const H head) {
vec.resize(head);
}
template<typename V, typename H, typename ... T>void resize(vector<V>& vec, const H& head, const T ... tail) {
vec.resize(head);
for (auto& v : vec) { resize(v, tail...); }
}
template<ll mod> struct ModInt {
//けんちょんさん作modをとる整数
//名前だけ変えた
//これがないと二項係数が動かないので注意
//普通に計算するとmodがとれる
long long val;
constexpr ModInt(long long v = 0) noexcept : val(v % mod) {
if (val < 0) v += mod;
}
constexpr int getmod() { return mod; }
constexpr ModInt operator - () const noexcept {
return val ? mod - val : 0;
}
constexpr ModInt operator + (const ModInt& r) const noexcept { return ModInt(*this) += r; }
constexpr ModInt operator - (const ModInt& r) const noexcept { return ModInt(*this) -= r; }
constexpr ModInt operator * (const ModInt& r) const noexcept { return ModInt(*this) *= r; }
constexpr ModInt operator / (const ModInt& r) const noexcept { return ModInt(*this) /= r; }
constexpr ModInt& operator += (const ModInt& r) noexcept {
val += r.val;
if (val >= mod) val -= mod;
return *this;
}
constexpr ModInt& operator -= (const ModInt& r) noexcept {
val -= r.val;
if (val < 0) val += mod;
return *this;
}
constexpr ModInt& operator *= (const ModInt& r) noexcept {
val = val * r.val % mod;
return *this;
}
constexpr ModInt& operator /= (const ModInt& r) noexcept {
long long a = r.val, b = mod, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
val = val * u % mod;
if (val < 0) val += mod;
return *this;
}
constexpr bool operator == (const ModInt& r) const noexcept {
return this->val == r.val;
}
constexpr bool operator != (const ModInt& r) const noexcept {
return this->val != r.val;
}
friend ostream& operator << (ostream &os, const ModInt<mod>& x) noexcept {
return os << x.val;
}
friend istream& operator >> (istream &is, ModInt<mod>& x) noexcept {
return is >> x.val;
}
friend constexpr ModInt<mod> modpow(const ModInt<mod> &a, long long n) noexcept {
if (n == 0) return 1;
auto t = modpow(a, n / 2);
t = t * t;
if (n & 1) t = t * a;
return t;
}
};
template<class T> struct nCk {
//けんちょんさん作二項係数ライブラリ
//名前だけ変えた
//nCk<ModInt<MOD>> c(200000);
//↑のような感じで初期化
vector<T> fact_, inv_, finv_;
constexpr nCk() {}
constexpr nCk(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
init(n);
}
constexpr void init(int n) noexcept {
fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
int MOD = fact_[0].getmod();
for (int i = 2; i < n; i++) {
fact_[i] = fact_[i - 1] * i;
inv_[i] = -inv_[MOD%i] * (MOD / i);
finv_[i] = finv_[i - 1] * inv_[i];
}
}
constexpr T com(int n, int k) const noexcept {
if (n < k || n < 0 || k < 0) return 0;
return fact_[n] * finv_[k] * finv_[n - k];
}
constexpr T fact(int n) const noexcept {
if (n < 0) return 0;
return fact_[n];
}
constexpr T inv(int n) const noexcept {
if (n < 0) return 0;
return inv_[n];
}
constexpr T finv(int n) const noexcept {
if (n < 0) return 0;
return finv_[n];
}
};
int dx[] = { 0,1,-1, 0,1,-1, 1,-1 }; //i<4:4way i<8:8way
int dy[] = { 1,0, 0,-1,1,-1,-1, 1 };
ll PowMod(ll n, ll k, ll mod) {
//繰り返し2乗法
//n^kをmodで求める
ll r = 1;
for (; k > 0; k >>= 1) {
if (k & 1) {
r = (r * n) % mod;
}
n = (n * n) % mod;
}
return r;
}
ll Gcd(ll a, ll b) {//最大公約数
return b != 0 ? Gcd(b, a % b) : a;
}
ll Lcm(ll a, ll b) {//最小公倍数
return a / Gcd(a, b) * b;
}
vector<string> Split(string s, string t) {
//文字列を文字列で分割する
vector<string> v;
int p = s.find(t);
if (p != s.npos) {
v.push_back(s.substr(0, p));
s = s.substr(p + t.size());
}
v.push_back(s);
return v;
}
vector<int> Lis(const vector<int>& a) {
//#define Index_of(as, x) distance(as.begin(), lower_bound(as.begin(), as.end(), x))
#define Index_of(as, x) distance(as.begin(), upper_bound(as.begin(), as.end(), x))
//upper_boundを使用すると、重複を許した最長増加部分列になる
//-1倍した値を入れれば、最長減少部分列になる
const int n = a.size();
vector<int> A(n, INF);
vector<int> id(n);
for (int i = 0; i < n; ++i) {
id[i] = Index_of(A, a[i]);
A[id[i]] = a[i];
}
int m = *max_element(id.begin(), id.end());
vector<int> b(m + 1);
for (int i = n - 1; i >= 0; --i)
if (id[i] == m) b[m--] = a[i];
return b;//最長部分列のどれか1つ
}
string LcsAlphabeticalMinOrder(string a, string b) {
if (a.size() < b.size()) { swap(a, b); }
int n = a.size(), m = b.size();
vector<string> dp(m + 1);
for (int i = 0; i < n; i++) {
vector<string> to(m + 1);
for (int j = 0; j < m; j++) {
if (a[i] == b[j]) {
to[j + 1] = dp[j] + a[i];
}
else {
if (to[j].size() > dp[j + 1].size()) { to[j + 1] = to[j]; }
else if (to[j].size() < dp[j + 1].size()) { to[j + 1] = dp[j + 1]; }
else if (to[j] < dp[j + 1]) { to[j + 1] = to[j]; }
else {to[j + 1] = dp[j + 1];}
}
}
dp.swap(to);
}
return dp[m];
}
string Lcs(const string &s,const string &t) {
int dp[3001][3001];
int n = s.size();
int m = t.size();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
string ans = "";
int i = s.size(), j = t.size();
while (i > 0 && j > 0) {
if (s[i - 1] == t[j - 1]) {
ans += s[i - 1];
i--;
j--;
}
else if (dp[i - 1][j] >= dp[i][j - 1])
i--;
else
j--;
}
reverse(ans.begin(), ans.end());
return ans;
}
vector<int> LcsInteger(const vector<int> &a, const vector<int> &b) {
#define index_of(as, x) distance(as.begin(), lower_bound(as.begin(), as.end(), x))
struct node {
int value;
node *next;
node(int value, node *next) : value(value), next(next) { }
};
const int n = a.size(), m = b.size();
map< int, vector<int> > M;
for (int j = m - 1; j >= 0; --j)
M[b[j]].push_back(j);
vector<int> xs(n + 1, INF); xs[0] = -INF;
vector< node* > link(n + 1);
for (int i = 0; i < n; ++i) {
if (M.count(a[i])) {
vector<int> ys = M[a[i]];
for (int j = 0; j < (int)ys.size(); ++j) {
int k = index_of(xs, ys[j]);
xs[k] = ys[j];
link[k] = new node(b[ys[j]], link[k - 1]);
}
}
}
vector<int> c;
int l = index_of(xs, INF - 1) - 1;
for (node *p = link[l]; p; p = p->next)
c.push_back(p->value);
reverse(c.begin(), c.end());
return c;
}
bool IsPrime(ll n) {
//素数かどうかを判定
//true 素数
if (n < 2)return false;
for (ll i = 2; i*i <= n; i++)if (!(n%i))return false;
return true;
}
vector<bool> Eratosthenes(int n) {
//エラトステネスの篩
//返り値はbool
//return res;として、返り値の型をvector<int>とすれば、
//素数だけを取り出せる
vector<int> res;
vector<bool> Prime(n + 1, true);
Prime[0] = Prime[1] = false;
for (int i = 2; i*i <= n; i++) {
if (Prime[i]) {
for (int j = 2; i*j <= n; j++) {
Prime[i*j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (Prime[i]) {
res.emplace_back(i);
}
}
return Prime;
}
ll MergeCount(vector<int> &a) {
//反転数を数える
ll count = 0;
int n = a.size();
if (n > 1) {
vector<int> b(a.begin(), a.begin() + n / 2);
vector<int> c(a.begin() + n / 2, a.end());
count += MergeCount(b);
count += MergeCount(c);
for (int i = 0, j = 0, k = 0; i < n; ++i)
if (k == c.size()) a[i] = b[j++];
else if (j == b.size()) a[i] = c[k++];
else if (b[j] <= c[k]) a[i] = b[j++];
else { a[i] = c[k++]; count += n / 2 - j; }
}
return count;
}
bool WarshallFloyd(vector<vector<ll>> &c) {
//ワーシャルフロイド法
//全ての頂点間の最短距離を求める
//falseの時、負の閉路検出
int V = c.size();
for (int i = 0; i < V; i++) {
c[i][i] = 0;
}
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
for (int k = 0; k < V; k++) {
if (c[j][k] > c[j][i] + c[i][k]) {
c[j][k] = c[j][i] + c[i][k];
}
}
}
}
for (int i = 0; i < V; i++) {
if (c[i][i] < 0) {
return false;
}
}
return true;
}
vector<ll> Dijkstra(int i, vector<vector<edge>> graph) {
//i:始点
//graph:重み付きグラフ
int n = graph.size();
vector<ll> d(n, LONGINF);
d[i] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
q.push(make_pair(0, i));//第一引数:コスト 第二引数:頂点
while (!q.empty()) {
pair<ll, int> p = q.top();
q.pop();
int v = p.second;
if (d[v] < p.first) {
continue;
}
for (auto x : graph[v]) {
if (d[x.to] > d[v] + x.cost) {
d[x.to] = d[v] + x.cost;
q.push(make_pair(d[x.to], x.to));
}
}
}
return d;
}
bool BellmanFord(int start, int V, int E, vector<edge> Edge, vector<ll> &d) {
//第一引数:start 始点
//第二引数:V 頂点数
//第三引数:E 辺の数
//第四引数:Edge 辺の重み付きのグラフ
//第五引数:d 各頂点への距離を入れる配列(答えが入る)
//負の閉路検出でfalseが返り値
resize(d, V);
fill(d.begin(), d.end(), LONGINF);
d[start] = 0;
vector<bool> t(V, false);
for (int i = 0; i < V - 1; i++) {
for (int j = 0; j < E; j++) {
edge e = Edge[j];
if (d[e.from] == LONGINF) { continue; }
if (d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[e.from] + e.cost;
}
}
}
for (int i = 0; i < V; i++) {
for (int j = 0; j < E; j++) {
edge e = Edge[j];
if (d[e.from] == LONGINF) { continue; }
if (d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[e.from] + e.cost;
t[e.to] = true;
/*
if (i == V - 1) {//どこかに閉路があることを感知する
return false;
}
*/
}
if (t[e.from]) {
t[e.to] = true;
}
}
}
if (t[V - 1]) {
//V-1は頂点番号n-1で、始点からn-1までに負の閉路を検出したい場合には、
//コメントアウトを解除すること。
return false;
}
return true;
}
bool TopologicalSort(const vector<vector<edge>> &g, vector<int> &ans) {
//トポロジカルソート
//trueが帰る時、トポロジカルソートが成功し、その結果がansに渡される
//falseはトポロジカルソートの失敗
int n = g.size(), k = 0;
vector<int> ord(n), in(n);
for (auto &es : g) {
for (auto &e : es) {
in[e.to]++;
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (in[i] == 0) q.push(i);
}
while (!q.empty()) {
int v = q.front();
q.pop();
ord[k++] = v;
for (auto &e : g[v]) {
if (--in[e.to] == 0) q.push(e.to);
}
}
ans = ord;
if (*max_element(in.begin(), in.end()) == 0) { return true; }
return false;
}
vector<int> ArticulationNode(const vector<vector<edge>>& g) {
//グラフの関節点を列挙する
//最後の2行で、erace uniqueをしない場合は、その分割によって何個のグラフに分かれるかを判定できる(要チェック)。
int n = g.size(), idx;
vector<int> low(n), ord(n), art;
function<void(int)> DFS = [&](int v) {
low[v] = ord[v] = ++idx;
for (auto& e : g[v]) {
int w = e.to;
if (ord[w] == 0) {
DFS(w);
low[v] = min(low[v], low[w]);
if ((ord[v] == 1 && ord[w] != 2) || (ord[v] != 1 && low[w] >= ord[v])) {
art.push_back(v);
}
}
else {
low[v] = min(low[v], ord[w]);
}
}
};
for (int u = 0; u < n; u++) {
if (ord[u] == 0) {
idx = 0;
DFS(u);
}
}
sort(art.begin(), art.end());//与えられた関節点をソート
art.erase(unique(art.begin(), art.end()), art.end());//同じ関節点が複数存在することがある,
return art;
}
vector<vector<edge>> ToRootTree(const vector<vector<edge>> &g, int r) {
//根付き木へ変換する。
//動作未確認。
int n = g.size();
vector<vector<edge>> G(n);
vector<int> ord(n, -1);
queue<int> q;
q.push(r);
int k = 0;
while (q.size()) {
int u = q.front(); q.pop();
for (auto &e : g[u]) {
int v = e.to;
if (ord[v] == -1) {
ord[v] = k; k++;
q.push(v);
G[u].emplace_back(e);
}
}
}
return G;
}
edge TreeDiameter(const vector<vector<edge>> &g) {
//重み付きグラフ(木)を受け取り、その木の直径を求める
//返り値はfrom,to,costを持った構造体
int start = 0;//どの始点から始めても良いので、0から始める
static const auto bfs = [](const vector<vector<edge>> &g, int s, queue<int> &q, vector<ll> &dist) {
while (!q.empty()) { q.pop(); }
q.push(s);
int n = g.size();
dist.assign(n, LONGINF);
dist[s] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (auto &e : g[u]) {
int v = e.to;
if (dist[v] == LONGINF) {
dist[v] = dist[u] + e.cost;
q.push(v);
}
}
}
return dist;
};
vector<ll> dist;
queue<int> q;
bfs(g, start, q, dist);
int n = g.size(), u = -1, v = -1;
for (int i = 0; i < n; i++)
if (dist[i] != LONGINF && (u == -1 || dist[i] > dist[u])) u = i;
bfs(g, u, q, dist);
for (int i = 0; i < n; i++)
if (dist[i] != LONGINF && (v == -1 || dist[i] > dist[v])) v = i;
ll d = dist[v];
if (u > v) swap(u, v);//念のため辞書順
return edge(u, v, d);
}
void add_edge(vector<vector<edge>> &g, int a, int b, ll cost, ll cap) {
//graph(vector<vector<edge>>)に対して無向辺として辺を貼る関数
//graph以外には当然使えないので注意
g[a].emplace_back(a, b, cost, cap);
g[b].emplace_back(b, a, cost, cap);
}
pair<vector<int>, vector<edge>> bridge(const vector<vector<edge>>& g) {
//グラフの橋となる辺を列挙する
//戻り値のfirst:二重辺連結成分分解の番号となる
//戻り値のsecond:橋となる辺を列挙したもの
const int n = g.size();
int idx = 0, s = 0, t = 0, k = 0;
vector<int> ord(n, -1), onS(n), stk(n), roots(n), cmp(n);
vector<edge> brdg;
function<void(int, int)> dfs = [&](int v, int u) {
ord[v] = idx++;
stk[s++] = v;
onS[v] = true;
roots[t++] = v;
for (auto& e : g[v]) {
int w = e.to;
if (ord[w] == -1) {dfs(w, v);}
else if (u != w && onS[w]) {
while (ord[roots[t - 1]] > ord[w]) { --t; }
}
}
if (v == roots[t - 1]) {
brdg.emplace_back(u, v, 0);
while (1) {
int w = stk[--s];
onS[w] = false;
cmp[w] = k;
if (v == w) break;
}
--t;
++k;
}
};
for (int u = 0; u < n; u++) {
if (ord[u] == -1) {
dfs(u, n);
brdg.pop_back();
}
}
return make_pair(cmp, brdg);
}
class UnionFind {
//satanicさん作 UnionFind
//追加機能:forest_num
//forestは、全体に含まれる木の数を表す
private:
std::vector<int> parent;
std::vector<int> height;
std::vector<int> m_size;
int forest_num;
public:
UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
forest_num = size_;
for (int i = 0; i < size_; ++i) parent[i] = i;
}
void init(int size_) {
parent.resize(size_);
height.resize(size_, 0);
m_size.resize(size_, 1);
forest_num = size_;
for (int i = 0; i < size_; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
int t = size(x) + size(y);
m_size[x] = m_size[y] = t;
if (height[x] < height[y]) parent[x] = y;
else parent[y] = x;
if (height[x] == height[y]) ++height[x];
forest_num--;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
if (parent[x] == x) return m_size[x];
return size(parent[x] = find(parent[x]));
}
int forest() {
return forest_num;
}
};
class Dinic {
//最大流を求める
private:
int n, s, t;
vector<int> level, prog, que;
vector<vector<ll>> cap, flow;
vector<vector<int>> g;
ll inf;
public:
Dinic(const vector<vector<edge>> &graph) :
n(graph.size()),
cap(n, vector<ll>(n)),//
flow(n, vector<ll>(n)),
g(n, vector<int>()),
inf(LONGINF) {
for (int i = 0; i < n; i++) {
for (auto &e : graph[i]) {
int u = e.from, v = e.to;
ll c = e.capa;
cap[u][v] += c;
cap[v][u] += c;
flow[v][u] += c;
g[u].push_back(v);
g[v].push_back(u);
}
}
}
inline ll residue(int u, int v) { return cap[u][v] - flow[u][v]; }
ll solve(int s_, int t_) {
this->t = t_, this->s = s_;
que.resize(n + 1);
ll res = 0;
while (levelize()) {
prog.assign(n, 0);
res += augment(s, inf);
}
return res;
}
bool levelize() {
int l = 0, r = 0;
level.assign(n, -1);
level[s] = 0;
que[r++] = s;
while (l != r) {
int v = que[l++];
if (v == t) break;
for (const int &d : g[v])
if (level[d] == -1 && residue(v, d) != 0) {
level[d] = level[v] + 1;
que[r++] = d;
}
}
return level[t] != -1;
}
ll augment(int v, ll lim) {
ll res = 0;
if (v == t) return lim;
for (int &i = prog[v]; i < (int)g[v].size(); i++) {
const int &d = g[v][i];
if (residue(v, d) == 0 || level[v] >= level[d]) continue;
const ll aug = augment(d, min(lim, residue(v, d)));
flow[v][d] += aug;
flow[d][v] -= aug;
res += aug;
lim -= aug;
if (lim == 0) break;
}
return res;
}
};
class MinimumCostFlow {
private:
using Flow = ll;
using Cost = ll;
struct Edge {
int d;
Flow c, f;
Cost w;
int r, is_r;
Edge(int d_, Flow c_, Flow f_, Cost w_, int r_, bool is_r_)
: d(d_), c(c_), f(f_), w(w_), r(r_), is_r(is_r_) {}
};
int n;
vector<vector<Edge>> g;
public:
MinimumCostFlow(int n_) : n(n_), g(vector<vector<Edge>>(n_)) {}
void add_edge(int src, int dst, Flow cap, Cost cost) { // 有向辺
int rsrc = g[dst].size();
int rdst = g[src].size();
g[src].emplace_back(dst, cap, 0, cost, rsrc, false);
g[dst].emplace_back(src, cap, cap, -cost, rdst, true);
}
Cost solve(int s, int t, Flow f) {
Cost res = 0;
vector<Cost> h(n + 10), dist(n);
vector<int> prevv(n + 10), preve(n + 10);
using pcv = pair<Cost, int>;
priority_queue<pcv, vector<pcv>, greater<pcv> > q;
fill(h.begin(), h.end(), 0);
while (f > 0) {
fill(dist.begin(), dist.end(), LONGINF);
dist[s] = 0;
q.emplace(0, s);
while (q.size()) {
Cost cd;
int v;
tie(cd, v) = q.top();
q.pop();
if (dist[v] < cd) continue;
for (int i = 0; i < (int)(g[v].size()); ++i) {
Edge &e = g[v][i];
if (residue(e) == 0) continue;
if (dist[e.d] + h[e.d] > cd + h[v] + e.w) {
dist[e.d] = dist[v] + e.w + h[v] - h[e.d];
prevv[e.d] = v;
preve[e.d] = i;
q.emplace(dist[e.d], e.d);
}
}
}
if (dist[t] == LONGINF) return -1; // 経路が見つからなかった
// s-t 間を最短路に沿って目一杯流す
for (int i = 0; i < n; ++i) h[i] += dist[i];
Flow d = f;
for (int v = t; v != s; v = prevv[v]) {
chmin(d, residue(g[prevv[v]][preve[v]]));
}
f -= d;
res += d * h[t];
for (int v = t; v != s; v = prevv[v]) {
Edge &e = g[prevv[v]][preve[v]];
e.f += d;
g[v][e.r].f -= d;
}
}
return res;
}
Flow residue(const Edge &e) { return e.c - e.f; }
// 流量を表示
void show() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (int)(g[i].size()); ++j) {
Edge &e = g[i][j];
if (e.is_r) continue;
cout << i << "->" << e.d << "(flow:" << e.f << ")" << endl;
}
}
}
};
class BipartiteMatching {
private:
int V;
vector<int> match;
vector<bool> used;
vector<vector<int>> g;
vector<pair<int, int>> match_pair;
bool dfs(int v) {
used[v] = true;
for (int i = 0; i < (int)g[v].size(); i++) {
int u = g[v][i];
int w = match[u];
if (w < 0 || !used[w] && dfs(w)) {
match[v] = u;
match[u] = v;
match_pair.emplace_back(make_pair(u, v));
return true;
}
}
return false;
}
public:
BipartiteMatching(int n) {
V = n;
resize(match, n);
resize(used, n);
resize(g, n);
}
void add_edge(int u, int v) {
g[u].emplace_back(v);
g[v].emplace_back(u);
}
int MatchingSolve() {
int res = 0;
fill(match.begin(), match.end(), -1);
for (int v = 0; v < V; v++) {
if (match[v] < 0) {
fill(used.begin(), used.end(), false);
if (dfs(v)) {
res++;
}
}
}
return res;
}
vector<pair<int, int>> get_pair() {
for (auto x : match_pair) {
cout << x.first << " " << x.second << endl;
}
return match_pair;
}
};
class Lca {
private:
int n;
int log2_n;
vector<vector<int>> parent;
vector<int> depth;
void dfs(const vector<vector<edge>> &g, int v, int p, int d) {
parent[0][v] = p;
depth[v] = d;
for (auto &e : g[v]) {
if (e.to != p) { dfs(g, e.to, v, d + 1); }
}
}
public:
Lca(const vector<vector<edge>> &g, int root) {
n = g.size();
log2_n = (int)log2(n) + 1;
resize(parent, log2_n, n);
resize(depth, n);
dfs(g, root, -1, 0);
for (int k = 0; k + 1 < log2_n; k++) {
for (int v = 0; v < (int)g.size(); v++) {
if (parent[k][v] < 0) {
parent[k + 1][v] = -1;
}
else {
parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
}
int get_lca(int u, int v) {
if (depth[u] > depth[v]) { swap(u, v); }//u≦v
for (int k = 0; k < log2_n; k++) {
if ((depth[v] - depth[u]) >> k & 1) {
v = parent[k][v];
}
}
if (u == v) { return u; }
for (int k = log2_n - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
int get_depth(int v) {
return depth[v];
}
};
class DAG {
//有向グラフをゴニョゴニョするクラス
//機能:longest_path 有向パスの最長経路(含まれる辺の数)を求める
private:
int n;
vector<vector<edge>> g;
vector<int> visited;
vector<int> dp;
vector<int> topological;
int dfs(int s) {
if ((int)g[s].size() == 0) {
return 1;
}
if (dp[s] > 0) { return dp[s]; }
int mx = 1;
for (auto j : g[s]) {
if (visited[j.to]==0) {
visited[j.to] = 1;
int l = 0;
l = dfs(j.to);
chmax(mx, l);
}
else {
chmax(mx, dp[j.to]);
}
}
return dp[s] = mx + 1;
}
public:
DAG(const vector<vector<edge>> &f) {
g = f;
n = f.size();
resize(visited, n + 1);
fill(visited.begin(), visited.end(), 0);
resize(dp, n + 1);
fill(dp.begin(), dp.end(), -1);
resize(topological, n);
}
DAG(int x) {
n = x;
resize(g, n);
resize(visited, n + 1);
fill(visited.begin(), visited.end(), 0);
resize(dp, n + 1);
fill(dp.begin(), dp.end(), -1);
}
void add_edge(int a,int b) {
g[a].emplace_back(a, b);
}
void add_edge(int a, int b, ll c) {
g[a].emplace_back(a, b, c);
}
void add_edge(int a, int b, ll c, ll d) {
g[a].emplace_back(a, b, c, d);
}
int longest_path() {
int mx = -1;
for (int i = 0; i < n; i++) {
int h = 0;
if (visited[i]==0) {
h = dfs(i);
chmax(mx, h);
}
}
return mx - 1;
}
bool TopologicalSort() {
//trueが帰る時、トポロジカルソートが成功
//falseはトポロジカルソートの失敗
int k = 0;
vector<int> ord(n), in(n);
for (auto &es : g) {
for (auto &e : es) {
in[e.to]++;
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (in[i] == 0) q.push(i);
}
while (!q.empty()) {
int v = q.front();
q.pop();
ord[k++] = v;
for (auto &e : g[v]) {
if (--in[e.to] == 0) { q.push(e.to); }
}
}
topological = ord;
if (*max_element(in.begin(), in.end()) == 0) { return true; }
return false;
}
};
class RangeMinimumUpdateQuerySegmentTree {
//区間最小値を求めることが出来るセグメント木
//query:指定した半開区間においての最小値を求める
//update:指定した半開区間の値を変更する
//RangeUpdateQueryも兼ねることが出来る(1つの要素の最小値はその要素のみ)
private:
int n;
ll inf = (1LL << 31) - 1;//2^31-1
vector<ll> dat, lazy;
void eval(int len, int k) {
if (lazy[k] == inf) return;
if (k * 2 + 1 < n * 2 - 1) {
lazy[2 * k + 1] = lazy[k];
lazy[2 * k + 2] = lazy[k];
}
dat[k] = lazy[k];
lazy[k] = inf;
}
public:
RangeMinimumUpdateQuerySegmentTree() {}
RangeMinimumUpdateQuerySegmentTree(int n_) {
n = 1; while (n < n_) n *= 2;
dat.assign(n * 2, inf);
lazy.assign(n * 2, inf);
}
// [a, b)
ll update(int a, int b, ll x, int k, int l, int r) {
eval(r - l, k);
if (b <= l || r <= a) return dat[k];
if (a <= l && r <= b) {
lazy[k] = x;
return lazy[k];
}
return dat[k] = min(update(a, b, x, 2 * k + 1, l, (l + r) / 2), update(a, b, x, 2 * k + 2, (l + r) / 2, r));
}
ll update(int a, int b, ll x) { return update(a, b, x, 0, 0, n); }
// [a, b)
ll query(int a, int b, int k, int l, int r) {
eval(r - l, k);
if (b <= l || r <= a) return inf;
if (a <= l && r <= b) return dat[k];
ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
return min(vl, vr);
}
ll query(int a, int b) { return query(a, b, 0, 0, n); }
};
class RangeSumQuerySegmentTree {
//区間和を求めることが出来るセグメント木
//update:指定した要素に加算
//query:指定した半開区間の合計を返す
//0-indexed
//半開区間
private:
struct Node {
Node *left, *right;
ll v;
Node() : left(nullptr), right(nullptr), v(0) {}
};
Node *root;
ll n, n0;
ll query(ll a, ll b, Node *n, ll l, ll r) {
if (a <= l && r <= b) {
return n->v;
}
if (r <= a || b <= l) {
return 0;
}
ll lv = n->left ? query(a, b, n->left, l, (l + r) >> 1) : 0;
ll rv = n->right ? query(a, b, n->right, (l + r) >> 1, r) : 0;
return (lv + rv) % MOD;
}
public:
RangeSumQuerySegmentTree(ll n) : n(n) {
n0 = 1;
while (n0 < n) n0 <<= 1;
root = new Node();
}
~RangeSumQuerySegmentTree() {
delete root; root = nullptr;
}
void update(ll k, ll x) {
Node *n = root;
ll l = 0, r = n0;
n->v = (n->v + x) % MOD;
while (r - l > 1) {
ll m = (l + r) >> 1;
if (k < m) {
if (!n->left) n->left = new Node();
n = n->left;
r = m;
}
else {
if (!n->right) n->right = new Node();
n = n->right;
l = m;
}
n->v = (n->v + x) % MOD;
}
}
ll query(ll a, ll b) {
return query(a, b, root, 0, n0);
}
ll lquery(ll b) {
return query(0, b, root, 0, n0);
}
ll rquery(ll a) {
return query(a, n0, root, 0, n0);
}
};
class KDimensionalTree{
//2Dの点がある区間内にあるかどうかを判定し、その点を列挙する
//makeKDTreeで前計算
//findが実際に探す部分
public:
struct Node {
int location;
int p, l, r;
Node() {}
};
struct Point {
int id,x, y;
Point() {}
Point(int i, int a, int b) {
id = i;
x = a;
y = b;
}
bool operator<(const Point &p)const {
return id < p.id;
}
void print() {
cout << id << endl;
}
};
static const ll NIL = -1;
static bool lessX(const Point &p1, const Point &p2) { return p1.x < p2.x; }
static bool lessY(const Point &p1, const Point &p2) { return p1.y < p2.y; }
int N;
vector<Point> P;
vector<Node> T;
int np;
KDimensionalTree() {}
KDimensionalTree(int N) { init(N); }
void init(int n) {
N = n;
P.clear();
T.clear();
resize(P, N);
resize(T, N);
np = 0;
}
int makeKDTree(int l, int r, int depth) {
if (l >= r) { return NIL; }
int mid = (l + r) / 2;
int t = np++;
if (depth & 1) {
sort(P.begin() + l, P.begin() + r, lessY);
}
else {
sort(P.begin() + l, P.begin() + r, lessX);
}
T[t].location = mid;
T[t].l = makeKDTree(l, mid, depth + 1);
T[t].r = makeKDTree(mid + 1, r, depth + 1);
return t;
}
void find(int v, int sx, int tx, int sy, int ty, int depth, vector<Point> &ans) {
int x = P[T[v].location].x;
int y = P[T[v].location].y;
if (sx <= x && x <= tx && sy <= y && y <= ty) {
ans.push_back(P[T[v].location]);
}
if (depth % 2 == 0) {
if (T[v].l != NIL) {
if (sx <= x) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
}
if (T[v].r != NIL) {
if (x <= tx) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
}
}
else {
if (T[v].l != NIL) {
if (sy <= y) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
}
if (T[v].r != NIL) {
if (y <= ty) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
}
}
}
void add_point(int i, int x, int y) {
P[i].id = i;
P[i].x = x;
P[i].y = y;
T[i].l = T[i].r = T[i].p = NIL;
}
};
class RangeAddQuerySegmentTree {
//区間に足し算をする機能と、ある要素を参照する機能があるセグメント木
private:
int n;
vector<ll> data;
public:
RangeAddQuerySegmentTree() {}
RangeAddQuerySegmentTree(int N) {
n = N;
resize(data, n + 1);
fill(data.begin(),data.end(), 0);
}
void add(int i, ll x) {
while (i) {
data[i] += x;
i -= (i&-i);
}
}
void add(int i, int j, ll x) {
add(j, x);
add(i - 1, -x);
}
ll get(int i) {
ll res = 0;
while (i <= n) {
res += data[i];
i += (i&-i);
}
return res;
}
};
class RangeSumAddQuerySegmentTree {
//update:ある区間に対して足し算を行う機能
//query:ある区間に対して合計値を求める機能
private:
vector<ll> bit0, bit1;
int n;
ll sum(const vector<ll> &b, int i) {
ll s = 0;
while (i > 0) {
s += b[i];
i -= (i&-i);
}
return s;
}
void add(vector<ll> &b, int i, ll v) {
while (i <= n) {
b[i] += v;
i += (i&-i);
}
}
public:
RangeSumAddQuerySegmentTree() {}
RangeSumAddQuerySegmentTree(int N) {
n = N;
resize(bit0, n + 1);
resize(bit1, n + 1);
fill(bit0.begin(), bit0.end(), 0);
fill(bit1.begin(), bit1.end(), 0);
}
void update(int l, int r, ll x) {
add(bit0, l, -x * (l - 1));
add(bit1, l, x);
add(bit0, r + 1, x*r);
add(bit1, r + 1, -x);
}
ll query(int l, int r) {
ll res = 0;
res += sum(bit0, r) + sum(bit1, r)*r;
res -= sum(bit0, l - 1) + sum(bit1, l - 1)*(l - 1);
return res;
}
};
int main() {
int c; cin >> c;
cout << "1 " << c << endl;
return 0;
}