akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int k,res=1e9;
bool Free[100005][55];

void Cal(int i,int j)
{
    if(Free[i][j]==true)
        return;
    Free[i][j]=true;
    if(i==0)
    {
        res=min(res,j);
        return;
    }
    for(int t=0;t<=9;t++)
        if(j+t<=50)
            Cal((i*10+t)%k,j+t);
}

int main()
{
    cin>>k;
    for(int i=1;i<=9;i++)
        Cal(i%k,i);
    cout<<res;
}


Measured memory_bytes: 119040
#include <bits/stdc++.h>
using namespace std;
vector<int> seg, a;
void build (int l, int r, int node) {
  if (l == r) {
    seg[node] = a[l];
  } else {
    int mid = l + (r - l) / 2;
    build (l, mid, 2 * node + 1);
    build (mid + 1, r, 2 * node + 2);
    seg[node] = __gcd(seg[2 * node + 1], seg[2 * node + 2]);
  }
}
void update (int l, int r, int node, int pos, int x) {
  if (l == pos && r == pos) {
    seg[node] = x;
    return;
  }
  if (l > pos || r < pos) return;
  int mid = l + (r - l) / 2;
  update (l, mid, 2 * node + 1, pos, x);
  update (mid + 1, r, 2 * node + 2, pos, x);
  seg[node] = __gcd(seg[2 * node + 1], seg[2 * node + 2]);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, ans;
  cin >> n;
  a = vector<int> (n);
  seg = vector<int> (4 * n);
  for (int i = 0; i < n; i++) cin >> a[i];
  build (0, n - 1, 0);
  ans = seg[0];
  for (int i = 0; i < n; i++) {
    int m = a[i];
    update (0, n - 1, 0, i, 0);
    ans = max(ans, seg[0]);
    update (0, n - 1, 0, i, m);
  }
  cout << ans << '\n';
  return 0;
}

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


int main() {
  long n;
  cin>>n;
  cout<<(1000-n%1000)%1000<<endl;
}




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

int main() {
	int n;

	cin >> n  ;
	
	int num = 0;
	int tmp = n;

	while (tmp > 0) {
		num += tmp % 10;
		tmp /= 10;
	}
	
	if (n % num == 0) {
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
}

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

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1ll << 60;

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

int N, A[21][21];
int dp[22][1 << 21];

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

    cin >> N;
    rep(i, 0, N) rep(j, 0, N) cin >> A[i][j];

    dp[0][0] = 1;
    int mod = 1e9 + 7;
    rep(i, 0, N) {
        for(int mask = 0; mask < 1 << N; mask++) {
            if(i == __builtin_popcount(mask)) {
                rep(j, 0, N) if(!(mask & (1 << j)) and A[i][j]) {
                    (dp[i + 1][mask | (1 << j)] += dp[i][mask]) %= mod;
                }
            }
        }
    }

    cout << dp[N][(1 << N) - 1] << endl;

}


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16

ll x,y;

int main(){
	cin>>x>>y;
  if(x%y==0)cout<<-1<<endl;
  else cout<<x<<endl;
	return 0;
}


Measured memory_bytes: 256
n, a, b, c, d = map(int, input().split())
s = input()

a,b,c,d=a-1,b-1,c-1,d-1
if a > b:
    a, b, c, d = b, a, d, c


if '##' in s[a:c] or '##' in s[b:d]:print('No')
else:
    if c < d:
        print('Yes')

    else:
        if '...' in s[b - 1 : d + 2]:
            print('Yes')
        else:
            print('No')


Measured memory_bytes: 3636
s = int(input())
a = [s]
dic = {s: 1}
ans = 1
for i in range(1, 1000000):
    if a[i-1] % 2 == 0:
        item = a[i-1]//2
        a.append(item)
    else:
        item = 3*a[i-1]+1
        a.append(item)
    if item in dic:
        ans = i + 1
        break
    dic[item] = i
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
typedef long long ll;
#define _GLIBCXX_DEBUG
int main()	{
  int n,m;
  double sum=0;
  cin>>n>>m;
  vector<int>a(n);
  rep(i,n) {
    cin>>a[i];
    sum+=a[i];
  }
  sort(rall(a));
  sum=sum/(4*m);  
  rep(i,m){
    if((double)a[i]<sum){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}

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

public class Main {

	private static List<Ab> getStrings(Scanner sc, int num) {
		List<Ab> stringList = new ArrayList<>();
		while(num>0) {
			long a = sc.nextLong();
			long b = sc.nextLong();
			stringList.add(new Ab(a,b));
			num--;
		}
		return stringList;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Ab> ablist = getStrings(sc, n);
		long suma = 0;
		long sumb = 0;
		List<Long> alist = new ArrayList<>();
		List<Long> blist = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			alist.add(ablist.get(i).a);
			blist.add(ablist.get(i).b);
		}
		alist.sort(Long::compareTo);
		blist.sort(Long::compareTo);
		double mediana = 0;
		double medianb = 0;
		if (n % 2 == 1) {
			mediana = alist.get((n+1)/2-1);
			medianb = blist.get((n+1)/2-1);
			System.out.println((long)(medianb - mediana + 1));
		} else {
			mediana = (alist.get(n/2-1) + alist.get(n/2))/2.0;
			medianb = (blist.get(n/2-1) + blist.get(n/2))/2.0;
			System.out.println((long)((medianb - mediana) * 2 + 1));
		}
		return;
	}

	public static class Ab {
		long a;
		long b;

		public Ab(long a, long b) {
			this.a = a;
			this.b = b;
		}
	}

}


Measured memory_bytes: 78668
#include<stdio.h>

int search(int A[], int n, int key) {
    int i = 0;
    A[n] = key;
    while (A[i] != key) i++;
    return i != n;
}

int main() {
    int i, n, A[10000 + 1], q, key, sum = 0;

    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", &A[i]);

    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &key);
	if (search(A, n, key)) sum++;
    }
    printf("%d\n", sum);
    return 0;
}


