akhauriyash/Code-Regression huggingface dataset:
// URL: https://atcoder.jp/contests/abc174/tasks/abc174_d

import std.algorithm, std.array, std.bitmanip, std.container, std.conv, std.format,
       std.functional, std.math, std.range, std.traits, std.typecons, std.stdio, std.string;

version(unittest) {} else
void main()
{
  int N; io.getV(N);
  dchar[] c; io.getV(c);

  if (c.all!(ci => ci == 'R') || c.all!(ci => ci == 'W'))
    io.put!"{exit: true}"(0);

  auto i = 0, j = N-1, r = 0;
  for (;; ++r) {
    while (c[i] == 'R') ++i;
    while (c[j] == 'W') --j;
    if (i > j) io.put!"{exit: true}"(r);
    swap(c[i], c[j]);
  }
}

auto io = IO!()();
import std.stdio;
struct IO(alias IN = stdin, alias OUT = stdout)
{
  import std.meta : allSatisfy;
  import core.stdc.stdlib : exit;

  void getV(T...)(ref T v)
  {
    foreach (ref w; v) get(w);
  }
  void getA(T)(size_t n, ref T v)
    if (hasAssignableElements!T)
  {
    v = new T(n);
    foreach (ref w; v) get(w);
  }
  void getC(T...)(size_t n, ref T v)
    if (allSatisfy!(hasAssignableElements, T))
  {
    foreach (ref w; v) w = new typeof(w)(n);
    foreach (i; 0..n) foreach (ref w; v) get(w[i]);
  }
  void getM(T)(size_t r, size_t c, ref T v)
    if (hasAssignableElements!T && hasAssignableElements!(ElementType!T))
  {
    v = new T(r);
    foreach (ref w; v) getA(c, w);
  }
  template getS(E...)
  {
    void getS(T)(size_t n, ref T v)
    {
      v = new T(n);
      foreach (ref w; v) foreach (e; E) mixin("get(w."~e~");");
    }
  }

  const struct PutConf
  {
    bool newline = true, flush, exit;
    string floatFormat = "%.10f", delimiter = " ";
  }

  void put(alias conf = "{}", T...)(T v)
  {
    mixin("const PutConf c = "~conf~"; putMain!c(v);");
  }
  void putB(alias conf = "{}", S, T)(bool c, S t, T f)
  {
    if (c) put!conf(t);
    else put!conf(f);
  }
  void putRaw(T...)(T v)
  {
    OUT.write(v);
    OUT.writeln;
  }

  private
  {
    dchar[] buf;
    auto sp = (new dchar[](0)).splitter;

    void nextLine()
    {
      IN.readln(buf);
      sp = buf.splitter;
    }
    void get(T)(ref T v)
    {
      if (sp.empty) nextLine();
      v = sp.front.to!T;
      sp.popFront();
    }

    void putMain(PutConf c, T...)(T v)
    {
      foreach (i, w; v) {
        putOne!c(w);
        if (i+1 < v.length) OUT.write(c.delimiter);
      }
      static if (c.newline) OUT.writeln;
      static if (c.flush) OUT.flush();
      static if (c.exit) exit(0);
    }
    void putOne(PutConf c, T)(T v)
    {
      static if (isInputRange!T && !isSomeString!T) putRange!c(v);
      else static if (isFloatingPoint!T) OUT.write(format(c.floatFormat, v));
      else static if (hasMember!(T, "fprint")) v.fprint(OUT);
      else OUT.write(v);
    }
    void putRange(PutConf c, T)(T v)
    {
      auto w = v;
      while (!w.empty) {
        putOne!c(w.front); w.popFront();
        if (!w.empty) OUT.write(c.delimiter);
      }
    }
  }
}


Measured memory_bytes: 4000
#include<iostream>
main(){for(int a,b,d,x,y,i,t;std::cin>>a>>b>>d,d;printf("%d %d\n",x,y)){x=y=1<<29;for(i=1<<17;i-->0;){t=d-a*i;if(!(d<a*i|t%b)&&x+y>i+t/b|(x+y==i+t/b&a*x+b*y>a*i+t)){x=i;y=t/b;}t=a*i-d;if(!(a*i<d|t%b)&&x+y>i+t/b|(x+y==i+t/b&a*x+b*y>a*i+t)){x=i;y=t/b;}t=a*i+d;if(t%b==0&&x+y>i+t/b|(x+y==i+t/b&a*x+b*y>a*i+t)){x=i;y=t/b;}}}}

