akhauriyash/Code-Regression huggingface dataset:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 1005
char S[N];
int A[N][N];
int h, w, l1, l2, cnt, tot;
int Pow(int a, ll k)
{
	int ret = 1;
	while (k)
	{
		if (k & 1)
			ret = (ll)ret * a % mod;
		a = (ll)a * a % mod;
		k >>= 1;
	}
	return ret;
}
struct Matrix
{
	int X[2][2];
	Matrix(){memset(X, 0, sizeof(X));}
	void Init()
	{
		memset(X, 0, sizeof(X));
		for (int i = 0; i < 2; i++)
			X[i][i] = 1;
	}
}W;
void Add(int &a, int b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}
void Mul(Matrix &A, Matrix &B)
{
	Matrix C;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				Add(C.X[i][j], (ll)A.X[i][k] * B.X[k][j] % mod);
	A = C;
}
void Pow(Matrix &A, ll k)
{
	Matrix ret;
	ret.Init();
	while (k)
	{
		if (k & 1)
			Mul(ret, A);
		Mul(A, A);
		k >>= 1;
	}
	A = ret;
}
int n, m;
ll k;
int main()
{
	scanf("%d%d%lld", &n, &m, &k);
	if (k <= 1)
	{
		puts("1");
		return 0;
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%s", S + 1);
		for (int j = 1; j <= m; j++)
		{
			A[i][j] = (S[j] == '#');
			if (A[i][j])
				cnt++;
		}
	}
	for (int i = 1; i <= m; i++)
		if (A[1][i] && A[n][i])
			l1++;
	for (int i = 1; i <= n;i++)
		if (A[i][1] && A[i][m])
			l2++;
	if (!l1 && !l2)
	{
		printf("%d\n", Pow(cnt, k - 1));
		return 0;
	}
	if (l1 && l2)
	{
		puts("1");
		return 0;
	}
	if (l1)
	{
		for (int i = 1; i < n; i++)
			for (int j = 1; j <= m; j++)
				if (A[i][j] && A[i + 1][j])
					tot++;
	}
	else
	{
		for (int i = 1; i <= n; i++)
			for (int j = 1; j < m; j++)
				if (A[i][j] && A[i][j + 1])
					tot++;
	}
	W.X[0][0] = cnt;
	W.X[0][1] = tot;
	W.X[1][1] = l1 + l2;
	Pow(W, k - 2);
	int ans = ((ll)W.X[0][0] * tot % mod + (ll)W.X[0][1] * (l1 + l2) % mod) % mod;
	ans = (Pow(cnt, k - 1) - ans) % mod;
	if (ans < 0)ans += mod;
	printf("%d\n", ans);
}
//

Measured memory_bytes: 7680
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1ll, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }

#include<atcoder/fenwicktree.hpp>
using namespace std;
using namespace atcoder;
int main() {
	int n, q;
	cin >> n >> q;
	fenwick_tree<ll> fw(n);
	rep(i, 0, n) {
		int a;
		cin >> a;
		fw.add(i, a);
	}
	rep(i, 0, q) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 0)fw.add(a, b);
		else printf("%lld\n", fw.sum(a, b));
	}
	return 0;
}

Measured memory_bytes: 8204
#include <stdio.h>
int main(void)
{
	int a, b;
	
	scanf("%d", &a);
	scanf("%d", &b);
	
	if (a <= 8){
		if (b <= 8){
			printf("Yay!\n");
		}
		else {
			printf(":(\n");
		}
	}
	
	else {
		printf(":(\n");
	}
	
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define pf push_front
#define PI acos(-1)
#define EPS 1e-5
#define sz(v) ((int)(v).size())
#define all(v) v.begin(),v.end()
#define forn(i, n) for(ll i=0;i<(ll)n;i++)
#define fi first
#define se second
 

int main() {
	int n;
	cin >> n;
	string s, t, r;
	cin >> s >> t;
	forn(i, n) {
		r += s[i];
		r += t[i];
	}
	cout << r << endl;
	return 0;
}



Measured memory_bytes: 3588
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);		

		List<Integer> a = new ArrayList<Integer>(); 
		List<Integer> b = new ArrayList<Integer>(); 
		List<Character> op = new ArrayList<Character>();
		
		while (true) {
			int _a = scan.nextInt();
			char _op = scan.next().charAt(0);
			int _b = scan.nextInt();

			if (_op == '?')
				break;
			
			a.add(_a);
			b.add(_b);
			op.add(_op);
		}

		for (int i = 0; i < a.size(); i++) {
			int _a = a.get(i);
			int _b = b.get(i);
			int _op = op.get(i);
			
			switch(_op) {
				case '+':
					System.out.println(_a + _b);
					break;
				case '-':
					System.out.println(_a - _b);
					break;
				case '*':
					System.out.println(_a * _b);
					break;
				case '/':
					System.out.println(_a / _b);
			}
		}
		
		scan.close();
	}
}

Measured memory_bytes: 18112
n = int(input())

ls = [list(map(int,input().split())) for _ in range(n)]