Measured memory_bytes: 2104
import java.util.*;

public class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int N, cnt = 0;
		int[] A = new int[100];
		int i, j, temp, min;
		
		N = sc.nextInt();
		
		for(i = 0; i < N; i++){
			A[i] = sc.nextInt();
		}
		
		for(i = 0; i < N; i++){
			min = i;
			for(j = i; j < N; j++){
				if(A[j] < A[min]){
					min = j;
				}
			}
			
			if(i != min){
				temp = A[i];
				A[i] = A[min];
				A[min] = temp;
				cnt ++;
			}
		}
		
		for(i = 0; i < N - 1; i++){
			System.out.print(A[i] + " ");
		}
		System.out.println(A[i]);
		System.out.println(cnt);
	}
}

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

int check(int n, int path[8][8],int now) {
  	bool fin = true;
	int count = 0;
	path[now][now] = 9;
	for(int i = 1; i < n; i++) {
		if(path[i][i] != 0) {
			continue;
		}
		if(path[i][now] == 1) {
			count += check(n,path,i);
          	fin = false;
        }
	}
  
  	path[now][now] = 0;
	
  	if(fin) {
		for(int i = 0; i < n; i++) {
        	if(i == now)
              	continue;
          	if(path[i][i] == 0)
              	return 0;
        }
      	return 1;
    } else { 
        return count;
    }
}
int main()
{
	int n,m,count = 0;
	cin >> n >> m;
	vector<int> a(m);
	vector<int> b(m);
	int path[8][8];
	for(int i = 0; i < 8; i++) {
		for(int j = 0; j <= 8; j++) {
			path[i][j] = 0;
		}
	}
	
	for(int i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		path[--a[i]][--b[i]] = 1;
		path[b[i]][a[i]] = 1;
	}
	count = check(n,path,0);
	
	
	cout << count << endl;
}


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

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

using namespace std;

using ll = long long;

ll s(ll n) {
    return n * (n + 1) / 2;
}

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> c(N);
    REP(i, N) {
        cin >> c[i];
        --c[i];
    }
    vector<vector<int>> g(N);
    REP(i, N - 1) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int root = 0;
    // add an extra node which is the parent of the root and has all the colors.
    int super_root = N;

    vector<ll> result(N);
    vector<int> last_color(N, super_root);
    vector<int> del_size(N);
    vector<int> super_root_del_size(N);

    function<int(int, int)> dfs = [&](int u, int parent) {
        int same_color_parent = last_color[c[u]];
        int last_color_old = last_color[c[u]];
        int size = 1;
        for (int v: g[u]) {
            if (v == parent) 
                continue;
            last_color[c[u]] = u;
            del_size[u] = 0;
            int child_size = dfs(v, u);
            result[c[u]] += s(child_size - del_size[u]);
            size += child_size;
        }
        if (same_color_parent == super_root) {
            super_root_del_size[c[u]] += size;
        } else {
            del_size[same_color_parent] += size;
        }
        last_color[c[u]] = last_color_old;
        return size;
    };

    dfs(root, -1);

    REP(c, N) {
        result[c] += s(N - super_root_del_size[c]);
        result[c] = s(N) - result[c];
        cout << result[c] << '\n';
    }
    cout << flush;

    return 0;
}


Measured memory_bytes: 40656
def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.append(n)
    return divisors
#return only >=2

n=int(input())
div=make_divisors(n)
tmp_div=div
ctr=0
#N=K^i(jK+1)
#i>0
for k in div:
  tmp_div=div
  k_i=k #k^i
  while n%(k_i*k)==0:
    k_i*=k
  if (n//k_i)%k==1:
    ctr+=1

#i==0
div=make_divisors(n-1)
for k in div:
  if n%k==1:
    ctr+=1
print(ctr)

Measured memory_bytes: 39792
fun main() {
    val N = readLine()!!.toInt()
    val an = readLine()!!.split(" ").map(String::toInt)

    var count = 0
    an.forEachIndexed { i, n ->
        if (i % 2 == 0 && n % 2 == 1) {
            count++
        }
    }
    println(count)
}

Measured memory_bytes: 36364
def main():
    N = int(input())
    B = list(map(int,input().split()))
    A = []

    for i in range(N):
        # 先頭追加
        if(i == 0):
            A.append(B[i])
            continue

        # ラスト追加
        if(i == N-1):
            A.append(B[i-1])
            continue

        # 通常
        A.append(min([B[i],B[i-1]]))

    print(sum(A))

    
if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
  int H=1,W=1;
  int h,w;

  while(1){
    scanf("%d%d", &H, &W);
    if(H==0 && W==0)
      break;
    for(h=0;h<H;h++){
      for(w=0;w<W;w++)
	if((h%2 == 0 && w%2 == 0) || (h%2 == 1 && w%2 == 1))
	  printf("#");
	else
	  printf(".");
      printf("\n");
    }
    printf("\n");
  }
  
  return 0;
}

