akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>

using namespace std;

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

int main()
{
	int ans = 0;
	int k;
	cin >> k;
	for(int a=1; a <= k; a++)
	{
		for(int b=1; b <= k; b++)
		{
			for(int c=1; c <= k; c++)
			{
				int t = gcd(gcd(a, b), c);
				ans += t;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3576
using System;
using System.Collections.Generic;
class Program
{
	//static long[,] dp;
	//static	Dictionary<string, long> dp;
	//static int[] weight, value;
    //static List<string> str = new List<string>();
	//static int INT_MAX = 1000000007;
	static void Main(string[] args)
	{
			// 入力フェーズ
			int N = Int32.Parse(Console.ReadLine());
			string[] input = Console.ReadLine().Split(' '); // p1, p2... pn
			//int H = Int32.Parse(input[0]);
			//int W = Int32.Parse(input[1]);
			Decimal[] pob = new Decimal[N];
			for(int i=0; i< N; i++)
			{
				pob[i] = Decimal.Parse(input[i]);
			}

			// i枚目まで投げて、j枚表になる確率
			Decimal[,] dp = new Decimal[N+1,N+1];
			dp[1,1] = pob[0]; // 初期値
			dp[1,0] = 1 - pob[0]; // 裏になる
			for(int i=1; i<N; i++)
			{
				for(int j=0; j<=N; j++)
				{
					if(i+1 < j)
					{
						// i+1枚投げてi+1枚以上表になることはないので
						break;
					}
					// i+1枚投げて、j枚表になる確率は。。。
					// i枚投げてj-1枚表になっている→i+1枚目が表になる確率
					// + i枚投げて j枚表になっている→i+1枚目が裏になる確率

					if(j==0)
					{
						// j-1<0なので
						dp[i+1, j] = dp[i, j] * (1 - pob[i]);
					}
					else
					{
						dp[i+1, j] = dp[i, j] * (1 - pob[i])
													+ dp[i, j-1] * pob[i];
					}
				}
			}

			// 表になるコインが半分より大きい確率は
			int half = N/2 + 1; // half枚以降を足し合わせる

			Decimal ret = 0;
			for(int j=half; j<=N; j++)
			{
				ret += dp[N, j];
			}

			Console.WriteLine(ret + "");
    }
}


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

int main(){
  string S;
  cin >> S;

  string T;
  T = "ATCG";
  int ans = 0;

  for(int i=0; i<S.size(); ++i){

    int now = 0;
    for(int j=i; j<S.size(); ++j){
      bool ok = false;
      for(int k=0; k<T.size();++k){
        if(S[j]==T[k]) ok = true;
      }

    if(ok){
      now++;
      ans = max(now,ans);
    } else{
      break;
    }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
H = [int(x) for x in input().split()]
c = 0
hc = 0
for i in range(len(H)-1):
  if H[i] >= H[i+1]:
    c += 1
  else:
    if hc < c:
      hc = c
    c = 0
if hc < c:
      hc = c    
print(hc)

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

using namespace std;

int h,w,grid[102][102],vis[102][102];
int dx1[6]={0,1,-1,1,0,1};
int dx2[6]={-1,0,-1,1,-1,0};
int dy[6]={-1,-1,0,0,1,1};

int rec(int x,int y){
  vis[y][x]=1;
  int res=0;

  for(int i=0;i<6;i++){
    int nx=x+(y%2?dx1[i]:dx2[i]),ny=y+dy[i];
    if(nx<0 || ny<0 || w+1<nx || h+1<ny)continue;
    if(grid[ny][nx])res++;
    if(!vis[ny][nx])res+=rec(nx,ny);
  }

  return res;
}

int main(void){

  fill(grid[0],grid[102],0);
  fill(vis[0],vis[102],0);

  cin >> w >> h;
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      cin >> grid[i][j];
      vis[i][j]=grid[i][j];
    }
  }

  cout << rec(0,0) << endl;

  return 0;
}

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

namespace _1_9_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string _target_W;
            List<string> _text_T = new List<string>();
            _target_W = Console.ReadLine();
            while(true)
            {
                string _text = Console.ReadLine();
                string[] _text1 = _text.Split(' ');
                for (int j = 0; j < _text1.Length; j++)
                {
                    _text_T.Add(_text1[j]);
                }
                if (_text == "END_OF_TEXT") break;

            }

            int _count = 0;
                for (int i = 0; i < _text_T.Count; i++)
                {
                    if (_target_W.Length == _text_T[i].Length)
                    {
                        if (_text_T[i].ToLower().Contains(_target_W))
                        {
                            _count++;
                        }
                        else if (_text_T[i].ToUpper().Contains(_target_W))
                        {
                            _count++;
                        }
                    }
                }
                Console.WriteLine(_count);
            
        }
    }
}


Measured memory_bytes: 15864
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main(void){
	int a[30];
	char ss[110];
	int b;
	int c1, c2;
	int k;
	int n, m;
	int s, t;
	int x1, y1, x2,y2;
	int z=0;
	for (int i = 0; i < 30; i++)a[i] = 0;
	scanf("%d %d",&n,&m);
	for (int i = 0; i < n; i++){
		scanf("%s", ss);
		for (int j = 0; j < m; j++)a[ss[j] - 97]++;
	}
	c1 = 0;
	c2 = 0;
	for (int i = 0; i < 26; i++){
		if (a[i] % 2 != 0){
			c1++;
			b = i;
		}
		else if (a[i] % 4 != 0)c2++;
	}
	if (n % 2 == 1 && m % 2 == 1){
		if (c1 <= 1){
			a[b]--;
			if (a[b] % 4 != 0)c2++;
			if (2 * c2 <= n + m - 2)z = 1;
		}
	}
	else if (n % 2 == 1){
		if (c1 == 0 && 2*c2 <= m)z = 1;
	}
	else if (m % 2 == 1){
		if (c1 == 0 && 2*c2 <= n)z = 1;
	}
	else if (c1 == 0 && c2 == 0)z = 1;

	if(z==1)printf("Yes\n");
	else printf("No\n");

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1001001001;
constexpr long long INFL = (1LL<<60);
constexpr double eps = (1e-9);


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

  int n;
  cin >> n;
  map<int, int> pre;
  rep(i, n) {
    int d;
    cin >> d;
    pre[d]++;
  }

  int m;
  cin >> m;
  rep(i, m) {
    int t;
    cin >> t;
    if (pre[t] <= 0) {
      puts("NO");
      return 0;
    } else {
      pre[t]--;
    }
  }

  puts("YES");

  return 0;
}


Measured memory_bytes: 12992
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long ll;
typedef pair<int, int> P;
typedef pair<pair<int, int>, int> PP;
const ll INFL = 1LL << 60;
const ll MOD = 1000000007;
const int INF = 1000000005;
const int MAX = 300000;
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
//------------------------------------------------------------------------------------------------------------------------------

int main(void) {
    // Here
    int K, N;
    cin >> K >> N;
    int mx = -1;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        mx = max(mx, A[i + 1] - A[i]);
    }
    mx = max(mx, K - A[N - 1] + A[0]);
    cout << K - mx << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int n;
    cin >> n;
    vi a(n);
    rep(i,n)cin >> a[i];
    vi l,r;
    l = r = a;
    loop(i,1,n)l[i] = gcd(l[i],l[i-1]);
    for(int i = n-2; i >= 0; i--)r[i] = gcd(r[i],r[i+1]);
    int ans = 1;
    rep(i,n){
        int t;
        if(i == 0){
            t = r[i+1];
        }else if(i == n-1){
            t = l[i-1];
        }else{
            t = gcd(l[i-1],r[i+1]);
        }
        ans = max(ans,t);
    }
    cout << ans << endl;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
       Scanner scan= new Scanner(System.in);
       int n=scan.nextInt();
       int min,max;
       long sum=0;
       int start=scan.nextInt();
       min=start;
       max=start;
       sum+=start;
       for(int i=1;i<n;i++){
           int a=scan.nextInt();
           sum+=a;
           if(min>a){
               min=a;
           }
           if(max<a){
               max=a;
           }
       }
        System.out.println(min+" "+max+" "+sum);
    }
}