sum = 0
for i in range(n-1):
  for j in range(i+1,n):
    sum += ((ls[i][0]-ls[j][0])**2+(ls[i][1]-ls[j][1])**2)**0.5
    
print(sum*2/n)

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 0;
        N = scanner.nextInt();
        int[] val= new int[N];
       for(int x=0; x<N; x++)val[x]=scanner.nextInt();
        Arrays.sort(val);
        System.out.println(val[N-1]-val[0]);
    }

}


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

int main(){
	int d,n;
	cin >> d >> n;
	if (d==0 && n == 100) {cout << 101; return 0;}
	if (d==1 && n == 100) {cout << 10100; return 0;}
	if (d==2 && n == 100) {cout << 1010000; return 0;}
	cout << pow(10,d*2) *n;
	
		
 }


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

using namespace std;

const int MAX_N = 1010;

int n, xi[MAX_N], yi[MAX_N], parity, m, segs[MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &xi[i], &yi[i]);
    parity = (xi[1] + yi[1]) & 1;
    for (int i = 2; i <= n; i++)
        if (((xi[i] + yi[i]) & 1) != parity)
            puts("-1"), exit(0);
    if (parity == 0)
        segs[++m] = 1;
    for (int i = 30; i >= 0; i--)
        segs[++m] = (1 << i);
    printf("%d\n", m);
    for (int i = 1; i <= m; i++)
        printf("%d ", segs[i]);
    puts("");
    for (int i = 1; i <= n; i++, puts(""))
        for (int j = 1; j <= m; j++)
            if (abs(xi[i]) > abs(yi[i]))
                if (xi[i] > 0)
                    xi[i] -= segs[j], putchar('R');
                else
                    xi[i] += segs[j], putchar('L');
            else if (yi[i] > 0)
                yi[i] -= segs[j], putchar('U');
            else
                yi[i] += segs[j], putchar('D');
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
int main(void){
    ll n,t;
    cin>>n>>t;
    ll a[100000];
    for(int i=0;i<n;i++) cin>>a[i];
    ll nowMIN=a[0];
    map<ll,ll> m;
    for(int i=1;i<n;i++){
        if(a[i]<a[i-1]){
            m[a[i-1]-nowMIN]++;
            nowMIN=min(nowMIN,a[i]);
        }
        else if(i==n-1) m[a[i]-nowMIN]++;
    }
    ll MAX=-1;
    for(auto itr=m.begin();itr!=m.end();itr++){
        MAX=max(MAX,itr->first);
    }
    cout<<m[MAX]<<endl;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
typedef long long ll;
#define endl "\n"
#define all(s) s.begin(),s.end()
#define pb push_back
#define uno unordered_map
#define pi 3.1415926536
#define dig(a) fixed<<setprecision(a)
#define test(zz) int zz; cin>>zz; while(zz--)
#define foreach(var,i) for(auto i = var.begin();i!=var.end();i++)
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
ll power(ll a, ll n) {ll res = 1; while (n) {if (n % 2) {res *= a;} n >>= 1; a *= a;} return res;}
ll powerm(ll a, ll n, ll m) {ll res = 1; while (n) {if (n % 2) {res = (res * a) % m;} n >>= 1; a = (a * a) % m;} return res;}
using namespace std;

const int M=1e9+7;
ll mod(ll x){
      return ((x%M + M)%M);
}
ll add(ll a, ll b){
      return mod(mod(a)+mod(b));
}
ll mul(ll a, ll b){
      return mod(mod(a)*mod(b));
}

int main(){
	fast();
	
	//test(t){}
	
	int n;
	cin>>n;
	vector<ll> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	vector<ll> suff(n+1,0);
	for(int i=n-1;i>=0;i--){
		suff[i] = a[i]+suff[i+1];
	}
	ll sum = 0;
	for(int i=0;i<n;i++){
		sum = add(sum,mul(a[i],suff[i+1]));
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 6364
n = int(input())
H = list(map(int, input().split()))

H[0] -= 1
for i in range(1, n):
    if H[i-1] < H[i]:
        H[i] -= 1

if all(H[i-1] <= H[i] for i in range(1, n)):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
 
int main() {

    int N;
    cin >> N;
    vector<char>S(N);
    vector<long long>count(5,0);
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        S.at(i) = s.at(0);
        if (S.at(i) == 'M'){
            count.at(0)++;
        }
        else if (S.at(i) == 'A'){
            count.at(1)++;
        }
        else if (S.at(i) == 'R'){
            count.at(2)++;
        }
        else if (S.at(i) == 'C'){
            count.at(3)++;
        }
        else if (S.at(i) == 'H'){
            count.at(4)++;
        }
    }

    long long sum = 0;

    for (int i = 0; i < 3; i++) {
        for (int j = i+1; j < 4; j++) {
            for (int k = j+1; k < 5; k++) {
                sum += count.at(i) * count.at(j) * count.at(k);
            }
        }
    }

    cout << sum << endl;
}

Measured memory_bytes: 3672
import java.util.Scanner;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long K = sc.nextLong();
        long[] ans = new long[100000];
        Arrays.fill(ans, 0);
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            long b = sc.nextLong();
            a--;
            ans[a] += b;
        }
        for (int i = 0; i < 100000; i++) {
            K = K - ans[i];
            if (K <= 0) {
                System.out.println(i + 1);
                return;
            }

        }
    }

}