Measured memory_bytes: 572
using System;
using System.Linq;

class C
{
	static void Main() => Console.WriteLine(Enumerable.Range(0, int.Parse(Console.ReadLine())).Select(i => new string(Console.ReadLine().OrderBy(s => s).ToArray())).GroupBy(s => s).Select(g => g.Count()).Where(c => c > 1).Sum(c => (long)c * (c - 1) / 2));
}


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

int main(void){
    int N;
    while( cin >> N , N ){
        string L[50];
        int P[50], A[50], B[50], C[50], D[50], E[50], F[50], S[50], M[50];
        vector< pair<double, string> > ans(N);

        for(int i = 0; i < N; i++){
            int time = 0, value = 0;
            cin >> L[i] >> P[i] >> A[i] >> B[i] >> C[i] >> D[i] >> E[i] >> F[i] >> S[i] >> M[i];
            ans[i].second = L[i];
            time = A[i] + B[i] + C[i] + (D[i] + E[i]) * M[i];
            value = M[i] * F[i] * S[i] - P[i];
            ans[i].first = -value / (double)time;
        }

        sort(ans.begin(), ans.end());
        for(int i = 0;  i< N; i++){
            cout << ans[i].second << endl;
        }
        cout << "#" << endl;

    }
    return 0;
}

Measured memory_bytes: 1220
fun main() {
    var n = readLine()!!.toLong()
    val az = listOf("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z")
    var result = StringBuilder()
    
    while(n > 0) {
        val h = (n % 26).toInt()
        if(h == 0) {
            result.append(az[25])
            n--
        } else {
            result.append(az[h - 1])
        }
        n /= 26
    }
    val output = result.split("").reversed().joinToString("")
    println(output)
}

Measured memory_bytes: 39904
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        boolean flag = true;
        while(n--!=0){
            int x = s.nextInt();
            if(x%2==0&&x%5!=0&&x%3!=0){
                flag = false;
                break;
            }
        }
        System.out.println(flag?"APPROVED":"DENIED");
    }
}




class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int nextInt() throws IOException {return Integer.parseInt(next());}

    public long nextLong() throws IOException {return Long.parseLong(next());}

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 25428
#include <iostream>
//#include <iomanip>
//#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
//ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}

int main(){
	ll a,b,c,d ;
	cin >> a >> b >> c >> d ;
	a-- ;
	ll ans = b-a ;
	ans -= b/c-a/c ;
	ans -= b/d-a/d ;
	ll e = lcm(c,d) ;
	ans += b/e-a/e ;
	cout << ans << endl ;
}


Measured memory_bytes: 256
import sys,collections
V,E = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
#sdw = [[src1 dist1 d1][src1 dist1 d1]...]# vect source1 -> distance1 distances
INF = float("inf")

st = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param

G = [[] for _ in range(V)]

for s,t in st:
    G[s].append(t)

visited = set()
indeg = [0]*V
ret = []
def bfs(s):
    q = collections.deque([s])
    visited.add(s)
    while q:
        u = q.popleft()
        ret.append(u)
        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and not v in visited:
                visited.add(v)
                q.append(v)

def topologicalSort_bfs():
    for a in G:
        for t in a:
            indeg[t] += 1
    #print(G,indeg)
    for i in range(V):
        if indeg[i] == 0 and not i in visited:
            bfs(i)

def dfs(s):
    #print("s:",s)
    if s in visited:
        return
    for e in G[s]:
        dfs(e)
    ret.append(s)
    visited.add(s)

def topologicalSort_dfs():
    for i in range(V):
        dfs(i)
    ret.reverse()

topologicalSort_bfs()
#topologicalSort_dfs()
print(*ret,sep='\n')



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

using ll = long long;
const ll HSIZE=100001;
const ll INF=1e15;