Measured memory_bytes: 41504
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

//Rhythm Machine
public class Main{

	class R implements Comparable<R>{
		int k, c;
		public R(int k, int c) {
			this.k = k;
			this.c = c;
		}
		public int compareTo(R o) {
			return k-o.k;
		}
	}
	
	int gcd(int a, int b){
		return b==0?a:gcd(b, a%b);
	}
	int lcm(int a, int b){
		int g = gcd(a, b);
		return a/g*b;
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			int n = sc.nextInt();
			int[] N = new int[n];
			List<R>[] l = new List[n];
			for(int i=0;i<n;i++){
				l[i] = new ArrayList<R>();
				char[] s = sc.next().toCharArray();
				N[i] = s.length/2;
				int g = N[i];
				for(int k=0;k<N[i];k++){
					int c = (s[k*2]-'0')*16+s[k*2+1]-'0';
					if(c==0)continue;
					l[i].add(new R(k, c));
					if(k!=0)g = gcd(g, k);
				}
				if(l[i].isEmpty())continue;
				N[i]/=g;
				for(R r:l[i])r.k/=g;
			}
			int lcm = 1;
			for(int i=0;i<n;i++){
				if(1024<lcm||l[i].isEmpty())continue;
				lcm = lcm(lcm, N[i]);
			}
			if(1024<lcm){
				System.out.println("Too complex."); continue;
			}
			List<R> res = new ArrayList<R>();
			for(int i=0;i<n;i++){
				int mul = lcm/N[i];
				for(R r:l[i])res.add(new R(r.k*mul, r.c));
			}
			if(res.isEmpty())System.out.println("00");
			else{
				Collections.sort(res);
				int[] a = new int[lcm];
				for(R r:res)a[r.k]+=r.c;
				StringBuilder sb = new StringBuilder();
				for(int i=0;i<lcm;i++)sb.append(String.format("%02X", a[i]));
				System.out.println(sb);
			}
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

int main()
{
	ll N;
	cin >> N;
	ll ans;
	if (N % 2 == 1)
	{
		ans = 0;
	}
	else
	{
		/*
		ll C2 = 0, C5 = 0, pow5 = 1;
		while(pow5 <= N)
		{
			ll max2 = N / pow5;
			ll cnt2 = 0;
			while(max2 >= 2)
			{
				cnt2++;
				max2 /= 2;
			}
			C5 += cnt2;
			C2 += cnt2 * (cnt2+1) / 2;
			cout << C5 << " " << C2 << endl;
			pow5 *= 5;
		}
		*/

		ll cnt2 = 0, cnt5 = 0;
		ll now = N;
		while(now >= 2)
		{
			cnt2 = cnt2 + now/2;
			now /= 2;
		}

		now = N / 2;
		while(now >= 5)
		{
			cnt5 = cnt5 + now/5;
			now /= 5;
		}
		ans = min(cnt2,cnt5);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

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

const int oo = 1e9 + 7;
const ll mod = 1e9 + 7,maxn = 100000000;
const double PI = acos(-1);


int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    string a, b, c;
    cin >> a  >> b >> c;

    cout << (a.back() == b[0] and b.back() == c[0]? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 384
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

S = input()
N = len(S)

if S != S[::-1]:
    print("No")
    exit()
SF = S[0:(N-1)//2]
if SF != SF[::-1]:
    print("No")
    exit()
SL = S[(N+3)//2-1:]
if SL != SL[::-1]:
    print("No")
    exit()
print("Yes")


Measured memory_bytes: 5300
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
	cin>>a>>b;
	if (a<=0 && b>=0)
	{
		puts("Zero");
	}
	else if (a<0 && (min(b+1,0)-a)&1)
	{
		puts("Negative");
	}
	else
	{
		puts("Positive");
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn 200000
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

typedef unsigned long long hashv;
const hashv base=131;
hashv pw[1000000+5],hx[maxn+5];

char buff[1000000+maxn+5];
char* s[maxn+5];

bool ok[26];

unordered_set<hashv> H;

int main()
{
    pw[0]=1;
    rep(i,1,1000000) pw[i]=pw[i-1]*base;
    int n; scanf("%d",&n);
    int ptr=0;
    rep(i,1,n)
    {
        scanf("%s",buff+ptr);
        s[i]=buff+ptr;
        int l=strlen(buff+ptr);
        ptr+=l+1;
    }
    rep(i,1,n)
    {
        int l=strlen(s[i]);
        rep(j,0,l-1) hx[i]=hx[i]*base+s[i][j];
        H.insert(hx[i]);
    }
    ll ans=0;
    rep(i,1,n)
    {
        int l=strlen(s[i]);
        hashv h=hx[i];
        memset(ok,0,sizeof ok);
        rep(j,0,l-1) 
        {
            ok[s[i][j]-'a']=1;
            h-=s[i][j]*pw[l-j-1];
            rep(c,0,26) if(ok[c] && H.find(h+('a'+c)*pw[l-j-1])!=H.end()) ans++;//,printf("!! %d, %d: %d\n",i,j,c);
        }
    }
    printf("%lld\n",ans-n);
    return 0;
}

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

using namespace std;

int n;
int a[200005];
int f[(1 << 20) + 5];
inline bool rep(){
    for(int i = 1; i <= (1 << 20) ; i = i * 2)
        if(f[i] > 1) return 1;
    return 0;
}
int main()
{
    scanf("%d", &n);
    long long Sol = 0;
    int j = 1;
    for(int i = 1; i <= n ; ++i){
        scanf("%d", &a[i]);
        int x = a[i];
        while(x > 0){
            ++f[(x & (-x))];
            x = x - (x & (-x));
        }
        while(rep()){
            int x = a[j++];
            while(x > 0){
                --f[(x & (-x))];
                x = x - (x & (-x));
            }
        }
        Sol = Sol + (i - j + 1);
    }
    printf("%lld", Sol);

    return 0;
}


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

using namespace std;

#define int long long

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

#define pb push_back
#define fst first
#define snd second

#define vdel(v, n) v.erase(v.begin() + (n))
#define all(v) v.begin(), v.end()

#define tint(str) atoi(str.c_str())
#define tstr(num) to_string(num)

#define prt(x) cout << x << endl

#ifdef DEBUG
#define debug(x) cout << x << endl
#else
#define debug(x)
#endif

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
template<typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using RPQ = priority_queue<T, vector<T>, less<T>>;

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

//-------------------------------

set<int> used;
vector<int> DP[1000];

signed main() {
    int N;
    cin >> N;
    if (N %10==3){
        prt("bon");
    }
    else if(N % 10 ==0 || N % 10 ==1 || N % 10 ==6 || N % 10 ==8){
        prt("pon");
    }
    else {
        prt("hon");
    }

    return 0;
}


Measured memory_bytes: 3616
import math
k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = math.gcd(i,j)
        if a == 1:
            ans += k
        else:
            for l in range(1,k+1):
                ans += math.gcd(a,l)
print(ans)


Measured memory_bytes: 9176
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> P;
struct Jud{ bool pass; int rest; };
const int MAX_N = 5000;
const int INF = 100000000;
int N, K, C[MAX_N + 1], R[MAX_N + 1], A, B;
int cost[MAX_N + 1];
vector<int> V[MAX_N + 1];
queue<P> que;
Jud jud[MAX_N + 1];

void dfs(int t, int c, int r){
	if(r == 0 || (jud[t].pass && jud[t].rest >= r)) return;
	
	jud[t].pass = true;
	jud[t].rest = r;
	for(int i = 0; i < V[t].size(); i++){
		if(cost[V[t][i]] > c){
			cost[V[t][i]] = c;
			que.push(make_pair(V[t][i], c));
		}
		dfs(V[t][i], c, r - 1);
	}
}

int main(){
	P p;
	int t;
	
	for(int i = 0; i < MAX_N + 1; i++){
		cost[i] = INF;
	}
	
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= N; i++) scanf("%d%d", &C[i], &R[i]);
	for(int i = 1; i <= K; i++){
		scanf("%d%d", &A, &B);
		V[A].push_back(B);
		V[B].push_back(A);
	}
	
	cost[1] = 0;
	que.push(make_pair(1, 0));//(town, cost)
	while(!que.empty()){
		p = que.front();
		que.pop();
		
		t = p.first;
		
		if(p.second != cost[t]) continue;
		
		for(int i = 1; i <= N; i++){
			jud[i].pass = false;
			jud[i].rest = 0;
		}
		dfs(t, cost[t] + C[t], R[t]);
	}
	
	printf("%d\n", cost[N]);
	
	//for(int i = 1; i <= N; i++) printf("cost[%d] = %d\n", i, cost[i].first);
	
	return 0;
}

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

int main(){
  string s;
  cin >> s;
  
  int sum=0;
  
  for(int i=0;i<s.size();i++){
    sum += (s.at(i) - '0');
  }
  
  if((sum % 9) == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3752
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

class UnionFind{
    vector<ll> par; vector<ll> r_size;
    public:
        UnionFind(ll N) : par(N),r_size(N){
            for(int i=0; i<N; ++i){ par[i] = i; r_size[i] = 1;}
        }

        //Nの大きさで初期化
        void init(ll N){
            par.resize(N); r_size.resize(N);
            for(int i=0; i<N; ++i){ par[i] = i; r_size[i] = 1;}
        }

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

        //xとyとが所属する集合を併呑する
        void unite(ll x,ll y){
            ll rx = find(x); ll ry = find(y);
            if(rx == ry) return;
            if(r_size[rx]<r_size[ry]) swap(rx,ry);
            r_size[rx] += r_size[ry];
            par[ry] = rx;
        }

        bool same(ll x, ll y){
            ll ry = find(x); ll rx = find(y);
            return rx == ry;
        }

        //素集合の大きさを返す
        ll el_size(ll x){
            return r_size[find(x)];
        }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,k; cin>>n>>m>>k;
    UnionFind al(n);
    UnionFind fri(n);
    vint appear(n,0);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        --a; --b;
        appear[a]++; appear[b]++;
        al.unite(a,b);
        fri.unite(a,b);
    }
    rep(i,k){
        int c,d;
        cin>>c>>d;
        --c; --d;
        if(fri.same(c,d)){appear[c]++; appear[d]++;}
        al.unite(c,d);
    }
    rep(i,n){
        cout<<al.el_size(i)-1-appear[i]-(al.el_size(i)-fri.el_size(i))<<' ';
    }
}


Measured memory_bytes: 4352
def main():
  M=10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[1]+[0]*k]
  for b,i in zip(dp,a):
    t,d=0,[]
    for v in b[:i+1]:
      t+=v
      t%=M
      d+=t,
    for w,v in zip(b,b[i+1:]):
      t+=v-w
      t%=M
      d+=t,
    dp+=d,
  print(t)
main()

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

int main(){
    int n,x,y;cin>>n>>x>>y;
    x--;y--;//頂点を0オリジンにする.
    vector<int> dist(n,0);
    for(int i = 0;i<n-1;i++){
        for(int j = i+1;j<n;j++){
            int tmp = min(j-i,abs(i-x)+abs(j-y)+1);
            dist[tmp]++;
        }
    }
    rep(k,n){
        if(k==0)continue;
        cout<<dist[k]<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
// D - Handstand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int main() {
	int N, K;
	string S;

	cin >> N >> K;
	cin >> S;

	vector<int> T;
	if (S[0] == '0') {
		T.push_back(0);
	}

	int cnt = 1;
	for (int i=1; i<N; i++) {
		if (S[i-1] == S[i]) {
			cnt++;
		} else {
			T.push_back(cnt);
			cnt = 1;
		}
	}
	T.push_back(cnt);

	if (S[N-1] == '0') {
		T.push_back(0);
	}

	vector<int> U(T.size() + 1);
	for (int i=0; i < T.size(); i++) {
		U[i+1] = U[i] + T[i];
	}

	int ans = 0;
	for (int l=0; l<U.size(); l+=2) {
		int r = min(l+(2*K)+1, (int)U.size()-1);
		ans = max(ans, U[r] - U[l]);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4184
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n,m,c;
    cin >> n >>m >>c;
    vector<int> hai_b(m);
    for(int i=0;i<m;i++){
        cin >> hai_b.at(i);
    }
    vector<vector<int>> hai_a(n,vector<int>(m));
    int cnt=0;
    for(int i=0;i<n;i++){
        int sum =c;
        for(int j=0;j<m;j++){
            cin >> hai_a.at(i).at(j);
            sum += hai_a.at(i).at(j) * hai_b.at(j);
        }
        if(sum >0){
            cnt++;
        }
    }
    cout << cnt <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

const long long int mod=1000000007,INF=1099999999999999999;
void YES_OR_NO(bool check){
    if(check){cout<<"YES"<<endl;}
    else{cout<<"NO"<<endl;}
}

long long int m,k,n,a,b,res=0,sum;
long double d[3000],dres=0;
string str;
int main() {
	cout << fixed << setprecision(10);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>d[i];
    }
    sort(d,d+n);
    dres=(d[0]+d[1])/2.0;
    for(int i=2;i<n;i++){
        dres=(dres+d[i])/2.0;
    }
    cout<<dres<<endl;
    
} 


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
const int MAX=2e5;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k>0){
        if(k%2==1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k/=2;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}

int main()
{
	int n, m;
	cin>>n>>m;
	vector<P> fc;
	for(int i=2; i*i<=m; i++){
		if(m%i==0){
			int e=0;
			while(m%i==0){
				e++;
				m/=i;
			}
			fc.push_back(P(i, e));
		}
	}
	if(m>1){
		fc.push_back(P(m, 1));
	}
	ll f[MAX]; f[0]=1;
	for(ll i=1; i<MAX; i++){
		f[i]=f[i-1]*i%MOD;
	}
	ll invf[MAX];
	invf[MAX-1]=inv(f[MAX-1]);
	for(ll i=MAX-2; i>=0; i--){
		invf[i]=invf[i+1]*(i+1)%MOD;
	}
	ll ans=1;
	for(auto p:fc){
		int e=p.second;
		ans=(ans*f[n+e-1]%MOD*invf[e]%MOD*invf[n-1]%MOD);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using str = string;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
const double PI = 3.141592653589793238;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define REP(i, m, n) for (int i = m; i < (int)n; i++)
#define all(a) (a).begin(), (a).end()
#define allg(a) (a).begin(), (a).end(), greator<>()
#define d20 std::setprecision(20)
#define veci vector<int>
#define vecll vector<long long int>
#define vecb vector<bool>
#define vecd vector<double>
template <typename T>
T lcm(T a, T b)
{
	return a / __gcd(a, b) * b;
}

int main()
{
	str s;
	cin >> s;
	int start, end;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'A')
		{
			start = i;
			break;
		}
	}
	for (int i = s.size(); i >= 0; i--)
	{
		if (s[i] == 'Z')
		{
			end = i;
			break;
		}
	}
	cout << end - start + 1 << endl;

	return 0;
}

Measured memory_bytes: 3744
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

constexpr int MOD = 1e9+7;

constexpr int COMB_MAX = 2e6+10;
ll fac[COMB_MAX], finv[COMB_MAX], inv[COMB_MAX];

void initComb(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < COMB_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;
    }
}

ll comb(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(void){
    initComb();
    Cin(int, k);
    Cin(string, s);
    int n = (int)s.size();
    
    ll ans = 0;
    ll p = 1;
    For(i, k+1){
        ans = (ans + comb(n+k, i) * p % MOD) % MOD;
        p = p * 25 % MOD;
    }
    Cout(ans);
    // sum_{i = n ~ n+k} binom(n+k, i) 2^{n+k-i}
    // sum_{i = 0 ~ k} binom(n+k, i) 2^i
}


Measured memory_bytes: 52208
#include<iostream>
using namespace std;
int main()
{
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == t[i])
			ans += 1;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<math.h>
using namespace std;

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

	double tmp = N / 1.08;
	int roundUp = (int)ceil(tmp);
	int roundDown = (int)floor(tmp);

	double roundUpX = roundUp * 1.08;
	double roundDownX = roundDown * 1.08;

	if (N == (int)floor(roundUpX)) {
		cout << roundUp;
	}
	else if (N == (int)floor(roundDownX)) {
		cout << roundDown;
	}
	else {
		cout << ":(";
	}
}

Measured memory_bytes: 3588
import java.util.*;

public class Main {

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

        int n = sc.nextInt();
        int array[] = new int[100001];

        long ans = 0;

        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            array[a]++;
            ans += a;
        }

        int q = sc.nextInt();

        for (int i = 0; i < q; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = array[a];
            array[a] = 0;
            array[b] += c;
            ans += (b - a) * c;
            System.out.println(ans);
        }
        
    }

}


Measured memory_bytes: 61692
#include <iostream>

using namespace std;

int main() {
	long long n; cin >> n;
	long long f, s, t, ans = 0;
	while (n > 1) {
		f = n / 3 + (n % 3 != 1 ? 0 : 1);
		s = (n - f) / 2, t = s;
		n = max(f, t);
		ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define ll unsigned long long
using namespace std;
int main(){
    int N;cin>>N;
    vector<int> P(N);
    REP(i,N)cin>>P[i];
    vector<int> K(N);
    K=P;
    sort(K.begin(),K.end());
    int cnt=0;
    REP(i,N)if(K[i]!=P[i])cnt++;
    cout<<(cnt==2||cnt==0?"YES":"NO")<<endl;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  int a[200001], b[200001];
  for (int i=0; i<n; i++) {
    a[i] = b[i] = false;
  }
  for (int i=0; i<m; i++) {
    int tmp1, tmp2;
    cin >> tmp1 >> tmp2;
    if (tmp1 == 1) {
      a[tmp2] = true;
    }
    if (tmp2 == n) {
      b[tmp1] = true;
    }
  }

  for (int i=0; i<n; i++) {
    if (a[i] && b[i]) {
      printf("POSSIBLE\n");
      return 0;
    }
  }

  printf("IMPOSSIBLE\n");
  return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var NM = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (N, M) = (NM[0], NM[1]);
        var X = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var sortedX = X.OrderBy(x => x).ToArray();

        var D = Enumerable.Range(0, M - 1).Select(i => (v: sortedX[i + 1] - sortedX[i], i));
        var sortedD = D.OrderByDescending(x => x.v);
        
        var sepPos = sortedD.Take(N - 1).Select(x => x.i + 1);
        var startIdx = new[] { 0 }.Concat(sepPos);
        var endIdx = sepPos.Concat(new[] { M }).Select(i => i - 1);

        var L = startIdx.Zip(endIdx, (si, ei) => sortedX[ei] - sortedX[si]);
        var ans = L.Sum();
        
        WriteLine(ans);
    }
}


Measured memory_bytes: 38920
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
vector<int> fac[300001];
bool ispr[300001];
int main(){
	for(int i=2;i<=300000;i++) for(int j=1;j*i<=300000;j++) fac[i*j].push_back(i);
	rep1(i,300000) if(i%7==1 || i%7==6) ispr[i]=true;
	rep1(i,300000){
		rep(j,(int)fac[i].size()-1) if(ispr[fac[i][j]]) ispr[i]=false;
	}
	while(true){
		int n;
		cin >> n;
		if(n==1) break;
		cout << n << ":";
		rep(i,fac[n].size()) if(ispr[fac[n][i]]) cout << " " << fac[n][i];
		cout << endl;
	}
}

Measured memory_bytes: 32876
N, M = map(int, input().split())
A = list(map(int, input().split()))
d = []
for i in A:
    d.append((i, 1))
for i in range(M):
    B, C = map(int, input().split())
    d.append((C, B))
d.sort()
d.reverse()
i = 0
ans = 0
for j, k in d:
    if i + k >= N:
        ans += j * (N - i)
        break
    i += k
    ans += j * k
print(ans)

Measured memory_bytes: 76568
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <complex>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

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

using Graph = vector<vector<ll>>;

#define ketasitei setprecision(15) //15桁表示

const ll MOD = 1000000007;

int main(void)

{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << ketasitei;

	ll n;
	cin >> n;
	vector<ll> a(n-1);
	rep(i, n-1)
	{
		cin >> a[i];
	}
	vector<ll> buka(n);
	rep(i, n-1)
	{
		buka[a[i] - 1]++;
	}
	rep(i, n )
	{
		cout << buka[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 6364
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            a[i] = scanner.nextInt();
            map.put(a[i], map.getOrDefault(a[i], 0)+1);
        }
        long ans = 0;
        for(Integer key : map.keySet()){
            ans += C2(map.get(key));
        }
        for(int i = 0; i < n; i++){
            System.out.println((ans - map.get(a[i])+1));
        }
    }
    public static long C2(long n){
        return n * (n-1) / 2;
    }
}

Measured memory_bytes: 108224
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x = 0, N, A=0;
  cin >> N;
  string S;
  cin >> S;
  for(int i =0;i < N;i++){
    if(S.at(i) == 'I'){
      x++;
    }else{
      x--;
    }
    A = max(A, x);
  }
  cout << A << endl;
}

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

int main(){
  int a,b,c,d,e;
  cin >> a >> b >> c >> d >> e;
  if(a==0){
    cout << 1 <<endl;
  }
  if(b==0){
    cout << 2 <<endl;
  }
  if(c==0){
    cout << 3 <<endl;
  }
  if(d==0){
    cout << 4 <<endl;
  }
  if(e==0){
    cout << 5 <<endl;
  }
}


Measured memory_bytes: 3584
x0, y0, x1, y1 = gets.split.map(&:to_i)
gets.to_i.times do
  x, y = gets.split.map(&:to_i)
  ax = x1 - x0
  ay = y1 - y0
  px = x - x0
  py = y - y0
  # ?????????????????????
  r = (ax * px + ay * py) / (ax * ax + ay * ay).to_f
  puts [x0 + r * ax, y0 + r * ay] * ' '
end

Measured memory_bytes: 8860
#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(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const bool debug = 0;

int main() {
	int N;
	priority_queue<int, vector<int>, greater<int> > pq;
	
	cin >> N;
	REP(i, N) {
		int a, b;
		scanf("%d %d", &a, &b);
		pq.push(a + b);
	}
	
	vector<int> ans;
	while (pq.size() > 1) {
		int a = pq.top(); pq.pop();
		int b = pq.top(); pq.pop();
		
		if (a == b) pq.push(a + 1);
		else {
			pq.push(b);
			ans.push_back(a);
		}
	}
	if (pq.size() > 0) ans.push_back(pq.top());
	
	REP(i, ans.size()) printf("%d 0\n", ans[i], i == ans.size() - 1 ? '\n' : ' ');
	
	return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 7;
const double pi = acos(-1);
const int mod = 998244353;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
map<string,int> mp;
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		string s;
		cin >> s;
		mp[s] = 1;
	}
	cout << mp.size()<<endl;
    return 0;
}

Measured memory_bytes: 19268
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100005,K=1000000007;
int n,m,ans,f[maxn];
int Pow(int A,int B)
{
	int res=1;
	while (B)
	{
		if (B&1) res=(LL)res*A%K;
		A=(LL)A*A%K;
		B>>=1;
	}
	return res;
}
int finds(int k)
{
	if (f[k]) return f[k];
	int res=Pow(k,n);
	for (int i=2;i<=k;i++)
	{
		res-=finds(k/i);
		if (res<0) res+=K;
	}
	return f[k]=res;
}
int main()
{
	scanf("%d%d",&n,&m);
	f[1]=1;
	ans=finds(m);
	for (int i=2;i<=m;i++) ans=(ans+(LL)f[m/i]*i)%K;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 3848
use io::*;

fn main() {

    let con = read_string();
    let mut sc = Scanner::new(&con);

    let n: usize = sc.next();
    let a: usize = sc.next();
    let b: usize = sc.next();

    let mut ans = 0;
    for i in 1..n+1 {
        let mut x = i;
        let mut sum = 0;
        while x > 0 {
            sum += x % 10;
            x /= 10;
        }
        if sum >= a && sum <= b {
            ans += i;
        }
    }
    println!("{}", ans);
}

pub mod io {

    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}

Measured memory_bytes: 4352
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
//constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

ll PowMod(ll a, ll n, ll MOD){
	if(n < 0) return PowMod(PowMod(a, -n, MOD), MOD-2, MOD);
	if(n == 0) return 1;
	if(n == 1) return a;
	if(n%2 == 0) return PowMod(a*a%MOD, n/2, MOD);
	return a*PowMod(a*a%MOD, n/2, MOD)%MOD;
}

ll inv(ll a, ll mod){
	if(a == 1) return 1;
	return mod - mod * inv(mod % a, a) / a % mod;
}

int main(void){
	ll x;
	cin >> x;

	unordered_map<ll, ll> ump;
	rep(i, 1000){
		ll p = 1;
		rep(j, 5) p *= i;
		ump[p] = i;
		p = 1;
		rep(j, 5) p *= -i;
		ump[p] = -i;
	}

	ll a, b;
	rep(i, 1000){
		ll p = 1;
		rep(j, 5) p *= i;
		if(ump.find(p + x) != ump.end()){
			a = i, b = ump[p + x];
			break;
		}
		p = 1;
		rep(j, 5) p *= -i;
		if(ump.find(p + x) != ump.end()){
			a = -i, b = ump[p + x];
			break;
		}
	}
	if(a < b) swap(a, b);
	co({a, b});

	return 0;
}


Measured memory_bytes: 3696
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int nums = scanner.nextInt();
        System.out.print(num*nums);
        System.out.print(" ");
        System.out.println(num*2+nums*2);

    }
}


Measured memory_bytes: 26124
#include<stdio.h>
int main(){
  double a;
  double s[11],sum;
  int i;
  while(scanf("%lf",&a)!=EOF){
    s[1]=a;
    sum=a;
    for(i=2;i<11;i++){
      if(i%2==0){
	s[i]=s[i-1]*2;
      }
      else{
	s[i]=s[i-1]/3;
      }
      sum+=s[i];
    }
    printf("%.8f\n",sum);
  }
  return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int 
const int MOD = 1e9+7;
const int MAXN = 2e5+5;

int32_t main()
{
   
    IOS
    int n;
    cin>>n;
    int arr[n+1];   
    for(int i=1;i<=n;i++)  cin>>arr[i];
    int dp[n+1];
    memset(dp,MAXN,sizeof(dp));
    dp[1]=0;
    //for(auto it :dp) cout<<it<<" ";
    for(int i=1;i<=n;i++){
        for(int j:{i+1, i+2}){
            if(j<=n){
                dp[j]=min(dp[j],dp[i]+abs(arr[i]-arr[j]));
            
            }
        }
    }
    
    cout<<dp[n]<<'\n';
    return 0;
}
        

Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000000
#define MAX 200001

const int MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<MOD>;

int main(){
    ll N, D;
    cin >> N >> D;
    int ans = 0;
    rep(i,N){
        ll x,y;
        cin >> x >> y;
        ll d = x*x + y*y;
        if(D*D >= d) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3592
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>


long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;


int main(){
int N;
cin>>N;
long long ans;
ans=N*N*N;
cout<<ans <<endl;


 return 0;
}

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

Measured memory_bytes: 580