Measured memory_bytes: 64692
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int n,k,a[SZ],b[SZ],pn=0,pl[SZ],pr[SZ],pg[SZ];
#define SS 5555555
const int inf=1e9;
int mi[SS],ch[SS][2],an=0,ro;
void edt(int& x,int l,int r,int ql,int qr,int v)
{
	if(qr<l||r<ql) return;
	if(!x) x=++an,mi[x]=inf;
	if(ql<=l&&r<=qr)
	{mi[x]=min(mi[x],v); return;}
	int m=(l+r)>>1;
	edt(ch[x][0],l,m,ql,qr,v);
	edt(ch[x][1],m+1,r,ql,qr,v);
}
int qmin(int x,int l,int r,int v)
{
	if(!x) return inf;
	int p=mi[x];
	if(l==r) return p;
	int m=(l+r)>>1;
	if(v<=m) p=min(p,qmin(ch[x][0],l,m,v));
	else p=min(p,qmin(ch[x][1],m+1,r,v));
	return p;
}
ll f[SZ];
int main()
{
	scanf("%d%d",&n,&k);
	int su=0;
	edt(ro,0,k-1,0,k-1,n);
	for(int i=0;i<n;++i)
	{
		scanf("%d%d",a+i,b+i);
		if(a[i]==1) b[i]=2;
		if(b[i]==1&&a[i]*2>k)
		{
			puts("-1");
			return 0;
		}
		pr[i]=(su+k-1)%k;
		(su-=a[i]*2)%=k;
		if(su<0) su+=k;
		pl[i]=(su+1)%k;
		pg[i]=(pr[i]+1)%k;
	}
	for(int i=n-1;i>=0;--i) if(b[i]==1)
	{
		int g=qmin(ro,0,k-1,pg[i]);
		if(g==n) f[i]=0;
		else f[i]=f[g]+(pg[g]-pg[i]+k)%k;
		if(pl[i]<=pr[i]) edt(ro,0,k-1,pl[i],pr[i],i);
		else edt(ro,0,k-1,0,pr[i],i),edt(ro,0,k-1,pl[i],k-1,i);
	}
	ll ans=1e18;
	for(int i=0;i<n;++i)
	{
		int g=qmin(ro,0,k-1,pg[i]);
		if(g==n) ans=0;
		else ans=min(ans,f[g]+(pg[g]-pg[i]+k)%k);
	}
	for(int i=0;i<n;++i) ans+=a[i]*2LL;
	printf("%lld\n",ans);
}


