akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

ll gcd(ll a,ll b){
    if(b ==0) return a;
    return gcd(b,a%b);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h,w,n,ans[20]={};
    map<pll,ll> mp;
    cin>>h>>w>>n;
    ans[0]=(h-2)*(w-2);
    cout<<endl;
    rep(i,n){
        ll a,b;
        cin>>a>>b;
        rep(j,9){
            ll L=b-2,cnt=0;
            if(j<3){
                if(a-2<1) continue;
                if(L+j<1 || L+j+2>w) continue;
                rep(k,3){
                    rep(l,3){
                        if(mp[pll(a-2+k,L+j%3+l)]>0) cnt++;
                    }
                }
            } else if(3<=j && j<6){
                if(a-1<1 || a+1>h) continue;
                if(L+j%3<1 || L+j%3+2>w) continue;
                rep(k,3){
                    rep(l,3){
                        if(mp[pll(a-1+k,L+j%3+l)]>0) cnt++;
                    }
                }
            } else{
                if(a<1 || a+2>h) continue;
                if(L+j%3<1 || L+j%3+2>w) continue;
                rep(k,3){
                    rep(l,3){
                        if(mp[pll(a+k,L+j%3+l)]>0) cnt++;
                    }
                }
            }
            ans[cnt]--;
            ans[cnt+1]++;
            // cout<<i<<" "<<j<<" "<<cnt<<endl;
        }
        mp[pll(a,b)]++;
    }
    rep(i,10){
        cout<<ans[i]<<endl;
    }
    return 0;
}

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

int n, ds[200009], a[200009], ra[200009];
pair<int, int> r[200009];