ll solve(int n){
    vector<int> h(n);
    for(int i=0;i<n;i++) cin>>h[i];
    int m;
    cin>>m;
    vector<ll> smp,sdmg;
    vector<ll> amp,admg;
    bool isok=false;
    for(int i=0;i<m;i++){
        string buf,tar;
        int mp,dmg;
        cin>>buf>>mp>>tar>>dmg;
        if(mp==0){
            if(dmg==0) continue;
            isok=true;
        }
        else if(tar=="Single"){
            smp.push_back(mp);
            sdmg.push_back(dmg);
        }
        else{
            amp.push_back(mp);
            admg.push_back(dmg);
        }
        
    }
    if(isok) return 0;
    int N=sdmg.size();
    vector<ll> sdp;
    {
        vector<vector<ll>> tmp(2,vector<ll>(HSIZE,INF));
        tmp[0][0]=0;
        for(int i=0;i<N;i++){
            int fr=i&1;
            int to=(i+1)&1;
            fill(tmp[to].begin(),tmp[to].end(),INF);
            for(int j=0;j<HSIZE;j++){
                tmp[to][j]=min(tmp[to][j],tmp[fr][j]);
                tmp[to][min(j+sdmg[i],HSIZE-1)]=min(tmp[to][min(j+sdmg[i],HSIZE-1)],tmp[to][j]+smp[i]);
            }
        }
        sdp=tmp[N&1];
    }
    N=admg.size();
    vector<ll> adp;
    {
        vector<vector<ll>> tmp(2,vector<ll>(HSIZE,INF));
        tmp[0][0]=0;
        for(int i=0;i<N;i++){
            int fr=i&1;
            int to=(i+1)&1;
            fill(tmp[to].begin(),tmp[to].end(),INF);
            for(int j=0;j<HSIZE;j++){
                tmp[to][j]=min(tmp[to][j],tmp[fr][j]);
                tmp[to][min(j+admg[i],HSIZE-1)]=min(tmp[to][min(j+admg[i],HSIZE-1)],tmp[to][j]+amp[i]);
            }
        }
        adp=tmp[N&1];
    }
    for(int i=HSIZE-2;i>=0;i--){
        sdp[i]=min(sdp[i],sdp[i+1]);
    }
    ll res=ll(1e15);
    for(int i=0;i<HSIZE;i++){
        ll sc=adp[i];
        for(int j=0;j<n;j++){
            sc+=sdp[max(h[j]-i,0)];
        }
        res=min(res,sc);
    }
    return res;
}
int main(){
    int n;
    while(cin>>n,n){
        cout<<solve(n)<<endl;
    }
    return 0;
}


Measured memory_bytes: 5920
n = int(input())
a = list(map(int, input().split()))
b = [(a[i], i) for i in range(n)]
b.sort()
ans = [0 for i in range(n)]
ans[0] = b[0][0] * n
min_index = b[-1][1]
for i in range(n-1, 0, -1):
    min_index = min(min_index, b[i][1])
    if b[i-1][0] != b[i][0]:
        ans[min_index] += (b[i][0] - b[i-1][0]) * (n-i)
for i in range(n):
    print(ans[i])


Measured memory_bytes: 23932
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define int long long int
using namespace std;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
 //     freopen("q.gir","r",stdin);
 //     freopen("q.cik","w",stdout);
      int n;
      cin>>n;
      vector<int>arr(n+1,0);
      for(int i=1;i<=n;i++)cin>>arr[i];
      vector<int>dp(n+1,INF);
      dp[0]=INF;
      dp[1]=0;
      for(int i=2;i<=n;i++){
            dp[i]=min(dp[i],min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2])));
      }
      cout<<dp[n];
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll n,k;
    cin>>k>>n;
    ll a[n+5],b[n+5];
    for(ll i=0; i<n; i++)
    {

        cin>>a[i];


    }
    ll s1=0,s2=0;
    for(ll i=0; i<n-1; i++)
    {
       b[i]=a[i+1]-a[i];
    }
    b[n-1]=k-a[n-1]+a[0];
    sort(b,b+n);

    for(ll i=0; i<n-1; i++)
    {
        s2=s2+b[i];
    }

    //s2=s2+k-a[n-1]+a[0];
    // cout<<s1<<" "<<s2<<endl;
    cout<<s2<<endl;


    //cout<<s<<endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 105;
typedef long long ll;
int n, a[N], ans = 1e9;

int main() {
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    rep(p, a[1], a[n]) {
        int sum = 0;
        rep(i, 1, n) sum += (a[i] - p) * (a[i] - p);
        ans = min(ans, sum);
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		String a = sc.next();
		String b = sc.next();
		String c = sc.next();
		
		// 計算
		String result = "";
		result = a.substring(0,1).toUpperCase() + b.substring(0,1).toUpperCase() + c.substring(0,1).toUpperCase();
		
		// 出力
		System.out.println(result);
	}
}



