akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define REP(i,a) for (int i = 0;i < (a);++i)
#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 ALL(obj) (obj).begin,(obj).end()
#define SORT(list) sort(ALL((list)));
using namespace std;
using ll = long long;
int main(){
    int r,g;
    cin >> r >> g;
    cout << 2*g-r << endl;
    return 0;
}

Measured memory_bytes: 256
import math
import sys

sa = list(sys.stdin.readline().rstrip())
sb = list(sys.stdin.readline().rstrip())
sc = list(sys.stdin.readline().rstrip())
turn = "a"
while (1):
    # print(turn)
    if turn == "a":
        if len(sa) == 0:
            print("A")
            break
        turn = sa.pop(0)
    elif turn == "b":
        if len(sb) == 0:
            print("B")
            break
        turn = sb.pop(0)
    elif turn == "c":
        if len(sc) == 0:
            print("C")
            break
        turn = sc.pop(0)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define     siii(a,b,c)       scanf("%d%d%d",&a,&b,&c)
#define     si(a)             scanf("%d",&a)
#define     sii(a,b)          scanf("%d%d",&a,&b)
#define     sl(a)             scanf("%lld",&a);
#define     sll(a,b)          scanf("%lld%lld",&a,&b);
#define     slll(a,b,c)       scanf("%lld%lld%lld",&a,&b,&c);
#define     sd(a)             scanf("%lf",&a);
#define     sdd(a,b)          scanf("%lf%lf",&a,&b);
#define     pb(a)             push_back(a)
#define     deb(a)            printf("### %d ###\n",a)
#define     mp                make_pair
#define     pf                printf
#define     fl(a, b, c)       for(int a= b ;a<c;a++)
#define     mx                100000 //10^5
#define     fread             freopen("input.txt","r",stdin)
#define     fwrite            freopen("output.txt","w",stdout)
#define     CLR(a,b)          memset(a,b,sizeof(a))
#define     ll                long long
#define     D(x)              cout<<#x" = "<<x<<endl;
#define     sz                10000
#define     bl                printf("\n")
#define     spc               printf(" ")
#define     pCase(a)          printf("Case %d: ",a)

ll mod =1e9 + 7;