int uf(int n)
{
	if (n == ds[n]) return n;
	return ds[n] = uf(ds[n]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ra[a[i]] = i; ds[i] = i; r[i].first = r[i].second = i;
	}
	long long ans = 0;
	for (int i = n; i >= 1; i--) {
		int da = uf(ra[i]);
		if (ra[i] > 1 && a[ra[i] - 1] > a[ra[i]]) {
			int ta = uf(ra[i] - 1);
			if (ta != da) {
				r[da] = make_pair(r[ta].first, r[da].second);
				ds[ta] = da;
			}
		}
		if (ra[i] < n && a[ra[i] + 1] > a[ra[i]]) {
			int ta = uf(ra[i] + 1);
			if (ta != da) {
				r[da] = make_pair(r[da].first, r[ta].second);
				ds[ta] = da;
			}
		}
		ans += 1LL * (ra[i] - r[da].first + 1) * (r[da].second - ra[i] + 1) * i;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 4224
import sys
from operator import itemgetter


def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i


def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
lr = list(map(int, sys.stdin.buffer.read().split()))
lll = lr[0::2]
rrr = lr[1::2]
idx = sorted(enumerate(rrr), key=itemgetter(1))

bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for i, r in idx:
    while p < r:
        c = ccc[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1

    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, lll[i])

print('\n'.join(map(str, ans)))


Measured memory_bytes: 228376
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
using namespace std;
 
const ll N =(1e5+5);
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ll LOG = 29;

long long binpow(long long a, long long b) {
     a %= MOD;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%MOD ;
        a = (a * a)%MOD ;

        
        b >>= 1;
    }
    res%=MOD;
    return res;
}
void solve(){
    ll n,k;
    cin>>n>>k;
    ll a[n+1];
    for(int i =1;i<=n;i++){
        cin>>a[i];
    }
    ll ans = 0;
    ll ans2 = 0;
    for(int i =1;i<=n;i++){
        for(int j =1;j<=n;j++){
            if(a[i] > a[j]){
                ans2++;
               if(i<j) ans++;
            }
        }
        
    }
    ans = (ans*k)%MOD;
    if(ans<0)ans+=MOD;
    ll gg = k*(k-1);gg/=2ll;
    gg%=MOD;
    
    ans2 = (ans2 * gg)%MOD;
    if(ans2<0)ans2+=MOD;
    ans2%=MOD;
    ans = (ans+ans2)%MOD;
    if(ans<0)ans+=MOD;
    ans%=MOD;   
    cout<<ans<<endl;
}



int main()
{
    ios_base::sync_with_stdio(0);
     cin.tie(NULL);
     
    ll t=1;
    while(t--){
        solve();
    }
     
 
 
    return 0;     
    
        
}

Measured memory_bytes: 256
def isp(n):
  for i in range(2, int(n**(1/2))+1):
    if n % i == 0:
      return False
  return True    

N = int(input())
prime = []
ans = 1
mod = 10 ** 9 + 7

for i in range(2, N+1):
  if isp(i):
    prime.append(i)
A = [1] * len(prime)

for i in range(2, N+1):
  n = i
  for j in range(len(prime)):
    p = prime[j]
    while n % p == 0:
      n = n//p
      A[j] += 1
for a in A:
  ans = ans * a % mod
#print(A)
print(ans)

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

class Task{
  private:
  int age;
  int n;
  int m;
  int border;
  vector<int>* array;

  public:
  Task(int age, int n, int m, int border, vector<int>* array) 
  :age(age), n(n), m(m), border(border), array(array){
  }

  vector<int>* getArray(){
    return array;
  }

  void nextReq(stack<Task*>* stk){
    for(int i = border; i <= m; i++){
      auto* newArr = new vector<int>(*array);
      newArr->push_back(i);
      stk->push(new Task(age + 1, n, m, i, newArr));
    }
  }

  int getAge(){
    return age;
  }
};


signed main(){
  int n, m, q;
  cin >> n >> m >> q;
  stack<Task*>* stk = new stack<Task*>();
  vector<vector<int>> allVecs;
  
  for(int i = 1; i <= m; i++){
      vector<int>* arr = new vector<int>();
      arr->push_back(i);
      stk->push(new Task(2, n, m, i, arr));
  }

  while(!stk->empty()){
    auto* currTask = stk->top();
    stk->pop();
    if(currTask->getAge() <= n){
      currTask->nextReq(stk);
    }else{
      allVecs.push_back(*(currTask->getArray()));
    }
  }

  vector<long> scores;
  vector<vector<int>> scoreTuples;
  for(int i = 0; i < q; i++){
    int a, b, c, score;
    cin >> a >> b >> c >> score;
    scores.push_back(score);
    vector<int> scoreTuple;
    scoreTuple.push_back(a);
    scoreTuple.push_back(b);
    scoreTuple.push_back(c);
    scoreTuples.push_back(scoreTuple);
  }

  long maxScore = -1;
  for(int i = 0; i < allVecs.size(); i++){
    long score = 0;
    auto vec = allVecs[i];

    for(int j = 0; j < q; j++){
      auto tuple = scoreTuples[j];
      
      if(vec[tuple[1] - 1] - vec[tuple[0] - 1] == tuple[2]){
        score += scores[j];
      }
    }

    if(maxScore == -1 || maxScore < score){
      maxScore = score;
    }
  }

  cout << maxScore << endl;
}

Measured memory_bytes: 35032
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const long long INF = 1LL << 60;

int main(void)
{

	int N;
	cin >> N;
	vector<long long> h(N);
	for (auto &x : h){
		cin >> x;
	}

	vector<long long> dp(N, INF);
	dp[0] = 0;
	for (int i = 0; i < N - 1; i++){
		dp[i + 1] = min(abs(h[i] - h[i + 1]) + dp[i], dp[i + 1]);
		if(i < N-2) 
			dp[i + 2] = min(abs(h[i] - h[i + 2]) + dp[i], dp[i + 2]);
		//cout << dp[i + 1] << endl;
	}

	cout << dp[N - 1] << endl;
	return 0;
}

Measured memory_bytes: 1792
a,b=map(int,input().split())
l1=[1,3,5,7,8,10,12]
l2=[2]
l3=[4,6,9,11]
if (a in l1 and b in l1) or (a in l2 and b in l2) or (a in l3 and b in l3):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
def main():
    N = int(input())
    remainder = N % 1000
    quotient = int(N / 1000)
    ans = 0
    if N < 1000:
        ans = 1000 - N
    elif remainder == 0:
        ans = 0
    elif remainder > 0:
        ans = 1000 - remainder

    print(f'{ans}')


if __name__ == '__main__':
    main()

Measured memory_bytes: 9172
s = input()
now = ">"
count = 0
result = 0
temp = 0
for c in s:
    if now == ">" and c == "<":
        now = "<"
        if temp < count:
            result += count
        else:
            result += temp
        count = 1
    elif now == "<" and c == ">":
        now = ">"
        temp = count
        count = 1
    else:
        result += count
        count += 1

if c == ">":
    if temp < count:
        result += count
    else:
        result += temp
else:
    result += count
print(result)


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

string grade(int m, int f, int r){
  if(m == -1 || f == -1) { return "F"; }
  if(m + f >= 80) { return "A"; }
  if(m + f >= 65) { return "B"; }
  if(m + f >= 50) { return "C"; }
  if(m + f < 30) { return "F"; }
  if(r >= 50) { return "C"; }
  return "D";
}

int main(){
  int m, f, r;
  for(;;){
    cin >> m; cin >> f; cin >> r;
    if(m == -1 && f == -1 && r == -1) { break; }
    cout << grade(m, f, r) << endl;
  }
  return 0;
}

Measured memory_bytes: 1192
import sys
s=input()
count =0
isSuccession = True #True:1 False:0
for i in range(len(s) -1):
    if s[i] != s[i+1]:
        if isSuccession == False:
            count +=1
    else:
        isSuccession = (isSuccession+1)%2
        if isSuccession == False:
            count +=1
print(min(count, len(s) - count))
                

Measured memory_bytes: 3188
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
a_sum = sum(a)
a_count = Counter(a)

for i in range(q):
    b, c = map(int, input().split())
    a_sum = a_sum + (c - b)*a_count[b]
    if a_count[c]:
        a_count[c] += a_count[b]
        a_count[b] = 0
    else:
        a_count[c] = a_count[b]
        a_count[b] = 0
    print(a_sum)


Measured memory_bytes: 24060
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef  long long  ll;
const int maxn = 2e5 + 5;
int n, q;
ll a, t[maxn], ans[maxn];
vector<ll> v;
int main() {
    scanf("%d %d",&n,&q);
    v.push_back(n);//!!!
    for (int i=0; i<q; i++) {
        scanf("%lld",&a);
        while (v.size() && v.back() >= a)
            v.pop_back();
        v.push_back(a);
    }
    if ( q== 0) {
        for (int i=0; i<n; i++) puts("1");
        return 0;
    }
    //for (int i=0; i<v.size(); i++) cout<<v[i]<<"  ";
    t[v.size() - 1] = 1;
    for (int i=v.size()-1; i>=0; i--) {
        ll k = v[i];
        //cout<<endl<<i<<" : \n";
        while (k > v[0]) {
            int j = lower_bound(v.begin(), v.end(), k) - (v.begin() + 1);
            t[j] += k / v[j] * t[i];
            //cout<<k<<" "<<j<<" : "<<v[j]<<" "<<t[j]<<" "<<t[i]<<endl;
            k %= v[j];
        }
        ans[k] += t[i];
    }
    for (int i=n-1; i>=1; i--) ans[i] += ans[i+1];
    for (int i=1; i<=n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

Measured memory_bytes: 4212
#include <iostream>
#include <string>

using namespace std;

int main() {
    while (true) {
        string S;
        cin >> S;
        if (S == "-") break;

        int N = S.size();

        int M;
        cin >> M;

        for (int i = 0; i < M; ++i) {
            S += S;
            int h;
            cin >> h;
            S = S.substr(h, N);
        }

        cout << S << endl;
    }
    return 0;
}


Measured memory_bytes: 3236
#!/usr/bin/env python3
#diverta B

import sys

def main():
	N = int(input())
	xy = []
	for i in range(N):
		x, y = map(int, input().split(" "))
		xy.append((x, y))

	if N == 1:
		print(1)
		sys.exit()

	re = {}
	for i, val in enumerate(xy):
		x, y = val
		for j, vol in enumerate(xy):
			if i == j:
				continue
			nx, ny = vol
			p = nx - x
			q = ny -y
			if (p, q) in re:
				re[(p, q)] += 1
			else:
				re[(p, q)] = 1


	ans = N - max(re.values())

	print(ans)


if __name__ == "__main__":
	main()

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;



int main(void) {
  ll N;
  cin >> N;
  ll i, j;
  
  P p[MAX];
  for(i=0; i<N; i++) {
    ll a, b;
    cin >> a >> b;
    p[i]={a+b, a};
  }
  sort(p, p+N);
  reverse(p, p+N);
  
  ll ans=0;
  for(i=0; i<N; i++) {
    if((i&1)==0) ans+=p[i].second;
    else ans-=p[i].first-p[i].second;
  }
  
  pt(ans);
}


Measured memory_bytes: 1792
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
//const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int N, M;
pii B[100010];

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	rep(i, 0, N)
	{
		cin >> B[i].first >> B[i].second;
	}

	sort(B, B + N);

	priority_queue<int> pq;
	int ans = 0;
	int bi = 0;
	rep(i, 1, M + 1)
	{
		while (bi < N&&B[bi].first == i)
		{
			pq.push(B[bi].second);
			bi++;
		}
		if (!pq.empty())
		{
			int v = pq.top();
			pq.pop();
			ans += v;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
ll k,a,b;
int main(){
	cin>>k>>a>>b;
	if(b-a <= 2){
		cout << k+1 << endl;
	}
	else{
		if(a-1 >= k){
			cout << k+1 << endl;
		}
		else{
			ll zan = k-(a-1);
			ll ans = a;
			ans += (zan/2) * (b-a);
			if(zan%2 == 1) ans++;
			cout << ans << endl;
		}
	}
}

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

int main() {
    int n;
    cin >> n;
    double x[n], y[n];
    double sum = 0.0;
    for(int i=0; i<n; i++) cin >> x[i] >> y[i];
    for(int i=0; i<n-1; i++) {
        for(int j=i+1; j<n; j++) {
            sum += sqrt(pow(x[i]-x[j], 2) + pow(y[i]-y[j], 2));
        }
    }
    cout << fixed << setprecision(10) << sum * 2 / n << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int n;
	scanf("%d",&n);
	int x[100]; int i;
	for(i=0;i<n;i++){
		scanf("%d",&x[i]);
	}
	for(i=n-1;i>0;i--){
		printf("%d ",x[i]);
	}
	printf("%d",x[0]);
	printf("\n");
	return 0;
}


Measured memory_bytes: 2036
n, Lxy = int(input()),\
         [abs(x - y) for x, y in zip( list(map(int, input().split())),
                                      list(map(int, input().split())) )]
print(sum(Lxy))
print((sum([d**2 for d in Lxy])**(1/2)))
print((sum([d**3 for d in Lxy])**(1/3)))
print(max(Lxy))

Measured memory_bytes: 7852
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <math.h>
#include <assert.h>
#include <set>
#include <map>
#include <bitset>
#include <ctime>
#include <time.h>
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <stack>
#include <ctype.h>
#include <numeric>
#include <sstream>
#include <unistd.h>
#include <unordered_map>
#include <limits>
const int oo = 1 << 30;
using namespace std;


int main(){
    // freopen("/Users/deepsajeda/Documents/FIRST/in", "r", stdin);
    // freopen("/Users/deepsajeda/Documents/FIRST/out", "w", stdout);

    int n;
    int K;
    scanf("%d %d", &n, &K);
    vector<int> arr(n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &arr[i]);
    }
    vector<int> dp(n + 1, oo);
    dp[0] = 0;
    for(int i = 1; i < n; ++i){
        for(int j = 1; j <= K && j <= i; ++j){
            dp[i] = min(dp[i], dp[i - j] + abs(arr[i] - arr[i - j]));
        }
    }
    printf("%d\n", dp[n - 1]);
}
//printf("%.5f\n", clock() / (float)CLOCKS_PER_SEC); time in seconds


Measured memory_bytes: 1024
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s = input()
    ok = False
    if s[0] == 'A':
        cnt_C = 0
        for i in s[2:-1]:
            if i=='C':
                cnt_C += 1
        if cnt_C == 1:
            cnt_up = 0
            for i in s:
                if i != i.lower():
                    cnt_up+= 1
            
            if cnt_up == 2:
                ok = True
    
    if ok:
        print('AC')
    else:
        print('WA')


solve()


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

typedef pair<int,int> P;
const int MAX_W = 20;
const int MAX_H = 20;
const int MAX_N = 10;
const int INF  = 1e+8;

int w, h;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int d[MAX_H][MAX_W];
int g[MAX_N][MAX_N];

void debug(int n){
	cout << "[debug]" << endl;
	for(int i=0 ; i < n ; i++ ){
		for(int j=0 ; j < n ; j++ ){
			if( g[i][j] == INF )
				cout << -1 << "  ";
			else
				cout << g[i][j] << "  ";
		}
		cout << endl;
	}
	cout << endl;
}

void init(){
	for(int i = 0 ; i < MAX_N ; i++ ){
		for(int j = 0 ; j < MAX_N ; j++ ){
			g[i][j] = INF;
		}
	}
}

void clear_d(){
	for(int y=0 ; y < MAX_H ; y++ ){
		for(int x= 0 ; x < MAX_W ; x++ ){
			d[y][x] = INF;
		}
	}
}

// 文字 c がある座標の位置を求める
void search(const vector<string>& m, vector<P>& vp, char c){
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			if( m[y][x] == c ){
				vp.push_back( P(x,y) );
			}
		}
	}
}

// spから汚れたタイルまでの距離を調べる
void bfs(const vector<string>& m, P sp, map<P,int> f){
	d[sp.second][sp.first] = 0;
	queue<P> q;
	q.push( sp );
	while( !q.empty() ){
		P p = q.front(); q.pop();
		int cnt = d[p.second][p.first];
		for(int i=0 ; i < 4 ; i++ ){
			int mx = p.first + dx[i];
			int my = p.second + dy[i];
			if( mx < 0 || my < 0 || mx >= w || my >= h || m[my][mx] == 'x' ){
				continue;
			}
			if( d[my][mx] == INF ){
				if( m[my][mx] == '*' ){
					int u = f[sp];
					int v = f[P(mx,my)];
					g[u][v] = g[v][u] = cnt + 1;
				} 
				d[my][mx] = cnt + 1;
				q.push( P(mx,my) );
			}
		}
	}
}

int main(){
	while( cin >> w >> h , w || h ){
		// 初期化
		init();
		// m[y][x] := (x,y)の状態
		vector<string> m(h);
		// vp[i] := i 番目の汚れたタイルの座標
		vector<P> vp;
		// f[p] := 座標 p と対応する i を返す (i番目の汚れたタイル)
		map<P,int> f;
		
		// 入力
		for(int y=0 ; y < h ; y++ ){
			cin >> m[y];
		}
		// スタート地点と汚れたタイルの位置を調べる
		search( m , vp , '*' );
		search( m , vp , 'o' );
		for(int i=0 ; i < vp.size() ; i++ ){
			f[ vp[i] ] = i;
		}
		// 各汚れたタイル同士の距離を調べる
		for(int i=0 ; i < vp.size() ; i++ ){
			clear_d();
			bfs( m , vp[i] , f );
		}
		//debug( vp.size() );
			
		// dp[s][v] := s は訪れたかどうかのbit列, v は最後に訪れたマス
		int dp[1<<10][10];
		int N = vp.size() - 1;
		// 初期化
		for(int i=0 ; i < (1<<N) ; i++ ){
			for(int j=0 ; j < N ; j++ ){
				dp[i][j] = INF;
			}
		}
		// スタートから i までの距離
		int start = N;
		for(int i=0 ; i < N ; i++ ){
			dp[1<<i][i] = g[N][i];
		}
		for(int s=0 ; s < (1<<N) ; s++ ){
			for(int u=0 ; u < N ; u++ ){
				for(int v=0 ; v < N ; v++ ){
					dp[s|1<<v][v] = min( dp[s|1<<v][v] , dp[s][u] + g[u][v]);
				}
			}
		}
		int ans = INF;
		for(int i=0 ; i < N ; i++ ){
			ans = min(ans,dp[(1<<N)-1][i]) ;
		}
		if( ans == INF )
			cout << -1 << endl;
		else
			cout << ans << endl;
	}
}

Measured memory_bytes: 956
#include <stdio.h>
#include <string.h>
int main(){
	int N, i, j, k;
	char S[102], T[102], p[204];
	scanf("%d %s %s", &N, S, T);
	j=k=0;
	for (i=0;i<2*N;i++){
		if (i%2==0) p[i]=S[j++];
		else p[i]=T[k++];
	}
	p[i]='\0';
	printf("%s\n", p);
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int dp[2][114514];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, K, a[114];
	cin>>n>>K;
	REP(i, n){
		cin>>a[i];
	}
	REP(i, a[0]){
		dp[0][i]=dp[1][i]=-1;
	}
	REP(i, K+1){
		REP(x, 2){
			int y=(x+1)&1;
			if(dp[x][i]!=0){
				continue;
			}
			bool ok=false;
			REP(j, n){
				if(i<a[j]){
					break;
				}
				if(dp[y][i-a[j]]==-1){
					ok=true;
					break;
				}
			}
			dp[x][i]=(ok ? 1 : -1);
		}
	}
	cout<<(dp[0][K]==1 ? "First" : "Second")<<'\n';
	return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n,z,w;
  cin >> n >> z >> w;
  vll a(n+1);
  a[0] = w;
  REP(i, n)
    cin >> a[i+1];

  ll x[n+1][n+1],y[n+1][n+1];
  REP(i, n+1){
    REP(j, n+1)
      x[i][j] = y[i][j] = 0;
  }


  REP(i, n)
    y[n][i] = x[n][i] = abs(a[n]-a[i]);

  for(ll j = n-1; j>=0; j--){
    ll newx,newy;
    newx = LLINF;
    newy = 0;
    for(ll i=j+1; i<=n; i++){
      newx = min(newx, y[i][j]);
      newy = max(newy, x[i][j]);
    }

    for(ll i=0; i<j || (i==0&&j==0); i++){
      x[j][i] = newx;
      y[j][i] = newy;
    }
  }

  cout << y[0][0] << endl;
}


Measured memory_bytes: 62848
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    a.sort(key = lambda x:-abs(x))
    p = 0
    m = 0
    for i in a:
        if i >= 0:
            p += 1
        else:
            m += 1
    f = 1
    for x in range(min(p,k)+1):
        y = k-x
        if y < 0 or y > m:
            continue
        if not y&1:
            f = 0
            break
    if f:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in a[:k]:
            ans *= i
            ans %= mod
        print(ans)
        return
    minus = []
    s = 1
    s2 = 1
    k1 = 0
    k2 = 0
    ans = 1
    if k&1:
        m = max(a)
        for i in range(n):
            if a[i] == m:
                break
        a = a[:i]+a[i+1:]
        ans *= m
        k -= 1
    for i in a:
        if i < 0:
            k1 ^= 1
            s *= -i
            if not k1:
                minus.append(s)
                s = 1
        else:
            k2 ^= 1
            s2 *= i
            if not k2:
                minus.append(s2)
                s2 = 1
    x = k>>1
    minus.sort(reverse = True)
    for m in minus[:x]:
        ans *= m
        ans %= mod
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 113692
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pll pair<ll,ll>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define bp __builtin_popcountll
#define MOD  1000000007
#define MOD1 1000000006
const int N = 10000005;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));
ll divi[N];
void solve()
{
    for(ll i=1;i<N;i++)
    {
        for(ll j=i;j<N;j+=i)   divi[j]++;
    }
    ll n;
    cin >> n;
    ll ans = 0;
    for(ll i=1;i<=n;i++)
    {
        ans += i*divi[i];
    }
    cout<<ans;
}

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

