akhauriyash/Code-Regression huggingface dataset:
from collections import deque

n,m = map(int,input().split())
li = [list(map(int,input().split())) for i in range(m)]

road = [[] for i in range(n)]

for i in li:
    i[0]-=1
    i[1]-=1
    road[i[0]].append(i[1])
    road[i[1]].append(i[0])

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.popleft()
    for i,r in enumerate(road[v]):
        if dist[r]!=-1:
            continue
        dist[r] = v+1
        que.append(r)

dist.pop(0)
print('Yes')
print(*dist,sep='\n')

Measured memory_bytes: 62556
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 10005

int N,W;
int dp[NUM];

int main(){

	dp[0] = 0;
	for(int i = 1; i < NUM; i++){

		dp[i] = BIG_NUM;
	}

	scanf("%d %d",&N,&W);

	int value,weight;

	for(int loop = 0; loop < N; loop++){

		scanf("%d %d",&value,&weight);

		for(int i = NUM-1; i >= 0; i--){
			if(i-value < 0)break;

			dp[i] = min(dp[i],dp[i-value]+weight);
		}
	}

	for(int i = NUM-1; i >= 0; i--){

		if(dp[i] <= W){

			printf("%d\n",i);
			return 0;
		}
	}

	return 0;
}



Measured memory_bytes: 3268
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <functional>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <string>
#define SIZE 405

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

int C[SIZE][4];
map <PP,int> mp;

void rem(int a,int b,int c,int d)
{
	mp[PP(P(a,b),P(c,d))]--;
	mp[PP(P(b,c),P(d,a))]--;
	mp[PP(P(c,d),P(a,b))]--;
	mp[PP(P(d,a),P(b,c))]--;
}
void remp(PP p)
{
	rem(p.first.first,p.first.second,p.second.first,p.second.second);
}
void ins(int a,int b,int c,int d)
{
	mp[PP(P(a,b),P(c,d))]++;
	mp[PP(P(b,c),P(d,a))]++;
	mp[PP(P(c,d),P(a,b))]++;
	mp[PP(P(d,a),P(b,c))]++;
}
void insp(PP p)
{
	ins(p.first.first,p.first.second,p.second.first,p.second.second);
}
int same(PP p,PP q)
{
	int a=p.first.first,b=p.first.second,c=p.second.first,d=p.second.second;
	int ret=0;
	if(q==PP(P(a,b),P(c,d))) ret++;
	if(q==PP(P(b,c),P(d,a))) ret++;
	if(q==PP(P(c,d),P(a,b))) ret++;
	if(q==PP(P(d,a),P(b,c))) ret++;
	return ret;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d %d %d %d",&C[i][0],&C[i][1],&C[i][2],&C[i][3]);
	vector <PP> vx;
	ll ret=0;
	for(int i=n-1;i>=0;i--)
	{
		for(int j=0;j<vx.size();j++)
		{
			PP p=vx[j];
			int a=p.first.first,b=p.first.second,c=p.second.first,d=p.second.second;
			//rem(a,b,c,d);
			PP x=PP(P(C[i][0],C[i][1]),P(b,a));
			PP y=PP(P(C[i][1],C[i][2]),P(c,b));
			PP z=PP(P(C[i][2],C[i][3]),P(d,c));
			PP w=PP(P(C[i][3],C[i][0]),P(a,d));
			ll all=1;
			all*=(ll) mp[x]-same(p,x);
			int A=same(x,y);
			all*=(ll) mp[y]-A-same(p,y);
			int B=same(x,z)+same(y,z);
			all*=(ll) mp[z]-B-same(p,z);
			int D=same(x,w)+same(y,w)+same(z,w);
			all*=(ll) mp[w]-D-same(p,w);
			//if(i==1&&a==1&&b==1&&c==0&&d==0) printf("%d : %d %d %d %d : %d %d %d %d : %lld\n",i,a,b,c,d,mp[x],mp[y],mp[z],mp[w],all);
			ret+=all;
			//ins(a,b,c,d);
		}
		int a=C[i][0],b=C[i][3],c=C[i][2],d=C[i][1];
		ins(a,b,c,d);
		vx.push_back(PP(P(a,b),P(c,d)));
		vx.push_back(PP(P(b,c),P(d,a)));
		vx.push_back(PP(P(c,d),P(a,b)));
		vx.push_back(PP(P(d,a),P(b,c)));
	}
	printf("%lld\n",ret);
	return 0;
}