int arr[mx+10];
int main()
{
    int n;
    si(n);

    //bool flag = false;
    fl(i,1,n+1)
    {
        arr[abs(n-i-(i-1))]++;
    }
    fl(i,0,n)
    {
        int dif;
        si(dif);
        arr[dif]--;
        if(arr[dif]<0)
        {
            printf("0\n");
            return 0;
        }
    }
    ll ans = 1;
    fl(i,0,n/2)
    {
        ans= ans*2%mod;
    }
    printf("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 640
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	var result bool
	if s[0] == s[1] && s[2] == s[3] {
		result = true
	}
	if s[0] == s[2] && s[1] == s[3] {
		result = true
	}
	if s[0] == s[3] && s[1] == s[2] {
		result = true
	}
	if s[0] == s[1] && s[1] == s[2] {
		result = false
	}
	if result {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#include<utility>
#include <algorithm>
#include<iterator>
#define  go return 0
#define pb push_back
#define lp(j, n)  for(int j=0; j<(int)(n); ++j)
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v)   ((v).begin()), ((v).end())
#define sz(v)    ( (int)((v).size()) )
#define F first
#define S second
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int,string> > vpii;
typedef map<int, int> mii;
const ll N=1e5+5;
ll arr[N],A[N]  ;
//bool visited[N]={} , cnt[N]={};
int main()
{

 int n,m,p,c1=0,c2=0;
  int visited[100005] = {};
  int cnt[100005] = {};
 string s;
 cin>>n>>m;
 for(int i=0 ; i<m ; i++)
 {
     cin>>p>>s;
     if(s=="AC" && visited[p]==0 )
     {
         c1++ , c2+=cnt[p] , visited[p]=1;
     }
     else if(s=="WA" && visited[p]==0)
     {
            cnt[p]++;
     }

 }
 cout<<c1<<" " <<c2;

 go;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N,M;
  cin >> N >> M;
  cout << N*(N-1)/2 + M*(M-1)/2 << endl;
  return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
    string at, s, co;
    cin >> at >> s >> co;
    cout << at[0] << s[0] << co[0] << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    long wt;
    cin >> n >> wt;
    long w0, w[n], v[n];
    cin >> w0 >> v[0]; w[0] = 0;
    for (int i=1; i<n; i++) {
        cin >> w[i] >> v[i];
        w[i] -= w0;
    }
    long dp[101][301] = {{0}};
    for (int i=0; i<n; i++)
        for (int j=i+1; j>=1; j--)
            for (int k=300; k>=0; k--)
                if (k - w[i] >= 0) 
                    dp[j][k] = max(dp[j-1][k-w[i]] + v[i], dp[j][k]);
    long best = 0;
    for (int i=wt/w0; i>=0; i--) {
        if (i > n) continue;
        int j = min(wt - i * w0, 300l);
        best = max(best, dp[i][j]);
        // cerr << i << ' ' << j << '\n';
    }
    cout << best << '\n';
    return 0;
}

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

using namespace std;

using ll = long long;



int main(){
  int N, X;
  cin >> N >> X;
  vector<int> L(N);
  for(int i=0; i<N; i++) cin >> L[i];
  
  int ans = 1;
  int D = 0;
  while(ans<=N){
    D += L[ans-1];
    if(D>X) break;
    
    ans++;
  
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3536
#122 C
n,q=map(int,input().split())
s=input()
t=[0]*n
lr=[list(map(int,input().split())) for i in range(q)]
i=0
cnt=0
while i<n-1:
    if s[i]=="A":
        if s[i+1]=="C":
            t[i]+=cnt
            cnt+=1
            i+=1
            t[i]+=cnt
            i+=1
        else:
            t[i]+=cnt
            i+=1
    else:
        t[i]+=cnt
        i+=1
if i==n-1:
    t[i]+=cnt
for j in range(q):
    print(t[lr[j][1]-1]-t[lr[j][0]-1])

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

using namespace std;
const int N = 110;
const int M = 1<<8;
const int mod = 1e9 + 7;

typedef long long LL;

int n, k, a[N];
LL dp[N][N][M], fac[N];

int main(){
    fac[0] = 1;
    for(int i=1; i<N; i++){
        fac[i] = fac[i-1] * i % mod;
    }
    while(~scanf("%d %d", &n, &k)){
        for(int i=1; i<=n; i++){
            scanf("%d", a+i);
        }
        memset(dp[0], 0, sizeof(dp[0]));
        dp[0][0][0] = 1;
        for(int i=1; i<=n; i++){
            for(int j=0; j<=n; j++){
                for(int k=0; k<M; k++){
                    if(j){
                        dp[i][j][k] = (dp[i-1][j][k] + dp[i-1][j-1][k^a[i]])%mod;
                    } else {
                        dp[i][j][k]  = dp[i-1][j][k];
                    }
                }
            }
        }
        LL ans = 0;
        for(int i=1; i<=n; i++){
            ans = (ans + fac[i] * dp[n][i][k] % mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 20864
import heapq
N,M=map(int,input().split())
kakaku=list(map(int,input().split()))
han=[]
for i in range(N):
  han.append(-kakaku[i])
  
heapq.heapify(han)
for _ in range(M):
  k=heapq.heappop(han)
  k=k/2
  heapq.heappush(han,k)

sum=0
for j in range(N):
  sum+=int(-han[j])
print(sum)

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

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

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

struct Edge {
  int to, id;
};

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

  int mx = 0;
  rep(i, n) mx = max(mx, (int)g[i].size());

  int ans[n - 1];
  queue<int> q;
  vector<int> used(n);
  q.push(0);
  used[0] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();

    int c = -1;
    for (auto x : g[u]) {
      int v = x.to, ei = x.id;
      if (used[v]) c = ans[ei];
    }

    int k = 1;
    for (auto x : g[u]) {
      int v = x.to, ei = x.id;
      if (used[v]) continue;
      if (k == c) ++k;
      ans[ei] = k;
      ++k;
      q.push(v);
      used[v] = 1;
    }
  }

  cout << mx << endl;
  rep(i, n - 1) cout << ans[i] << endl;

  return 0;
}


Measured memory_bytes: 7296
#include <stdio.h>

int main(void)
{
	int dis[10], v1, v2;
	int i, j, sum;
	double x, cross;
	
	while (scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d", &dis[0], &dis[1], &dis[2], &dis[3], &dis[4], &dis[5], &dis[6], &dis[7], &dis[8], &dis[9], &v1, &v2) != EOF){
		
		sum = 0;
		for (i = 0; i < 10; i++){
			sum += dis[i];
		}
		x = (double)sum / (v1 + v2);
		cross = v1 * x;
		
		i = 0;
		while (cross > 0){
			cross -= dis[i];
			i++;
		}
		printf("%d\n", i);
	}
	
	return (0);
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> pll;
#define fu(i,a,b)   for(ll i=a;i<=b;i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define uni(a)      (a).erase(unique(all(a)), (a).end())
#define pb(i)       push_back(i)
#define popb()      pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define pr(a)       cout<<a<<" "
#define pr2(a,b)    cout<<a<<" "<<b<<" "
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)  lower_bound(all(a),x) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()						
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define se          second
#define fi          first 
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
void inline minize(ll& a,ll b){a=(a>b?b:a);};
void inline maxize(ll& a,ll b){a=(a<b?b:a);};
string inline toString(ll n) {stringstream ss; ss << n;return ss.str();}
double const eps = 1e-6;
ll const Base=1e9+7,oo=1e17,MAXN=1e6;


ll arr[MAXN+5],mark1[MAXN+5],markn[MAXN+5];

ll Solves(){
	
	ll n,m,k,cnt=0,ans=0,x,a,b;
	// PROCESSING IN HERE
	sc2(n,m);
	while(m--){
		sc2(a,b);
		if(a==1)mark1[b]=1;
		assert(a<b);
		if(b==n)markn[a]=1;
	}
	
	fu(i,2,n-1){
		if(mark1[i] and markn[i])re pr("POSSIBLE"),0;
	}
	pr("IMPOSSIBLE");
	re 0;
	// Hack it if you can :)
}

int main(){
	//INPUT;
	ll JUDGE_ONLINE = 1;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	Solves();
	if (!JUDGE_ONLINE) cout << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";  
		
}

Measured memory_bytes: 5888
import java.util.*;

public class Main{
	public static void main(String[] args){
		// Scanner sc = new Scanner(System.in);
		// String str = sc.nextLine();
		// sc.close();

		// int result=0;

		Scanner scan = new Scanner(System.in);

		String input_str = scan.nextLine();

		String[] num_str = input_str.split(" ");

		int[] num_int = new int[num_str.length];

		int ans;

		for(int i= 0; i < num_str.length; i++){
			num_int[i] = Integer.parseInt(num_str[i]);		
		}

		if (num_int[0] % num_int[1] ==0){
			ans = num_int[0] / num_int[1] * num_int[2];
		}
		else{
			ans = (num_int[0] / num_int[1]+1) * num_int[2];
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 35844
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

void sub(char& ch, int d){
  REP(i,d)
	if(ch == 'a')
	  ch = 'Z';
	else if(ch == 'A')
	  ch = 'z';
	else
	  --ch;
}

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

  int N;
  while(cin>>N, N){
	VI key(N);
	REP(i,N) cin >> key[i];
	string str; cin >> str;
	REP(i,SZ(str)){
	  sub(str[i], key[i%N]);
	}
	cout << str << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1204
import java.util.*;


class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		while(true) {
			int n = stdIn.nextInt();
			if(n == 0) break;
			Data[] list = new Data[n];
			for(int i = 0; i < n; i++) {
				int p = stdIn.nextInt();
				int d1 = stdIn.nextInt();
				int d2 = stdIn.nextInt();
				list[i] = new Data(p,d1,d2);
			}
			Arrays.sort(list,new Comp());
			
			System.out.println(list[0].id + " " + list[0].d1);
		}
 	}
	static class Comp implements Comparator<Data>{
		public int compare(Data o1, Data o2) {
			if(o1.d1 > o2.d1) {
				return -1;
			}
			else {
				return 1;
			}
		}
		
	}
	static class Data{
		int id;
		int d1;
		Data(int a, int b, int c) {
			id = a;
			d1 = b+c;
		}
		
	}
}

Measured memory_bytes: 168484
#include <iostream>
using namespace std;
typedef long long ll;
int main(void){
    int a,b,c;
    ll k,ans;
    cin >> a >> b >> c >> k;
    if(k % 2 == 0){
        cout << a-b << endl;
        return 0;
    }else{
        cout << b-a << endl;
        return 0;
    }
}


Measured memory_bytes: 256
import sys
import math
from collections import deque
import heapq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M = NMI()
    A = NLI()
    A = [-a for a in A]
    heapq.heapify(A)
    for i in range(M):
        a_max = -heapq.heappop(A)
        a_max = a_max // 2
        heapq.heappush(A, -a_max)
    print(-sum(A))



if __name__ == "__main__":
    main()

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int a, b;
  cin >> a >> b;
  int k = b - a;
  int c[1000] = {};
  int sum = 0;
  rep(i, 1, 1000) {
    sum += i;
    c[i] = sum;
    if(c[i] - c[i - 1] == k) {
      cout << c[i - 1] - a << endl;
      break;
    }
  }

}


Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def factorization(n):
    factors = []

    if n < 2:
        return n

    while n % 2 == 0:
        factors.append(2)
        n //= 2

    for i in range(3, int(n ** 0.5) + 5, 2):
        while n % i == 0:
            factors.append(i)
            n //= i

    if n != 1:
        factors.append(n)

    return factors


def main():
    from collections import Counter

    n = int(input())
    counter = Counter()

    for i in range(2, n + 1):
        factors = factorization(i)
        counter.update(factors)

    x1 = len([c for c in counter.values() if c >= 4])
    y1 = len([c for c in counter.values() if c >= 2])
    x2 = len([c for c in counter.values() if c >= 14])
    y2 = len([c for c in counter.values() if c >= 4])
    x3 = len([c for c in counter.values() if c >= 24])
    y3 = len([c for c in counter.values() if c >= 2])
    x4 = len([c for c in counter.values() if c >= 74])

    ans = 0
    ans += (x1 * (x1 - 1) // 2) * (y1 - 2)
    ans += x2 * (y2 - 1)
    ans += x3 * (y3 - 1)
    ans += x4

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
N = int(input())
H = list(map(int, input().split()))

inf = float('inf')
dp = [inf] * (N + 1)
dp[1] = 0

for i in range(1, N):
    dp[i + 1] = min(dp[i + 1], dp[i] + abs(H[i - 1] - H[i]))
    if i + 2 <= N:
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(H[i + 1] - H[i - 1]))

print(dp[N])
# print(dp)


Measured memory_bytes: 13928
#include<iostream>
using namespace std;
int main()
{
	int n,m,a[111],b,c,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i],sum+=a[i];
	cin>>m;
	while(m--)
	cin>>b>>c,cout<<sum-a[b]+c<<endl; 
	return 0;
}

Measured memory_bytes: 256
#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 ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<29;
const ll LLINF = 1LL<<61;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H,W,a,b;
  cin >> H >> W >> a >> b;
  if (b*2>H || a*2>W){
      cout << "No" << endl;
  }else{
      REP(h,H){
          REP(w,W){
          cout << ((int) h<b ^ (int) w<a);
          }
          cout << endl;
      }
  }
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll INF = 922337203685477;
#define pb push_back
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define maxN 503
using namespace std;
int main(){
  fastio;
  ll x=0,y=0;
  cin>>x>>y;
  bool f=false;
  for(ll i=0;i<=100;++i){
    for(ll j=0;j<=100;++j){
        if(i+j == x and 2*i+4*j==y)
            f=true;
    }
  }
  if(f) cout<<"Yes\n";
  else cout<<"No\n";
  return 0;
}


Measured memory_bytes: 3636
let n = read_int ()
let g, ds = Array.(make n [], make n 0)
let rec f v p s = ds.(v) <- s; List.iter (fun (u, d) -> if u <> p then f u v (s + d)) g.(v)
let _ = for _ = 1 to n - 1 do Scanf.scanf " %d %d %d" @@ fun a b c -> g.(a - 1) <- (b - 1, c) :: g.(a - 1); g.(b - 1) <- (a - 1, c) :: g.(b - 1) done; 
  Scanf.scanf " %d %d" @@ fun q k -> f (k - 1) ~-1 0; for _ = 1 to q do Scanf.scanf " %d %d" @@ fun x y -> Printf.printf "%d\n" @@ ds.(x - 1) + ds.(y - 1) done

Measured memory_bytes: 26112
#pragma GCC optimize("O3")
#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

vector<int> f;
int n,m;
int find(int a){
  return f[a] == a ? a : f[a]= find(f[a]);
}
int res;
void uni(int a,int b){
  a = find(a);
  b = find(b);
  if(a == b)return;
  res--;
  f[a] = b;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> m;
  res = n-1;
  f.resize(n);
  R(i,n){
    f[i] = i;
  }
  R(i,m){
    int a,b;
    cin >> a >> b;
    uni(a-1,b-1);
  }
  cout << res << "\n";
}


Measured memory_bytes: 4032
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
};
typedef struct node * Node;
#define NIL NULL
Node root;
Node min(Node x);
Node max(Node x);
Node search(Node u, int k);
Node successor(Node x);
void delete(Node z){};
void insert(int k);
void inorder(Node u);
void preorder(Node u);
int main(){
  int n,i,x;
  Node t;
  char com[20];;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",com);
    if (com[0]=='f'){
      scanf("%d",&x);
       t= search(root,x);
      if(t!=NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(com[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }
    else if(com[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    
    else if(com[0]=='d'){
      scanf("%d",&x);
      delete(search(root,x));
    }
  }
  return 0;
}
Node min(Node x){
  while(x->l!=NIL){
    x= x->l;}
  return x;
}
Node max(Node x){
  while(x->r!=NIL){
    x=x->r;
  }
  return x;
}
Node search(Node u,int k){
  while(u!=NIL &&u->key!=k){
    if (k>u->key){
      u=u->r;
    }
    else u=u->l;
  }
  return u;
}
Node successor(Node x){
  Node y;
  if(x->r!=NIL) return min(x->r);
  y=x->p;
  while(y!=NIL && x==y->r){
    x=y;
    y=y->p;
  }
  return x;
}
void insert (int k){
  Node y= NIL;
  Node x=root;
  Node z;
  
  z=malloc(sizeof(struct node));
  z->key=k;
  z->l=NIL;
  z->r=NIL;
  
  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->l;
    }  else x=x->r;
  }
  z->p=y;
  if(y==NIL) root=z;
  else if(z->key<y->key){
    y->l=z;
  }
  else y->r=z;
}

void inorder(Node u){
  if(u==NIL )return ;
  inorder(u->l);
  printf(" %d",u->key);
  inorder(u->r);
}

void preorder(Node u){
  if(u==NIL)return ;
  printf(" %d",u->key);
  preorder(u->l);
  preorder(u->r);
}



Measured memory_bytes: 20460
#include<bits/stdc++.h>
using namespace std;
 
/// ----------------------------- (Debug) ------------------------------
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {ris << "(" << d.first << ", " << d.second << ")";}
sim dor(rge<c> d) {*this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]";}
#else
sim dor(const c&) { ris; }
#endif
};
vector<char*> tokenizer(const char* args) {
  char *token = new char[111]; strcpy(token, args); token = strtok(token, ", ");
  vector<char*> v({token});
  while(token = strtok(NULL,", ")) v.push_back(token);
  return reverse(v.begin(), v.end()), v;
}
void debugg(vector<char*> args) { cerr << "\b\b "; }
template <typename Head, typename... Tail>
void debugg(vector<char*> args, Head H, Tail... T) {
  debug() << " [" << args.back() << ": " << H << "] ";
  args.pop_back(); debugg(args, T...);
}
#define harg(...) #__VA_ARGS__
#ifndef ONLINE_JUDGE
#define dbg(...) { debugg(tokenizer(harg(__VA_ARGS__, \b\t-->Line)), __VA_ARGS__, __LINE__); cerr << endl;}
#else
#define dbg(...) { }
#endif
/// -----------------------------------------------------------------------

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi; 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)    
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define REP(i,a,b) for(i=a;i<=b;i++)
#define RAP(i,a,b) for(i=a;i>=b;i--)
#define spa <<" "<<
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
ll mod=998244353;
const int MX=0x3f3f3f3f;

int main() {
    IOS;
    ll n,x,cnt=1,ans;
    int m,i;
    cin>>n>>x>>m;
    ans=x;
    vi v;
    set<int> s;
    s.insert(x);
    v.EB(x);
    while(cnt<n&&s.find((x*x)%m)==s.end()){
    	x=(x*x)%m;
    	// dbg(x,s,ans);
    	s.insert(x);
    	v.EB(x);
    	ans+=x;
    	cnt++;
    }
    if(cnt<n){
    	ll sum=0;
    	int num=0;
    	x=(x*x)%m;
    	// dbg(v);
    	RAP(i,sz(v)-1,0){
    		sum+=v[i];
    		num++;
    		if(v[i]==x) break;
    	}
    	// dbg(i,num,cnt);
    	ans+=((n-cnt)/num)*sum;
    	num=(n-cnt)%num;
    	sum=0;
    	while(num--){
    		sum+=v[i];
    		i++;
    	};
    	ans+=sum;
    }
    cout<<ans;
    return 0;   
} 

Measured memory_bytes: 5944
N = int(input())
sT = input().split()
T = []
P = []
X = []
for i in range(N):
    T.append(int(sT[i]))
M = int(input())
for i in range(M):
    PX = input().split()
    P.append(int(PX[0]))
    X.append(int(PX[1]))


total = sum(T)
for i in range(M):
    print(total - T[P[i] - 1] + X[i])

Measured memory_bytes: 3192
def comb(n,k,mod):
  a = 1
  b = 1
  for i in range(k):
    a = a * (n-i) % mod
    b = b * (i+1) % mod
  return a * pow(b, mod-2, mod) % mod
n,k=map(int,input().split())
mod=10**9+7
for i in range(1,k+1):
  print((comb(n-k+1,i,mod)*comb(k-1,i-1,mod))%mod)


Measured memory_bytes: 9216
import java.util.*;
import java.math.BigDecimal;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
      
        int count = 1,tmp;
        int brick = 0;
        for(int i = 0;i<n;i++){
          tmp = sc.nextInt();
          if(tmp == count){
            count += 1;
          }else{
            brick += 1;
          }
        }
        if(count == 1){brick = -1;}
        System.out.println(brick);
        

        
    }
}

Measured memory_bytes: 58760
s = gets.chomp
n = s.size + 1

t = 0
l_r = [t]
(0...s.size).each do |i|
  if s[i] == '<'
    t += 1
  else
    t = 0
  end
  l_r << t
end

t = 0
r_r = [t]
(s.size-1).downto(0) do |i|
  if s[i] == '>'
    t += 1
  else
    t = 0
  end
  r_r.unshift(t)
end

ans = 0
(0...n).each do |i|
  ans += [l_r[i], r_r[i]].max
end

puts ans

Measured memory_bytes: 11268
#include<stdio.h>
int main(void){
  char s[101],t[101];
  int n,i;
  scanf("%d",&n);
  scanf("%s%s",s,t);
  for(i=0;i<n;i++){
    printf("%c%c",s[i],t[i]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
int main(void){
    int X;
    scanf("%d", &X);
    
    if(X%7 == 0) printf("thu\n");
    else if(X%7 == 1)  printf("fri\n");
    else if(X%7 == 2)  printf("sat\n");
    else if(X%7 == 3)  printf("sun\n");
    else if(X%7 == 4)  printf("mon\n");
    else if(X%7 == 5)  printf("tue\n");
    else if(X%7 == 6)  printf("wed\n");
    
    return 0;
    
}



Measured memory_bytes: 2104
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}
ll gcd(ll(a), ll(b)) {
	ll c = a;
	while (a % b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return b;
}



int main() {
	ll N,x;
	cin >> N >> x;
	vector<ll> a(N);
	rep(i, N) {
		cin >> a.at(i);
	}
	sort(a.begin(), a.end());
	ll an = 0;
	rep(i, N) {
		x -= a.at(i);
		if (x >= 0) {
			an++;
		}
	}
	if (x > 0) {
		an--;
	}
	cout << an << endl;
	
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define mod 998244353 
int32_t main()
{
    int n,k;
    cin>>n>>k;
    int a[n],b[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
    }
    int dp[k+1][n+1];
    for (int i = 0; i <=k; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            if(i==0 or j==0)
            {
                dp[i][j]=0;
            }
            else if(i>=a[j-1])
            {
                dp[i][j]=max(dp[i-a[j-1]][j-1]+b[j-1],dp[i][j-1]);
            }
            else
            {
                dp[i][j]=dp[i][j-1];
            }
            //cout<<dp[i][j]<<" ";
            
        }
       // cout<<"\n";
    }
    cout<<dp[k][n];


}

Measured memory_bytes: 79104
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>

#define FOR(i,a,count) for(int i = a; i < count; ++i)
#define endl '\n'
#define I_love using
#define EVA namespace
#define GREEN std;
#define pb push_back
#define mp make_pair
#define NOS_VEMOS_EN_JAVA class
#define SAYONARAAA_ARRIVEDERCCI return 0;
#define Im_a_intERo_newbie int main()
#define AL_INFINITO_Y_MAS_ALLA (int)1e9
#define all(a)  a.begin(),a.end()
#define max_i(a,b) ( (a) > (b) ? (a) : (b))
#define min_i(a,b) ( (a) < (b) ? (a) : (b))
#define AHORA_SOY_UNA_BALA 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


			I_love EVA GREEN


typedef pair<int,int> pii;
typedef vector<long long> vi;
typedef unsigned long long ull;
typedef vector<string> vs;
typedef vector<pii> vii;


inline bool max_bool(int a, int b){return a>b;}
inline int max_int(int a, int b ){ if(a>b)return a ; return b ;}
template<typename T> inline void prnt(T d){cout<<d<<endl;}



	Im_a_intERo_newbie{
	AHORA_SOY_UNA_BALA
	int n ;cin>>n;
	if (n<1000){
		prnt("ABC");
		SAYONARAAA_ARRIVEDERCCI
	}
	prnt("ABD");

	SAYONARAAA_ARRIVEDERCCI}


Measured memory_bytes: 256
def getResult(pos, K) :
    for i in range(len(pos)-1) :
        for j in pos[i+1:] :
            if abs(pos[i] - j) > K :
                return ":("
    return "Yay!"

position = []
for i in range(5) :
    position.append(int(input()))
k = int(input())
print(getResult(position, k))



Measured memory_bytes: 2940
#include <stdio.h>

int main()
{
    int a,b,c;
    scanf("%d%d%d", &a, &b, &c);
    if((a+b+c)<22){
        printf("win");
    }
    else if((a+b+c)>=22){
        printf("bust");
    }
    else{}


    return 0;
}


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

int keta(int n){
    int count = 0;
    while(n){
        n/=10;
        count++;
    }
    return count;
}

int main()
{
    int n;
    std::cin>>n;
    int count = 0;
    for(int i = 1;i<=n;i++){
        if(keta(i)%2==1)count++;
    }
    std::cout<<count<<std::endl;

}

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

long long n, satu, dua, empat, arr[100005];

int main () {
	cin>>n;
	
	for(int i=1; i<=n; i++){
		cin>>arr[i];
		arr[i]%=4;
		if(arr[i]%4==0) empat++;
		else if(arr[i]%2==0) dua++;
	}
	
	satu=n-dua-empat;
	
	if(dua>0){
		if(empat>=satu){
			cout<<"Yes\n";
			return 0;
		}
	}
	else{
		if(empat>0&&(empat+1>=satu)){
			cout<<"Yes\n";
			return 0;
		}
	}
    cout<<"No\n";
}

Measured memory_bytes: 4340
import java.io.*;

class Main {
	public static void main(String[] arg)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] div = str.split(" ");
		int s =  Integer.parseInt(div[0]);
		int l =  Integer.parseInt(div[1]);
		System.out.println(s*l + " "+ 2*(s+l));
	}	
}

Measured memory_bytes: 16896
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int N,M,X,Y,i;
    cin >> N >> M >> X >> Y;
    int x[N],y[M];
    for(i=0;i<N;i++){
        cin >> x[i];
    }
    for(i=0;i<M;i++){
        cin >> y[i];
    }
    sort(x,x+N);
    sort(y,y+M);
    if(x[N-1]<y[0]&&x[N-1]<Y&&X<y[0]&&X<Y){
        cout << "No War" << endl;
    }else{
        cout << "War" << endl;
    }
}


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

for i in range(1, N + 1):
    A[i -1] -= i

A.sort()
# print (A)
# max_count = 0
# tmp_count = 0
# tmp = A[0]
# candidate = A[0]
# for i in A:
#     if tmp == i:
#         tmp_count += 1
#     else:
#         if tmp_count > max_count:
#             max_count = tmp_count
#             candidate = tmp
#         tmp_count = 1
#         tmp = i

# if tmp_count > max_count:
#     candidate = tmp
# print (candidate)
ans = 0
for i in A:
    ans += abs(i - A[N//2])
print (ans)


Measured memory_bytes: 25284
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF=1e9;
constexpr double EPS=1e-9;
constexpr int    MOD=1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

int main(){
	string s="ACL";
	
	int k;
	cin>>k;
	
	REP(i,k) cout<<s;
	cout<<endl;
}

Measured memory_bytes: 3592
// 12:31 -> 13:03 = 32min
#include <bits/stdc++.h>
#define REP(i, n, s) for (int i = (s); i < (n); i++)
#define SIZE 1
using namespace std;
typedef long long int LL;
typedef long double LD;

const int MOD = 1e9 + 7;
int A[400], B[400];
LL cache[401][401];

LL _pow(LL a, int k) {
	LL res = 1;
	while (k) {
		if (k&1) res = (res * a) % MOD;
		a = (a * a) % MOD;
		k >>= 1;
	}
	return res;
}

LL func(int n, int c) {
	if (cache[n][c] > 0) return cache[n][c];
	if (n == 0) {
		return (cache[n][c] = (c == 0)? 1 : 0);
	}
	LL res = 0;
	REP(i, B[n-1] + 1, A[n-1]) {
		REP(j, c + 1, 0) {
			res = (res + _pow(i, j) * func(n - 1, c - j) % MOD) % MOD;
		}
	}
	return (cache[n][c] = res);
}

int main() {
	int N, C;

	scanf("%d %d", &N, &C);
	REP(i, N, 0) scanf("%d", A+i);
	REP(i, N, 0) scanf("%d", B+i);
/*
N = 400;
C = 400;
REP(i, N, 0) {
	A[i] = 1, B[i] = 400;
	fill(cache[i+1], cache[i+1] + 401, -1);
}
*/
LL dp[2][401];
int idx = 0;
memset(dp[idx], 0, sizeof(dp[idx]));
dp[idx][0] = 1;

LL sum[401];
REP(i, N, 0) {
	int _idx = idx;
	idx = (idx+1)%2;
	memset(dp[idx], 0, sizeof(dp[idx]));
	REP(k, B[i] + 1, A[i]) {
		sum[0] = dp[_idx][0];
		REP(j, C + 1, 1) {
			sum[j] = ((k * sum[j-1]) % MOD + dp[_idx][j]) % MOD;
		}
		REP(j, C + 1, 0) {
			dp[idx][j] = (dp[idx][j] + sum[j]) % MOD;
		}
	}
}

cout << dp[idx][C] << endl;
//	printf("%d\n", func(N, C));
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

using ll = long long;

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

#define input(...) __VA_ARGS__; in(__VA_ARGS__)

template<class T>
void print(vector<T> a) {
  cout << "[ ";
  REP(i, a.size()) cout << a[i] << " ";
  cout << "]" << endl;
}

void print() {
  std::cout << std::endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...);
}

void in() { }

template <class Head, class... Tail>
void in(Head&& head, Tail&&... tail) {
  cin >> head;
  in(std::forward<Tail>(tail)...);
}

int main() {
  ll input(n);
  cout << n + n*n + n*n*n << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <utility>
using namespace std;

typedef long long ll;

int main(){
  int n, d, x; cin >> n >> d >> x;
  int a[n];
  for(int i=0; i<n; i++) cin >> a[i];

  int ans=x;
  for(int i=1; i<=d; i++){
    for(int j=0; j<n; j++){
      if((i-1)%a[j]==0) ans += 1;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

//modでの累乗(繰り返し二乗法)
ll modpow(ll x, ll y, ll m)
{
    if (y == 0)
        return 1;
    ll res = modpow(x, y / 2, m);
    return res * res % m * (y & 1 ? x : 1) % m;
}

//modでの割り算
ll modinv(ll x, ll m) { return modpow(x, m - 2, m); }

//modでの安全な引き算
ll modsub(ll x, ll y, ll m){ return(x + m - y) % m; }

//乗算により二項係数を求める
ll binom(ll n, ll k, ll m)
{
    ll den = 1, num = 1;
    for (int i = 1; i <= k; ++i){
        den *= i;
        num *= (n + 1 - i);
        den %= m;
        num %= m;
    }
    return num * modinv(den,m);
}

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

    ll N, K;
    cin >> N >> K;
    vec coef(K + 10, 0);
    coef[0] = 1;
    rep(i, N){
        ll a;
        cin >> a;
        ++a;
        for (ll j = K - a; j >= 0; --j) coef[j + a] = modsub(coef[j + a], coef[j], MOD), coef[j + a] %= MOD;
    }
    COMinit();
    ll ans = 0;

    rep(i, K + 1) ans += COM(i + N - 1, i) * coef[K - i] % MOD, ans %= MOD;

    print(ans);

    return 0;
}

Measured memory_bytes: 12928
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <unordered_map>
#define rep(i,n) for(ll i=0;i<n;i++)
#define repn(i,n) for(ll i=1;i<=n;i++)
using namespace std;
typedef long long ll;

ll K;
queue<ll> lun;

int main(){
    repn(i,9) lun.push(i);
    cin>>K;

    ll ans;
    repn(i,K){
        ll x=lun.front();
        lun.pop();
        if(i==K){
           ans=x; 
        }else{
            if(x%10==0){
                lun.push(10*x);
                lun.push(10*x+1);
            }else if(x%10==9){
                lun.push(10*x+8);
                lun.push(10*x+9);
            }else{
                lun.push(10*x+(x%10)-1);
                lun.push(10*x+(x%10));
                lun.push(10*x+(x%10)+1);
            }
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <bitset>
#include <complex>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("");

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef complex<double> CD;

int main() {
	map<string, int> m;
	int q; cin >> q;
	rep(i, q) {
		int t, x;
		string key, l, r;
		decltype(m)::iterator it;
		cin >> t;

		switch (t) {
		case 0:
			cin >> key >> x;
			m.erase(key);
			m.insert(mp(key, x));
			break;
		case 1:
			cin >> key;
			it = m.find(key);
			if (it != m.end())Cout(m[key]);
			else Cout(0);
			break;
		case 2:
			cin >> key;
			m.erase(key);
			break;
		case 3:
			cin >> l >> r;
			decltype(m)::iterator it = m.lower_bound(l);
			decltype(m)::iterator last = m.upper_bound(r);
			while (it != last) {
				Cout2(it->first, it->second);
				++it;
			}
		}
	}
}


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

#define dump(x) cout << (x) << endl
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

typedef struct {
    Int y, x;
} p_t;

int main() {
    Int n, k;
    cin >> n >> k;
    vector<Int> a(n), b(n);
    for (Int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    Int tmp = k;
    Int cnt = 0;
    while (tmp > 0) {
        tmp /= 2;
        cnt++;
    }
    Int res = 0;
    Int x = 0;
    for (Int i = cnt - 1; i >= 0; i--) {
        if ((k>>i) & 1) {
            x |= (1<<i);
            Int ma = 0;
            for (Int j = 0; j < n; j++) {
                bool check = true;
                for (Int k = cnt - 1; k >= i; k--) {
                    if (((x>>k) & 1) == 1 and (((~a[j])>>k) & 1) == 0) {
                        check = false;
                    }
                }
                if (check and a[j] <= k) {
                    ma += b[j];
                }
            }
            res = max(res, ma);
            x &= ~(1<<i);
        }
        else {
            x |= (1<<i);
        }
    }
    Int ma = 0;
    x = ~k;
    for (Int i = 0; i < n; i++) {
        bool check = true;
        for (Int j = 0; j < cnt; j++) {
            if (((x>>j) & 1) == 1 and (((~a[i])>>j) & 1) == 0) {
                check = false;
            }
        }
        if (check and a[i] <= k) {
            ma += b[i];
        }
    }
    res = max(res, ma);
    dump(res);
    return 0;
}

Measured memory_bytes: 1792
<?php
$N = (int)trim(fgets(STDIN));
//$S = trim(fgets(STDIN));
//list($N,$D) = array_map('intval',explode(" ",trim(fgets(STDIN))));
//$A = array_map('intval',explode(" ",trim(fgets(STDIN))));


$x = 7 % $N;
$S=array();
$i=1;
while(!isset($S[$x])) {
  if ($x == 0) {
    printf("%d\n",$i);
    exit;
  }
  $S[$x]=1;
  $x = ($x*10+7)%$N;
  $i++;
}
printf("%d\n",-1);


Measured memory_bytes: 57732
func main2(text1: [Character] = Array(readLine()!), text2: [Character] = Array(readLine()!)) {
    let text2Count = text2.count
    var result = text2Count
    for index in text1.startIndex...(text1.endIndex - text2Count) {
        var difference = 0
        for (character1, character2) in zip(text1[index...], text2) where character1 != character2 {
            difference += 1
        }
        if result > difference {
            result = difference
        }
    }
    print(result)
}

main2()

Measured memory_bytes: 7808
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int H, W;
string Maze[20];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
struct Po { int y, x, dis; };

int walk(int sh, int sw) {
    Po po {sh, sw, 0};
    queue<Po> q;
    q.push(po);
    int memo[H][W];
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            memo[i][j] = 0;
        }
    }
    memo[sh][sw] = 1;
    int dis = 0;
    while(!q.empty()) {
        Po p = q.front();
        q.pop();
        dis = max(dis, p.dis);
        for (int i = 0; i < 4; ++i) {
            int ny = p.y + dy[i];
            int nx = p.x + dx[i];
            if (ny < 0 || H <= ny || nx < 0 || W <= nx) continue;
            if (memo[ny][nx] == 1) continue;
            if (Maze[ny][nx] == '#') continue;
            memo[ny][nx] = 1;
            Po npo {ny, nx, p.dis + 1};
            q.push(npo);
        }
    }
    return dis;
}

void solve() {
    cin >> H >> W;
    for (int i = 0; i < H; ++i) {
        cin >> Maze[i];
    }

    int ans = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (Maze[i][j] == '#') continue;
            ans = max(ans, walk(i, j));
        }
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 256
sx, sy, tx, ty = map(int, input().split())

x=tx-sx
y=ty-sy

route = 'U'*y+'R'*x+'D'*y+'L'*x
route += 'L'+'U'*(y+1)+'R'*(x+1)+'D' + 'R'+'D'*(y+1)+'L'*(x+1)+'U'
print(route)

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

namespace ABC130A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int X = int.Parse(input[0]);
            int A = int.Parse(input[1]);
            //XとAの大きさを比べたい
            //　X<Aのとき、０を出力
            //　X>=Aのとき、１０を出力
            // if文を使えばよい

            if (X<A) //ifと入力してTabキー２回で展開する
            {
                Console.WriteLine(0);//cwと入力してTabキーで展開
            }
            else
            {
                Console.WriteLine(10);
            }
        }
    }
}


Measured memory_bytes: 11092