Measured memory_bytes: 81772
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>
#include <stdio.h>
#include <sstream>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const ll mod = 1e9 + 7;
const ll inf = 1LL << 60;
const long double pi = 3.14159265358979323846;

// ****************************************CODE***************************************//

ll n, m;
vector<vector<ll> > g;
vector<ll> num;
ll dp[100100];

int main() {
    cin >> n >> m;
    g.assign(n, vector<ll>());
    num.assign(n, 0);
    for(int i = 0; i < m; i++){
        ll x, y; cin >> x >> y; x--; y--; g[x].push_back(y); num[y]++;
    }

    queue<ll> que;
    for(int i = 0; i < n; i++) if(num[i] == 0) que.push(i);

    while(!que.empty()){
        ll i = que.front(); que.pop();
        for(auto j: g[i]){
            num[j]--;
            if(num[j] == 0) {
                que.push(j);
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }

    ll res = 0;
    for(int i = 0; i < n; i++) res = max(res, dp[i]);
    cout << res << endl;
}

Measured memory_bytes: 7296
#include<bits/stdc++.h>
 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i,n) for(int i = 0; i < n; i++)
#define for1(i,n) for(int i = 1; i <= n; i++)
#define ford(i,n) for(int i = n-1; i >= 0; i--)
#define fore(i,a,b) for(int i = a; i <= b; i++)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
 
 
const  int MAXn= 3e5+5;
const  long long INF= 1e18;
const long long mod= 1e9+7;
 
 
int main(){
		ll h ;
		cin >> h;
		ll temp = 1;
		ll ans = 0;
		while(h){
			h /= 2;
			ans += temp;
			temp = temp * 2;
		}
		cout << ans;
	}
			


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int DP[3002][3002];
string S,T,LCS;
void Print()
{
  int i=S.length(),j=T.length();
  while(i&&j)
  {
    if(S[i-1]==T[j-1])
    {
      LCS+=S[i-1];
      i--;
      j--;
    }
    else
    {
      if(DP[i-1][j]>DP[i][j-1])
        i--;
      else	j--;
    }
  }
  reverse(LCS.begin(),LCS.end());
  cout<<LCS<<endl;
  return ;
}
int main()
{
  cin>>S>>T;
  if(S.length()==1)
  {
  	for(int i=0;i<T.length();i++)
  	  if(S[0]==T[i])
  	  {
        cout<<S[0]<<endl;
        return 0;
	  }
	puts("");
	return 0;
  }
  if(T.length()==1)
  {
  	for(int i=0;i<S.length();i++)
  	  if(T[0]==S[i])
  	  {
        cout<<T[0]<<endl;
        return 0;
	  }
	puts("");
	return 0;
  }
  S+=' ';
  T+=' ';
  for(int i=0;i<S.length();i++)
  	if(T[0]==S[i])
  	  DP[i+1][1]=1;
  for(int i=0;i<T.length();i++)
  	if(S[0]==T[i])
  	  DP[1][i+1]=1;
  for(int i=1;i<S.length();i++)
  	for(int j=1;j<T.length();j++)
    {
      if(S[i]==T[j])
        DP[i+1][j+1]=max(DP[i+1][j+1],DP[i][j]+1);
      DP[i+1][j]=max(DP[i+1][j],DP[i][j]);
      DP[i][j+1]=max(DP[i][j+1],DP[i][j]);
    }
  Print();
  return 0;
}

Measured memory_bytes: 35456
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int u[maxn] , v[maxn]  , first[maxn] , nextt[maxn] , sign;
int h[maxn];
void addedge(int x , int y)
{
    u[++sign] = x;
    v[sign] = y;
    nextt[sign] = first[x];
    first[x] = sign;
}
int main()
{
    ios::sync_with_stdio(false);
    int n , m ; cin  >> n >> m;
    for (int i = 1 ; i <= n ; i++) cin >>h[i];
    for (int i = 1 ; i <= m ; i++) {
        int x , y; cin >> x >> y;
        addedge(x , y);
        addedge( y , x );
    }
    int ans = 0;
    for (int node = 1 ; node <= n ; node++){
        int flag = 1;
        for (int i = first[node] ; i && flag; i = nextt[i]){
            if (h[v[i]] >= h[node]) flag = 0;
        }
        ans += flag;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6772
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	n := scanInt()

	wl := make([]int, n)

	for i := 1; i < n; i++ {
		num := scanInt()
		wl[num-1] += 1
	}

	for i := 0; i < n; i++ {
		fmt.Println(wl[i])
	}
}

func scanInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

Measured memory_bytes: 6184
#include<stdio.h>

int main(){
  int n,i,x,y,b,p,ans,ans1;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d %d %d %d",&x,&y,&b,&p);
    
    if(b >= 5 && p >= 2){
      ans = (b*x)*0.8 + (p*y)*0.8;
      printf("%d\n",ans);
    }else{
      ans1 = (b*x)+(p*y);
      if(b<5 && p<2){
	ans = (5*x)*0.8+(2*y)*0.8;
      }else if(b < 5){
	ans = (5*x)*0.8+(p*y)*0.8;
      }else if(p<2){
	ans = (b*x)*0.8+(2*y)*0.8;
      }

      if(ans < ans1){
	printf("%d\n",ans);
      }else{
	printf("%d\n",ans1);
      }
    }
  }

  return 0;
}



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

template<class T>
void chmax(T &a, T b) {if (a < b) a = b;}

template<class T>
void chmax(T &a, initializer_list<T> init)
{
	chmax(a, *max_element(init.begin(), init.end()));
}

string s, t;
ll dp[3010][3010];

int main(int argc, char **argv)
{
	cin >> s >> t;
	ll N{(ll)s.size()}, M{(ll)t.size()};

	for (ll i = 0; i < N; ++i)
	{
		for (ll j = 0; j < M; ++j)
		{
			if (s[i] == t[j])
				chmax(dp[i+1][j+1], dp[i][j]+1);
			chmax(dp[i+1][j+1], {dp[i][j+1], dp[i+1][j]});
		}

	}

	string res;
	ll i{N}, j{M};

	while (i > 0 && j > 0)
	{
		if (dp[i][j] == dp[i][j-1])
			--j;
		else if (dp[i][j] == dp[i-1][j])
			--i;
		else if (dp[i][j] == dp[i-1][j-1]+1)
		{
			res = s[i-1] + res;
			--j, --i;
		}
	}

	std::cout << res << std::endl;
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

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

    string t, p;
    cin>>t>>p;
    int n = t.size() - p.size() + 1;
    rep(i, n) {
        string s = t.substr(i, p.size());
        if (s == p) cout<<i<<endl;
    }
}


Measured memory_bytes: 3232
n = int(input())
d, x = map(int, input().split())
a = [int(input()) for _ in range(n)]
count = 0
A = len(a)

for i in range(A):
  day = 1
  while d >= day:
    count += 1
    day = day + a[i]
    
    
print(count + x)
  

Measured memory_bytes: 3060
import java.util.*;
import java.lang.*;

class Main{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = Integer.parseInt(sc.next());
      int M = Integer.parseInt(sc.next());
      double c = 1900.0*M + 100.0*(N-M);
      double p = 1.0;
      double res = 0.0;
      double q = 1.0;
      for(int i = 0; i<M; i++) p *= 0.5;
      for(int i = 1; i<3000000; i++){
          res += i*c*p*q;
          q *= 1-p;
      }
      double eps = 0.0000001;
      int ret = (int)Math.floor(res+eps);
      System.out.println(ret);
  }
}

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

