akhauriyash/Code-Regression huggingface dataset:
/**
        	C++14 (GCC 5.4.1)
**/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
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> C(N-1);
    for(int i=0; i < N-1 ; i++){
        cin >> C[i];
    }

    int cc = 0;
    int count = B[A[0]-1];
    for(int i = 1; i < N ; i++){
        count += B[A[i]-1];
        // cout << B[A[i]-1] << endl;
        if(A[i-1] + 1 == A[i]){
            count += C[A[i-1]-1];
            // cout << i <<endl;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
inline int xmod(int a, int b) {
    return (a >= 0) ? a%b : a%b + b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    int len=1000050;
    vector<int> li(len);
    int fi=0, la=0;

    string op;
    int key;
    for (int i=0; i<n; ++i) {
        cin >> op;
        if (op == "insert") {
            cin >> key;
            fi = xmod(fi-1, len);
            li[fi] = key;
            continue;
        } else if (op == "deleteFirst") {
            while (li[fi] == -1) fi = (fi+1) % len;
            fi = (fi+1) % len;
        } else if (op == "deleteLast") {
            while (li[xmod(la-1, len)] == -1) la = xmod(la-1, len);
            la = xmod(la-1, len);
        } else {
            cin >> key;
            for (int j=fi; j!=la; j=(j+1)%len) {
                if (li[j] == key) {
                    li[j] = -1;
                    break;
                }
            }
        }
    }

    bool nospace = true;
    for (int i=fi; i!=la; i=(i+1)%len) {
        if (li[i] == -1) continue;
        if (nospace) {
            cout << li[i];
            nospace = false;
        } else {
            cout << " " << li[i];
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 4964
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef double db;
typedef vector <ll> vll;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define MAX 1000000
#define mod 1000000007
#define all(_) _.begin(), _.end()
#define F first
#define S second
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll n, i, k;
    cin >> n >> k;
    if(2 * k > (n - 2) * (n - 1))
        cout << -1 << endl;
    else
    {
        ll v = n * (n - 1) / 2 - k;
        cout << v << endl;
        for(i = 1; i <= n && v; i++)
            for(ll j = i + 1; j <= n && v; j++)
            {
                cout << i << ' ' << j << endl; v--;
            }
    }
    return 0;
}

Measured memory_bytes: 256
H,W = map(int,input().split())
S = [input() for _ in range(H)]
answer = [[0 if cell == '.' else '#' for cell in row] for row in S]
 
import itertools
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            continue
        for dx,dy in itertools.product([-1,0,1],repeat=2):
            x = i+dx
            y = j+dy
            if x < 0 or x >= H:
                continue
            if y < 0 or y >= W:
                continue
            if S[x][y] == '#':
                continue
            answer[x][y] += 1
            
for row in answer:
    print(*row,sep='')

Measured memory_bytes: 3444
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>

typedef long long ll;
using namespace std;


int main()
{
    int N, M, sum = 0;
    cin >> N >> M;

    vector <int> X(M, 0);

    for (int i = 0; i < M; i++) {
        cin >> X[i];
    }

    sort(X.begin(), X.end());

    vector <int> L(M-1, 0);

    for (int i = 0; i < M-1; i++) {
        L[i] = X[i+1] - X[i];
    }

    sort(L.begin(), L.end());

    for (int i = 0; i < M-N; i++) {
        sum += L[i];
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
int num;
  cin>>num;
  int k;
  k=num*500;
  int x;
  cin>>x;
  if(k>=x){
  cout<<"Yes"<<endl;
  }
  else{
  cout<<"No"<<endl;
  }
  return 0;
}

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

int main()
{
	int a,b,c,k;
	cin >> a >> b >> c >> k;

	int count=0;
	while (a>=b)
	{
		b<<=1;
		++count;
	}
	while (b>=c)
	{
		c<<=1;
		++count;
	}

	if (count<=k)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
}







Measured memory_bytes: 3616
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int32_t n;

    cin >> n;

    vector<double> d(n);

    for (int32_t i = 0; i < n; i++) {
        cin >> d[i];
    }
    for (int32_t i = 0; i < n; i++) {
        double y;
        cin >> y;
        d[i] = abs(d[i] - y);
    }

    cout << fixed << setprecision(5) << accumulate(d.begin(), d.end(), 0.0) << endl;
    cout << fixed << setprecision(5) << sqrt(accumulate(d.begin(), d.end(), 0.0, [](double sum, double d_i) {
        return sum + d_i * d_i;
    })) << endl;
    cout << fixed << setprecision(5) << pow(accumulate(d.begin(), d.end(), 0.0, [](double sum, double d_i) {
        return sum + d_i * d_i * d_i;
    }), 1.0 / 3.0) << endl;
    cout << fixed << setprecision(5) << *max_element(d.begin(), d.end()) << endl;

    return 0;
}

Measured memory_bytes: 3452
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <map>
#include <ctime>
#include <set>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 100001
#define MACRO(a) for(int a = 1; a < 1001; a++)

using namespace std;

int main(void)
{
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	vector<int> vec(3, 0);
	for (int i = 0; i < 3; i++) cin >> vec[i];
	sort(vec.begin(), vec.end());
	cout << vec[1] - vec[0] + (vec[2] - vec[1]);

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define ll long long
#define P pair<int, int>

using namespace std;

int N;
int main() {
  cin >> N;
  bool ans[101] = {false};
  ans[0] = true;
  rep(i, 101) {
    if (i+4 < 101) {
      ans[i + 4] = ans[i + 4] || ans[i];
    }
  }
  rep(i, 101) {
    if (i+7 < 101) {
      ans[i+7] = ans[i+7] || ans[i];
    }
  }
  cout << (ans[N] ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define erep(i, n) for (ll i = 1; i <= (n); i++)
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
// input
ll h[100010][3];
// dp table
ll dp[100010][3];

int main(void) {
  int n;
  cin >> n;
  rep(i, n) rep(j, 3) cin >> h[i][j];
  rep(i, n) rep(j, 3) rep(k, 3) if (j != k) {
    maxs(dp[i + 1][j], dp[i][k] + h[i][j]);
  }
  ll ans = 0;
  rep(i, 3) maxs(ans, dp[n][i]);
  cout << ans << '\n';
  return 0;
}

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


// type {{{
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
// }}}


// macro {{{
#define REP(i,n) for (ll i=0; i<(n); ++i)
#define RREP(i,n) for (ll i=(ll)(n)-1; i>=0; --i)
#define FOR(i,a,n) for (ll i=(a); i<(n); ++i)
#define RFOR(i,a,n) for (ll i=(ll)(n)-1; i>=(a); --i)

#define SZ(x) ((ll)(x).size())
#define all(x) begin(x),end(x)
// }}}


// debug {{{
#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    REP (i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "(" << p.first << " " << p.second << ")";
}
// }}}


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



// constants {{{
#define inf(T) (numeric_limits<T>::max() / 2)
const ll MOD = 1e9+7;
const ld EPS = 1e-9;
// }}}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    for (;;) {
        int n; cin >> n;
        if (n == 0) break;

        vvi schedule(31);
        REP (i, n) {
            int m; cin >> m;
            REP (_, m) {
                int d; cin >> d; --d;
                schedule[d].push_back(i);
            }
        }

        int ans = -1;
        vvll dp(31, vll(n));
        REP (i, n) {
            dp[0][i] = 1LL<<i;
        }
        REP (d, 30) {
            REP (i, n) {
                dp[d+1][i] = dp[d][i];
            }
            for (int i : schedule[d]) {
                for (int j : schedule[d]) {
                    dp[d+1][i] |= dp[d][j];
                }
            }
            REP (i, n) {
                if (dp[d+1][i] == (1LL<<n)-1) {
                    ans = d+1;
                    break;
                }
            }
            if (ans != -1) break;
        }
        cout << ans << endl;
    }

    return 0;
}



Measured memory_bytes: 3104
import java.util.*;

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

	class Ev implements Comparable<Ev>{
		int x;
		int time;
		int kind;

		public Ev(int x, int time, int kind) {
			this.x=x;
			this.time=time;
			this.kind=kind;
		}

		@Override
		public int compareTo(Ev arg0) {
			return this.time - arg0.time;
		}
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		int Q=sc.nextInt();

		ArrayList<Ev> ev = new ArrayList<>();
		for(int i=0; i<N; i++) {
			int s=sc.nextInt();
			int t=sc.nextInt();
			int x=sc.nextInt();
			ev.add(new Ev(x, s-x, 1));
			ev.add(new Ev(x, t-x, -1));
		}

		Collections.sort(ev);

		ArrayList<Integer> D = new ArrayList<>();
		for(int i=0; i<Q; i++) {
			D.add(sc.nextInt());
		}

		TreeSet<Integer> set = new TreeSet<>();

		int ans[] = new int[Q];
		Arrays.fill(ans, -1);
		int didx = 0;

		for(Ev e : ev) {

			//アクティブイベントに対してDがぶつかるかテスト
			while(didx<D.size() && D.get(didx) < e.time) {
				if(set.isEmpty()) {
					ans[didx] = -1;
				}else {
					ans[didx] = set.first();
				}
				didx++;
			}


			//アクティブイベント更新
			if(e.kind==1) {
				set.add(e.x);
			} else {
				set.remove(e.x);
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0; i<Q; i++) {
			sb.append(ans[i]).append("\n");
		}
		System.out.println(sb.toString());
		sc.close();
	}
}


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

using namespace std;

// Useful Marcos
//====================START=====================
// Compile use C++11 and above
#ifdef LOCAL
#define debug(args...)                           \
    {                                            \
        string _s = #args;                       \
        replace(_s.begin(), _s.end(), ',', ' '); \
        stringstream _ss(_s);                    \
        istream_iterator<string> _it(_ss);       \
        err(_it, args);                          \
    }
void err(istream_iterator<string> it)
{
}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
#define MSG cout << "Finished" << endl
#else
#define debug(args...)
#define MSG
#endif
#if __cplusplus >= 201703L
template <typename... Args>
void readln(Args &... args)
{
    ((cin >> args), ...);
}
template <typename... Args>
void writeln(Args... args)
{
    ((cout << args << " "), ...);
    cout << endl;
}
#elif __cplusplus >= 201103L
void readln()
{
}
template <typename T, typename... Args>
void readln(T &a, Args &... args)
{
    cin >> a;
    readln(args...);
}
void writeln()
{
    cout << endl;
}
template <typename T, typename... Args>
void writeln(T a, Args... args)
{
    cout << a << " ";
    writeln(args...);
}
#endif
#if __cplusplus >= 201103L
#define FOR(_i, _begin, _end) for (auto _i = _begin - (_begin > _end); _i != _end - (_begin > _end); _i += 1 - 2 * (_begin > _end))
#define FORE(_i, _c) for (auto _i : _c)
#define FORER(_i, _c) for (auto &_i : _c)
#else
#define FOR(_i, _begin, _end) for (__typeof(_end) _i = _begin - (_begin > _end); _i != _end - (_begin > _end); _i += 1 - 2 * (_begin > _end))
#define FORE(_i, _c)
#define FORER(_i, _c)
#define nullptr NULL
#endif
#if __cplusplus >= 201402L
#define VIS(_kind, _name, _size) \
    vector<_kind> _name(_size);  \
    for (auto &i : _name)        \
        cin >> i;
#else
#define VIS(_kind, _name, _size)    \
    vector<_kind> _name;            \
    _name.resize(_size);            \
    for (int i = 0; i < _size; i++) \
        cin >> _name[i];
#endif
// alias
#define mp make_pair
#define pb push_back
#define eb emplace_back
//====================END=====================

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;

// Constants here

// Pre-Build Function
void build()
{
}

// Actual Solver
void solve()
{
    int n;
    cin >> n;
    VIS(int, v, n);
    sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
    int a, b;
    a = b = 0;
    int flag = 0;
    for (auto i : v)
    {
        if (flag)
            b += i;
        else
            a += i;
        flag = !flag;
    }
    cout << a - b << endl;
}

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

#ifdef LOCAL
    clock_t _begin = clock();
#endif

    build();
    solve();

#ifdef LOCAL
    cerr << "Elapsed Time: " << (double)(clock() - _begin) * 1000 / CLOCKS_PER_SEC << "ms." << endl;
#endif

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl


const int MAX_ROW = 1010; // to be set appropriately
const int MAX_COL = 1010; // to be set appropriately
struct BitMatrix {
    int H, W;
    bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
    inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};

ostream& operator << (ostream& s, BitMatrix A) {
    s << endl; 
    for (int i = 0; i < A.H; ++i) {
        for (int j = 0; j < A.W; ++j) {
            s << A[i][j] << ", ";
        }
        s << endl;
    }
    return s;
}

int GaussJordan(BitMatrix &A, bool is_extended = false) {
    int rank = 0;
    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = rank; row < A.H; ++row) {
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(A[pivot], A[rank]);
        for (int row = 0; row < A.H; ++row) {
            if (row != rank && A[row][col]) A[row] ^= A[rank];
        }
        ++rank;
    }
    return rank;
}

int linear_equation(BitMatrix A, vector<int> b, vector<int> &res) {
    int m = A.H, n = A.W;
    BitMatrix M(m, n + 1);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) M[i][j] = A[i][j];
        M[i][n] = b[i];
    }
    int rank = GaussJordan(M, true);

    // check if it has no solution
    for (int row = rank; row < m; ++row) if (M[row][n]) return -1;

    // answer
    res.assign(n, 0);
    for (int i = 0; i < rank; ++i) res[i] = M[i][n];
    return rank;
};



int main() {
    int N, M, D;
    while (cin >> M >> N >> D, N) {
        vector<vector<int> > a(N, vector<int>(M, 0));
        for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> a[i][j];

        BitMatrix A(N*M, N*M);
        vector<int> b(N*M, 0), res;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                A[i*M+j][i*M+j] = 1;
                for (int k = 0; k < N; ++k) {
                    for (int l = 0; l < M; ++l) {
                        if (abs(i - k) + abs(j - l) != D) continue;
                        A[i*M+j][k*M+l] = 1;
                    }
                }
                b[i*M+j] = 1 - a[i][j];
            }
        }
        int rank = linear_equation(A, b, res);
        if (rank == -1) cout << 0 << endl;
        else cout << 1 << endl;
    }
}