Measured memory_bytes: 48128
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    int a[3];
    while(cin >> a[0] >> a[1] >> a[2])
    {
        sort(a,a + 3);
        if(a[0] + a[1] == a[2])
        cout << "Yes" << endl;
        else
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def placingMarbles(input_str):
    vals = input_str.split(" ")
    A = int(vals[0])
    B = int(vals[1])
    if A >= 13:
        return int(B)
    elif 6 <= A and A<=12:
        return int(B / 2)
    else:
        return 0

if __name__ == "__main__":
    print(placingMarbles(input()))


Measured memory_bytes: 2940
from itertools import permutations
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
i = a = b = 0
for x in permutations(range(1, N+1), N):
  i += 1
  if x == P:
    a = i
  if x == Q:
    b = i
print(abs(a - b))

Measured memory_bytes: 39024
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;
const int MOD = 1000000007;

ll f(ll x){
    if (x == 1) return 1;
    return f(x/2)*2 + 1;
}

int main(){
    ll H; cin >> H;
    cout << f(H) << endl;
}


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

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define rer(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int inf = 1000000000;
const int mod = 1000000007;
const double eps = 1e-9;
const int dx[] = { -1, 0, 1, 0};
const int dy[] = { 0, -1, 0, 1};

int main() {
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.size(), m = s2.size();
	vector<vi> dp(n + 1, vi(m + 1, inf));
	dp[0][0] = 0;
	rep(i, n + 1) rep(j, m + 1) {
		int x = dp[i][j];
		if (i + 1 <= n) dp[i + 1][j] = min(dp[i + 1][j], x + 1);
		if (j + 1 <= m) dp[i][j + 1] = min(dp[i][j + 1], x + 1);
		if (i + 1 <= n && j + 1 <= m) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], x + (s1[i] != s2[j]));
	}
	int ans = dp[n][m];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4964
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod

#include <bits/stdc++.h>
using namespace std;

signed main(){
    int N,M; cin>>N>>M;
    vec X(M); REP(i,M) cin>>X[i];
    Sort(X);
    vec D(M-1);
    REP(i,M-1) D[i] = X[i+1]-X[i];
    Sort(D);
    int ans = 0;
    REP(i,M-N) ans += D[i];
    Out(ans);
}
  


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

int main ()
{
    string  s ;
    cin >> s;
    vector <int> c(2019, 0) ; 
    int  ss=0,ans=0,cur=1;
    c[0] = 1 ; 
    for (int i=s.size()-1;i>=0;i--){
        ss = (ss+(s[i]-'0')*cur)%2019;
        ans += c[ss] ; 
        c[ss]++ ; 
        cur = (cur*10)%2019; 
    }
    cout << ans << endl ; 
    return 0;
}


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

using namespace std;

int a[200000];
string s;

void Process()
{
    int n = s.length(), cou = -1;

    for (int i=0; i<=n-1; i++)
        if (s[i] == 'R') cou++;
            else if (cou != -1)
            {
                if (cou % 2 == 1)
                {
                    a[i] += (cou+1)/2;     a[i-1] += (cou+1)/2;
                }
                    else
                    {
                        a[i-1] += cou/2 + 1;     a[i] += cou/2;
                    }

                cou = -1;
            }

//    for (int i=0; i<=n-1; i++)
//        cout << a[i] << " ";
//    cout << endl;

    for (int i=n-1; i>=0; i--)
        if (s[i] == 'L') cou++;
            else if (cou != -1)
            {
                if (cou % 2 == 1)
                {
                    a[i] += (cou+1)/2;     a[i+1] += (cou+1)/2;
                }
                    else
                    {
                        a[i+1] += cou/2 + 1;     a[i] += cou/2;
                    }

                cou = -1;
            }

    for (int i=0; i<=n-1; i++)
        cout << a[i] << " ";
}

void Input()
{
    ios_base::sync_with_stdio(0);   cin.tie(0);

    cin >> s;
}

int main()
{
    Input();
    Process();
    return 0;
}


Measured memory_bytes: 1104
#include<stdio.h>
int main(void){
 int N,D,see,ans=1;
  scanf("%d %d",&N,&D);
  see=2*D+1;
  N=N-see;
  while(N>0){
    ans++;
    N=N-see;
  }
  printf("%d",ans);
  return 0;
}
  

Measured memory_bytes: 128
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
struct UnionFind
{
    vector<int> par,num; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N),num(N,1)
    { //最初は全てが根であるとして初期化
        for (int i = 0; i < N; i++)
            par[i] = i;
    }

    int root(int x)
    { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {                     // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry)
            return;   //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        num[ry]+=num[rx];
    }

    bool same(int x, int y)
    { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k,l;
    cin>>n>>k>>l;
    UnionFind tree(n);
    rep(i,k){
        ll x,y;
        cin>>x>>y;
        x--;y--;
        tree.unite(x,y);
    }
    UnionFind tree2(n);
    rep(i,l){
        ll x,y;
        cin>>x>>y;
        x--;y--;
        tree2.unite(x,y);
    }
    map<P,ll> mp;
    rep(i,n){
        mp[{tree.root(i),tree2.root(i)}]++;
    }
    rep(i,n){
        cout<<mp[{tree.root(i),tree2.root(i)}]<<" ";
    }
    cout<<endl;
}


Measured memory_bytes: 15104
#include<iostream>
#include<algorithm>
using namespace std;
int h,w;
string s[50];
main()
{
	int t;cin>>t;
	while(t--)
	{
		cin>>h>>w;
		for(int i=0;i<h;i++)cin>>s[i];
		bool flag=1;
		while(flag)
		{
			flag=0;
			for(char c='A';c<='Z';c++)
			{
				int sx=h,sy=w,gx=0,gy=0;
				for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(s[i][j]==c)
				{
					sx=min(sx,i);
					sy=min(sy,j);
					gx=max(gx,i);
					gy=max(gy,j);
				}
				bool f=sx<=gx&&sy<=gy;
				for(int i=sx;f&&i<=gx;i++)for(int j=sy;f&&j<=gy;j++)
				{
					if(!(s[i][j]==c||s[i][j]=='?'))f=false;
				}
				if(f)
				{
					flag=true;
					for(int i=sx;i<=gx;i++)for(int j=sy;j<=gy;j++)s[i][j]='?';
				}
			}
		}
		bool ans=true;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)
		{
			if(s[i][j]!='.'&&s[i][j]!='?')ans=false;
		}
		cout<<(ans?"SAFE":"SUSPICIOUS")<<endl;
	}
}



Measured memory_bytes: 3120
def GCD(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    else:
        return GCD(b, a % b)


def LCM(a, b):
    return a * b // GCD(a, b)

n = int(input())
ans = int(input())
for i in range(n-1):
    ans = LCM(ans, int(input()))

print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main(void){
	int N;
	cin >> N;
	vector<int> P(N, 0);
	int max = 0;
	int index = 0;
	for(int cnt = 0; cnt < N; cnt++){
		cin >> P[cnt];
		if(P[cnt] > max){
			max = P[cnt];
			index = cnt;
		}
	}
	long long sum = 0;
	for(int cnt = 0; cnt < N; cnt++){
		if(cnt == index){
			sum += P[cnt]/2;
		}else{
			sum += P[cnt];
		}
	}
	cout << sum << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF 10000000000
#define PI 3.141592653589793

int main() {
	int n, ans, front = 0, loop = 0;
	long long k;
	cin >> n >> k;
	vector<int> a(n);
	vector<int> rec(0);
	vector<bool> table(n, false);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}

	rec.push_back(a[0]);
	table[a[0]] = true;
	for (int i = 1; i < n+1; i++) {
		if (!table[a[rec[i-1]]]) {
			rec.push_back(a[rec[i-1]]);
			table[a[rec[i-1]]] = true;
		} else {
			for (int j = 0; j < rec.size(); j++) {
				if (rec[j] != a[rec[i-1]]) {
					front++;
				} else {
					loop = rec.size() - front;
					break;
				}
			}
			break;
		}
	}

	if (k > front) {
		k = (k - front) % loop;
		if (k == 0) k = loop;
		k += front;
	}
	ans = rec[k - 1] + 1;

	cout << ans;
	return 0;
}

Measured memory_bytes: 5064
#include <iostream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N; cin.ignore();

  string str;
  getline(cin, str);
  stringstream ss(str);
  vector<int> a_vec;
  for (int i; !ss.eof();){
    ss >> i;
    a_vec.push_back(i);
  }

  int ans = 0;
  for (size_t index=0; index<N; index++) {
    if (a_vec[index] == index+1 && index == N-1) {
      ans++;
    } else if (a_vec[index] == index+1) {
      swap(a_vec[index], a_vec[index+1]);
      ans++;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2332
n = int(input())
a = list(map(int, input().split()))
dic = {}
ans = {}
for item in a:
    if item in dic.keys():
        dic[item] += 1
    else:
        dic[item] = 1

all_ans = sum([item * (item - 1) // 2 for item in dic.values()])

for i in range(n):
    print(all_ans - dic[a[i]] + 1)


Measured memory_bytes: 26268
using System;

public class Program {

        public static void Main(string[] args) {

            const string STR = "abcdefghijklmnopqrstuvwxyz";

            var c = Console.ReadLine();

            var index = STR.IndexOf(c);

            Console.WriteLine(STR.Substring(index + 1, 1));


        }

    }

Measured memory_bytes: 11348
x = list(map(int, input().split()))
ans = 0
for i in x:
    if i == 1:
        ans += 300000
    elif i == 2:
        ans += 200000
    elif i == 3:
        ans += 100000

if ans == 600000:
    print(1000000)
else:
    print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int N, M, R;
int d[201][201];
int r[10];
int A, B, C;
int res;
bool used[10];
void dfs(int c, int las, int dist) {
	if (c == R) {
		if (res > dist)res = dist;
		return;
	}
	for (int i = 0; i < R; ++i) {
		if (!used[i]) {
			used[i] = true;
			if (las == -1) {
				dfs(c + 1, i, 0);
			}
			else {
				dfs(c + 1, i, dist + d[r[las]][r[i]]);
			}
			used[i] = false;
		}
	}
}
int main() {
	cin >> N >> M >> R;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i != j)d[i][j] = INF;
			else d[i][j] = 0;
		}
	}
	for (int i = 0; i < R; ++i) {
		cin >> r[i];
		r[i]--;
	}
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
	    d[a][b] = c;
		d[b][a] = c;
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < N; ++k) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
	res = INF;
	dfs(0, -1, 0);
	cout << res << endl;
	return 0;

}

Measured memory_bytes: 384
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static AtCoderTemplate.MyLibrary;

namespace AtCoderTemplate
{
    class Program
    {
        static void Main (string[] args)
        {
            string str = Console.ReadLine ();

            while (str.Length > 0)
            {

                int l = str.Length;

                if (str.Substring (l - 5, 5) == "dream") str = str.Remove (l - 5, 5);
                else if (l >= 7 && str.Substring (l - 7, 7) == "dreamer") str = str.Remove (l - 7, 7);
                else if (str.Substring (l - 5, 5) == "erase") { str = str.Remove (l - 5, 5); }
                else if (l >= 6 && str.Substring (l - 6, 6) == "eraser") str = str.Remove (l - 6, 6);
                else
                {
                    Console.WriteLine ("NO");
                    return;
                }
            }

            Console.WriteLine ("YES");
        }
    }

    class MyLibrary
    {

        // 自作の関数
        public static int MyFunction (int n)
        {
            return 0;
        }
    }
}

Measured memory_bytes: 29600
from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 182764
#include<bits/stdc++.h>
using namespace std;
char a[1000000];
long long ans=0;
void ck(int s)
{
	if(a[s+1]=='W')ans++;
}
void ckk(int s)
{
	if(a[s+1]=='B')ans++;
}
int main()
{
	gets(a);
	int len=strlen(a);
	for(int i=0;i<len;i++)
	{
		if(a[i]=='B')ck(i);
		else if(a[i]=='W')ckk(i);
	}
	cout<<ans;
	return 0;
} 

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,a,t;
	vector<int>x(100);

	cin >>n;
	for(int i=0;i<n;i++){
		cin >> x[i];
	}
	int mx =99999999;
	for(int i=0;i<=100;i++){
		t=0;
		for(int j=0;j<n;j++){
			a= abs(i-x[j]);
			t+=pow((double)a,2);
		}
		mx=min(t,mx);
	}
	cout << mx<< endl;
	return 0;
}


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

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

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string S, T; cin >> S >> T;
    T.pop_back();
    if(S == T) cout << "Yes" << endl;
    else cout << "No" << endl;    

    return 0;
}