int dp[310][310];
int w[310];

int fall(int left, int right) {
    if (dp[left][right] >= 0) return dp[left][right];
    if (left==right) return dp[left][right] = 0;
    if (left + 1 == right) {
        if (abs(w[left] - w[right]) <= 1) return dp[left][right] = 2;
        else return dp[left][right] = 0;
    }

    for (int mid=left; mid<=right-1; mid++) {
        dp[left][right] = max(dp[left][right], fall(left, mid) + fall(mid+1, right));
    }

    if (right - left >= 3 && dp[left+1][right-1] == right - left - 1) {
        if (abs(w[left] - w[right]) <= 1) dp[left][right] = right - left + 1;
    }
    return dp[left][right];
}

void daruma (int N) {
    rep(i, N) cin >> w[i];
    rep(i, N) rep(j, N) dp[i][j] = -1;

    int ans = fall(0, N-1);
    cout << ans << endl;

}

int main() {
    int n;
    while (cin >> n, n != 0) {
        daruma(n);
    }

    return 0;
}


Measured memory_bytes: 3480
S = list(input())

if len(S) % 2 == 1:
  print("No")
  exit()

for i in range(len(S)):
  if i % 2 == 0:
    if S[i] != "h":
      print("No")
      break
  else:
    if S[i] != "i":
      print("No")
      break