Measured memory_bytes: 80128
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int dp[N];
int h[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&h[i]),dp[i] = 1<<30;
    dp[1] = 0;
    for(int i=2;i<=n;i++){
        if(i-1>0)   dp[i] = min(dp[i],dp[i-1]+abs(h[i]-h[i-1]));
        if(i-2>0)   dp[i] = min(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
    }
    printf("%d\n",dp[n]);
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;



int main(){
	int n, mx = 0, id = 0, a[55];
	scanf("%d", &n);
	for(int i = 1; i<=n; i++){
		scanf("%d", &a[i]);
		if(abs(a[i])>mx){
			mx = abs(a[i]);
			id = i;
		}
	}
	if(id == 0) id = 1;
	printf("%d\n", 2*n-1);
	for(int i = 1; i<=n; i++)
		printf("%d %d\n", id, i);
	if(a[id]>0)
		for(int i = 1; i<n; i++)
			printf("%d %d\n", i, i+1);
	else
		for(int i = n; i>1; i--)
			printf("%d %d\n", i, i-1);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF (1<<30)
long long data[50001];

int main(){
  int n,m; //nがしたい金額、　mがコインの種類
  cin >> n >> m;
  for(int i=0;i<=n;i++){
    data[i] = INF;
  }
  data[0] = 0;
  int a,b;
  for(int i=0;i<m;i++){
    cin >> a;
    data[a] = 1;
  }
  for(int i=2;i<=n;i++){
    for(int j=i-1;j>0;j--){
      data[i] = min( (data[j]+data[i-j]), data[i]);
    }
  }
  cout << data[n] << endl;
  return 0;
}

Measured memory_bytes: 3468
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            n -= Integer.parseInt(st.nextToken());
        }

        pw.println(n >= 0 ? n : -1);

        pw.close();
    }
}

Measured memory_bytes: 34316
n = int(input())
A = list(map(int, input().split()))
count = 0

for i in range(n):
    minj = i
    for j in range(i, n):
        if A[j] < A[minj]:
            minj = j
        else:
            pass
    A[i], A[minj] = A[minj], A[i]
    if i != minj:
        count += 1
        
print(*A)
print(count)


Measured memory_bytes: 5608
n = int(input())
a = list(map(int,input().rstrip().split(" ")))
summ = 0
ans_when_odd_indexes_plus = 0
ans_when_odd_indexes_minus = 0
for i in range(n):
    summ += a[i]
    if i % 2 == 0:
        if summ <= 0:
            ans_when_odd_indexes_plus += 1 - summ
            summ = 1
    else:
        if summ >= 0:
            ans_when_odd_indexes_plus += 1 + summ
            summ = -1

summ = 0
for i in range(n):
    summ += a[i]
    if i % 2 == 1:
        if summ <= 0:
            ans_when_odd_indexes_minus += 1 - summ
            summ = 1
    else:
        if summ >= 0:
            ans_when_odd_indexes_minus += 1 + summ
            summ = -1

print(min(ans_when_odd_indexes_plus,ans_when_odd_indexes_minus))

Measured memory_bytes: 19872
import java.util.Scanner;

public class Main {

  static String compare(int a, int b) {
    String operator = "";
    if (a < b) {
      operator = " < ";
    } else if (a > b) {
      operator = " > ";
    } else {
      operator = " == ";
    }
    return operator;
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    int a = stdIn.nextInt();
    int b = stdIn.nextInt();
    String operator = compare(a,b);
    System.out.println("a"+operator+"b");
  }
}

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

int main(void) {
    int N;cin>>N;
    int D,X;cin>>D>>X;
    int chocolate = 0;
    for (int i = 0; i < N; i++) {
        int A;cin>>A;
        int j = 0;
        while (j * A + 1 <= D) {
            chocolate++;
            j++;
        }
    }
    cout << chocolate + X << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <array>
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

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

  cin >> katanaNum >> enemyHP;
  vector<int> a(katanaNum);
  vector<int> d(katanaNum);
  int maxA = 0;

  for(int i=0; i<katanaNum; i++) cin >> a[i] >> d[i];

  sort(a.begin(), a.end(), greater<int>());
  sort(d.begin(), d.end(), greater<int>());

  maxA = a[0];
  
  int ans = enemyHP;
  for (int katanaIdx = 0; katanaIdx <= katanaNum; katanaIdx++) {
    enemyHP -= d[katanaIdx];
    int count = 0;
    if(enemyHP > 0) {
    	count = (enemyHP + maxA -1) / maxA;
    }
    ans = min(ans, count + katanaIdx + 1);
  }

  cout << ans;

  return 0;
}

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

using namespace std;

using   ll=long long;
using   ld=long double;

#define fast           ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl           "\n"
#define long long      int 
#define pb             push_back
#define mp             make_pair
#define ff             first
#define ss             second
#define pll            pair<ll,ll>
#define ALL(v)         v.begin(),v.end()
#define ALLR(v)        v.rbegin(),v.rend()
#define pii            3.14159265358979323
#define inf 		   LLONG_MAX
#define ones(x)		   __builtin_popcount(x)

void solve()
{
	string s;
	
	cin>>s;
	
	if(s.size()%2)
	{
		cout<<"No";
		return;
	}
	
	for(int i=0;i<s.size();i+=2)
	{
		if(s[i] != 'h' || s[i+1] != 'i')
		{
			cout<<"No";
			return;
		}
	}
	
	cout<<"Yes";
}
 
signed main()
{
 
    fast;
 
    ll t;
    
    t=1;
    
    //cin>>t;
    
    while(t--)
    {
        solve();
    }
 
    return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B, C = MAP()
print(max(10*A + B + C, 10*B + A + C, 10*C + A + B))

Measured memory_bytes: 5192
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    char s;
    s = getchar();
    if(s=='a'||s=='e'||s=='i'||s=='o'||s=='u')
        printf("vowel\n");
    else printf("consonant\n");
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	int n , x , min , max;
	long long sum = 0;
	min = 10000001;
	max = -10000001;
	
	cin >> n;
	
	for (int i = 1 ; i <= n ; i++){
		cin >> x;
		if(min > x) {
			min=x;
			
		}if(max < x){
			max = x;	
			}
		sum += x;
	}
	cout << min << " " << max << " " << sum << endl;
}