Measured memory_bytes: 3580
#include <iostream>
using namespace std;
int main(){
    int a,b;
    
    int k;
    cin>>k;
    cin>>a>>b;
    int c=0;
    c=b/k;
    int d=0;
    d=c*k;
    if(a<=d&&d<=b){
        cout<<"OK"<<endl;
    }else{
        cout<<"NG"<<endl;
    }
}


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

const int size=100000;

int main(int argc, char const *argv[])
{
	int n,k;
	cin>>n;

	int a[size][3]={};
	//dp[size][3]={0};

	for (int i = 0; i < n; i++)
	{
		for(int j=0;j<3;j++)
		cin>>a[i][j];
	}

	//dp[0][0]=a[0][0];
	//dp[0][1]=a[0][1];
	//dp[0][2]=a[0][2];
	int cur;
	for (int i = 1; i < n; i++)
	{
		for(int j=0;j<3;j++){
			cur=a[i][j];
			a[i][j]=INT_MIN;
			for(int k=0;k<3;k++){
				if(j==k) continue;
				a[i][j]=max (a[i][j],a[i-1][k]+ cur);
			}
		}
	}
	
	cout<<max(a[n-1][0],max(a[n-1][1],a[n-1][2]));
	return 0;
}

Measured memory_bytes: 1536
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <functional>
#define rep(i,n) for (int i = 0; i < (n); ++i)