else:
  print("Yes")

Measured memory_bytes: 3060
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;

namespace Contest
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            var a = Array.ConvertAll(Console.ReadLine().Split(), Convert.ToInt32);
            int[] S = new int[n];
            for (int i = 0; i < n; i++) S[0] += (int)Math.Pow(-1, i) * a[i];
            for (int i = 1; i < n; i++) S[i] = 2 * a[i - 1] - S[i - 1];
            Console.WriteLine(string.Join(" ", S));
        }
    }
}


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

::std::vector<::std::pair<::std::int64_t, ::std::int32_t>> primeFactors(::std::int64_t x) {
  ::std::vector<::std::pair<::std::int64_t, ::std::int32_t>> res;
  for (::std::int64_t i = 2; i*i <= x; ++i) {
    if (x % i == 0) {
      res.emplace_back(i, 1);
      x /= i;
      while (x % i == 0) x /= i, res.back().second++;
    }
  }
  if (x != 1) res.emplace_back(x, 1);
  return res;
}

::std::vector<::std::int64_t> divisors(::std::int64_t x) {
  ::std::vector<::std::int64_t> res;
  for (::std::int64_t i = 1; i*i <= x; ++i) {
    if (x % i == 0) {
      res.push_back(i);
      if (i * i != x) res.push_back(x / i);
    }
  }
  ::std::sort(res.begin(), res.end());
  return res;
}