Measured memory_bytes: 3128
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;

struct Node{
  int key;
  Node *right,*left,*parent;
};

Node *root,*NIL;

Node *treeMinimum(Node *x){
  while(x->left!=NIL)x=x->left;
  return x;
}
Node *find(Node *u,int k){
  while(u!=NIL && k!=u->key){
    if(k<u->key)u=u->left;
    else u = u->right;
  }
  return u;
}

Node * treeSuccessor(Node *x){
  if(x->right!=NIL)return treeMinimum(x->right);
  Node *y=x->parent;
  while(y!=NIL&&x==y->right){
    x=y;y=y->parent;
  }
  return y;
}

void treeDelete(Node *z){
  Node *y;
  Node *x;

  if(z->left == NIL || z->right==NIL)y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL){
    x=y->left;
  }
  else{
    x=y->right;
  }
  if(x!=NIL){
    x->parent = y->parent;
  }
  if(y->parent==NIL){
    root=x;
  }
  else{
    if(y==y->parent->left){
      y->parent->left=x;
    }
    else{
      y->parent->right=x;
    }
  }
  if(y!=z){
    z->key=y->key;
  }
  free(y);
}

void insert(int k){
  Node *y=NIL;
  Node *x=root;
  Node *z;

  z=(Node *)malloc(sizeof(Node));
  z->key=k;
  z->left=NIL;
  z->right=NIL;

  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL){
    root=z;
  }
  else{
    if(z->key<y->key){
      y->left=z;
    }
    else{
      y->right=z;
    }
  }
}
void inorder(Node *u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node *u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}
int main(){
  int n,i,x;
  string com;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    cin >> com;
    if(com[0]=='f'){
      scanf("%d",&x);
      Node *t=find(root,x);
      if(t!=NIL)printf("yes\n");
      else printf("no\n");
    }
    else if(com=="insert"){
      scanf("%d",&x);
      insert(x);
    }
    else if(com=="print"){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(com=="delete"){
      scanf("%d",&x);
      treeDelete(find(root,x));
    }
  }
  return 0;
}

Measured memory_bytes: 22048
#include<stdio.h>
#include<math.h>
#include<stdlib.h>


int main(){
	int i,j,k;
	int A,B,C,D;
	
	scanf("%d",&A);
	scanf("%d",&B);
	scanf("%d",&C);
	scanf("%d",&D);
	
	A += B;
	C += D;
	
	if(A>C)printf("Left\n");
	else if(A<C)printf("Right\n");
	else printf("Balanced\n");
	
	return 0;
}

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

int main(){
int n;
cin>>n;
if(n==0){
  cout<<1<<endl;
}else if(n==1){
  cout<<2<<endl;
}else if(n==2){
  cout<<1<<endl;
}else{
  cout<<0<<endl;
}
return 0;
}



Measured memory_bytes: 3116
#include <stdio.h>
#include <math.h>
void main()
 {
  int n,i,s[1000];
  double avg,sum,sum1;
  while(1)
    {
    scanf("%d", &n);
    if (n == 0)
    {
      break;
    }
    sum=sum1=0.0;
    for (i=0;i<n;i++) {
      scanf("%d",&s[i]);
      sum += s[i];
      sum1 += s[i]*s[i];
    }
    avg = sum / n;
    printf("%.8lf\n", sqrt(sum1/n-avg*avg));
  }
  return 0;
}



Measured memory_bytes: 2104
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
    cin >> first;
    IN(rest...);
    return;
}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))

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; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second < b.second; }

const int MOD = 1000000007;

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

ll divi_wa(ll n,ll m){
    ll ans = 0;
    for (ll i = 0; n>0 ; i++)
    {
        ans+=(n%m);//n進法での各けたの数の和を取る
        n = n/m;
    }
    return ans;
}
vl divisor(ll n){
    vector<ll> ret;
    for(ll i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(i * i != n) ret.push_back(n / i);
        }
    }
    return ret;
}