Measured memory_bytes: 3424
#include <cmath>
#include <iostream>
#include <vector>
int main()
{
	int n = 0;
	std::cin >> n;

	std::vector<int> x(n);
	std::vector<int> y(n);

	double sum = 0;

	int xinput = 0;
	int yinput = 0;

	for (int i = 0; i < n; ++i)
	{
		std::cin >> xinput >> yinput;
		for (int j = 0; j < i; ++j)
		{
			sum += std::sqrt(std::pow((xinput - x.at(j)), 2) + std::pow((yinput - y.at(j)), 2));
		}
		x.at(i) = xinput;
		y.at(i) = yinput;
	}

	printf("%f", sum * 2 / n);
}




Measured memory_bytes: 256
def main():
    n = int(input())
    d_lst = list(map(int, input().split()))

    d_lst.sort()

    if d_lst[n // 2 - 1] == d_lst[n // 2]:
        ans = 0
    else:
        ans = d_lst[n // 2] - d_lst[n // 2 - 1]

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 84420
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = aaa[0]
for a in aaa[1:]:
    lcm = lcm * a // gcd(lcm, a)
lcm %= MOD

ans = 0
for a in aaa:
    ans = (ans + lcm * pow(a, MOD - 2, MOD)) % MOD
print(ans)


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

int main() {
  long long n, ans = 0; 
  cin >> n;
  vector<long long> ret;
  for(long long i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  for(int i = 1; i < ret.size(); i++) {
    long long C = ret.at(i)-1; 
    if(n / C == n % C) ans += C;
  }
  cout << ans;
}

Measured memory_bytes: 384
#include<stdio.h>
int main( )
{
  int i, j,mini,temp,count=0;
  int A[100],N;
  scanf("%d",&N);
  for(i=0; i < N; i++){
    scanf("%d",&A[i]);
  }
  for(i=0; i < N-1; i++){
    mini = i;
    for(j = i+1; j < N; j++){
      if(A[j]<A[mini]){
	mini = j;
      }
    }
    temp = A[i];
    A[i] = A[mini];
    A[mini] = temp;
    if(i != mini){
    count++;
    }
  }
  for(i = 0; i < N ; i++){
    if(i == N-1){
      printf("%d",A[i]);
    }
    else printf("%d ",A[i]);
  }
  printf("\n%d\n",count);
  return 0;
}

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

long long N;
int main(){
	cin >> N;

	long long ans = N;
	for(long long i = 1; i * i <= N; i++){
		if(N%i == 0){
			ans = min(ans, i + N/i - 2);

		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
const ll INF = 1000000000000007;

using namespace std;

int main(){
    ll N,M,res;
    cin >> N >> M;

    if( N >= 2 && M >= 2)
    {
      res = (N-2)*(M-2);
    }
    else if( N == 1 && M == 1)
    {
      res = 1;
    }
    else
    {
      res = max(N,M) -2;
    }

    cout << res << endl;

    return 0;

}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PI 3.1415926535897932384626433832795
#define endl "\n"
#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const long long MOD = 998244353;
pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct chash {int operator()(int x) const { return x ^ RANDOM; }};
string toString(long long x){stringstream ss;ss << x;string str = ss.str();return str;}
long long fastpow(long long x,long long k){if(!k)return 1;if(k & 1)return ((x * fastpow(x,k-1) % MOD) % MOD) % MOD;
long long ans = fastpow(x,k/2);ans %= MOD;ans *= ans;ans %= MOD;return ans;}
long long sumF(long long x){int s = 0;while(x)s += x%10,x /= 10;return s;}
bool isS(char c){return (c >= 'a' && c <= 'z');}
bool isB(char c){return (c >= 'A' && c <= 'Z');}
bool isD(char c){return (c >= '0' && c <= '9');}
bool isSqrt(long long x){ long long f = sqrt((long double)x + 0.5); return f*f == x;}
bool isCubic(long long x) {long long f = cbrt((long double)x + 0.5); return f*f*f == x;}
long long lcm(long long a,long long b){return a * (b / __gcd(a,b));}
vector<long long> divisorsVector(long long x){vector<long long> tmp;for(long long i = 1;1LL*i*i <= x;i++){if(x % i == 0){tmp.push_back(i);if(x / i != i)
tmp.push_back(x / i);}}sort(tmp.begin(),tmp.end());return tmp;}
long long countDiv(long long L,long long R,long long C){return ((R/C) - ((L-1)/C));}
int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
long long ADDMOD(long long x,long long y){return (x % MOD + y % MOD) % MOD;}
long long MULMOD(long long x,long long y){return (x % MOD * y % MOD) % MOD;}
long long DIFFMOD(long long x,long long y){return (((x % MOD - y % MOD) % MOD) + MOD) % MOD;}
long long FACMOD(long long x){if(x == 0) return 1;return (x * (FACMOD(x - 1) % MOD));}
int arr[3005];
long long dp[2][3005];
int32_t main()
{
    IO;
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> arr[i];
    for(int i = n;i >= 1;i--)
    {
        for(int j = i;j <= n;j++)
        {
            dp[i%2][j] = 0;
            if(((i-1)+(n-j)) % 2 == 0)
                dp[i%2][j] = max(arr[i] + dp[(i+1)%2][j],arr[j] + dp[i%2][j-1]);
            else
                dp[i%2][j] = min(-arr[i] + dp[(i+1)%2][j],-arr[j] + dp[i%2][j-1]);
        }
    }
    cout << dp[1][n];
    return 0;
}


Measured memory_bytes: 384
N, M = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(N)]
cd = [list(map(int, input().split())) for i in range(M)]
for ab_i in ab:
    min_j = -1
    min_manh = float('inf')
    for j, cd_j in enumerate(cd):
        if min_manh > abs(ab_i[0]-cd_j[0])+abs(ab_i[1]-cd_j[1]):
            min_manh = abs(ab_i[0]-cd_j[0])+abs(ab_i[1]-cd_j[1])
            min_j = j+1
    print(min_j)


Measured memory_bytes: 3064
#include<stdio.h>
 
#define N 100000
 
int A[N],n;
 
int partition(int p,int r){
  int x,i,j,tmp;
  x=A[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(A[j] <= x){
      i++;
      tmp=A[i]; A[i]=A[j]; A[j]=tmp;
    }
  }
  tmp=A[i+1]; A[i+1]=A[r]; A[r]=tmp;
  return i+1;
}
 
int main(void){
 
  int i,p;
   
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&A[i]);
  p=partition(0,n-1);
 
  for(i=0;i<n;i++){
    if(i) printf(" ");
    if(i==p) printf("[%d]",A[i]);
    else printf("%d",A[i]);
  }
  printf("\n");
   
  return 0;
}

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

int main(){
  char a,b;
  cin>>a>>b;
  if(a=='H'&&b=='H') cout<<'H'<<endl;
  else if(a=='D'&&b=='D') cout<<'H'<<endl; 
  else cout<<'D'<<endl;
}

Measured memory_bytes: 256
D, N = map(int, input().split())  

if N == 100 and D == 0:
    print(101)
elif N == 100 and D == 1:
    print(10100)
elif N == 100 and D == 2:
    print(1010000)
    
elif D == 0:
    print(N)
elif D == 1:
    print(100*N)
elif D == 2:
    print(10000*N)

Measured memory_bytes: 3060
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int K = in.nextInt(), A = in.nextInt(), B = in.nextInt();
        System.out.println(A % K == 0 || A / K < B / K ? "OK" : "NG");
    }
}

Measured memory_bytes: 35772
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
using namespace std;

void solve(std::string S){
    auto n=S.length();
    long long ndiff=0;
    auto curr = S[0];
    for(int i=1; i<n; i++){
        if(curr != S[i]){
            ndiff++;
            curr = S[i];
        }
    }
    cout << ndiff << endl;
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) obj.begin(),obj.end()
#define pb(obj) push_back(obj)
#define REP(i,N) for(ll i=0;i<N;i++)
typedef long long ll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    char A1,A2;
    int c1=0,c2=0;
    string S;
    cin>>S;
    A1=S[0];
    if(S[1]!=A1){A2=S[1];}
    else if(S[2]!=A1){A2=S[2];}
    else if(S[3]!=A1){A2=S[3];}
    else{cout<<"No"<<endl;exit(0);}
    for(int i=0;i<4;i++){
        if(S[i]!=A1&&S[i]!=A2){cout<<"No"<<endl;exit(0);}
    }
    for(int i=0;i<4;i++){
        if(S[i]==A1)c1++;
        if(S[i]==A2)c2++;
    }
    if(c1==2&&c2==2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

using namespace std ;

int n , k;
int height[100001];
int dp[100002];

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

        cin >> n >> k; 
        for(int i=0;i<n;i++)
                cin>>height[i];
        fill(dp,dp+n,LONG_LONG_MAX);
        dp[0]=0;
        for(int i=1;i<n;i++){
                if(i<=k){
                        for(int j=0;j<=i;j++){
                                dp[i] = min(dp[i],dp[j]+abs(height[i]-height[j]));
                        }
                }else{
                        for(int j=1;j<=k;j++){
                                dp[i] = min(dp[i],dp[i-j]+abs(height[i]-height[i-j]));
                        }
                }
                //cout << dp[i] << endl ;
        }

        cout << dp[n-1] << endl;

        return 0;
}

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

typedef long long ll;
using pii = pair<int, int>;
template <class T>
using v = vector<T>;
template <class T>
using vv = v<v<T>>;
#define ALL(c) (c).begin(), (c).end()

int main()
{
    string s;
    cin >> s;
    if (s[s.size() - 1] == 's')
    {
        cout << s << "es" << endl;
    }
    else
    {
        cout << s << "s" << endl;
    }
    return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define szof(x) int32_t((x).size())
#define str(x) to_string(x)

using namespace std;

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

const ll MOD = 1e9 + 7;
const ll MOD998 = 998244353;
const int INF = 1e9;
const ll LLINF = 1e18;

mt19937_64 rng((uint) chrono::steady_clock::now().time_since_epoch().count());

template <class T>
T rnd(T l, T r) {
	return uniform_int_distribution<T>(l, r)(rng);
}

void run() {
	int n;
	cin >> n;
	vector<double> p(n);
	for (auto &x : p) {
		cin >> x;
	}
	vector<double> dp(n + 1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		vector<double> new_dp(n + 1);
		for (int am = 0; am <= n; am++) {
			if (am > 0) {
				new_dp[am] += dp[am - 1] * p[i - 1];
			}
			new_dp[am] += dp[am] * (1 - p[i - 1]);
		}
		dp.swap(new_dp);
	}
	cout << accumulate(dp.begin() + (n + 1) / 2, dp.end(), 0.0) << "\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cout.precision(10); cout << fixed;
	int tests = 1;
	// cin >> tests;
	while (tests--) {
		run();
	}
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<iomanip>
using namespace std;

int main(){
    int n;
    cin >> n;
    double ans = 0;
    while(n-- > 0){
        double x;
        string s;
        cin >> x >> s;
        if(s == "JPY")  ans += x;
        else            ans += 380000.0*x;
    }
    cout << fixed << setprecision(12) << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define nt _int128
#define mod 1000000007
ll dp[2005];
ll solve(ll n)
{

	if(n==0)
		return 1;
	if(n<3)
		return 0;
	else if(dp[n]!=-1)
		return dp[n];
	ll ans=0;
	for(int i=3;i<=2000;i++)
	{
		ans=(ans+solve(n-i))%mod;
	}
	// cout<<n<<" "<<ans<<endl;
	return dp[n]=ans;
}
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    // cin >> t;
    t  = 1;
    while(t--)
    {
    	ll n;
    	cin>>n;
    	memset(dp,-1,sizeof dp);
    	cout<<solve(n);
    }
    return 0;
}

Measured memory_bytes: 3688
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;
long long A[100010], M[100010];
int main()
{
	int N;

	long long sum = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &A[i]);
		sum += A[i];
	}
	A[N] = A[0];
	long long S = 0;
	for (int i = 1; i < N; i += 2) {
		S += A[i];
	}
	M[0] = sum - S * 2;
	for (int i = 0; i < N; i++) {
		M[i + 1] = 2 * A[i] - M[i];
	}
	for (int i = 0; i < N; i++) {
		printf("%lld ", M[i]);
	}
	return 0;
}

Measured memory_bytes: 2816
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define cl clear() ;
#define vl vector<ll>
#define sz size()
#define len length()
#define emp empty()
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define en end()
#define ro return 0
#define eb emplace_back
#define con continue
#define ms(x) memset(x , 0, so x)
#define all(x) (x).be , (x).en
#define acc(x) accumulate((x).be , (x).en , 0ll)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
#define trace3(a,b,c) cerr <<"a is " << a << " b is " << b << " c is " << c << el;
#define trace4(a,b,c,d) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << el ;
#define trace5(a,b,c,d,e) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << el;
#define trace6(a,b,c,d,e,f) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << " f is " << f << el ;

bool check(vl &v)
{
    forn(i , 1 , ll(v.sz) -1 ) {
       if(v[i] != v[i-1]) return false;
    }
    return true;
}

int main()
{
    ios;
    ll N, K ;
    cin >> N >> K;

     int ans = (N- 1 + K- 2 ) / (K- 1 );
     cout << ans << endl;
    ro ;
}































Measured memory_bytes: 256
#include <cstdio>
#include <vector>

#define MAX_N 100000

using namespace std;

vector<int> G[MAX_N];
int color[MAX_N] = {0};
int each[2] = {0}; //各色のノードが何個ずつあるか

bool dfs(int n, int c) {
    color[n] = c;
    each[c == -1]++;
    size_t len = G[n].size();
    for (size_t i=0; i<len; i++) {
        int to = G[n][i];
        if (color[to] == c || (color[to] == 0 && !dfs(to, -c)))
            return false; 
    }
    return true;
}


int main() {
    int N, M, A, B;
    scanf("%d %d", &N, &M);
    for (int i=0; i<M; i++) {
        scanf("%d %d", &A, &B);
        G[A-1].push_back(B-1);
        G[B-1].push_back(A-1);
    }
    printf("%ld\n", (dfs(0,1) ? (long)each[0]*each[1] : (long)N*(N-1)/2) - M);
    return 0;
}

Measured memory_bytes: 6528
#include<stdio.h>
int main(void){
  int a, b, i, ans=0, n, q, w, e, r, t;
  scanf("%d %d", &a, &b);
  for(i=a;i<=b;i++){
    n=i;
    q=n/10000;
    n%=10000;
    w=n/1000;
    n%=1000;
    e=n/100;
    n%=100;
    r=n/10;
    t=n%10;
    if(q==t&&w==r){
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
from sys import stdin


def main():
    N, D = [int(x) for x in stdin.readline().rstrip().split()]
    Xs = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
    count = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            sum_ = sum([(a - b) ** 2 for a, b in zip(Xs[i], Xs[j])])
            ans = sum_ ** (1 / 2)
            if int(ans) == ans:
                count += 1
    print(count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<utility>
using namespace std;

bool self(vector<vector<int> >& G, int s, int t, vector<pair<int, int> >& stock_idx, vector<int>& searched){
    if (searched[s] == 1) return false;
    searched[s] = 1;
    if (G[s][t] != -1 && stock_idx.size() > 1) {
        stock_idx.push_back(make_pair(s, t));
        return true;
    }
    for (int i = 0; i < G[s].size(); i++) {
        if (G[s][i] != -1) {
            stock_idx.push_back(make_pair(s, i));
            if (self(G, i, t, stock_idx, searched)) return true;
            stock_idx.pop_back();
        }
    }
    return false;
}

bool DFS(vector<vector<int> >& G, int s, int t, vector<pair<int, int> >& stock_idx){
    vector<int> searched(G.size(), 0);
    return self(G, s, t, stock_idx, searched);
}

void cut(vector<vector<int> >& G, vector<pair<int, int> >& stock_idx){
    pair<int, int> max_idx = stock_idx[0];
    for (int i = 0; i < stock_idx.size(); i++) {
        if (G[stock_idx[i].first][stock_idx[i].second] > G[max_idx.first][max_idx.second]) {
            max_idx = stock_idx[i];
        }
    }
    G[max_idx.first ][max_idx.second] = -1;
    G[max_idx.second][max_idx.first ] = -1;
    stock_idx.clear();
}

int main(){
    int n;
    cin >> n;
    vector<vector<int> > G(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> G[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        vector<pair<int, int> > stock_idx;
        while (DFS(G, i, i, stock_idx)) cut(G, stock_idx);
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (G[i][j] != -1) sum += G[i][j];
        }
    }
    cout << sum << endl;

    return 0;
}



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define ld long double
#define sb __builtin_popcount
#define vi vector<int>
#define vc vector<char>
#define ii pair<int, int>
#define pq priority_queue<ii, vector<ii>, greater<ii>>
#define vii vector<ii>
#define sz(a) int((a).size())
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <=n; i++)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rloop(i,a,b) for(int i=a;i>=b;i--)
#define in(a, b) (b.find(a) != string::npos)
#define minin(a) *min_element(all(a))
#define maxin(a) *max_element(all(a))
#define X first
#define Y second
#define fill(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define pf push_front
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) reverse(v.begin(), v.end())
#define el "\n"
#define mx3(a, b, c) max(max(a, b), c)
#define mn3(a, b, c) min(min(a, b), c)
#define S(v) accumulate(all(v), (ll)0)
#define SP(n) cout.precision(n)
#define PI = atan(1.0) * 4.0;
#define MOD = 1e9 + 7;
void start() {
    fio;
    SP(10);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
int32_t main() {
    start();
    int n;
    cin >> n;
    unordered_map<int, int> mp;
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        mp[x]++;
    }
    vi v;
    for (auto x : mp) {
        if (x.Y == 1) {
            v.pb(x.X);
        }
    }
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        int g = 1;
        for (int j = 1; j * j <= v[i] && g; j++) {
            if (v[i] % j == 0) {
                if (v[i] / j == j) {
                    if (mp[j] != 0 && j != v[i]) {
                        g = 0;
                    }
                }
                else {
                    if (mp[j] != 0 && j != v[i]) {
                        g = 0;
                    }
                    if (mp[v[i] / j] != 0 && v[i] / j != v[i]) {
                        g = 0;
                    }
                }
            }
        }
        if (g)ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 32408
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;


int main(){
    int n, r;
    cin >> n >> r;
    int ans;
    if (n>=10) {
        ans = r;
    }
    else {
        ans = r + 100*(10-n);
    }
    
    
    
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)

int main(){

	lli n;
	cin>>n;

	vector<lli> a(n);
	REP(i,0,n)cin>>a[i];

	lli num = 1;
	lli ans = 0;

	for(lli i=0;i<n;i++){
		if(DEBUG)cout<<"i="<<i<<"a[i]="<<a[i]<<endl;
		if(DEBUG)cout<<"num="<<num<<"ans="<<ans<<endl;
		if(a[i]==num){
			num++;
			continue;
		}
		lli plus = a[i]/num;
		if(a[i]%num==0)plus--;
		ans += plus;
		if(i==0)num++;
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector< pair<int64_t,int64_t> > v(N);
    for(int i=0; i<N; i++) {
        int64_t a, b;
        cin >> a >> b;
        if(a > b) swap(a, b);
        v[i] = make_pair(a, b);
    }

    sort(v.begin(), v.end());
    v.emplace_back(v.front().second, v.back().first);

    vector<int64_t> lmax(N+1), lmin(N+1), r(N+1);
    for(int i=0; i<=N; i++) {
        lmax[i] = v[i].second;
        lmin[i] = v[i].second;
        r[i] = v[i].second;
    }
    for(int i=1; i<=N; i++) {
        lmax[i] = max(lmax[i-1], lmax[i]);
        lmin[i] = min(lmin[i-1], lmin[i]);
    }
    for(int i=N-1; i>=0; i--) {
        r[i] = max(r[i], r[i+1]);
    }

    int64_t ans = numeric_limits<int64_t>::max();
    for(int i=0; i<N; i++) {
        int64_t R_min = v.front().first;
        int64_t R_max = r[i+1];
        int64_t B_min = min(v[i+1].first, lmin[i]);
        int64_t B_max = max(lmax[i], v[N-1].first);
        cerr << i << ' ' << R_min << ' ' << R_max << ' ' << B_min << ' ' << B_max << endl;
        ans = min(ans, (R_max - R_min) * (B_max - B_min));
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12104
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define mod 1000000007
#define vi vector<int>
#define vll vector<ll>
#define pb push_back

ll power(int x, unsigned int y){
    ll res = 1;
    while(y > 0){
        if(y & 1) res = res * x;
        y >>= 1;
        x *= x;
    }
    return res;
}

const ll mx = 1e6 + 5;


// Check for number of Cases!!
void solve() {
    int n; cin >> n;

    int arr[n];
    ll gcd;

    vector<int> mul_2;

    vector<int> extras;
    map<ll, ll> mp;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        if(!i) gcd = arr[i];
        else gcd = __gcd((ll)arr[i], gcd);

        mp[arr[i]]++;
    }

    if(gcd != 1) {
        cout << "not coprime";
        return;
    }

    for(auto i : mp) {
        if(i.second > 1 && i.first != 1) {
            cout << "setwise coprime";
            return;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 2; j*j <= arr[i]; j++) {
            if(arr[i] % j == 0) {
                if(mp[j] || mp[arr[i] / j]) {
                    cout << "setwise coprime";
                    return;
                }
                mp[j] = true;
                mp[arr[i] / j] = true; 
            }
        }
    }

    cout << "pairwise coprime";
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t;
    while(t--) {
    solve();
    }
}

Measured memory_bytes: 69960
// KMP法を試してみる

#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<bool> check_eq(string s, string t) {
  int s_size = s.size();
  int t_size = t.size();
  vector<bool> result(s_size - t_size + 1);

  // まずtに対して部分マッチテーブル作成
  int a[t_size+1];
  a[0] = -1;
  for (int i = 0, j = -1; i < t_size; i++) {
    while (j >= 0 && t[i] != t[j]) {
      j = a[j];
    }

    j++;
    a[i+1] = j;
  }

/*  for (const auto& aa : a) {
    cout << aa << endl;
  }
  */

  // 照合
  int m = 0, i = 0;
  while (m + i < s_size) {
    bool need_to_move_m = false;

    if (t[i] == s[m + i]) {
      i++;
      if (i == t_size) {
        result[m] = true;
        //全部見つけるので、一致した場合もmを進める
        i--;
        need_to_move_m = true;
      }
    } else {
      need_to_move_m = true;
    }

    if (need_to_move_m) {
      m = m + i - a[i];
      if (i > 0) {
        i = a[i];
      }
    }
  }
  
  return result;
}

int main() {
  string s,t,s_origin;
  cin >> s >> t;
  s_origin = s;
  int s_origin_size = s_origin.size();
  int t_size = t.size();
  
  while(s.size() < t_size + s_origin_size) {
    s += s_origin;
  }
  
  vector<bool> eqs = check_eq(s,t);
  
  int max_length = 0;
  vector<int> length(s_origin_size, -1);

  for (int i = 0; i < s_origin_size; i++) {
    if (length[i] != -1) {
      continue;
    }

    if (!eqs[i]) {
      length[i] = 0;
      continue;
    }

    int current = i;
    int diff = 0;
    queue<int> q;
    while(eqs[current]) {
      if (!q.empty() && i == current) {
        // 無限に一致する
        max_length = -1;
        goto finish;
      }

      if (length[current] != -1) {
        diff = length[current]; // すでに到達済みの場合、計算済みの長さを加えて終了する
        break;
      }
      length[current] = 0; // 一旦到達マーク設定
      q.push(current);
      current = (current + t_size) % s_origin_size;
    }

    max_length = max(max_length, diff + (int)q.size());

    while(!q.empty()) {
      int len = q.size();
      int current = q.front();
      q.pop();
      length[current] = len + diff; // 正確な長さで上書き
    }
  }

finish:
  cout << max_length << endl;
  
  return 0;
}


Measured memory_bytes: 8824
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for(int &ai: a) cin >> ai;
  vector<int> c(N, 0);
  int M=0;
  for(int i=N; i>0; i--){
    c[i-1]=a[i-1];
    for(int j=i*2; j<=N; j+=i){
      c[i-1] = (c[i-1]+c[j-1])%2;
    }
    if(c[i-1]==1) M++;
  }
  cout << M << endl;
  bool first=true;
  for(int i=0; i<N; i++){
    if(c[i]==1){
      if(first) first=false;
      else cout << " ";
      cout << i+1;
    }
  }
  if(!first) cout << endl;
  return 0;
}

Measured memory_bytes: 2432
#include<stdio.h>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
struct node
{
    string s;
    int x;
    int y;
}a[105];
int cmp(node p,node q)
{
    if(p.s==q.s) return p.x>q.x;
    else return p.s<q.s;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        cin>>a[i].s>>a[i].x;
        a[i].y=i+1;
    }
    sort(a,a+n,cmp);
    for(int i=0; i<n; i++)
    {
        printf("%d\n",a[i].y);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i = 0;i<n;i++)

int a[100000];
using namespace std;
int main(){
  int n;
  cin >> n;
  for(int i = 0;i<n;i++){
    int t;
    cin >> t;
    a[t]++;
  }
  if(n%2==1){
    if(a[0]!=1){
      cout << 0 << endl;
      return 0;
    }
    for(int i = 2;i<n;i+=2){
      if(a[i]!=2){
        cout << 0 << endl;
        return 0;
      }
    }
  }else{
    for(int i = 1;i<n;i+=2){
      if(a[i]!=2){
        cout << 0 << endl;
        return 0;
      }
    }
  }
  long long ans = 1;
  for(int i = 0;i<n/2;i++){
    ans *= 2;
    ans %= 1000000007;
  }
  cout << ans << endl;

  return 0;

}


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


int main(){
	int A1,A2,A3;
  	cin >> A1 >> A2 >> A3;
  	if(A1+A2+A3>= 22) cout << "bust" << endl;
  	else cout << "win" << endl;
  	return 0;
}


Measured memory_bytes: 3568
//Use valgrind once if the submission doesn't go through. It can detect uninitialized variables and see where they could be an issue.
#include <bits/stdc++.h>
#include <numeric>
#include <ext/pb_ds/assoc_container.hpp>
#define MOD 1000000007
using namespace __gnu_pbds;
using namespace std;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){

	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);

	long long n,pr=1,p0=1,p9=1,pb=1;
	cin>>n;
	while(n--){
		pr*=10;
		pr%=MOD;
		p0*=9;
		p0%=MOD;
		p9*=9;
		p9%=MOD;
		pb*=8;
		pb%=MOD;
	}
	pr-=p0+p9;
	pr+=pb;
	while(pr<0){
		pr+=MOD;
	}
	cout<<pr%MOD<<endl;
}


Measured memory_bytes: 3648
N, M, X = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(N)]
ans = float('inf')
for i in range(2**N):
    tca = [0]*(M+1)
    for j in range(N):
        if i & (1 << j) > 0:
            for k in range(M+1):
                tca[k] += ca[j][k]
    if min(tca[1:]) >= X:
        ans = min(ans, tca[0])

if ans != float('inf'):
    print(ans)
else:
    print(-1)


Measured memory_bytes: 68496
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,d;
      cin>>m>>d;

      int p1=d/10;
       int p2=d % 10;
           int c=0;

            if(p2!=0)
          {
        for(int i=2;i<=p1;i++)
        {
            if(i==p1)
            {
           for(int j=2;j<=p2;j++)
             if(i*j <= m) c++;
           }
            else
            {
              for(int j=2;j<=9;j++)
                if(i*j <= m) c++;
            }
        }
        cout<<c;
      }
        else
        {
          for(int i=2;i<p1;i++)
          {
             for(int j=2;j<=9;j++)
               if(i*j <= m) c++;
          }
          cout<<c;
        }
}


Measured memory_bytes: 256
a, b, c, d = gets.split.map(&:to_i)

aoki_turn = (c%b == 0 ? c/b : c/b + 1)
takahashi_turn = (a%d == 0 ? a/d : a/d + 1)

if takahashi_turn >= aoki_turn
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 14356
#include<iostream>
#include<stdio.h>

int main()
{
	int h, w;
	bool first = true;
	while (true)
	{
		std::cin >> h >> w;
		if (h == 0 && w == 0)break;

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
			    if(i%2==0)
			    {
			        if(j%2==0) std::cout << "#";
			        if(j%2==1) std::cout << ".";
			    }
			    else
			    {
			        if(j%2==0) std::cout << ".";
			        if(j%2==1) std::cout << "#";			        
			    }
			}
			std::cout << "\n";
		}
		std::cout << "\n";
	}
}


Measured memory_bytes: 3100