::std::pair<::std::int64_t, ::std::int64_t> extgcd(::std::int64_t a, ::std::int64_t b) {
  ::std::pair<::std::int64_t, ::std::int64_t> pa(1, 0), pb(0, 1);
  while (b != 0) {
    ::std::swap(a, b); ::std::swap(pa, pb);
    pb = ::std::make_pair(pb.first - pa.first * (b / a), pb.second - pa.second * (b / a));
    b = b % a;
  }
  return pa;
}

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

	int64 N;
	cin >> N;
	N*=2;
	auto div = primeFactors(N);
	vector<int64> pp(div.size(), 1) ;
	int64 M = div.size();
  REP(i, M) {
    REP(j, div[i].sc)
      pp[i] *= div[i].fs;
  }
  int64 res = N-1;
  REP(i, 1 << M) {
    int64 p = 1, q = 1;
    REP(j, M) {
      if (i >> j & 1)
        p *= pp[j];
    }
    q = N / p;
    PLL ret = extgcd(p, q);
    if (ret.fs == 0 || ret.sc == 0) continue;

    chmin(res, abs(ret.fs * p));
    chmin(res, abs(ret.sc * q));
	}
	cout << res << endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> lr;

    int l = 1;
    int r = N;

    for (int i = 0; i < M; i++)
    {
        int tl, tr;
        cin >> tl >> tr;
        l = (tl > l) ? tl : l;
        r = (tr < r) ? tr : r;
    }

    cout << ((r - l + 1) > 0 ? r - l + 1 : 0) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stdio.h>