int main() {
    SS(ll,n,s);
    if(n==s){
        p(n+1);
        return 0;
    }
    else if(n<=1000000){ //全探索
        rep(i,n-1){
            if(divi_wa(n,i+2)==s){
                p(i+2);
                return 0;
            }
        }
    }else{
        auto v=divisor(n-s);
        sort(v.begin(),v.end());
        rep(i,v.size()){
            if(divi_wa(n,v[i]+1)==s){
                p(v[i]+1);
                return 0;
            }
        }
    }
    p(-1);
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
using namespace std;
int main() {
  int n, k;
  cin >> n;
  cin >> k;
  char s[n];
  cin >> s;
  string begin = "";
  string ss = begin + s;
  string subStr = "RL";
  int unh = 1;
  for (int i = 0; i < n - 1; i++) {
    if (s[i] != s[i + 1]) {
      unh += 1;
    }
  }
  cout << n - max(unh - 2 * k, 1) << endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rem(i, s, n) for (int i = (s); i >= (n); --i)
using ll = long long;
const int MAX = 1e9+7;

int main(){
    int n; cin >> n;
    vector<ll> h(n); rep(i, 0, n) cin >> h[i];

    vector<ll> v(n, MAX); v[0] = 0;
    rep(i, 1, n){
        ll s1 = abs(h[i] - h[i-1]), s2 = 0;
        if(i > 1) s2 = abs(h[i] - h[i-2]);
        else {
            v[i] = v[i-1] + s1;
            continue;
        }
        v[i] = min((v[i-1] + s1), (v[i-2] + s2));
    }

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

    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF (long long)(1e18)
#define MOD (int)(1e9+7)
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define yn(f) (f?"Yes":"No")
#define YN(f) (f?"YES":"NO")
#define MAX  1100

int N, K, a[MAX];
int b[MAX][MAX][60];
bool bb[MAX][MAX];

long long power(long long x, long long n){
	long long ans = 1;
	while(n){
		if(n&1) ans *= x;
		n >>= 1;
		x *= x;
	}
	return ans;
}

void hoge(int i, int j, int k){
	int  count = 0;
	while(k){
		b[i][j][count++] = k%2;
		k/=2;
	}
	// for(int k = 10; k >= 0; k--){
		// cout<<b[i][j][k];
	// }
	// cout<<endl;
}

signed main(){
	cout<<fixed<<setprecision(7);
	int ans = 0;
	cin>>N>>K;
	
	for(int i = 0; i < N; i++){
		cin>>a[i];
	}
	for(int i = 0; i < N; i++){
		int s = 0;
		for(int j = i; j < N; j++){
			s += a[j];
			// cout<<s<<" "<<endl;;
			hoge(i,j,s);
			bb[i][j] = true;
		}
	}
	for(int y = 50; y >= 0; y--){//cout<<y<<endl;
		int s = 0;
		for(int i = 0; i < N; i++){
			for(int j = i; j < N; j++){
				if(bb[i][j])s += b[i][j][y];
			}
		}
		if(s >= K){
			for(int i = 0; i < N; i++){
				for(int j = i; j < N; j++){
					if(b[i][j][y] == 0) bb[i][j] = false;
				}
			}
			// ans += (long long)(2<<y)/2;
			ans += power(2,y);
			// cout<<y<<" "<< (2<<y)/2<<" "<<(2<<y)<<endl;
		}
		// cout<<y<<" "<<(long long)((2<<(long long)y)/2)<<endl;
		// cout<<y<<" "<<power(2,y)<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 518272
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

void solve(std::string s)
{
    ll ans = 0;
    ll cntA = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == 'A')
        {
            cntA++;
        }
        else if (s[i] == 'B' && s[i + 1] == 'C')
        {
            ans += cntA;
            i++;
        }
        else
        {
            cntA = 0;
        }
    }

    cout << ans << endl;
}

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


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

ll modinv[100005]={}; 

int main(void) {
    ll n,k;
    cin >> n>> k;
    bool checked[n]={};
    set<ll> neighbor[n];
    queue<ll> que;
    rep(i,n-1){
        ll tmpa,tmpb;
        cin >> tmpa >> tmpb;
        tmpa--;
        tmpb--;
        neighbor[tmpa].insert(tmpb);
        neighbor[tmpb].insert(tmpa);
    }
    for(auto x:neighbor[0]){
        que.push(x);
        checked[x]=true;
    }
    ll res=0;
    res+=k;
    rep(i,que.size()){
        res *= k-1-i;
        res %= MOD;
    }
    checked[0]=true;
    while(!que.empty()){
        ll cur=que.front();
        que.pop();
        rep(i,neighbor[cur].size()-1){
            res *= k-2-i;
            res %=MOD;
        }
        for(auto x:neighbor[cur]){
            if(!checked[x]){
                que.push(x);
                checked[x]=true;
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 15232
#include<cstdio>
using namespace std;
int main(){
  int k;
  long a[100000],minx,maxx,x,y;
  scanf("%d",&k);
  for(int i=0;i<k;i++)
    scanf("%ld",&a[i]);
  minx=maxx=2;
  
  for(int i=k-1;i>=0;i--){
    x=minx;
    y=maxx;
    if(x%a[i]==0)
      minx=x;
    else
      minx=a[i]*(x/a[i]+1);
    if(y%a[i]==0)
      maxx=y+a[i]-1;
    else
      maxx=y-y%a[i]+a[i]-1;
  }
  if(maxx<minx)
    printf("-1\n");
  else
    printf("%ld %ld\n",minx,maxx);
}

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

void reader(int *x) {
	int k = getchar_unlocked(); *x = k - '0';
	while (1) {
		k = getchar_unlocked();
		if (k < '0' || k > '9') break;
		*x = ((*x) << 1) + ((*x) << 3) + k - '0';
	}
}
vector<int>E[100000];
int u[200000], v[200000], r[200000], ans[200000], d[100000], cnt = 1;
char b[200000], ok[100000]{ 1 };
queue<int>que;

void bfs(int u, int t) {
	que.push(u);
	while (!que.empty()) {
		int p = que.front(); que.pop(); for (int v : E[p]) {
			if (t) {
				if (d[v] > d[p] && !ok[v]) {
					ok[v] = 1; cnt++; que.push(v);
				}
			}
			else if (!~d[v]) {
				d[v] = d[p] + 1; que.push(v);
			}
		}
	}
}
int main() {
	int n, m, q; reader(&n); reader(&m); reader(&q);
	rep(i, m) {
		reader(&u[i]); reader(&v[i]);
		u[i]--; v[i]--;
		E[u[i]].emplace_back(v[i]); E[v[i]].emplace_back(u[i]);
	}
	memset(d, -1, sizeof(d));
	d[0] = 0; bfs(0, 0);
	rep(i, m) {
		if (d[u[i]] > d[v[i]])swap(u[i], v[i]);
	}
	rep(i, n)E[i].clear();
	rep(i, q) {
		reader(&r[i]); r[i]--;
		b[r[i]] = 1;
	}
	rep(i, m) {
		if (!b[i]) {
			if (d[v[i]] > d[u[i]]) {
				E[u[i]].emplace_back(v[i]);
			}
		}
	}
	bfs(0, 1);
	for (int i = q - 1; i >= 0; i--) {
		ans[i] = n - cnt;
		if (d[v[r[i]]] > d[u[r[i]]] && !ok[v[r[i]]]) {
			E[u[r[i]]].emplace_back(v[r[i]]);
			if (ok[u[r[i]]]) {
				cnt++; ok[v[r[i]]] = 1;
				bfs(v[r[i]], 1);
			}
		}
	}
	rep(i, q)printf("%d\n", ans[i]);
}

Measured memory_bytes: 13708
use std::io::Read;
use itertools::Itertools;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let d: usize = iterator.next().unwrap().parse().unwrap();
    let c: Vec<isize> = (0..26).map(|_| iterator.next().unwrap().parse().unwrap()).collect();
    let mut s: Vec<Vec<isize>> = vec![vec![0; 26]; d];
    for i in 0..d {
        for j in 0..26 {
            s[i][j] = iterator.next().unwrap().parse().unwrap();
        }
    }

    let mut last: Vec<Vec<usize>> = vec![vec![0; 26]; d + 1];

    let mut t: Vec<usize> = vec![0; d];
    for i in 0..d {
        let mut m: isize = 0;
        let mut n: usize = 0;
        for j in 0..26 {
            let mut p = s[i][j];
            for k in 0..26 {
                if j != k {
                    p -= c[k] * (i + 1 - last[i + 1][k]) as isize;
                }
            }
            if p > m {
                m = p;
                n = j;
            }
        }
        t[i] = n + 1;
        for j in 0..26 {
            if j == n {
                last[i + 1][j] = i + 1;
            } else {
                last[i + 1][j] = last[i][j];
            }
        }
    }
    return t.iter().join("\n");
}


Measured memory_bytes: 2432
K = int(input())
AB = list(map(int, input().split()))
A = AB[0]
B = AB[1]
run = True
mul = 1
while run:
    if A<=mul*K<=B:
        break
    if mul*K>B:
        run = False
    else:
        mul += 1
if run:
    print('OK')
else:
    print('NG')

Measured memory_bytes: 9188
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define ll long long 
#define il inline
ll d,t,s;
int main(){
    cin>>d>>t>>s;
    if (t*s>=d) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3620
#include <stdio.h>

int main(){
  int n;
  
  scanf("%d", &n);
  
  int B[n - 1];
  for (int i = 0; i < n; i++) {
    scanf("%d", &B[i]);
  }
  
  int A[n];
  A[0] = B[0];
  
  for (int i = 0; i < n - 2; i++) {
    if (B[i] <= B[i + 1]) {
      A[i + 1] = B[i];
    } else {
      A[i + 1] = B[i + 1];
    }
  }
  
  A[n - 1] = B[n - 2];
  
  int count = 0;
  
  for (int i = 0; i < n ; i++){
    count += A[i];
  }
  
  printf("%d", count);
}


Measured memory_bytes: 128
<?php
list($n, $k) = ints();
$aArray = ints();
$sum = array_sum($aArray);
$d = divisor($sum);
$d = array_reverse($d);
foreach($d as $dd){
  $modArray = [];
  foreach($aArray as $a){
    $modArray[] = $a%$dd; 
  }
  sort($modArray);
  $end = $n;
  $tmp = 0;$sum = 0;
//  o($modArray);
  for($i = 0; $i < $end; $i++){
    $tmp += $modArray[$i];
    $sum += $modArray[$i];
    while($tmp > 0){
      $tmp-=$dd - $modArray[$end - 1];
      $end--;
    }
  }
//  o($sum, $tmp);
  if($sum <= $k && $tmp == 0){
    echo $dd;
    exit;
  }
}

function divisor($n){
    for($i = ceil(sqrt($n)); $i >= 1; $i--){
        if($n % $i == 0){
            $f[] = $i;
            $f[] = $n / $i;
        }
    }
    sort($f);
    return array_unique($f);
}

function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array:";
            echo implode(" ", $val)."\n";
        }else{
            echo "array:array\n";
            foreach($val as $row){
                echo implode(" ", $row)."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}

Measured memory_bytes: 4728
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define inf (int)(3e18)
#define P pair<int,int>
#define mod (int)(1e9+7)
#define mod2 998244353

template<class T> inline void chmin(T &a, T b) {
	a = min(a, b);
}
template<class T> inline void chmax(T &a, T b) {
	a = max(a, b);
}

int N;
vector<int>G[100005];
int depth[100005],parent[100005];
bool used[100005];
void dfs(int x,int par){
    for(int i:G[x])if(i!=par){
        depth[i]=depth[x]+1;
        parent[i]=x;
        dfs(i,x);
    }
}
signed main(){
    cin>>N;
    rep(i,N-1){
        int a,b;cin>>a>>b;a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(0,0);
    vector<P>v;
    rep(i,N)v.push_back(P(depth[i],i));
    sort(all(v),greater<>());
    for(P i:v){
        if(!used[i.second]){
            if(!i.second||used[parent[i.second]]){
                cout<<"First"<<endl;
                return 0;
            }
            used[parent[i.second]]=true;
        }
    }
    cout<<"Second"<<endl;
}

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

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()

using namespace std;

typedef long long ll;

ll grundy(ll a, ll k){
    if(a % k == 0) return a/k;
    if(a == k+1) return 0;
    return grundy(a - (a/k+1) * max(1LL, (a%k) / (a/k+1)), k);
}

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    ll a,k,g = 0LL;
    rep(n){
        cin >> a >> k;
        g = g ^ grundy(a, k);
    }

    if(g){
        cout << "Takahashi" << endl;
    }else{
        cout << "Aoki" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using stkll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

// 2次元ベクトル構造体
// <: 偏角ソート
// verify: https://atcoder.jp/contests/abc139/tasks/abc139_f

const double eps = 1e-9;
struct V {
  double x, y;
  V(double x=0, double y=0): x(x), y(y) {}
  V& operator+=(const V& v) { x += v.x; y += v.y; return *this;}
  V operator+(const V& v) const { return V(*this) += v;}
  V& operator-=(const V& v) { x -= v.x; y -= v.y; return *this;}
  V operator-(const V& v) const { return V(*this) -= v;}
  V& operator*=(double s) { x *= s; y *= s; return *this;}
  V operator*(double s) const { return V(*this) *= s;}
  V& operator/=(double s) { x /= s; y /= s; return *this;}
  V operator/(double s) const { return V(*this) /= s;}
  double dot(const V& v) const { return x*v.x + y*v.y;}
  double cross(const V& v) const { return x*v.y - v.x*y;}
  double norm2() const { return x*x + y*y;}
  double norm() const { return sqrt(norm2());}

  int ort() const { // orthant
    if (abs(x) < eps && abs(y) < eps) return 0;
    if (y > 0) return x>0 ? 1 : 2;
    else return x<0 ? 3 : 4;
  }
  bool operator<(const V& v) const {
    int o = ort(), vo = v.ort();
    if (o != vo) return o < vo;
    return cross(v) > 0;
  }
};
istream& operator>>(istream& is, V& v) {
  is >> v.x >> v.y; return is;
}
ostream& operator<<(ostream& os, const V& v) {
  os<<"("<<v.x<<","<<v.y<<")"; return os;
}

int main() {
    int n;
    cin >> n;
    vector<V> v(n);
    rep(i,n) cin >> v[i];
    sort(v.begin(), v.end());
    double ans = 0;
    rep(l,n) {
        ll r = l;
        V now;
        rep(i,n) {
            now += v[r];
            chmax(ans, now.norm());
            r = (r+1)%n;
        }
    }

    cout.precision(20);
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int[] l = new int[N];
		int[] r = new int[N];
		
		int sum = 0;
		
		for(int i = 0; i < N; i++) {
			l[i] = sc.nextInt();
			r[i] = sc.nextInt();
			sum += r[i] - l[i] + 1;
		}
		
		System.out.println(sum);
		
	}
}


Measured memory_bytes: 28272
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
  ll a,b,c,d,k;
  cin >> a >> b >> c >> d >> k;
  ll x = (c - a) * 60;
  ll y = d - b;
  cout << x + y - k << "\n";
  return 0;
}

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

using ll = long long;
using pii = pair<int, int>;

#define vt          vector
#define sz(x)       (int)(x).size()
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

void solve(int tc) {
    int n;
    cin >> n;
    int a = 0, b = 0, c = 0;
    while (n--) {
        int x, y, z;
        cin >> x >> y >> z;
        tie(a, b, c) = make_tuple(
            max(b + x, c + x),
            max(a + y, c + y),
            max(a + z, b + z)
        );
    }
    cout << max({a, b, c});
}

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

    int tcs = 1;
    for (int tc = 1; tc <= tcs; tc++) solve(tc);
}


Measured memory_bytes: 3656
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        FastScanner in = new FastScanner();
        PrintWriter out = new PrintWriter(System.out, true);
//        int t = in.nextInt();
//        while (t-- > 0)
        solve(in, out);
        out.close();
    }

    public static void solve(FastScanner in, PrintWriter out) {
        String str = in.nextToken();
        System.out.println(str.equals("ABC")?"ARC":"ABC");
    }


    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            init();
        }

        public FastScanner(String name) {
            init(name);
        }

        public FastScanner(boolean isOnlineJudge) {
            if (!isOnlineJudge || System.getProperty("ONLINE_JUDGE") != null) {
                init();
            } else {
                init("input.txt");
            }
        }

        private void init() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        private void init(String name) {
            try {
                br = new BufferedReader(new FileReader(name));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }


        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }

    }

}





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

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

int bfs(long long d, long long N, int state) {
    int ret = 0;
    if (d > N) return 0;
    if (d <= N && state == 7) ret++;
    vector<int> a = {3, 5, 7};
    for (int i = 0; i < 3; i++) ret += bfs(d * 10 + a[i], N, state | (1 << i));
    return ret;
}

int main() {

    long long N;
    cin >> N;

    int ans = bfs(0, N, 0);
    cout << ans << endl;

    return 0;
}





























































Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  int ans = 0;
  for(int i=0;i<3;i++){
    ans *= 10;
    int div;
    if(i==0) div = 100;
    else if(i==1) div = 10;
    else if(i==2) div = 1;
    int sho = n/div;
    int ama = n%div;
    if(sho==9) ans += 1;
    else if(sho==1)ans += 9;
    else ans += sho;
    n = ama;
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
  int n; cin >> n; vector<int> v(n);
  int total = 0;
  for(int i = 0; i < n; ++i) 
  {
    cin >> v[i];
    total ^= v[i];
  }
  
  for(int i = 0; i < n; ++i)
  {
    cout << (total ^ v[i]) << " ";
  }
  return 0;
}


Measured memory_bytes: 4052
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<list>
#include<iomanip>
#include<vector>
using ll = long long;
using namespace std;
const ll MM = 1000000000;
const ll mod = MM + 7;

int main(){
    string s; cin >> s;
    for(int i = 0; i < 26; i++){
        char key = 'a' + i;
        bool flag = false;
        for(int j = 0; j <= s.size(); j++){
            if(s[j] == key){
                flag = true;
            }
        }
        if(!flag){
            cout << key << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
   int main()
   {
       int N;
       cin >> N;
       vector<int> vec(N);
       for (int i=0; i<N; i++) {
           cin >> vec.at(i);
       }
       int is_2 = false;
       int next = 1;
       int count = 1;
       for (int i=0; i<N; i++) {
           if (vec.at(next-1)==2) {
               is_2 = true;
               break;
           } else {
               count++;
               next = vec.at(next-1);
           }
       }
       cout << ((is_2) ? count : -1)<< endl;
    }

Measured memory_bytes: 3768
while True:
    try:
        n = int(input())
    except:
        break

    a = [0 for i in range(n + 1)]

    # sieve
    i = 3
    while i * i <= n:
        for j in range(3 * i, n + 1, 2 * i): a[j] = 1
        i += 2

    count = int(n >= 2)
    count += sum(a[i] == 0 for i in range(3, n + 1, 2))
    print(count)

Measured memory_bytes: 29100
import std.stdio, std.string, std.array, std.conv;

void main() {
    int n = readln.chomp.to!int;
    int[] d = readln.chomp.split.to!(int[]);
    int sum = 0;
    foreach (i; 0 .. n-1) {
        foreach (j; i+1 .. n) {
            sum += d[i] * d[j];
        }
    }
    sum.writeln;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repA(i,a,b) for(int i=a;i<=b;i++)
#define repD(i,b,a) for(int i=b;i>=a;i--)
#define fill(a) memset(a,0,sizeof(a))
#define f first
#define s second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main()
{
    double r;
    cin>>r;
    cout<<setprecision(20);
    cout<<fixed;
    cout<<r*6.28318530717958623200<<endl;
}

Measured memory_bytes: 3776
a, b = map(int, input().split())
if b == 0:
    print(a)
else:
    lis = list(map(int, input().split()))
    tt = [0] * 101
    for k in range(b):
        tt[lis[k]] = 1
    
    if tt[a] == 0:
        print(a)
        exit()
    for k in range(101):
        if a -k < 1:
            print(a-k)
            exit()
        if tt[a - k] == 0:
            print(a-k)
            exit()
        if a + k > 100:
            print(a+k)
            exit()
        if tt[a + k] == 0:
            print(a+k)
            exit()

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

int k,dist[100010];
bool used[100010];
deque<int> q;

inline void add_front(int x,int d)
{
	if(d<dist[x])
	{
		dist[x]=d;
		q.push_front(x);
	}
}

inline void add_back(int x,int d)
{
	if(d<dist[x])
	{
		dist[x]=d;
		q.push_back(x);
	}
}

int main()
{
	cin>>k;
	fill(dist,dist+100000,(1e9+7));
	
	add_front(1,0);
	while(!q.empty())
	{
		int x=q[0];q.pop_front();
		
		if(used[x]) continue;
		used[x]=1;
		
		int d=dist[x],cx=x*10%k;
		add_front(cx,d);
		
		cx=(x+1)%k;
		add_back(cx,d+1);
	}
	
	cout<<dist[0]+1;
	
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int n, a[200001], k[200001];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int m = 0;
    for (int i = n; i >= 1; --i)
    {
        int cnt = 0;
        for (int j = i * 2; j <= n; j += i)
            cnt += k[j];

        if (cnt % 2 != a[i])
            k[i] = 1, ++m;
    }
    if (m)
    {
        cout << m << endl;
        for (int i = 1; i <= n; ++i)
            if (k[i])
                cout << i << " ";
        cout << endl;
    }
    else
    {
        cout << 0 << endl;
    }
    return 0;
}

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

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = m - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout<<fixed<<setprecision(10);
  ll res=0,buf=0;
  bool judge = true;
  ll h,w;cin>>h>>w;
  vector<string>s(h);
  rep(i,0,h)cin>>s[i];
  vector<ll>a(26);
  rep(i,0,h)rep(j,0,w)a[s[i][j]-'a']++;
  vector<ll>p(3);
  rep(i,0,26){
    if(a[i]%4==0)p[2]++;
    else if(a[i]%2==0)p[1]++;
    else p[0]++;
  }
  //cout<<p[0] spa p[1] spa p[2]<<endl;
  if(~h&1&&~w&1)ans1(p[0]==0&&p[1]==0);
  else if(~h&1)ans1(p[0]==0&&p[1]<=h/2);
  else if(~w&1)ans1(p[0]==0&&p[1]<=w/2);
  else ans1(p[0]<=1&&p[1]<=h/2+w/2);
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int bubbleSort(int A[],int N);

int main(void){
  int A[100],N;
  int i;
  int num;

  scanf("%d",&N);

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

  num = bubbleSort(A,N);

  for(i = 0;i < N;i++){
    printf("%d",A[i]);
    if(i != N-1)printf(" ");
  }
  printf("\n");
  printf("%d\n",num);

  return 0;
}
   
  
  


int bubbleSort(int A[],int N){
  int i,j,temp;
  int count = 0;
 
  for(i = 0;i < N-1;i++){
    for(j = N-1;i < j;j--){
      if(A[j] < A[j-1]){
	temp = A[j-1];
	A[j-1] = A[j];
	A[j] = temp;
	
	count++;
      }
    }
  }
  return count;
}





Measured memory_bytes: 2144
s = int(input())
mod = 10**9+7

memo = {0: 0,
        1: 0,
        2: 0,
        3: 1,
        4: 1}

def dfs(n):
    if n in memo:
        return memo[n]
    else:
        ret = 0
        for i in range(3, n):
            ret += dfs(n-i)
            ret %= mod
        ret += 1
        ret %= mod
        memo[n] = ret
        return ret

print(dfs(s))


Measured memory_bytes: 9420
N = int(input())
s = input()
t = input()
lcm = 0
for i in range(N):
    f = False
    c = 0
    idx = 0
    for j in range(i, N):
        if s[j] == t[idx]:
            c += 1
        else:
            break
        idx += 1
    lcm = max(lcm, c)
print(N*2-lcm)


Measured memory_bytes: 38512
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define iss istringstream
#define sst stringstream
#define ite iterator
#define ll long long
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define pi pair<int,int>
#define pb push_back
#define sec second
#define sh(i) (1LL<<i)
#define sz size()
#define vi vector<int>
#define vc vector
#define vl vector<ll>
#define vs vector<string>

int n,a[110],b[110];
string s;

int main(){
	while(cin>>n&&n){
		cin>>s;
		rep(i,n)cin>>a[i]>>b[i],a[i]--,b[i]--;
		for(int i=n-1;i>=0;i--){
			int x=b[i]-a[i];
			rep(j,x){
				s[a[i]]++;
				if(s[a[i]]>'z')s[a[i]]='a';
				s[b[i]]++;
				if(s[b[i]]>'z')s[b[i]]='a';
			}
			//s[a[i]]=islower(s[a[i]]-26+x)?s[a[i]]-26+x:s[a[i]]+x;
			//s[b[i]]=islower(s[b[i]]-26+x)?s[b[i]]-26+x:s[b[i]]+x;
			swap(s[a[i]],s[b[i]]);
		}
		cout<<s<<endl;
	}
}

Measured memory_bytes: 0
#pragma GCC target ("avx")
char S[12];
char out[2<<20];
int outsz,Slen;
main()
{
	int N,K;
	scanf("%d%d ",&N,&K);
	gets(S);
	Slen=strlen(S);
	S[Slen++]='\n';
	for(int i=0;i<K;i++)
	{
		memcpy(out+i*Slen,S,Slen);
	}
	outsz=K*Slen;
	N-=K;
	for(int i=0;i<N;i++)
	{
		out[outsz+i*2]='7';
		out[outsz+i*2+1]='\n';
	}
	write(1,out,outsz+N*2);
}

Measured memory_bytes: 2304
#include<iostream>
#define rep(i, n) for (int i = 1; i <= (int)(n); i++)
using namespace std;

int main(){
    int A[5][4][11],n;
    for ( int i= 1 ; i <=4 ; i++)
      for ( int j = 1 ; j <= 3 ; j++)
        for ( int k = 1 ; k <= 10 ; k++) A[i][j][k] = 0;
    
    cin >> n;
    for ( int i = 0 ; i < n ; i++){
        int b, f , r , v;
        cin >> b >> f >> r >> v;
        A[b][f][r] += v;
    }
    rep(f,4){
        if (f > 1) cout << "####################\n";
        rep(b,3){
            rep(r,10){
                cout << " " << A[f][b][r];
            }
            cout << endl;
        }

    }
    return 0;
}


Measured memory_bytes: 3096