using namespace std;
const int MOD = 1000000007;


typedef long long int ll; 
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;

void floatOutPutSetup(){
    cout << fixed;
    cout << setprecision(10);
}

int main(){
    ll n,ans=0;
    cin>>n;
    vector<int> a(n,0);
    vector<bool> is(1000001,false);
    rep(i,n){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    rep(i,n){
        if(is[a[i]]==false){
            ans++;
            for(int j=a[i];j<=1000000;j+=a[i]){
                is[j]=true;
            }
            if(i<=a.size()&&a[i]==a[i+1]){
                ans--;
            }
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 4048
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (long long i = 0; i < (n); ++i)
#define rep(i, a, b) for (long long i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int n;
    cin >> n;
    vector<int> a;
    int sum = 0;
    REP(i, n)
    {
        int t;
        cin >> t;
        a.push_back(t);
        sum += t;
    }
    sort(a.begin(), a.end());
    if (sum % 10 != 0)
    {
        cout << sum << endl;
    }
    else
    {
        REP(i, n)
        {
            if ((sum - a[i]) % 10 != 0)
            {
                cout << sum - a[i] << endl;
                return 0;
            }
        }
        cout << "0" << endl;
    }
}

Measured memory_bytes: 256
X, Y = map(int,input().split())
ans = 'No'
if 4*X < Y:
    print(ans)
else:
    for i in range(X+1):
        crane = i
        turtle = X - i
        if 2*crane + 4*turtle == Y:
            ans = 'Yes'
            break
    print(ans)

Measured memory_bytes: 9108
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace mondai0004
{
	class Program
	{
		static void Main(string[] args)
		{
			while( true ) {
				var	str	= Console.ReadLine();
				if( str == null ) {
					break;
				}
				var	n	= str.Split();
				var	a	= double.Parse( n[ 0 ] );
				var	b	= double.Parse( n[ 1 ] );
				var	c	= double.Parse( n[ 2 ] );
				var	d	= double.Parse( n[ 3 ] );
				var	e	= double.Parse( n[ 4 ] );
				var	f	= double.Parse( n[ 5 ] );
				double	x	= (c * e - b * f) / (a * e - b * d);
				double	y	= (c * d - a * f) / (b * d - a * e);
				Console.WriteLine( "{0:f3} {1:f3}", x, y );
			}
			
			/*while( true ) {
				var	str	= Console.ReadLine();
				if( str == null ) {
					break;
				}
				var	n	= Array.ConvertAll( str.Split(), a => double.Parse( a ) );
				
				// 加減法
				var	nn	= Array.ConvertAll( str.Split(), a => double.Parse( a ) );
				for( int i = 0; i < 3; i++ ) {
					nn[ i ]	*= n[ 3 ];
				}
				for( int i = 3; i < 6; i++ ) {
					nn[ i ]	*= n[ 0 ];
				}
				double	y	= (nn[ 2 ] - nn[ 5 ]) / (nn[ 1 ] - nn[ 4 ]);
				double	x	= (n[ 2 ] - (n[ 1 ] * y)) / n[ 0 ];
				Console.WriteLine( "{0:f3} {1:f3}", x, y );
			}*/
		}
	}
}

Measured memory_bytes: 5724
#include <string.h>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <iterator>
#include <functional>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define sz(a)  int((a).size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
#define CLR(a) memset((a), 0, sizeof(a))
#define INF (1 << 31) - 1
const int dh[8] = {-1, 1, 0, 0,1,1,-1,-1};
const int dw[8] = {0, 0, 1, -1,1,-1,1,-1};
typedef long long ll;
typedef pair<double, double> p;
typedef vector <int> VI;
typedef vector <string> VS;


int main(){
  
  string s, t;
	cin >> s;
  cin >> t;

  int sn = sz(s);
  int tn = sz(t);

  bool flg = true;
  for(int i = sn - tn; i >= 0; --i){
     int j = 0;
     for(; j < tn; ++j){
      if(t[j] != s[i+j] && s[i + j] != '?') break;     
     }
     if(j == tn){
       flg = false;
       string ans = s;
        for(int k = 0; k < i; k++){
          ans[k] = s[k];
          if(ans[k] == '?') ans[k] = 'a';
        }
        for(int k = 0; k < tn; k++){
          ans[k + i] = t[k];
        }
        for(int k = i + tn; k < sn; k++){
          ans[k] = s[k];
          if(ans[k] == '?') ans[k] = 'a';
        }
        cout << ans << endl;
        break;
     }
  }
  if(flg) cout << "UNRESTORABLE" << endl;
  return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);i++)

bool multi=false;
vector<int> toposo(vector<vector<int>> &g){
  int n=g.size();
  vector<int> deg_in(n, 0);
  rep(i, n)for(int j: g[i]) deg_in[j]++;
  queue<int> Q;
  rep(i, n)if(deg_in[i]==0) Q.push(i);
  vector<int> order;
  while(Q.size()>0){
    auto i=Q.front(); Q.pop();
    order.push_back(i);
    int cnt=0;
    for(int j: g[i]){
      if((--deg_in[j])==0){
        Q.push(j);
        cnt++;
      }
    }
    if(cnt>=2) multi=true;
  }
  return order;
}

int main(){

  int n, m; cin>> n>> m;
  vector<vector<int>> g(n);
  rep(_, m){
    int a, b; cin>> a>> b;
    g[a-1].push_back(b-1);
  }

  auto order=toposo(g);

  for(int i: order) cout<< i+1<< endl;
  if(multi) cout<< 1<< endl;
  else cout<< 0<< endl;

  return 0;
}


Measured memory_bytes: 3876
import string

n = int(input())
alpha = string.ascii_lowercase
x = [[] for _ in range(26)]

for _ in range(n):
    s = input()
    for a in alpha:
        x[alpha.index(a)].append(s.count(a))

ans = ""
for i in range(26):
    ans += min(x[i]) * alpha[i]

print(ans)

Measured memory_bytes: 3772
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  long long int a,b,c,d,e,f,g;cin>>a>>b>>c;
  cout<<(a-1)*(b-1);
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);

	public static void main(String[] args){
		
		int[] d = new int[6];

		for(int i = 0; i < 6; i++){
			d[i] = scan.nextInt();
		}
		Dice dice1 = new Dice(d);
		for(int i = 0; i < 6; i++){
			d[i] = scan.nextInt();
		}
		Dice dice2 = new Dice(d);

		boolean flag = false;
		
		for(int j = 0; j < 4; j++){
			for(int k = 0; k < 4; k++){
				flag = Arrays.equals(dice1._d, dice2._d);
				if(flag == true)break;
				dice2.rollEast();
			}
			for(int k = 0; k < 4; k++){
				flag = Arrays.equals(dice1._d, dice2._d);
				if(flag == true)break;
				dice2.rollNorth();
			}
			flag = Arrays.equals(dice1._d, dice2._d);
			if(flag == true)break;
			dice2.rollRight();
		}
		System.out.println(flag? "Yes" : "No");
	}
}