#include<ctype.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector < long long  int > a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	long long int ans = 1;
	for (int i = 1; i < n; i++)
	{
		if (a[i - 1] >= a[i])
		{
			ans++;
		}
	}
	cout << ans << endl << n << endl;
}



Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	int co = 0;
	for (int i = 0; i < min(s.size(), t.size()); i++) {
		if (s[i] < t[t.size() - i - 1]) {
			cout << "Yes" << endl;
			return 0;
		}
		if (s[i] == t[t.size() - i - 1]) {
			co++;
		}
	}
	if (min(s.size(), t.size()) == co && s < t) {
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

string solve(const string& s) {
  string ret;
  for (const auto e : s) {
    if (e == '0') {
      ret += '0';
    } else if (e == '1') {
      ret += '1';
    } else {  // 'B'
      if (!ret.empty()) ret.pop_back();
    }
  }
  return ret;
}

int main() {
  string s;
  cin >> s;
  cout << solve(s) << endl;
}


Measured memory_bytes: 256
long A,x,i,j,d[2][5001];main(n){for(scanf("%d%d",&n,&A),d[0][A*n]=1;~scanf("%ld",&x);i=!i)for(x-=A,j=-1;j++<2*A*n;)d[!i][j]=d[i][j]+(j-x<0|j-x>2*A*n?0:d[i][j-x]);printf("%ld\n",d[i][A*n]-1);}

Measured memory_bytes: 256
#include <bits/stdc++.h>  // ver2.2.3
#define int long long
#define endl "\n"
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define VVi vector<Vi>
#define Vs vector<string>
#define Pii pair<int,int>
#define VPii vector<Pii>
#define Tiii tuple<int,int,int>
#define PQi priority_queue<int>
#define PQir priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define itos to_string
#define stoi stoll
#define FI first
#define SE second
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define sortr(v) sort(v,greater<>())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define dem(a,b) ((a+b-1)/(b))
#define Vin(a) rep(iI,0,a.size())cin>>a[iI]
#define Vout(a) rep(lZ,0,a.size()-1)cout<<a[lZ]<<' ';cout<<a.back()<<endl
#define VVout(a) rep(lY,0,a.size()){Vout(a[lY]);}
#define VPout(a) rep(lX,0,a.size())cout<<a[lX].FI<<' '<<a[lX].SE<<endl
#define Verr(a) rep(iZ,0,a.size()-1)cerr<<a[iZ]<<' ';cerr<<a.back()<<endl
#define VVerr(a) rep(iY,0,a.size()){Verr(a[iY]);}
#define VPerr(a) rep(iX,0,a.size())cerr<<a[iX].FI<<' '<<a[iX].SE<<endl
#define INF 3000000000000000000  //  3.0*10^18(MAXの1/3くらい)
#define MAX LLONG_MAX
#define MOD 1000000007  //  10^9 + 7
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm
void press(auto &v){v.erase(unique(ALL(v)),v.end());}  //  圧縮
int mypow(int x, int n, int m){  //  累乗x^n(mod m)  O(log(n))
if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}



signed main() {
  cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(12);
  int n,m;
  cin >> n >> m;
  Vi a(n);
  int qw,er,ty;
  rep(i,0,n){
    cin >> a[i];
    a[i] %= m;
  }
  rep(i,0,n-1){
    a[i+1] = a[i] + a[i+1];
    a[i+1] %= m;
  }
  Verr(a);
  int ans = count(ALL(a),0);
  map<int,int> kind;
  rep(i,0,n){
    kind[a[i]]++;
  }
  for (auto p : kind ) {
    auto k = p.first;
    auto v = p.second;
    ans += v*(v-1)/2;
    cerr << k << " => " << v << endl;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		String s = in.next();
		if(s.charAt(k-1)=='A') System.out.println(s.substring(0, k-1)+"a"+s.substring(k,n));
		else if(s.charAt(k-1)=='B') System.out.println(s.substring(0, k-1)+"b"+s.substring(k,n));
		else if(s.charAt(k-1)=='C') System.out.println(s.substring(0, k-1)+"c"+s.substring(k,n));
		in.close();
	}

}


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

#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                                                       \
    for(long long hoge = 0; (hoge) < (n); ++(hoge))                            \
    cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
const ll INF = LLONG_MAX / 2;
const ll MOD = 1e9 + 7;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int N, Y;
    cin >> N >> Y;
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= N - i; j++) {
            int k = N - i - j;
            if(10000 * i + 5000 * j + 1000 * k == Y) {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}

Measured memory_bytes: 256
def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk
n,k=map(int,input().split())
MOD=10**9+7
print(n-k+1)
if n==1:
    exit()
for i in range(2,k+1):
    ans=comb(n-k+1,i)*comb(k-1,i-1)
    print(ans%MOD)

Measured memory_bytes: 74448
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105],sum[105];
int main(){
	int n,ans=1e9;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		ans=min(ans,abs(sum[n]-2*sum[i]));
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    string a,b,c; cin>>a>>b>>c;
    char A,B,C;
    A=a[0]-32;
    B=b[0]-32;
    C=c[0]-32;
    cout<<A<<B<<C<<endl;
}