Measured memory_bytes: 23380
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = System.Console.ReadLine();
            var valAry = line.Split(' ');
            int valA = 0;
            int valB = 0;
            int.TryParse(valAry[0], out valA);
            int.TryParse(valAry[1], out valB);

            // 素因数分解
            var dictA = GetPrimeFactorization(valA);
            var dictB = GetPrimeFactorization(valB);

            // 辞書を結合
            Dictionary<int, int> varDict = dictA;
            foreach (var keyB in dictB.Keys)
            {
                if (varDict.ContainsKey(keyB) == false)
                {
                    varDict[keyB]= dictB[keyB];
                } else
                {
                    varDict[keyB] = Math.Max(varDict[keyB], dictB[keyB]);
                }
            }
            long lcm = 1; // Least common multiple(最小公倍数)
            foreach (var key in varDict.Keys)
            {
                lcm *= (long)Math.Pow(key, varDict[key]);
            }
            Console.WriteLine(lcm);
            return;
        }

        static int ConvToInt(string str)
        {
            int val = 0;
            return int.TryParse(str, out val) == true ? val : 0;
        }

        /// <summary>
        /// 素因数分解
        /// </summary>
        /// <param name="src"></param>
        /// <returns></returns>
        static Dictionary<int, int> GetPrimeFactorization(int src)
        {
            int val = src;
            List<Tuple<int, int>> tplList = new List<Tuple<int, int>>();
            Dictionary<int, int> varDict = new Dictionary<int, int>();
            int maxCnt = (int)Math.Sqrt(src);
            for (int i = 2; i <= maxCnt; i++)
            {
                if (val == 1)
                {
                    break;
                }
                // i の何乗で割り切れるか
                var calcRes = Calc(val, i);
                if (calcRes == 0)
                {
                    // i は val の約数じゃない
                    continue;
                }
                tplList.Add(new Tuple<int, int>(i, calcRes));
                varDict[i] = calcRes;
                val /= (int)Math.Pow(i, calcRes);
            }
            if (val != 1)
            {
                varDict[val] = 1;
            }
            return varDict;
        }

        /// <summary>
        /// src が divVal の何乗で割れるか
        /// </summary>
        /// <param name="src"></param>
        /// <param name="divVal"></param>
        /// <returns></returns>
        static int Calc(int src, int divVal)
        {
            int cnt = 0;
            while (true)
            {
                int divVal2 = (int)Math.Pow(divVal, cnt + 1);
                if (src % divVal2 != 0)
                {
                    break;
                }
                cnt++;
            }
            return cnt;
        }
    }
}


Measured memory_bytes: 28236
#include<iostream>
#include<map>
#include<cmath>
using namespace std;


int countOf2(int n){
	static map<int,int> memo;
	if(memo.count(n)==0){
		if(n%2==0){
			memo[n]=countOf2(n/2)+1;
		}else{
			memo[n]=0;
		}
	}
	return memo[n];
}

int main(){
	int N;
	int m=-1;
	cin >> N;
	for(int i=0;i<N;i++){
		int A;
		cin >> A;
		int cntOf2=countOf2(A);
		if(m==-1 || cntOf2<m){
			m=cntOf2;
		}
	}
	cout << m << endl;
}


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