class Dice{

	int[] _d = new int[6];
	public static final int
		TOP = 0, SOUTH = 1, EAST = 2,
		WEST = 3, NORTH = 4, BOTTOM = 5; // ?????°

	public Dice(int[] d){ // ?????????????????????
		for(int i = 0; i < 6; i++){
			_d[i] = d[i];
		}
	}

	public void rollSouth(){
		int tmp = _d[TOP];
		_d[TOP] = _d[NORTH];
		_d[NORTH] = _d[BOTTOM];
		_d[BOTTOM] = _d[SOUTH];
		_d[SOUTH] = tmp;
	}

	public void rollNorth(){
		int tmp = _d[TOP];
		_d[TOP] = _d[SOUTH];
		_d[SOUTH] = _d[BOTTOM];
		_d[BOTTOM] = _d[NORTH];
		_d[NORTH] = tmp;
	}

	public void rollEast(){
		int tmp = _d[TOP];
		_d[TOP] = _d[WEST];
		_d[WEST] = _d[BOTTOM];
		_d[BOTTOM] = _d[EAST];
		_d[EAST] = tmp;
	}

	public void rollWest(){
		int tmp = _d[TOP];
		_d[TOP] = _d[EAST];
		_d[EAST] = _d[BOTTOM];
		_d[BOTTOM] = _d[WEST];
		_d[WEST] = tmp;
	}

	public void rollRight(){
		int tmp = _d[SOUTH];
		_d[SOUTH] = _d[WEST];
		_d[WEST] = _d[NORTH];
		_d[NORTH] = _d[EAST];
		_d[EAST] = tmp;
	}
}