Measured memory_bytes: 256
/*
author: Apoorv Singh
*/

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

typedef vector <int> vi;
typedef vector <long long> vl;
typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
#define ll long long
#define eb emplace_back   
#define all(c) c.begin(), c.end()
#define watch(x) cout << (#x) << " " << (x) << endl;
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second

ll modulo = 1e9 + 7;

template <class X>

void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

ll fpow(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a)%modulo;
        a = (a*a)%modulo;
        n = n >> 1;
    }
    return ans;
}

/*
const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}
*/

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    ll arr[n];
    FOR(i,0,n)
        cin >> arr[i];
    ll gcd = arr[0];
    FOR(i,1,n)
        gcd = __gcd(arr[i], gcd);
    cout << gcd << endl;
    return 0;
}

Measured memory_bytes: 1024
n,m = map(int,input().split())
s = [[0]*n for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
#    print(a,b)
    s[a-1][b-1] += 1
    s[b-1][a-1] += 1
#    print(s)

for i in range(n):
    print(sum(s[i]))

"""
以下の指定では、一度の値変更で、全ての要素の該当部分の数値が一斉に変わる。
http://delta114514.hatenablog.jp/entry/2018/01/02/233002
n,m = map(int,input().split())
s = [[0]*n]*n
"""


Measured memory_bytes: 3060