int main(){
  long n,i,j,ans=0;
  cin >> n;
  vector<long> h(n+2);
  for(i=1; i<=n; i++){
    cin >> h[i];
  }
  for(i=0; i<100; i++){
    for(j=1; j<=n; j++){
      if(h[j-1]<=i && h[j]>i){
        ans++;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
 
int main(){
	long long n,a,min,num=0;
	vector<long long> p;
 
	cin >> n;
    cin >> min;
    num++;

    for(long long i = 1; i < n; i++){
        cin >> a;
        if(a <= min){
            min = a;
            num++;
        }
    }


	cout << num << endl;
}

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

using namespace std;
using ll = long long;

int main() {
    string s;
    cin>>s;
    string ans="No";
    for(int i = 0;i < 3;++i) {
        if(s[i]=='7')ans="Yes";
    }
    cout<<ans<<endl;
    return 0;
}


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

int main(){
    int N; cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    unordered_map<int, int> mp;
    for(int i = 0; i < N; i++){
        mp[A[i]]++;
    }
    int cnt = 0;
    for(auto e: mp){
        if(e.second % 2 == 1) cnt++; 
    }
    cout << cnt << endl;
}

Measured memory_bytes: 4772
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <math.h> 
#include <iomanip>
#include <string.h>
#include <vector>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 2e5 + 5;

 
int arr[N];

int32_t  main() {

	IOS;



	int x, n;
	cin >> x >> n;

	for (int i = 0; i < n; i++) {
		int tmp;

		cin >> tmp;
		arr[tmp]++;

	}

	int tmp =x;
	int tmp2 =x;
	for (; ; tmp--, tmp2++) {

		if (arr[tmp] != 1) {
			cout << tmp;
			break;

		}
		if (arr[tmp2] != 1) {
			cout << tmp2;
			break;
		}

	}


}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	long long ans = k * pow(k - 1, n - 1);
	cout << ans << '\n';
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
ll dp[1000][2][5]; //i 桁　ギリギリ攻めてるか　k個
int main()
{
    string n;
    cin >> n;
    int K;
    cin >> K;
    dp[0][0][0] = 0;
    dp[0][1][0] = 1;
    for (int i = 0; i < n.length(); i++)
    {
        rep(k, K)
        {
            int tmp = n[i] - '1';
            dp[i + 1][0][k] += dp[i][0][k];         //０を追加
            dp[i + 1][0][k + 1] += dp[i][0][k] * 9; // ０以外を追加
            if (n[i] != '0')
            {
                dp[i + 1][1][k + 1] += dp[i][1][k];       //ギリギリを追加
                dp[i + 1][0][k + 1] += dp[i][1][k] * tmp; //ギリギリ以外で0じゃない
                dp[i + 1][0][k] += dp[i][1][k];           //ギリギリ以外で0
            }
            else{
                dp[i + 1][1][k] += dp[i][1][k]; //ギリギリを追加
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n.length(); i++)
    {
        ans += dp[i][0][K];
        ans += dp[i][1][K];
    }
    cout << ans << endl;
    return 0;
}

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

#define maxn 100005

using namespace std;
typedef long long ll;

int main(){

  ios_base::sync_with_stdio(0);

  int L;
  cin >> L;
  L--;

  cout << 20 << ' ';

  vector < int > u, v, c;
  #define add(x, y, z) {u.push_back(x); v.push_back(y); c.push_back(z);}

  int i;

  for (i = 19; i > 0 && L > (1 << (19 - i)); --i){
    add(i, i + 1, 0);
    add(i, i + 1, (1 << (19 - i)));
    L -= (1 << (19 - i));
  }

  if (i) add(i, i + 1, 0);

  int val = (1 << (19 - i));

  for (int is = 0; is <= 20; ++is) {
    if ((L >> is)&1) {
      add(max(i, 1), 20 - is, val);
      val += (1 << is);
    }
  }

  while ((--i) > 0)
    add(i, i + 1, 0);

  cout << u.size() << '\n';

  for (int i = 0; i < u.size(); ++i)
    cout << u[i] << ' ' << v[i] << ' ' << c[i] << '\n';
  return 0;

}


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

#define ipr pair<int, int>
#define pb push_back
#define ff first
#define ss second
#define fr(i, j, k) for (int i = j; i < k; i++)
#define rf(i, j, k) for (int i = j; i >= k; i--)
#define ll unsigned long long
#define int long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mp make_pair
#define cnt_ones(x) __builtin_popcountll(x)

#define IOS                           \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

const int Maxn = (int)1e6;
const ld pi = acos(-1);
const int mod = (int)1e9 + 7;
const int inf = (int)1e18;

template <class T>
ostream &operator<<(ostream &out, vector<T> &A) {
    fr(i, 1, (int)A.size()) out << A[i]+1 << " ";
    return out;
}


int32_t main() {
    IOS 
    int n, ans=0;  cin>>n;
    fr(i,2,sqrt(n)+1){
        int cnt=0,temp=1;
        while(n%i==0){
            cnt++;
            n/=i;
        }
        while(cnt>0){
            ans ++;
            cnt -= temp;
            temp++;
        }
        if(cnt < 0) ans--;
    }
    if(n>1) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3676
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#include<sstream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[5];
int main()
{

    while(~scanf("%d%d%d",&a[0],&a[1],&a[2]))
    {
        sort(a,a+3);
        int sum=0;
        sum+=(a[1]-a[0])/2;
        a[0]+=(a[1]-a[0])/2*2;
        sum+=(a[2]-a[1]);
        a[0]+=(a[2]-a[1]);
        if(a[0]!=a[2]) sum+=2;
        printf("%d\n",sum);

    }


    return 0;
}


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

int main(){
    int k;
    cin >> k;
    char S[105];
    cin >> S;
    int l = strlen(S);
    if (l <= k) cout << S << endl;
    else{
        for(int i = 0; i < k; i++){
            cout << S[i];
        }
        cout << "..." << endl;
    }
    return 0;
}

Measured memory_bytes: 3132
//"I'll live the focused life, because it's the best kind there is" - Winifred Gallagher
#include<bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << ": " << a << endl
using namespace std;
#define ll long long
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> pii;
#define sz(a) int(a.size())
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define fast cin.tie(0); ios::sync_with_stdio(false);

int main(){fast;
	string s; cin>>s;
	rep(i, sz(s) - 1){
		if(s[i] != s[i + 1]){
			puts("Yes");
			return 0;
		}
	}	
	puts("No");
}


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

using namespace std;
using ll=long long;

int t;

void test_case(){
    int n;
    cin>>n;
    vector<ll>a(n);
    for(int i=0; i<n; i++)cin>>a[i];
    vector<vector<ll>>dp(n,vector<ll>(n));
    for(int l=n-1; l>=0; l--){
        for(int r=l; r<n; r++){
            if(l==r){
                dp[l][r]=a[l];
                continue;
            }
            dp[l][r]=max(a[l]-dp[l+1][r], a[r]-dp[l][r-1]);
        }
    }
    cout<<dp[0][n-1]<<endl;
}

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

    t=1;
    while(t--){
        test_case();
    }

    return 0;
}

Measured memory_bytes: 73652
import fractions
n,x = map(int,input().split())
X = list(map(int,input().split()))
X = list(map(lambda a:abs(a-x),X))

for i in range(n):
    if i == 0:
        now = X[i]
    else:
        now = fractions.gcd(X[i], now)

print(now)

Measured memory_bytes: 16280
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INT_INF = 2147483647;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef pair<int,int> P;

ll dp[105][100005];

int main(){
    int n,W;
    cin >> n >> W;
    int w[105],v[105];
    rep(i,n)cin >> w[i+1] >> v[i+1];
    for(int i=1;i<=n;i++){
        for(int j = 0;j<W+1;j++){
            dp[i][j]= dp[i-1][j];
            if(j-w[i]>=0)chmax(dp[i][j],dp[i-1][j-w[i]]+v[i]);
        }
    }
    cout << dp[n][W] << endl;
}

Measured memory_bytes: 79360
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
que = collections.deque()
que.append((0,0))
while que:
  i,j = que.popleft()
  A[i][j] = "."
  if 0 <= i+1 < h:
    if A[i+1][j] == "#":
      que.append((i+1,j))
      continue
  if 0 <= j + 1 < w:
    if A[i][j+1] == "#":
      que.append((i,j+1))
# print(*A,sep="\n")
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      print("Impossible")
      exit()
print("Possible")

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

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    char x,y;
    cin >> x >> y;
    if(x<y) cout << "<" << endl;
    else if(x>y) cout << ">" << endl;
    else cout << "=" << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
S = [list(map(int, input().split())) for l in range(Q)]
 
numList = {}
sum = 0

for n in range(N):
  if A[n] not in numList:
    numList[A[n]] = 0
  numList[A[n]] += 1
  sum += A[n]

for q in range(Q):
  if S[q][0] in numList:
    if S[q][1] not in numList:
      numList[S[q][1]] = 0
    sum += (S[q][1] - S[q][0]) * numList[S[q][0]]
    numList[S[q][1]] += numList[S[q][0]]
    numList[S[q][0]] = 0
  print(sum)

Measured memory_bytes: 36040
# include <bits/stdc++.h>
using namespace std;
# define F(i, s, t) for (int i = (s), _ = (t); i <= _; i ++)
# define LL unsigned long long
const int N = 605;
const LL X[2] = { 1009, 997 };
int n, m; char s[N][N]; LL Xn[2], h[2][N][N]; int ans;
int Get(int o, int x, int y) {
	return 	+ h[o][x+n-1][y+n-1]
			- h[o][x+n-1][y-1] * Xn[o]
			- h[o][x-1][y+n-1] * Xn[o^1]
			+ h[o][x-1][y-1] * Xn[o] * Xn[o^1];
}
int main() {
	scanf("%d", &n), m = n << 1;
	F(i, 1, n)
		scanf("%s", s[i] + 1);
	F(i, 1, m)
		F(j, 1, m)
			s[i][j] = s[i <= n ? i : i-n][j <= n ? j : j-n];
	Xn[0] = Xn[1] = 1;
	F(i, 1, n)
		Xn[0] *= X[0], Xn[1] *= X[1];
	F(o, 0, 1) {
		F(i, 1, m)
			F(j, 1, m)
				h[o][i][j] = h[o][i][j-1] * X[o] + s[i][j];
		F(j, 1, m)
			F(i, 1, m)
				h[o][i][j] = h[o][i-1][j] * X[o^1] + h[o][i][j];
	}
	F(i, 1, n)
		F(j, 1, n)
			ans += Get(0, i, j) == Get(1, i, j);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 6272
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include<random>
#include<iostream>
using namespace std;


int main() {
	int N;
	char S[10001];

	cin >> N;
	cin >> S;
	int L = strlen(S);
	for (int i = 0; i < L; i++) {
		S[i] = 'A' + (S[i] - 'A' + N) % 26;
	}
	cout << S;

}

Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; ++i)
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define P pair<int, int>
#define loc first
#define num second

map<string, int> m;
string s;
bool ng = false;

P atom(int now){
  stringstream ss;
  if(now + 1 < s.size() && islower(s[now + 1])){
    ss <<s[now] <<s[now + 1];
    now += 2;
  } else{
    ss <<s[now];
    now += 1;
  }
  //debug
  //cout <<ss.str() <<endl;
  if(m.find(ss.str()) == m.end()){
    ng = true;
    return P(now, 0);
  } else{
    return P(now, m[ss.str()]);
  }
}

P number(int now){
  stringstream ss;
  for( ; isdigit(s[now]); ++now) ss <<s[now];
  return P(now, atoi(ss.str().c_str()));
}

P molecule(int now){
  //debug
  //cout <<"-----------------" <<endl;

  int sum = 0;
  while(s[now] != ')' && now < s.size()){
    if(s[now] == '('){
      P ret = molecule(now + 1), n = number(ret.loc + 1);
      now = n.loc;
      sum += (ret.num * n.num);
    } else{
      P a = atom(now);
      sum += a.num;
      now = a.loc;
    }
  }
  return P(now, sum);
}

int main() {
  while(cin >>s && s != "END_OF_FIRST_PART"){
    int n; cin >>n;
    m[s] = n;
  }
  while(cin >>s && s != "0"){
    ng = false;
    stringstream ss;
    ss << "(";
    REP(i, s.size()){
      if(isalpha(s[i]) && isupper(s[i])){
        if(i + 1 < s.size() && isdigit(s[i + 1])){
          ss <<"(" << s[i] << ")";
        } else if(i + 2 < s.size() && islower(s[i + 1]) && isdigit(s[i + 2])){
          ss <<"(" <<s[i] <<s[i + 1] <<")";
          ++i;
        } else{
          ss <<s[i];
        }
      } else{
        ss << s[i];
      }
    }
    ss <<")1";
    //debug
    //cout <<ss.str() <<endl;

    s = ss.str();
    int ans = molecule(0).num;
    if(ng) cout <<"UNKNOWN" <<endl;
    else cout <<ans <<endl;
  }
  return 0;
}

Measured memory_bytes: 1256
//file_name:ABC61_B.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    ll a[m] = {};
    ll b[n] = {};
    rep(i,m){
        int x,y;
        scanf("%d%d",&x,&y);
        b[x-1]++;
        b[y-1]++;
    }
    rep(i,n){
        cout << b[i] << endl;
    }

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
struct POS{
  double x;
  double y;
};
bool cross(POS a, POS b, POS c, POS d);
int main(){
  POS a,b,c,d;
  for(;;){
    if(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&(a.x),&(a.y),&(b.x),&(b.y),&(c.x),&(c.y),&(d.x),&(d.y)) == EOF) break;
    if(cross(a,c,b,d) && cross(b,d,a,c)) cout <<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
  return 0;
}
bool cross(POS a, POS b, POS c, POS d){
  POS v,w,u;
  v.x = a.x-b.x;
  v.y = a.y-b.y;
  w.x = c.x-b.x;
  w.y = c.y-b.y;
  u.x = d.x-b.x;
  u.y = d.y-b.y;
  return (v.x*w.y-v.y*w.x)*(v.x*u.y-v.y*u.x)<0;
}

Measured memory_bytes: 1224
s = Array.new( 13, false )
h = Array.new( 13, false )
c = Array.new( 13, false )
d = Array.new( 13, false )

n = gets.to_i
for i in ( 0 ... n )
	pattern, num = gets.split( " " )
	case pattern
		when "S"
			s[ num.to_i-1 ] = true
		when "H" 
			h[ num.to_i-1 ] = true
		when "C"
			c[ num.to_i-1 ] = true
		when "D"
			d[ num.to_i-1 ] = true
		else
	end
end

for i in ( 0 ... 13 )
	if !s[i]
		print( "S #{i+1}\n" )		
	end
end

for i in ( 0 ... 13 )
	if !h[i]
		print( "H #{i+1}\n" )	
	end
end

for i in ( 0 ... 13 )
	if !c[i]
		print( "C #{i+1}\n" )	
	end
end

for i in ( 0 ... 13 )
	if !d[i]
		print( "D #{i+1}\n" )	
	end
end

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

int main()
{
	while (true)
	{
		int n;
		scanf("%d", &n);
		if (!n) break;
		
		std::vector<int> points(n);
		for (auto& e: points) scanf("%d", &e);
		std::sort(points.begin(), points.end());
		int sum{};
		for (int i{1}; i < n - 1; i++)
			sum += points[i];
		printf("%d\n", sum / (n - 2));
	}

	return 0;
}


Measured memory_bytes: 3176
# ND <= M
# D <= M // N
# DはMの約数


def divisors(n):
    """
    nの約数をO(√n)で列挙する
    """
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


N, M = map(int, input().split())
ans = 0
for D in divisors(M):
    if ans < D <= M // N:
        ans = D
print(ans)


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

int main() {
  int n, d;
  cin >> n >> d;
  int tph = 2 * d + 1;
  int ans = 0;
  for(int i=0; i<n; i++) {
    if(n>tph * i) {
      ans = i + 1;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import math
n = int(input())
ar = input()
w = 0
r = 0
ans = 0
for i in ar:
  if i == 'W':
    w += 1
  else:
    r += 1
if w == 0 or r == 0:
  print(ans)
else:
  for j in range(-1,-len(ar)-1,-1):
    if w == 0:
      break
    if ar[j] == 'R':
      ans += 1
    w -= 1
  print(ans)

Measured memory_bytes: 9460
import sys
def frog():
    for i in range(n):
        for j in range(i+1,i+k+1):
            if(j<n):
                dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
    return dp[n-1]
if __name__ == "__main__":
        n,k=map(int,input().split())
        dp = [sys.maxsize] * n
        dp[0] = 0
        l = list(map(int, input().split()))
        sys.stdout.write(str(frog()))

Measured memory_bytes: 53216
#include <bits/stdc++.h>
 
const double pi = 3.141592653589793238462643383279;
using namespace std;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
 
 
//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 SQ(a) ((a)*(a))
#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,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
 
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)

//ここから編集 
ll modPow(ll x, ll n, ll mod = MOD){
    ll res = 1;
    while(n){
        if(n&1) res = (res * x)%mod;
 
        res %= mod;
        x = x * x %mod;
        n >>= 1;
    }
    return res;
}
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int K; cin >> K;

  ll t = 7;
  for(int i=1; i<=2000000; i++){
    if(t%K == 0){
      cout << i << endl;
      return 0;
    }

    t += (7 * modPow(10, i, K))%K;
    //cout << t << endl;
    t %= K;
  }
  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 3648
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define d_5 100000
#define d9_7 1000000007
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define pb push_back
int main(void){
  ll n,k;
  cin>>n;
  vi a(n);
  vi b(n);
  vi c(n-1);
  rep(i,n){
    cin>>a[i];
    a[i]--;
  }
  rep(i,n){
    cin>>b[i];
  }
  rep(i,n-1){
    cin>>c[i];
  }
  ll ans=0;
  rep(i,n){
    ans+=b[a[i]];
    if(a[i]<n-1&&i<n-1){
      if(a[i]+1==a[i+1]){
        ans+=c[a[i]];
      }
    }
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
D,N=map(int, input().split())
c=0
if D==0:
    if N!=100:
        print(N)
    else: print(101)
    exit()
d=100**D
for i in range(d,d*200+1,d):
    if (i//d)%100 != 0:
        c+=1
        if c==N:
            print(i)
            exit()


Measured memory_bytes: 38384