Measured memory_bytes: 26300
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

int main(){

  string s;
  cin >> s;

  int len = s.length();
  REP(i,len - 1){
    if(s[i] == 'S' && s[i + 1] == 'T'){
      s.erase(i, 2);
      len -= 2;
      i -= 2;
    }
  }

  cout << len << "\n";
  return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    string s; cin >> s;
    int k = 1;
    int i = 0;
    string before = "";
    string tmp;
    while (i < s.size()){
        if ((tmp.size()==0) or tmp==before){
            tmp.push_back(s[i]);
            i++;
        } else {
            before = tmp;
            tmp = "";
            k++;
        }
    }
    if (before == tmp){
        k--;
    }
    cout << k << endl;
    return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;

const int maxn=55;
int n,K,m,x[maxn],y[maxn],a[maxn];
ll ans=5e18;
int main(){
	scanf("%d%d",&n,&K);
	for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++)
	  if (y[i]<=y[j]){
	 	m=0;
		for (int k=1;k<=n;k++) if (y[i]<=y[k]&&y[k]<=y[j]) a[++m]=x[k];
		sort(a+1,a+1+m);
		for (int l=1,r=1;l<=m&&r<=m;l++){
			while (r<=m&&r-l+1<K) r++;
			if (r>m) break;
			ans=min(ans,(ll)(a[r]-a[l])*(y[j]-y[i]));
		}
	  }
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
using namespace std;
int main() {
  long long n, sum = 0, a[10000];
  cin >> n;
  rep(i, n) {
    cin >> a[i];
    sum += a[i];
  }
  sort(a, a + n);
  cout << a[0] << ' ' << a[n - 1] << ' ' << sum << endl;
  return 0;
}

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

using namespace std;

int main()
{
	string s;
	cin >> s;
	int cnt=1,ans=0;
	for (int i=1; i<s.size(); i++)
	{
		if (cnt==0)
		{
			cnt++;
			if (s[i]=='p')	ans--;
			continue;
		}
		if (cnt>0)
		{
			cnt--;
			if (s[i]=='g')	ans++;
			continue;
		}
	}
	cout << ans;
}

Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,fn=0; cin>>n;
    int N=n;
    while(N>0){
        fn+=N%10;
        N/=10;
    }
    cout<<(n%fn==0 ? "Yes" : "No")<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100000
#define INFTY 2000000000

typedef struct{
  char name;
  int num;

}card;

void mergeSort(card*,int,int);
void merge(card*,int,int,int);
void quickSort(card*,int,int);
int partition(card*,int,int);


card L[N/2],R[N/2];
card Q[N],M[N];

int count;

int main(){
  int n,i,num;
  char Name[10];
  int stable=1;
    
  scanf("%d",&n);
    
  for(i=0;i<n;i++){
    scanf("%s %d",Name,&num);
    Q[i].name=M[i].name=Name[0];
    Q[i].num=M[i].num=num;
  }
    
  mergeSort(M,0,n);
  quickSort(Q,0,n-1);
    
  for(i=0;i<n;i++){
    if(M[i].name!=Q[i].name) stable=0;
  }

  if(stable==1) printf("Stable\n");
  else printf("Not stable\n");
  for(i=0;i<n;i++){
    printf("%c %d\n",Q[i].name,Q[i].num);
  }
    
  return 0;
    
}

void mergeSort(card *A,int left,int right){

  int mid;

  if(left+1 < right){

    mid = (left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
    
  }
  
}

void merge(card *A,int left,int mid,int right){

  int n1,n2,i,j,k,lcount=0,rcount=0;
  
  n1=mid-left;
  n2=right-mid;
  
  for(i=0;i<=n1-1;i++){
    L[i] = A[left+i];
    lcount++;
  }
 
  for(i=0;i<=n2-1;i++){
    R[i] = A[mid+i];
    rcount++;
  }
 

  L[n1].num=INFTY;
  R[n2].num=INFTY;

  i=0;
  j=0;
  
  for(k=left;k<=right-1;k++){

    if(L[i].num<=R[j].num){

      A[k]=L[i];
      lcount--;
      if(lcount>0){
        i++;
      }else{
        L[i].num=INFTY;
      }
      
    }else{

      A[k]=R[j];
      rcount--;
      if(rcount>0){
        j++;
      }else{
        R[j].num=INFTY;

      }
      
    }//if
    
    count++;
    
  }//for

}

int partition(card *A,int p,int r){

  int i,j;
  card x,temp1,temp2;

  x=A[r];
  i=p-1;
  
  for(j=p;j<=r-1;j++){


    if(A[j].num<=x.num){
      i=i+1;
      temp1=A[i];
      A[i]=A[j];
      A[j]=temp1;
      
    }

  }

  temp2=A[i+1];
  A[i+1]=A[r];
  A[r]=temp2;

  return i+1;
    
}


void quickSort(card *A,int p,int r){
  int q;
  if(p < r){
    q = partition(A, p, r);
    quickSort(A, p, q-1);
    quickSort(A, q+1, r);
  }
}



Measured memory_bytes: 4088