Measured memory_bytes: 0
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100100,M=400400,P=1000000007;
int i,j,k,n,m,ch,ff,S,T,Hn,dn,ans,En;
int h[N],d[N],z[N],f[N],g[N];
ll dis[N];
struct edge { int s,n,v;} E[M];
struct cc {
	int x;
	ll y;
	bool operator < (const cc &n) const {
		return y<n.y;
	}
} H[N+M];
void R(int &x) {
	ff=x=0;ch=getchar();
	while (ch<'0' || '9'<ch) { if (ch=='-') ff=1;ch=getchar();}
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
	if (ff) x=-x;
}
void W(int x) {
	if (x<0) putchar('-'),x=-x;
	if (x>=10) W(x/10);
	putchar(x%10+'0');
}
void up(int x) {
	while (x>1 && H[x]<H[x>>1]) swap(H[x],H[x>>1]),x>>=1;
}
void down(int x) {
	while ((x<<1)<=Hn) {
		int k=x<<1;
		if (k<Hn && H[k|1]<H[k]) k|=1;
		if (H[k]<H[x]) swap(H[x],H[k]),x=k;
		else break;
	}
}
int C2(int x) {
	return (ll) x*x%P;
}
void E_add(int x,int y,int v) {
	E[++En].s=y;E[En].v=v;
	E[En].n=h[x];h[x]=En;
	E[++En].s=x;E[En].v=v;
	E[En].n=h[y];h[y]=En;
}
int main() {
	R(n);R(m);
	R(S);R(T);
	for (i=1;i<=m;i++) {
		int x,y,v;
		R(x);R(y);R(v);
		E_add(x,y,v);
	}
	memset(dis,1,sizeof dis);
	dis[S]=0;
	z[S]=1;
	cc t;
	t.x=S;t.y=0;
	H[++Hn]=t;
	up(Hn);
	while (Hn) {
		cc tt=H[1];
		d[++dn]=tt.x;
		z[tt.x]=1;
		H[1]=H[Hn--];
		down(1);
		for (k=h[tt.x];k;k=E[k].n) if (!z[E[k].s] && tt.y+E[k].v<dis[E[k].s]) {
			dis[E[k].s]=tt.y+E[k].v;
			t.x=E[k].s;
			t.y=dis[E[k].s];
			H[++Hn]=t;
			up(Hn);
		}
		while (Hn && z[H[1].x]) {
			H[1]=H[Hn--];
			down(1);
		}
	}
	f[S]=1;g[T]=1;
	for (i=1;i<=dn;i++) if (f[d[i]])
		for (k=h[d[i]];k;k=E[k].n) if (dis[d[i]]+E[k].v==dis[E[k].s]) f[E[k].s]=(f[E[k].s]+f[d[i]])%P;
	for (i=dn;i;i--)
		for (k=h[d[i]];k;k=E[k].n) if (dis[d[i]]+E[k].v==dis[E[k].s]) g[d[i]]=(g[E[k].s]+g[d[i]])%P;
	ans=C2(f[T]);
	for (i=1;i<=dn;i++) {
		int num=0;
		for (k=h[d[i]];k;k=E[k].n) {
			if (dis[d[i]]+E[k].v==dis[E[k].s] && 2ll*dis[d[i]]<dis[T] && dis[T]<2ll*dis[E[k].s]) ans=(ans+P-C2((ll) f[d[i]]*g[E[k].s]%P))%P;
			if (dis[d[i]]+E[k].v==dis[E[k].s] && 2ll*dis[d[i]]==dis[T]) num=((ll) f[d[i]]*g[E[k].s]+num)%P;
		}
		ans=(ans+P-C2(num))%P;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 10880
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <iomanip>
using namespace std;

int main(){
	int n,mi=0,ma=0,ans=0;
	cin>>n;
	if(n/10==9||n%10==9){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	return 0;
	
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = ((B)-1); I >= (A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define pri(a) cout << (a) << endl

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	char a,b;
	cin >> a >> b;
	if(a=='H'){
		if(b=='H'){
			cout << 'H' << endl;
		}else{
			cout << 'D' << endl;
		}
	}else{
		if(b=='H'){
			cout << 'D' << endl;
		}else{
			cout << 'H' << endl;
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
#include <memory>
#include <deque>
#include <set>
#include <unordered_set>
#include <cmath>
#include <list>
#include <cassert>
#include <cstring>

using namespace std;

using big = long long;

const int N = 200009;


int f[N], g[N];
int ans[N];
set<int> fs[N], gs[N];

int gf(int fa[], int x) {
  if (fa[x] != x) {
    fa[x] = gf(fa, fa[x]);
  }
  return fa[x];
}

int main() {
	std::ios_base::sync_with_stdio(false);
  int n, K, L;
  cin >> n >> K >> L;
  for (int i = 1; i <= n; ++i) {
    f[i] = g[i] = i;
  }
  while (K--) {
    int x, y;
    cin >> x >> y;
    f[gf(f, x)] = gf(f, y);
  }
  while (L--) {
    int x, y;
    cin >> x >> y;
    g[gf(g, x)] = gf(g, y);
  }

  for (int i = 1; i <= n; ++i) {
    fs[gf(f, i)].insert(i);
    gs[gf(g, i)].insert(i);
  }
  for (int i = 1; i <= n; ++i) {
    if (!ans[i]) {
      int x = gf(f, i);
      int y = gf(g, i);
      auto *s1 = &fs[x];
      auto *s2 = &gs[y];
      if (s1->size() > s2->size()) {
        swap(s1, s2);
      }
      vector<int> inter;
      for (int t : *s1) {
        if (s2->count(t)) {
          inter.push_back(t);
        }
      }
      for (int t : inter) {
        ans[t] = inter.size();
      }
    }
  }
  for (int i = 1; i  <= n; ++i) {
    if (i > 1) {
      cout << " ";
    }
    cout << ans[i];
  }
}


Measured memory_bytes: 40456
#pragma GCC optimize("O3") //コンパイラ最適化用

#define _GLIBCXX_DEBUG //配列に[]でアクセス時のエラー表示
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
// Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはメントされる
#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--) //ループ変数は1ずつデクリ
#define FOR(i, a, b) for (ll i = a; i < ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i > ll(b); i--) //ループ変数は1ずつデクリ
// xにはvectorなどのコンテナ
#define ALL(x) x.begin(), x.end() // sortなどの引数を省略したい
#define SIZE(x) ll(x.size())      // sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 // 10^12:極めて大きい値,∞
#define MOD 1000000007    // 10^9+7:合同式の法
#define MAXR 100000 // 10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back // vectorヘの挿入
#define MP make_pair // pairのコンストラクタ
#define F first      // pairの一つ目の要素
#define S second     // pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000

int main() {
    ll n, y;
    cin >> n >> y;
    bool fl = false;
    set<int> ans;
    REP(i, n + 1) {
        REP(j, n + 1) {
            if (i + j <= n) {
                if (10000 * i + 5000 * j + 1000 * (n - i - j) == y) {
                    cout << i << ' ' << j << ' ' << n - i - j << endl;
                    fl = true;
                }
            }
            if (fl) {
                break;
            }
        }
        if (fl) {
            break;
        }
    }
    if (!fl) {
        cout << -1 << ' ' << -1 << ' ' << -1 << endl;
    }
}


Measured memory_bytes: 3632
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>

using namespace std;

#define all(x) (x).begin(),(x).end()
#define ll long long
#define pii pair<int,int>
#define y1 Emilia
#define N 500500
#define dracarys ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n, m;
int dp[1 << 13];
int a[1111], b[1111];
vector<int> L[1111];
int main(){
    dracarys
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i] >> b[i];
        for (int j = 0; j < b[i]; ++j) {
            int x;
            cin >> x;
            --x;
            L[i].push_back(x);
        }
    }
    
    dp[0] = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        dp[mask] = (int)1e9;
        for (int j = 1; j <= m; ++j) {
            int nmask = mask;
            for (int i = 0; i < L[j].size(); ++i)
                if ((nmask&(1 << L[j][i])))
                    nmask ^= (1 << L[j][i]);
            dp[mask] = min (dp[mask], dp[nmask] + a[j]);
        }
    }
    
    if (dp[(1 << n) - 1] == (int)1e9) cout << -1 << "\n";
    else cout << dp[(1 << n) - 1] << "\n";
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define range(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, b) for (int i = 0; i < (b); i++)
#define ranger(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define repr(i, b) for (int i = (b) - 1; i >= 0; i--)
#define all(a) (a).begin(), (a).end()
#define show(x) cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}
template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
	rep(i, v.size()) { os << v[i] << (i == v.size() - 1 ? "" : " "); }
	return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S>& p) {
	os << '(' << p.first << ',' << p.second << ')';
	return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
	for (T& x : v) { is >> x; }
	return is;
}

int n;
string s;

signed main() {
	cin>>n >>s;

	set<int> ans;
	rep(i,10){
		rep(j,10){
			rep(k,10){
				stack<int> st;
				st.push(k);
				st.push(j);
				st.push(i);
				rep(l,n){
					if(s[l] - '0' == st.top()){
						st.pop();
					}
					if(st.empty()) break;
				}
				if(st.empty()){
					ans.emplace(i * 100 + j * 10 + k);
				}
			}
		}
	}
	cout << ans.size() << endl;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>

#define rep(i,begin,end) for(int i=begin; i<end; i++)
#define lld long long int

#define MOD 1000000007

long long int MOD_pow(long long int a, long long int n){
    long long int res = 1;
    while(n>0){
        if(n&1){
            res = res*a % MOD;
        }
        a = a*a % MOD;
        n >>= 1;
    }
    return res;
}

int main(){
    lld n;
    scanf("%lld", &n);
    int a[(int)n];
    int b[100000] = {0};
    rep(i, 0, (int)n){
        scanf("%d", &a[i]);
        b[a[i]]++;
    }
    int flag = 1;
    if(n%2){
        if(b[0] != 1){
            flag = 0;
        }
        rep(i, 1, (int)n){
            if(i%2){
                if(b[i] != 0){
                    flag = 0;
                }
            }else{
                if(b[i] != 2){
                    flag = 0;
                }
            }
        }
    }else{
        rep(i, 0, n){
            if(i%2){
                if(b[i] != 2){
                    flag = 0;
                }
            }else{
                if(b[i] != 0){
                    flag = 0;
                }
            }
        }
    }
    if(flag){
        printf("%lld", MOD_pow(2, n/2));
    }else{
        printf("0");
    }

    return 0;
}

Measured memory_bytes: 896
# -*- coding: utf-8 -*-
"""
"""


def is_palindromic(num_txt):
    return num_txt[0] == num_txt[-1]


def main():
    num_txt = input().strip()
    result = is_palindromic(num_txt)
    if result:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()
    


Measured memory_bytes: 2940
s = input()
a = 0
b = 0
c = 0
for i in range(len(s)):
    if s[i] == 'a':
        a += 1
    elif s[i] == 'b':
        b += 1
    elif s[i] == 'c':
        c += 1
if a == 1 and b == 1 and c == 1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;

int main() {
   cin.tie(0);
   ios_base::sync_with_stdio(0);

   string s;
   cin >> s;
   int mod = 0;
   int n = s.size();
   rep(i, 0, n) {
      mod += s[i] - '0';
      mod %= 9;
   }
   if (mod == 0) {
      cout << "Yes" << endl;
   } else {
      cout << "No" << endl;
   }
   return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
#define all(v) v.begin(), v.end()
#define lint long long
auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail){
  std::cerr << " " << head;
  debug_impl(tail...);
}
#define debug(...)\
  std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
  debug_impl(__VA_ARGS__);\
  std::cerr << std::noboolalpha;

void err () {
  std::cout << "No" << std::endl;
  exit(0);
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  std::string s; std::cin >> s;
  auto x = 'L';
  for (auto c : s) {
    if (c == x) err();
    if (x == 'L') x = 'R';
    else x = 'L';
  }
  std::cout << "Yes" << std::endl;
  return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
int main() {
	int a[3], i, x;
	for (i = 0; i < 3; i++) {
		scanf("%d", &a[i]);
	}
	for (i = 0;i < 3; i++) {
		for (int j = i + 1; j < 3; j++) {
			if (a[i] > a[j]) {
				x = a[i];
				a[i] = a[j];
				a[j] = x;
			}
		}
	} printf("%d %d %d\n", a[0], a[1], a[2]);
	return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;

//https://github.com/hoget157/library/blob/master/DataStructure/UnionFind.cpp
struct UnionFind{
	vector<int> rnk,par;

	UnionFind(int sz) : rnk(sz,0),par(sz){
		for(int i = 0;i < sz;i++) par[i] = i;
	}

	int find(int x){
		if(par[x] == x) return x;
		return par[x] = find(par[x]);
	}

	void unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		if(rnk[x] < rnk[y]) swap(x,y);
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
	
	bool same(int x,int y){
		return (find(x) == find(y));
	}
};

struct edge{ int from,to,cost; };

signed main(){
	int n,t,k;
	for(int _t = 0;cin >> n >> t >> k,n;_t++){
		vector<edge> edges;
		UnionFind uf(n);
		int ans = 0;
		for(int i = 0;i < n - 1;i++){
			int a,b,w;
			cin >> a >> b >> w; a--;b--;
			edges.push_back({a,b,w});
			ans += w;
		}
		sort(edges.begin(),edges.end(),[](const edge &e1,const edge &e2){
			return e1.cost > e2.cost;
		});
		int base[10010];
		for(int i = 0;i < t;i++){
			cin >> base[i]; base[i]--;
			if(i) uf.unite(base[i],base[i - 1]);
		}
		int other = 0;
		for(const auto &e : edges){
			if(!uf.same(e.from,e.to)){
				uf.unite(e.from,e.to);
				ans -= e.cost;
			}else{
				if(other < t - k - 1) ans -= e.cost;
				other++;
			}
		}
		printf("Case %d: %d\n",_t + 1,ans);
	}
}


Measured memory_bytes: 3448
#include<iostream>
#include<stdio.h>
#include<vector>
#include<ctype.h>
#include<string>
#include<cmath>
using namespace std;

int gcd(int x,int y){
    int larger,smaller;
    if(x>y){
        larger=x;
        smaller=y;
    }
    else{
        larger=y;
        smaller=x;
    }
    int mod,divided,divisor;
    divisor = smaller;
    divided = larger;
    while(1){
        mod = divided%divisor;
        if(mod==0)return divisor;
        divided=divisor;
        divisor=mod;
    }
    return -1;
}

int x,y;

int main(){
    cin>>x>>y;
    cout<<gcd(x,y)<<endl;
    return 0;
}



Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>

// int max: 2 x 10^9, long long max: 9 x 10^18

using namespace std;

const int MOD = 1000000007;

int main()
{
  int n,m;
  cin >> n >> m;
  vector<int> l(m), r(m);
  
  for(int i=0; i<m; i++){
    cin >> l[i] >> r[i];
  }
  
  int lowwer = *max_element(l.begin(), l.end());
  int upper = *min_element(r.begin(), r.end());
  
  int result = upper - lowwer + 1;
  if(result < 0){
    cout << 0;
  }else{
    cout << result;
  }
  
  return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
/* END OF TEMPLATE */

// return a^b mod MOD O(logB)
ll powmod(ll a, ll b){
    ll ans = 1;
    ll temp = a;
    while(b > 0){
        if(b % 2){
            ans = (ans * temp) % MOD;
        }
        temp = (temp * temp) % MOD;
        b /= 2;
    }
    return ans;
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vll a(n);
    rep(i, n){
        cin >> a[i];
    }
    sort(ALL(a));
    bool f = 1;
    if(n % 2){
        rep(i, n){
            if(a[i] != i + (i%2)){
                f = 0;
                break;
            }
        }
        if(f){
            cout << powmod(2, (n-1)/2) << endl;
        }else{
            cout << 0 << endl;
        }
    }else{
        rep(i, n){
            if(a[i] != i + ((i+1)%2)){
                f = 0;
                break;
            }
        }
        if(f){
            cout << powmod(2, n/2) << endl;
        }else{
            cout << 0 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdlib.h>

using namespace std;

class Graph{
private:

  int n;
  int **vect;

public:

  Graph(int n){
    int i;
    int j;
    this->n = n;
    vect = new int*[n];
    for(i = 0;i < n;i++){
      vect[i] = new int[n];
    }
    for(i = 0;i < n;i++){
      for(j = 0;j < n;j++){
	vect[i][j] = 0;
      }
    }
  }

  ~Graph(){
    int i;
    for(i = 0;i < n;i++){
      delete[] vect[i];
    } 
    delete[] vect;
  }

  void setVector(int i,int j){
    vect[i-1][j-1] = 1;
  }

  void printVector(){
    int i;
    int j;

    for(i = 0;i < n;i++){
      for(j = 0;j < n-1;j++){
	cout << vect[i][j] << ' ';
      }
      cout << vect[i][n-1] << endl;
    }
  }

};

int main(){

  int i;
  int j;
  int n;
  int m;
  int x;
  int y;
  Graph* graph;

  cin >> n;

  graph = new Graph(n);

  for(i = 0;i < n;i++){
    cin >> x;
    cin >> m;
    for(j = 0;j < m;j++){
      cin >> y;
      graph->setVector(x,y);
    }
  }

  graph->printVector();

  delete graph;

  return 0;
}

Measured memory_bytes: 1236
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int a,b,c;
	int x,s;
	scanf("%d %d %d",&a,&b,&c);
	x=max(a,b);
	x=max(x,c);
	s=3*x-a-b-c;
	if(s%2!=0)
		s=3*(x+1)-a-b-c;
	printf("%d\n",s/2);
	return 0;
}
/*
a,b,c
x为max
(3x-a-b-c)/2
(3*(x+1)-a-b-c)/2
*/


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();


int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (abs(a-c) <= d) {
        cout << "Yes" << endl;
    } else if (abs(a-b) <= d && abs(b-c) <= d){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}




Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int n,a;
  scanf("%d",&n);
   a=n%10;
  if(a==0||a==1||a==6||a==8) puts("pon");
  else if(a==3) puts("bon");
  else puts("hon");
  return 0; 
 }

Measured memory_bytes: 1660
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(n) for(ll i=0; i<n; i++)
#define INF LLONG_MAX/2

vector<ll> dp0(10000000); //繰り下がりなし
vector<ll> dp1(10000000); //繰り下がりなあり
ll n;

void state()
{
  for (ll i = 0; i < n; i++)
  {
    cout << dp0[i] << " ";
  }
  cout << endl;
  for (ll i = 0; i < n; i++)
  {
    cout << dp1[i] << " ";
  }
  cout << endl;  
}

int main()
{
  vector<int> v;
  string s;
  cin >> s;
  n = s.length();
  for (ll i = 0; i < n; i++)
  {
    v.push_back(s[i]-'0');
  }

  dp0[0] = 0;
  dp1[0] = 1;


  for (ll i = 0; i < n; i++)
  {
    ll cur = v[i];
  
    if(cur==0) dp0[i+1] = dp0[i] + cur;
    else dp0[i+1] = min(dp1[i]+10-cur, dp0[i]+cur);


    if(cur==9) dp1[i+1] = dp1[i]+9-cur;
    else dp1[i+1] = min(dp1[i]+9-cur, dp0[i]+cur+1);

/*
    dp0[i+1] = min(dp1[i]+10-cur, dp0[i]+cur);
    dp1[i+1] = min(dp1[i]+9-cur, dp0[i]+cur+1);
*/
  }
//  state();
  
  cout << dp0[n] << endl;
  
  return 0;
}

Measured memory_bytes: 164092
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    input!{
        h: usize,
        w: usize,
        a: [[i32; w]; h],
    }
    let mut a = a;
    let mut seq = Vec::new();
    for i in 0 .. h {
        if i % 2 == 0 {
            for j in 0 .. w {
                seq.push((i, j));
            }
        } else {
            for j in (0 .. w).rev() {
                seq.push((i, j));
            }
        }
    }
    let mut ops = Vec::new();
    for i in 0 .. seq.len() - 1 {
        let (x, y) = seq[i];
        let (z, w) = seq[i + 1];
        if a[x][y] % 2 == 1 {
            ops.push((x, y, z, w));
            a[x][y] -= 1;
            a[z][w] += 1;
        }
    }
    puts!("{}\n", ops.len());
    for (a, b, c, d) in ops {
        puts!("{} {} {} {}\n", a+1, b+1, c+1, d+1);
    }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 21100
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <tuple>
#include <stdbool.h>
#include <bitset>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;
using namespace std;


int main(void) {
    vector<int> arr(5);
    for(int i = 0 ; i < 5 ; ++i) {
        cin >> arr[i];
    }
    int k;
    cin >> k;
    // 総当たり
    for(int i = 0 ; i < arr.size() ; ++i) {
        for(int j = 0 ; j < arr.size() ; ++j) {
            int d = abs(arr[i] - arr[j]);
            if(d > k) {
                cout << ":(" << endl;
                return 0;
            }
        }
    }
    cout << "Yay!" << endl;
    return 0;
}

Measured memory_bytes: 888
X=list(input())
ans=0
cnt=0
for i in range(len(X)):
  if cnt==0:
    if X[i]=="T":
      ans+=1
    else:
      cnt+=1
  else:
    if X[i]=="T":
      cnt-=1
    else:
      cnt+=1
    
print(ans+cnt)

Measured memory_bytes: 82276
N = int(input())
*p, = map(int, input().split())

LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]

E = [(v,i+1) for i,v in enumerate(p)]
E.sort()

ans = 0
for v,i in E:
  r0 = RR[i]; r1 = RR[r0]
  l0 = LL[i]; l1 = LL[l0]
  RR[l0] = r0; LL[r0] = l0
  
  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)

Measured memory_bytes: 25604
N, M = map(int, input().split())
l = list()
for i in range(N):
    la = [int(x) for x in input().split()]
    for j in range(1, la[0] + 1):
        l.append(la[j])

ans = 0

for k in range(M + 1):
    if l.count(k) == N:
        ans += 1
print(ans)

Measured memory_bytes: 3060
//libs

#include <bits/stdc++.h>

//other stuff

using namespace std;

//function call

//main

int main(){	
	int n,g=0;
	cin >> n;
	int a=0;
	for(int i=0;i<n;i++){
		cin >> a ;
		if(a%2==1){
			g++;
		}
	}
	if(g%2==0){
		cout<<"YES"<<endl;
	}
	else{
		cout<< "NO" <<endl;
	}
	

return 0;
}

//functions



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  a=read(),b=read()
#define in3(a,b,c)  a=read(),b=read(),c=read()
#define in4(a,b,c,d)  a=read(),b=read(),c=read(),d=read()
#define inl(a)  a=readl()
#define inl2(a,b)  a=readl(),b=readl()
#define inl3(a,b,c)  a=readl(),b=readl(),c=readl()
#define inl4(a,b,c,d)  a=readl(),b=readl(),c=readl(),d=readl()
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x) memset(x,0,sizeof(x))
inline int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
inline ll readl(){
    char c;ll s=0;int t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 110000
/*------------------------------------------------------------*/
map<int,int>u;
int main(){
	int n;
	int ans=0;
	cin>>n;
	FOR(i,1,n){
		int c;
		in(c);
		if(u[c]==0)ans++;
		 else ans--;
		u[c]=1-u[c];
	}
	out(ans);
}


Measured memory_bytes: 4992
#include <stdio.h>
#include <math.h>

int main(void){
	int N,K;
	scanf("%d %d",&N,&K);
	int A[N];
	int i,ans;
	for(i=0;i<N;i++){
		scanf("%d",&A[i]);
	}
	ans = (int)(ceil((double)(N-1)/(K-1)));
	
	printf("%d",ans);
	
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP1(i,a,b) for (int i = a; i <= (int)(b); i++)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }

int ok( int a ) {
  LL lb=0,ub=a;
  while ( ub-lb>1 ) {
    LL x=(lb+ub)/2;
    if ( x*(x+1)/2>=a ) ub=x;
    else lb=x;
  }
  if ( ub*(ub+1)/2==a ) return ub;
  return 0;
}

int main() {
  int n;
  cin >> n;
  int w=ok(n);
  if ( !w ) {
    cout << "No" << '\n';
    return 0;
  }
  cout << "Yes" << '\n';
  int h = n * 2 / w;
  cout << h << '\n';
  vector<VI> ans(h, VI(w));
  int k=1;
  for ( int i=0; i<h; i++ ) {
    for ( int j=i; j<w; j++ ) {
      ans[i][j]=k++;
    }
  }
  k=1;
  for (int j = 0; j<w; j++ ) {
    for (int i=j+1; i < h; i++) {
      ans[i][j]=k++;
    }
  }
  for ( int i=0; i<h; i++ ) {
    cout << w;
    for ( int j=0; j<w; j++ ) {
      cout << ' ' << ans[i][j];
    }
    cout << '\n';
  }
  return 0;
}



Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;

#define fi                      first
#define se                      second
#define pb                      push_back
#define endl                    '\n'
#define all(x)                  x.begin(),x.end()
#define pii                     pair<int,int>
#define fast                    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define SZ(x)                   ((int)x.size())

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

void solve();

int32_t main()
{
        fast;
        int t = 1;
        // cin >> t;
        for(int i = 1; i <= t; ++i)
                solve();
        cerr << "Time taken: " << ((clock() * 1000) / CLOCKS_PER_SEC) << "ms\n";
}

void solve() {
	ll a,b;
	cin >> a >> b;
	ll out = a*b;
	ll temp = __gcd(a,b);
	out = out/temp;
	cout << out << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  int n,x,t;
  cin>>n>>x>>t;
  if(n%x==0)
  {
    cout<<n/x*t<<endl;
  }
  else cout<<(n/x+1)*t<<endl;
}

Measured memory_bytes: 3592
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    P = Scanner.map_int()
    Q = Scanner.map_int()
    A = [i for i in range(1, N+1)]
    p, q = 0, 0
    for i, v in enumerate(itertools.permutations(A, N)):
        if list(v) == P:
            p = i
        if list(v) == Q:
            q = i
    print(abs(q-p))
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 41964
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;
#define ll long long
#define INF (int)(1e9+5)
#define MOD (int)(1e9 + 7) 
#define pi 3.14159265

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<int> red(a), green(b), col(c);
    for(int &i : red) cin >> i;
    for(int &i : green) cin >> i;
    for(int &i : col) cin >> i;
    sort(red.begin(), red.end(), greater<int>());
    sort(green.begin(), green.end(), greater<int>());
    for(int i = 0; i < x; ++i) col.push_back(red[i]);
    for(int i = 0; i < y; ++i) col.push_back(green[i]);
    sort(col.begin(), col.end(), greater<int>());
    ll ans = 0;
    for(int i = 0; i < x+y; ++i) ans += col[i];
    cout << ans << '\n';
    return 0;
}



Measured memory_bytes: 5568
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

trait InputValue {
    fn parse(s: &str) -> Self;
}

fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn powmod(a: i64, p: i64, m: i64) -> i64 {
    let mut ret = 1i64;
    let mut aa = a;
    let mut pp = p;
    while pp >= 1 {
        if pp & 1 == 1 {
            ret *= aa;
            ret %= m;
        }
        aa = aa * aa % m;
        pp >>= 1;
    }
    ret
}

fn inv(a: i64, m: i64) -> i64 {
    powmod(a, m-2, m)
}

struct Combination {
    fact: Vec<i64>,
    invfact: Vec<i64>,
    modulo: i64
}

impl Combination {
    fn new(n: usize, modulo: i64) -> Self {
        let mut fact: Vec<i64> = vec![0; n];
        let mut invfact: Vec<i64> = vec![0; n];
        fact[0] = 1;
        for i in 1..n {
            fact[i] = fact[i-1] * i as i64 % modulo;
        }
        invfact[n-1] = inv(fact[n-1], modulo);
        for i in (0..n-1).rev() {
            invfact[i] = (invfact[i+1] * (i+1) as i64) % modulo;
        }

        Combination { fact: fact, invfact: invfact, modulo: modulo }
    }

    fn combination(&self, n: usize, k: usize) -> i64 {
        if n < k {
            return 0;
        }
        self.fact[n] * self.invfact[n-k] % self.modulo * self.invfact[k] % self.modulo
    }
}

const MOD: i64 = 1e9 as i64 + 7;

fn main() {
    let mut n: usize = read();
    let a: Vec<usize> = readnc();
    n += 1;

    let mut z = vec![-1; n+1];
    let mut fr = 0;
    let mut to = 0;
    for i in 0..n {
        if z[a[i]] != -1 {
            fr = z[a[i]] as usize;
            to = i;
        } else {
            z[a[i]] = i as i32;
        }
    }

    let comb = Combination::new(n+100, MOD);
    let outer = fr + n - 1 - to;
    for c in 1..n+1 {
        let mut sum = 0;
        // 1: zero
        sum += comb.combination(n-2, c);

        // 1: one
        sum += comb.combination(n-2, c-1) * 2;
        sum += MOD - comb.combination(outer, c-1);

        if c >= 2 {
            sum += comb.combination(n-2, c-2);
        }

        println!("{}", sum % MOD);
    }
}

Measured memory_bytes: 9084
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

       




        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);


            var n = Read();
            var s = Console.ReadLine();
            long max = 0;
            long count = 0;
            for (int i = 0; i < n; i++)
            {
                if (s[i] == 'I') count++;
                else count--;
                max = Math.Max(count, max);
            }
            Console.WriteLine(max);



            Console.Out.Flush();
        }
    }
}




Measured memory_bytes: 13140
import math as m
a, b, x = map(int, input().split())
h = 2*(b - x/(a**2))
if h < b:
    print(m.degrees(m.atan(h/a)))
else:
    w = 2*x/(a*b)
    print(90 - m.degrees(m.atan(w/b)))


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	vector<int> b(n);
	for(int i = 0; i < n; ++i)
		cin >> b[i];
	vector<int> v;
	for(int i = 1; i <= n; ++i)
		v.push_back(i);
	vector<int> ans;
	int cnt = 1;
	do {
		if(v == a)
			ans.push_back(cnt);
		if(v == b)
			ans.push_back(cnt);
		++cnt;
	} while(next_permutation(v.begin(), v.end()));
	cout << abs(ans[1] - ans[0]);
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using ll=long long;

int main(){
    ll n,m,r;
    cin>>n>>m>>r;
    vector<ll> vis(r);
    for(int i=0;i<r;i++){
        cin>>vis[i];
        vis[i]--;
    }
    sort(vis.begin(),vis.end());
    vector<vector<ll>> dat(n,vector<ll>(n,1e9));
    rep(i,m){
        ll a,b,c;
        cin>>a>>b>>c;a--;b--;
        if(dat[a][b]==1e9){
            dat[a][b]=dat[b][a]=c;
        }
        else{
            dat[a][b]=dat[b][a]=min(dat[a][b],c);
        }
    }
    rep(k,n){
        rep(i,n){
            rep(j,n){
                dat[i][j]=min(dat[i][j],dat[i][k]+dat[k][j]);
            }
        }
    }
    ll ans=INT_MAX;
    do{
        ll sum=0;
        rep(i,r-1){
            sum+=dat[vis[i]][vis[i+1]];
        }
        ans=min(ans,sum);
    }while(next_permutation(vis.begin(),vis.end()));
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3892
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    string S, T;
    cin >> S >> T;
 
    //答えansを仮置きする。
    //これが十分に大きくないと不正解となるので、
    //この値なら絶対に正しい答えが出る、という値を仮置きすること
    int ans = T.size();
 
    //Sの何文字目から調べるかを全探索する
    for (int start = 0; start <= S.size() - T.size(); start++)
    {
        int diff = 0;
        for (int i = 0; i < T.size(); i++)
        {
            if (T[i] != S[start + i]) {
                diff++;
            }
        }
        ans = min(ans, diff);
    }
 
    cout << ans << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1000010;
const int M = 1000;
const ll INFLL = 1e15+1;
int _w;

int n, m, k;
ll a[N], b[N];

double sum( ll x ) {
	int y = 0;
	ll t = x;
	while(x) y += x % 10, x /= 10;
	return 1.0*t/y;
}

void solve() {
	for( int i = 1; i < M; ++i ) {
		ll x = i;
		while( x < INFLL ) {
			a[n++] = x;
			x = x * 10 + 9;
		}
	}
	sort(a, a+n);
	n = unique(a, a+n) - a;
	for( int i = 0; i < n; ++i ) {
		bool flag = true;
		for( int j = i+1; j < n; ++j )
			if( sum(a[j]) < sum(a[i]) ) {
				flag = false;
				break;
			}
		if( flag ) b[m++] = a[i];
	}
}

int main() {
	_w = scanf( "%d", &k );
	solve();
	for( int i = 0; i < k; ++i )
		printf( "%lld\n", b[i] );
	return 0;
}


Measured memory_bytes: 2304
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    if (args.length > 0 && args(0) == "TEST") {
      println(test())
    } else {
      val input = io.Source.stdin.getLines().mkString("\n")
      println(solve(input).trim())
    }
  }

  def solve(input: String): String = {
    val s: Scanner = new Scanner(input)
    val m = s.next
    if (m.toCharArray.count(_ == 'x') >= 8) "NO" else "YES"
  }

  val tests = List(
    """oxoxoxoxoxoxox""".stripMargin -> """YES""",
    """xxxxxxxx""".stripMargin -> """NO"""
  )

  def test(): String = tests.map { case (i, o) => (i.trim(), o.trim()) }
    .zipWithIndex.map {
    case ((input, outputExpect), i) =>
      val output = solve(input).trim()
      val tnum = i + 1
      s"test$tnum:" + (
        if (output == outputExpect) "Passed"
        else s"Failed\nexpect:\n$outputExpect\noutput:\n$output")
  }
    .mkString("\n")
}

Measured memory_bytes: 25936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll a, ll b) {
    if (a > b) swap(a, b);
    if (b % a == 0) {
        return (b/a)*a*2-a;
    }
    return (b/a)*a*2+f(b%a, a);
}
int main () {
    ll N, X;
    cin >> N >> X;
    cout << N+f(X, N-X) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

const int M = 1e7 + 5;

int sz, p[M];

void sieve() {
    p[0] = p[1] = 1;
    for (int i = 2 * 2; i < M; i += 2)
        p[i] = 1;
    for (int i = 3; i * i < M; i += 2) if (!p[i]) {
        for (int k = i * i; k < M; k += i)
        p[k] = 1;
    }
    p[sz++] = 2;
    for (int i = 3; i < M; i += 2) {
        if (!p[i]) p[sz++] = i;
    }
}

int main() {
    sieve();
    int n;
    cin >> n;
    for (int i = 0; i < sz; i++) {
        if (p[i] >= n) {
            cout << p[i] << '\n';
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 39296
#include<bits/stdc++.h>
using namespace std;
int d,k;
int main()
{
    while(cin>>d>>k)
    {
        int sum=1;
        for(int i=0;i<d;i++)
            sum*=100;
        if(k==100)
            k+=1;
        cout<<k*sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=(n);i<(int)N;i++)
#define p(s) cout<<(s)<<endl
#define ck(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf=1e9;

ll d[100010];//dist
ll fromS[100010];
ll fromT[100010];
vector<ll> edge[100100];
int main() {
	ll N,M,s,t;
	cin>>N>>M>>s>>t;
	s--;t--;
	REP(i,0,M){
		ll x,y;
		cin>>x>>y;
		x--;y--;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	queue<ll> q,qq;
	fromS[0]=1;fromT[0]=1;
	q.push(s);
	REP(i,0,N) d[i]=inf;
	d[s]=0;
	while(!q.empty()){
		int now=q.front();q.pop();
		for(int next:edge[now]){
			if(d[next]<inf) continue;
			q.push(next);
			d[next]=d[now]+1;
			fromS[d[next]]++;
		}
		if(d[t]<inf) break;
	}

	REP(i,0,N) d[i]=inf;
	qq.push(t);
	d[t]=0;
	while(!qq.empty()){
		int now=qq.front();qq.pop();
		for(auto next:edge[now]){
			if(d[next]<inf) continue;
			qq.push(next);
			d[next]=d[now]+1;
			fromT[d[next]]++;
		}
		if(d[s]<inf) break;
	}
	ll ans=0;
	REP(i,0,d[s]-1){
		ans+=fromS[i]*fromT[d[s]-2-i];
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 11524
#include <bits/stdc++.h>
using namespace std;

int main() {
  string name[3] = {};
  string result;

  for (int i = 0; i < 3; i++) {
	cin >> name[i];
	if (i == 1) {
		if (!(name[i].size() >= 1) || !(name[i].size() <= 100)) {
			break;
		}
		if(!isupper(name[i].at(0))) {
			break;
		}
		for (int j = 1; j < name[i].size(); j++) {
			if (!islower(name[i].at(j))) {
				break;
			}
		}
	}
	result = result + name[i].at(0);
  }
  cout << result << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int uruu(int year) {
    if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)return 1;
    return 0;
}

int main(void) {
    int a,b;
    int cnt=0;
    while(1) {
        scanf("%d %d",&a,&b);
        if(a == 0 && b == 0)break;
        if(cnt)puts("");
        cnt = 0;
        for(;a <= b;a++) {
            if(uruu(a)) {
                printf("%d\n",a);
                cnt = 1;
            }
        }
        if(cnt == 0){
            printf("NA\n");
        }
        cnt = 1;
    }
    return 0;
}

Measured memory_bytes: 612