akhauriyash/Code-Regression huggingface dataset:
/*
      author : Nishikawa
      created: 10.08.2020 13:04:16
*/

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


int main(){
    string s;
    cin >> s;
    if(s == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
    return 0;
}


Measured memory_bytes: 3520
# coding: utf-8

import sys
input = sys.stdin.readline


def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


N = int(input())
A = list(map(int, input().split()))
# A, B, T = map(int, input().split())
# S = input()

left = [0] * (N + 1)
right = [0] * (N + 1)

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

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

ans = -1
for i in range(N):
    ans = max(ans, gcd(left[i], right[i + 1]))

print(ans)


Measured memory_bytes: 14076
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

ii ma[19][1 << 18];

void Update(ii& a, int x) {
  if (x > a.first) {
    a.second = a.first;
    a.first = x;
  } else if (x > a.second) {
    a.second = x;
  }
}

ii Join(ii a, ii b) {
  Update(a, b.first);
  Update(a, b.second);
  return a;
}

int main()
{
  int n;
  cin >> n;
  vector<int> a(1 << n);
  for (int i = 0; i < a.size(); ++i) cin >> a[i];

  for (int i = 0; i < (1 << n); ++i) ma[0][i].first = a[i];  

  for (int b = 1; b <= n; ++ b) {
    int r = n - b;
    for (int i = 0; i < (1 << r); ++i) {
      ma[b][i] = Join(ma[b - 1][i * 2], ma[b - 1][i * 2 + 1]);
    }
  }

  for (int b = 0; b < n; ++b) {
    for (int i = 0; i < n; ++i) for (int mask = 0; mask < (1 << n); ++ mask) {
      if (mask & (1 << i)) {
        ma[b][mask] = Join(ma[b][mask], ma[b][mask ^ (1 << i)]);
      }
    }          
  }

  for (int k = 1; k < (1 << n); ++k) {
    ii p = ma[0][k];
    int result = p.first + p.second;
    for (int b = 0; b < n; ++b) {
      int x = k >> b;
      if (x & 1) {
        x--;
        ii p = ma[b][x];
        result = max(result, p.first + p.second);
      }
    }
    cout << result << endl;
  }

  return 0;
}


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

int main(){
	ll N,M,V,P;
	cin >> N >> M >> V >> P;
	vector<ll> A(N);
	for(auto &x:A) cin >> x;
	sort(A.begin(), A.end());

	ll ok = N-1, ng = -1;
	while(ok-ng>1){
		ll mid = (ok+ng)/2;
		auto B = A;
		ll rest = V*M-M;
		B[mid] += M;
		ll morebig = 0;
		for(int i=N-1;i>=0;i--){
			if(i==mid)continue;
			if(B[i]+M>B[mid] && morebig<P-1){
				morebig++;
				B[i] += M;
				rest -= M;
			}else if(B[i]>B[mid]){
				rest = 1;
				break;
			}else if(rest){
				ll add = min(M,B[mid]-B[i]);
				B[i] += add;
				rest -= add;
			}
		}
		if(rest<=0){
			ok = mid;
		}else{
			ng = mid;
		}
	}
	cout << N-ok << endl;
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	K,X = inputMap()

	ans = []
	for i in range(1,(K*2)):
		ans.append(X-K+i)

	print(*ans)



if __name__ == "__main__":
	main()


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w,d;
  cin >> h >> w >> d;
  int i,j;
  vector<pair<int,int> >a(h*w+1);
  int aa;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cin >> aa;
      a[aa] = make_pair(i,j);
    }
  }
  int q;
  cin >> q;
  vector<int>l(q);
  vector<int>r(q);

  long tmp = 0;
  for(i=0;i<q;i++){
    cin >> l[i] >> r[i];
  }
  vector<int>summ(h*w+1);
  for(i=0;i<=h*w;i++){
    if(i<d)summ[i] = 0;
    else{
      summ[i] = summ[i-d] + abs(a[i].first-a[i-d].first) + abs(a[i].second - a[i-d].second);
    }
  }
  for(i=0;i<q;i++){
    tmp = summ[r[i]]-summ[l[i]];
    cout << tmp << endl;
  }


}


Measured memory_bytes: 2944
#include <iostream>
using namespace std;
int main(){
    int n;
    string s;
    cin >> n;
    cin >> s;
    int ans = 0;
    int flag = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'A') flag = 1;
        else if(s[i] == 'B' && flag == 1) flag = 2;
        else if(s[i] == 'C' && flag == 2){
            flag = 0;
            ans++;
        }
        else flag = 0;
    }
    cout << ans;
    return 0;
}

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

int main(){
  int K,S;cin>>K>>S;
  long long res=0;
  
  for(int x=0;x<=K;x++){
    for(int y=0;y<=K;y++){
      int z=S-x-y;
      if(0<=z && z<=K)
        res++;
    }
  }
  
  cout<<res<<endl;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func arrayEqual(A []int, B []int, N int) bool {
	for i := 0; i < N; i++ {
		if A[i] != B[i] {
			return false
		}
	}
	return true
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	N, K := nextInt(), nextInt()
	A := make([]int, N+1)
	for i := 0; i < N; i++ {
		A[i] = nextInt()
	}

	for k := 0; k < K; k++ {
		B := make([]int, N+1)

		for i := 0; i < N; i++ {
			B[max(i-A[i], 0)] += 1
			B[min(i+A[i]+1, N)] -= 1
		}

		for i := 0; i < N; i++ {
			B[i+1] += B[i]
		}

		if arrayEqual(A, B, N) {
			break
		}

		for i := 0; i < N; i++ {
			A[i] = B[i]
		}
		A = B
	}

	for i := 0; i < N; i++ {
		fmt.Fprintf(out, "%d ", A[i])
	}
}


Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3fffffff;
const ll MOD=1000000007;
const ll MODD=998244353;
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
  
int main()
{
  	ll n, a, b;
	cin >> n >> a >> b;
  	cout << min(n*a, b) << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int f=0;
	long long int n;
	cin>>n;
	long long int p=0,r;
	if(n%7==0)
	n=n/7;
	for(long double i=1;i<=n;i++)
	{
	p=(10*p+1)%n;
	//r=p/n;
	if(p==0)
	{
	f=1;
	r=i;
	break;
}
}
	if(f==1)
	cout<<r<<endl;
	else
	cout<<"-1"<<endl;
	return 0;
}

Measured memory_bytes: 3508
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

const int MAXS = 300010;
char str[MAXS];

int main() {
    int N;
    int K;
    int C;

    scanf("%d %d %d", &N, &K, &C);
    scanf("%s", str);

    vector <int> best(N);
    vector <int> slack(N, K);

    ++C;
    for (int i = 0; i < N; ++i) {
        if (i) {
            best[i] = max(best[i], best[i-1]);
        }

        if (str[i] == 'o') {
            int preMax = 0;

            if (i-C >= 0) {
                preMax = best[i-C];
            }


            best[i] = max(best[i], preMax+1);
        }
    }

    for (int i = N-1; i >= 0; --i) {
        if (str[i] == 'o') {
            if (i-C >= 0) {
                slack[i-C] = min(slack[i-C], slack[i]-1);
            }
        }

        if (i) {
            slack[i-1] = min(slack[i-1], slack[i]);
        }
    }

    // for (int i = 0; i < N; ++i) {
    //     cout << best[i] << " ";
    // }

    // cout << endl;


    // for (int i = 0; i < N; ++i) {
    //     cout << slack[i] << " ";
    // }

    // cout << endl;

    unordered_map <int, int> critCount;

    for (int i = 0; i < N; ++i) {
        if (slack[i] == best[i] && str[i] == 'o') {
            ++critCount[best[i]];
        }
    }

    for (int i = 0; i < N; ++i) {
        if (slack[i] == best[i] && str[i] == 'o' && critCount[best[i]] == 1) {
            cout << i+1 << endl;;
        }
    }

    return 0;
}

Measured memory_bytes: 11464
import java.util.*;
import java.math.*;
public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		BigInteger v = new BigInteger("11");
		BigInteger input = new BigInteger(sc.next());
		if(input.compareTo(v) <= 0){
			if(input.compareTo(new BigInteger("6")) <= 0 ){
				System.out.println(1);
			}
			else{
				System.out.println(2);
			}
		}
		else{
			BigInteger res = new BigInteger("0");
	//		System.out.println();
			res = input.divide(v).multiply(new BigInteger("2"));
	//		System.out.println("res = " + res);
	//		System.out.println(input.mod(v).compareTo(new BigInteger("6")));
			if(input.mod(v).equals(new BigInteger("0")) ){
		//		System.out.println("T");
			}
			else if(input.mod(v).compareTo(new BigInteger("6")) <= 0 ){
				res = res.add(new BigInteger("1"));
			}
			else{
				res = res.add(new BigInteger("2"));
			}
			System.out.println(res);
		}
		
	}
	
}


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

#include <set>
#include <map>
#include <iomanip>

using namespace std;

#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define rrep(i, n) for(long long i = (long long)(n - 1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using ll = long long;
using ull = unsigned long long;

int main()
{
	int N;
	cin >> N;
	
	vector<ll> A(N);

	rep(i, N)
	{
		cin >> A[i];
	}
	sort(all(A));
  
  	if(A[0] == 0)
    {
      cout << 0 << endl;
      return 0;
    }

	ll ans = 1;
	ll max = 1000000000000000000;
	rep(i, N)
	{
      	if(A[i] <= max / ans) {
			ans *= A[i];
        } else {
          	cout << -1 << endl;
			return 0;
        }
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3572
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=100000,Maxk=1000;
int x[Maxn+5],y[Maxn+5],c[Maxn+5],y1[10*Maxk+5];
int main()
{
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	int N,K,Max=0,cnt=0;
	scanf("%d %d",&N,&K);
	for(int i=1;i<=N;i++)
	{
		char ch;
		scanf("%d %d %c",&x[i],&y[i],&ch);
		if(ch=='W')c[i]=1;
		else c[i]=0;
		x[i]=x[i]%(2*K);
		y[i]=y[i]%(2*K);
	}
	for(int i=0;i<=K;i++)
	{
		cnt=0;
		memset(y1,0,sizeof(y1));
		for(int j=1;j<=N;j++)
		{
			int p=(i<=x[j]&&x[j]<i+K);
			int q=(0<=y[j]&&y[j]<K);
			if(p^q==c[j])
			{
				cnt++;
				y1[y[j]]++;
			}
			else
				y1[y[j]]--;
		}
		for(int j=0;j<=K;j++)
		{
			if(cnt>Max)Max=cnt;
			if(N-cnt>Max)Max=N-cnt;
			if(j!=K)cnt=cnt-y1[j]-y1[K+j];
		}
	}
	printf("%d\n",Max);
	return 0;
}

Measured memory_bytes: 1408
#include<cstdio>
#define ll long long
using namespace std;

int main() {
	ll k = 0; ll ans = 0;
	scanf("%lld", &k);
	
	for (ll i = 1; i <= k; i++) {
		if (i % 5 != 0 && i % 3 != 0) {
			ans = ans + i;
		}


	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 3248
#include <iostream>
#include <cstdio>
#define N 100005
using namespace std;

int n, a, mx, c[N];
int main()
{
	int i;
	cin >> n;
	while (n--) {
		scanf("%d", &a);
		c[a]++; c[a + 1]++; c[a + 2]++;
	}
	for (i = 0; i < N; i++) mx = max(mx, c[i]);
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 200000;
const int R = 2000;
const int M = 1000000007;

inline int add(int a, const int &b)
{
	a += b;
	return a >= M ? a - M : a;
}
inline int dec(int a, const int &b)
{
	a -= b;
	return a < 0 ? a + M : a;
}

inline int modpow(int a, const int &n)
{
	int res = 1;
	for (int i = n; i; i >>= 1)
	{
		if (i & 1)
			res = (s64)res * a % M;
		a = (s64)a * a % M;
	}
	return res;
}

int n;
int vx[MaxN], vy[MaxN];

int f[R * 2 + 1][R * 2 + 1];

int fact[R * 4 + 1];
int rfact[R * 4 + 1];

inline int binom(int n, int m)
{
	return (s64)fact[n] * rfact[m] % M * rfact[n - m] % M;
}

int main()
{
	fact[0] = 1;
	for (int i = 1; i <= R * 4; ++i)
		fact[i] = (s64)fact[i - 1] * i % M;
	rfact[R * 4] = modpow(fact[R * 4], M - 2);
	for (int i = R * 4; i; --i)
		rfact[i - 1] = (s64)rfact[i] * i % M;

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		vx[i] = getint(), vy[i] = getint();
		++f[R - vx[i]][R - vy[i]];
	}

	for (int i = 0; i <= R * 2; ++i)
		for (int j = 0; j <= R * 2; ++j)
		{
			if (i > 0)
				f[i][j] = add(f[i][j], f[i - 1][j]);
			if (j > 0)
				f[i][j] = add(f[i][j], f[i][j - 1]);
		}

	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		int x = vx[i], y = vy[i];
		res = dec(res, binom(x + y << 1, x << 1));
		res = add(res, f[x + R][y + R]);
	}

	cout << (s64)res * rfact[2] % M << endl;

	return 0;
}

Measured memory_bytes: 64384
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    while (cin>>n) {
        if (n==0) {
            break;
        }
        int m,a;
        std::vector<vector<int>> vec(110,vector<int>(110));
        for (int i=0;i<110;i++) {
            for (int j=0;j<110;j++) {
                vec[i][j]=0;
            }
        }
        for (int i=1;i<=n;i++) {
            cin>>m;
            for (int j=0;j<m;j++) {
                cin>>a;
                vec[i][a]=1;
            }
        }
        int k;
        std::deque<int> deq;
        cin>>k;
        for (int i=0;i<k;i++) {
            cin>>a;
            deq.emplace_back(a);
        }
        int ans=0;
        for (int i=1;i<=n;i++) {
            int count=0;
            for (int j=0;j<k;j++) {
                if (vec[i][deq[j]]==1) {
                    count++;
                } else {
                   break; 
                }
            }
            if (count==k) {
                if (ans==0) {
                    ans=i;
                } else {
                    ans=-1;
                }
            }
        }
        if (ans!=0&&ans!=-1) {
            cout<<ans<<endl;
        } else if (ans==0||ans==-1) {
            cout<<-1<<endl;
        }
    }
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char a[3],b[3];
    gets(a);
    gets(b);
    char ch=a[2];
    a[2]=a[0];
    a[0]=ch;
    for(int i=0;i<3;i++)
    {
        if(a[i]!=b[i])
        {
            cout<<("NO\n");
            return 0;
        }
    }
    cout<<"YES\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//一括include
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if ((a + b) % 2 == 1)
    {
        cout << (a + b) / 2 + 1 << endl;
    }
    else
        cout << (a + b) / 2 << endl;
}


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

#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FILL0(x) memset(x,0,sizeof(x))

using namespace std;

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

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

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

    int N, M;
    cin >> N >> M;

    vector<ll> town[N];

    map<ll, ll> my;
    map<ll, ll> mp;
    vector<P> order;

    rep(i, M)
    {
        ll pt, yt;
        cin >> pt  >> yt;
        pt--;
    
        my[yt]=i;
        mp[pt]=i;
        order.push_back(P(pt, yt));

        town[pt].push_back(yt);
    }

    rep(i, N)
    {
        sort(town[i].begin(), town[i].end());
    }

    rep(i ,M)
    {
        ll p, y;
        p = order[i].first;
        y = order[i].second;

        int index = lower_bound(town[p].begin(), town[p].end(), y)-town[p].begin();

        string num1 = to_string(p+1);
        string num2 = to_string(index+1);


        int size1 = 6-num1.size();
        int size2 = 6-num2.size();
        
        cout << string(size1,'0') + num1+string(size2,'0')+num2 << endl;

    }








    return 0;
}


Measured memory_bytes: 20976
n, m = gets.split.map &:to_i
A = Array.new(m){gets.to_i}

dp = Array.new(n+2,0)
dp[0] = 1
m.times do |i|
  dp[A[i]] = nil
end

0.upto(n-1) do |i|
  1.upto(2) do |j|
    if dp[i] && dp[i+j]
      dp[i+j] += dp[i]
      dp[i+j] %= 1000000007
    end
  end

end

  p dp[n] 



Measured memory_bytes: 3580
N,A,B=gets.chomp.split(" ").map(&:to_i)
array=gets.chomp.split(" ").map(&:to_i)
ret=0
(1..(N-1)).each do |i|
    diff = array[i] - array[i-1]
    if diff * A < B
        ret+=A*diff
    else
        ret+=B
    end
end
puts ret


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

#define REP(i,num) for(ll i=0;i<(num);++i)
#define FOR(i,c,num) for(ll (i)=(c);(i)<(num);++(i))
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){ T x; cin >> x; return (x); }
template<typename T=ll,typename C=vector<T>>
C vecin(int N){ C x(N);REP(i,N){ x[i]=in<T>(); }return x; }

void vout(){ cout << endl; }
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){ cout << ' ' << h;vout(forward<Tail>(t)...); }
void out(){ cout << endl; }
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){ cout << h;vout(forward<Tail>(t)...); }

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

vll M;

ll powermod(ll a,ll b,ll m){
	if(b==0){
		return 1LL;
	}
	if(b%2){
		return (a*powermod(a,b-1LL,m))%m;
	}
	return powermod((a*a)%m,b/2LL,m);
}

ll dfs(ll v){
	if(M[v]>=0) return M[v];

	ll B=__builtin_popcount(v);

	if(!B){
		M[v]=0;
		return 0;
	}
	if(!(v%B)){
		M[v] = 1;
		return 1;
	}

	ll C = dfs(v%B)+1;
	M[v] = C;
	return C;
}

ll safemod(ll a,ll m){
	return (a%m+m)%m;
}

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

	auto N=in();
	string X=in<string>();
	M.resize(N+1,-1);
	ll C=0;
	REP(i,N){
		if(X[i]=='1'){
			C++;
		}
	}
	ll modP=0,modD=0;
	if(C<N){
		REP(j,N){
			if(X[N-1-j]=='1'){
				modP += powermod(2,j,C+1);
				modP %= (C+1);
			}
		}
	}
	if(C>1){
		REP(j,N){
			if(X[N-1-j]=='1'){
				modD += powermod(2,j,C-1);
				modD %= (C-1);
			}
		}
	}

	ll K[2]={C-1,C+1};
	REP(i,N){
		ll B;
		auto T=X;
		ll mod=0;
		if(T[i]=='0'){
			T[i] = '1';
			B = 1;
			mod = modP;
			mod += powermod(2,N-1-i,K[B]);
			mod %= K[B];
		}
		else{
			T[i] = '0';
			B = 0;
			if(K[B]==0){
				out(0);
				continue;
			}
			mod = modD;
			mod -= powermod(2,N-1-i,K[B]);
			mod = safemod(mod,K[B]);
		}

		ll Z=dfs(mod)+1;
		out(Z);
	}


	return 0;
}


Measured memory_bytes: 5268
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve() {
	vector<vector<int>> a(3, vector<int>(3));
    map<int, P> mp;
    set<int> se;
    rep(i, 3) {
        rep(j, 3) {
            cin >> a[i][j];
            mp[a[i][j]] = P{i, j};
            se.insert(a[i][j]);
        }
    } 
    int n; cin >> n;
    vector<vector<int>> c(3, vector<int>(3, 0));
    rep(i, n) {
        int b; cin >> b;
        if(se.find(b) != se.end()) {
            int x = mp[b].fr, y = mp[b].sc;
            c[x][y] = 1;
        }
    }
    bool check = false;
    rep(i, 3) {
        if(c[i][0] && c[i][1] && c[i][2]) check = 1;
    }
    rep(i, 3) {
        if(c[0][i] && c[1][i] && c[2][i]) check = 1;
    }
    if(c[0][0] && c[1][1] && c[2][2]) check = 1;
    if(c[0][2] && c[1][1] && c[2][0]) check = 1;
    if(check) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    long long int n;
    cin >> n;

    long long int result = n;
    REP(i,n+1){
        long long int cc = 0,t=i;
        while(t>0){
            cc += t % 6;
            t /= 6;
        }
        t = n - i;
        while(t>0){
            cc += t % 9;
            t /= 9;
        }
        result = min(result, cc);
    }
    cout << result << endl;

    return 0;
}


Measured memory_bytes: 256
s=input()
t=input()

li=[]

for i in range(0,len(s)-len(t)+1):
    li.append(s[i:i+len(t)])

maxi=0
for w in li:
    count=0
    for k in range(len(t)):
        if(w[k]==t[k]):
            count+=1
    maxi=max(maxi,count)
print(len(t)-maxi)
    
            
        

        
        


Measured memory_bytes: 9232
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PokerPlaying {
    class Class2 {
        static void Main(string[] args) {
            while (true) {
                string input = Console.ReadLine();
                if (input == "0 0") {
                    return;
                }
                string[] lengthIdx = input.Split(' ');
                int Y = int.Parse(lengthIdx[0]);
                int X = int.Parse(lengthIdx[1]);

                string[,] map = new string[Y,X];

                for (int i = 0; i < Y; i++) {
                    string piece_map = Console.ReadLine();
                    for (int j = 0; j < X; j++) {
                        map[i, j] = piece_map.Substring(j,1);
                    }
                }
                bool[,] checkedTile = new bool[Y, X];
                int[] currentTile = new int[]{0,0};

                while (true) {
                    if (checkedTile[currentTile[1],currentTile[0]]==true) {
                        Console.WriteLine("LOOP");
                        break;
                    }
                    if (map[currentTile[1], currentTile[0]] == ">") {
                        checkedTile[currentTile[1], currentTile[0]] = true;
                        currentTile[0]++;
                    } else if (map[currentTile[1], currentTile[0]] == "<") {
                        checkedTile[currentTile[1], currentTile[0]] = true;
                        currentTile[0]--;
                    } else if (map[currentTile[1], currentTile[0]] == "^") {
                        checkedTile[currentTile[1], currentTile[0]] = true;
                        currentTile[1]--;
                    } else if (map[currentTile[1], currentTile[0]] == "v") {
                        checkedTile[currentTile[1], currentTile[0]] = true;
                        currentTile[1]++;
                    } else if (map[currentTile[1], currentTile[0]] == ".") {
                        checkedTile[currentTile[1], currentTile[0]] = true;
                        Console.WriteLine(currentTile[0].ToString()+" "+currentTile[1].ToString());
                        break;
                    }
                }
            }
        }
    }
}

Measured memory_bytes: 9704
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#include <cstdio>
#include <iomanip>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)

int main() {
    int A, B;
    cin >> A >> B;

    if ((A >= 1 && A <= 9) && (B >= 1 && B <= 9)) {
        cout << A * B << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

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

//result = Math.pow(num1, num3)
//StringBuffer str = new StringBuffer(hoge1);
//String hoge2 = str.reverse().toString();
//map.containsKey(A)
//Map<String, Integer> map = new HashMap<String, Integer>(n);
//ArrayList<String> cc = new ArrayList<>(n);
//Collections.sort(list);
//Array.sort(list);
//Arrays.asList(c).contains("a")

public class Main {
	private static Scanner sc = new Scanner(System.in);
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
	//static String eikomoji[]={"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"};
	public static void main(String[] args) {
	int N=sc.nextInt();
	int M=sc.nextInt();
	ArrayList<Integer> cc = new ArrayList<>(N+1);
	long wa=0;
	for(int i=0;i<N;i++) {
		cc.add(sc.nextInt());
		wa+=cc.get(i);
	}
	Collections.sort(cc,Collections.reverseOrder());
	int ctn=0;
	boolean a=true;
	for(int i=0;i<cc.size();i++) {
		if(cc.get(i)>=((double)wa/(4*M))) {
		ctn++;
		}
		if(ctn==M) {
			p("Yes");
			a=false;
			break;
		}
	}
	if(a) {
		p("No");
	}
	//if() {}
	
	
	}
}


Measured memory_bytes: 22740
/**
 * @brief ユーザ定義リテラル
 * @author えびちゃん
 */

#ifndef H_int_literals
#define H_int_literals

#include <cstddef>
#include <cstdint>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

#endif  /* !defined(H_int_literals) */

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

int main() {
  size_t n;
  scanf("%zu", &n);

  std::vector<int> x(n);
  for (auto& xi: x) scanf("%d", &xi);

  int res = 1e9;
  for (int p = 0; p <= 100; ++p) {
    int cur = 0;
    for (int xi: x) cur += (xi-p) * (xi-p);
    res = std::min(res, cur);
  }
  printf("%d\n", res);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int main(){
    int a[3][3];
    for (int i = 0; i < 3;i++){
        for (int j = 0; j < 3;j++){
            cin >> a[i][j];
        }
    }
    bool jud[3][3];
    bool ans = false;
    for (int i = 0; i < 3;i++){
        for (int j = 0; j < 3;j++){
            jud[i][j] = false;
        }
    }
    int N;
    cin >> N;
    int b[N];
    for (int i = 0; i < N; i++)cin >> b[i];
    for (int i = 0; i < N;i++){
        for (int j = 0; j < 3;j++){
            for (int k = 0; k < 3;k++){
                if(a[j][k]==b[i]){
                    jud[j][k] = true;
                }
            }
        }
    }
    for (int i = 0; i < 3;i++){
        if(jud[i][0]&&jud[i][1]&&jud[i][2]){
            ans = true;
        }
    }
    for (int i = 0; i < 3; i++){
        if(jud[0][i]&&jud[1][i]&&jud[2][i]){
            ans = true;
        }
    }
    if(jud[0][0]&&jud[1][1]&&jud[2][2]){
        ans = true;
    }
    if(jud[0][2]&&jud[1][1]&&jud[2][0]){
        ans = true;
    }
    if(ans)cout << "Yes";
    else cout << "No";
}

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

int main(){
  int n,m;
  cin >> n >> m;
  cout << (n-1)*(m-1) << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.C
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var A = ReadLongs();

            var s = A.Select((x, i) => new { Index = i + 1, Count = x }).ToList();
            return string.Join(" ", s.OrderBy(x => x.Count).Select(x => x.Index).ToArray());
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


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

#define REP(A, H) for(int A = 0; A < H; A++)
#define RREP(A, B, H, W) for(int A = 0; A < H; A++) for (int B = 0; B < W; B++)
#define MAX(A, B) (A = std::max(A, B))
#define MIN(A, B) (A = std::min(A, B))

typedef long long ll;

struct POINT {
  int x; int y;
  POINT(int x, int y) : x(x), y(y) {}
};

POINT operator +(const POINT& a, const POINT& b) {
  return POINT(a.x + b.x, a.y + b.y);
}

POINT operator -(const POINT& a, const POINT& b) {
  return POINT(a.x - b.x, a.y - b.y);
}

/* std::cout << ;*/
/* std::cout << << std::endl; */

struct JOB {
  int a; int b;

public:
  JOB(int a, int b) : a(a), b(b) {}

  bool operator<(const JOB &another)
  {
        return b < another.b;
  };
};

int main(void) {

  int N; std::cin >> N;
  std::vector<JOB> jobs;
  REP(i, N) {
    int a, b; std::cin >> a >> b;
    jobs.push_back(JOB(a, b));
  }

  std::sort(jobs.begin(), jobs.end());

  ll elapsed;
  if (jobs[0].b < jobs[0].a) {
    std::cout << "No" << std::endl;
    return 0;
  }

  elapsed = jobs[0].a;

  REP(i, N) {
    if (i == 0) continue;

    if (jobs[i].b - elapsed < jobs[i].a) {
      std::cout << "No" << std::endl;
      return 0;
    }

    elapsed += jobs[i].a;
  } 

  std::cout << "Yes" << std::endl;

  return 0;
}

Measured memory_bytes: 2420
#include<iostream>
#include<algorithm>
#include<vector>
int main() {
	int a = 0;
	int b = 0;
	std::vector<int> v(0), w(0);
	while (true)
	{
		++a;
		++b;
		w.resize(b);
		v.resize(a);
		std::cin >> v[a - 1] >> w[b - 1];
		if ((v[a - 1] == 0) && (w[b - 1] == 0)) { break; }
	}
	for (int i = 0; i < a - 1; ++i) {
		if (v[i] > w[i])std::cout << w[i] << " " << v[i] << std::endl;
		else if (v[i] < w[i])std::cout << v[i] << " " << w[i] << std:: endl;
		else std::cout << v[i] << " " << w[i] << std:: endl;
	}
	return 0;
}

Measured memory_bytes: 1240
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<list>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {1, 1, 0, -1, -1, 0};
int dx[] = {1, 0, -1, -1, 0, 1};
#define ceil(a, b) a / b + !!(a % b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)

int main() {
    int a, b, t;
    cin >> a >> b >> t;
    cout << (t / a) * b << endl;
}


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

int main() {
  int n, k, sum;
  cin >> n >> k;

  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;

    if ((2 * x) <= (2 * (k - x))) {
      sum += 2 * x;
    } else {
      sum += 2 * (k - x);
    }
  }

  cout << sum << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Edge=pair<ll,ll>;
using Graph=vector<vector<Edge>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
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 vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
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(){
  ll N,M,L;
  cin>>N>>M>>L;
  Graph G(N);
  REP(i,M){
    ll A,B,C;
    cin>>A>>B>>C;
    G[A-1].PB(Edge(B-1,C));
    G[B-1].PB(Edge(A-1,C));
  }
  
  ll DIS[N][N];
  REP(i,N){
    REP(j,N){
      if(i==j) DIS[i][j]=0;
      else DIS[i][j]=INF;
    }
  }
  
  REP(i,N){
    FORE(j,G[i]){
      DIS[i][j.first]=j.second;
    }
  }
  
  REP(k,N){
    REP(i,N){
      REP(j,N){
        chmin(DIS[i][j],DIS[i][k]+DIS[k][j]);
      }
    }
  }
  
  
  
  
  Graph GG(N);
  REP(i,N){
    REP(j,N){
      if(DIS[i][j]<=L){
        GG[i].PB(Edge(j,1));
      }
    }
  }
  
  ll DDIS[N][N];
  REP(i,N){
    REP(j,N){
      if(i==j) DDIS[i][j]=0;
      else DDIS[i][j]=INF;
    }
  }
  
  REP(i,N){
    FORE(j,GG[i]){
      DDIS[i][j.first]=j.second;
    }
  }
  
  REP(k,N){
    REP(i,N){
      REP(j,N){
        chmin(DDIS[i][j],DDIS[i][k]+DDIS[k][j]);
      }
    }
  }
  
  ll Q;
  cin>>Q;
  REP(i,Q){
    ll S,T;
    cin>>S>>T;
    if(DDIS[S-1][T-1]!=INF) co(DDIS[S-1][T-1]-1);
    else co(-1);
  }
  return 0;
}

Measured memory_bytes: 9400
#include<bits/stdc++.h>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOR(i,m,n) for(ll i=m;i<n;i++)
#define MOD 1000000007
#define INF 1e9
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
using namespace std;
const double PI = acos(-1);
typedef long long ll;


int main(void){
    int a,b,c,d;
    cin>>a>>b>>c>>d;

    if(a==c){
        cout<<0<<endl;
    }else{
        cout<<1<<endl;
    }

}




Measured memory_bytes: 256
public class Hello{
    public static void Main(){
        
        var line = System.Console.ReadLine();
        string[] array = line.Split(' ');
        
        int count = 0;
        for(int i = 0; i < 2; i++)
        {
            if(int.Parse(array[i]) >= 2)
            {
                int p = int.Parse(array[i]);
                count = count + (p * (p - 1)) / 2 ;
            }
        }
        
        System.Console.WriteLine(count);
    }
}

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

int main(){
	int D,E;
	while( cin >> D >> E and D and E ){
		double ans = 1e9;
		for(int i = 0 ; i <= D ; i++){
			int j = D - i;
			ans = min(fabs(sqrt(i * i + j * j) - E),ans);
		}
		printf("%.10lf\n",ans);
	}
}

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

int main() {
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++ ) {
    string s;
    cin >> s;
    
    if (s == "Y" ) {
      cout << "Four" << endl;
      break;
    }
    
    else if ( i + 1 == N)
      cout << "Three" << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  char in;
  scanf("%c", &in);
  
  char trans[256];
  trans['A'] = 'T';
  trans['T'] = 'A';
  trans['G'] = 'C';
  trans['C'] = 'G';
  
  printf("%c\n", trans[in]);
  
  return 0;
  
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

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

struct edge{ int s, t, w; };

int main() {
  int n, m; cin >> n >> m;
  auto dis = make_v(n, n, numeric_limits<int>::max() / 10);
  vector<edge> edges;

  REP(i, m){
    int s, t, w; cin >> s >> t >> w;
    --s; --t;
    dis[s][t] = dis[t][s] = w;
    edges.push_back({s, t, w});
  }

  REP(k, n)REP(i, n)REP(j, n){
    if(i == j) dis[i][j] = 0;
    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);  
  }

  int ans = m;
  for(const auto& edge: edges){
    int s = edge.s, t = edge.t, w = edge.w;
    bool sh = false;
    REP(i, n){
      if(dis[i][t] == dis[i][s] + w) sh = true;
    }
    if(sh) ans--;
  }

  cout << ans << endl;

  return 0;
}


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

typedef long long ll;

int main()
{
    string s;
    cin >> s;
    
    int ans_one = 0; //0101
    int ans_two = 0; //1010
    for(int i = 0; i < s.size(); i++)
    {
        if (s[i] == '0'){
            if ((i % 2) == 0){
                ans_two++;
            } else {
                ans_one++;
            }
        } else {
            if ((i % 2) == 0) {
                ans_one++;
            } else {
                ans_two++;
            }
        }
    }
    cout << min(ans_one, ans_two) << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, A[20], B[20], C[20], res;

int main(){
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
		--A[i];
	}
	for (int i = 0; i < N; ++i) {
		cin >> B[i];
	}
	for (int i = 0; i < N - 1; ++i) {
		cin >> C[i];
	}
	for (int i = 0; i < N; ++i) {
		res += B[A[i]];
	}
	for (int i = 0; i < N - 1; ++i) {
		if (A[i] + 1 == A[i + 1]) {
			res += C[A[i]];
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 256
S=input()
s=0
c=0
for i in range(len(S)):
    if("S"==S[i]):
        s+=1
    else:
        if(s>0):
            s-=1
            c+=1

if(c>10**5):
    print(len(S)-(2*(10**5)))
else:
    print(len(S)-(2*c))

Measured memory_bytes: 40048
#include<iostream>
using namespace std;
int f[10000009];
int main(){
	for(int i=1;i<=10000007;i++){
		for(int j=i;j<=10000007;j=j+i){
			f[j]++;
		}
	}
	int a;
	cin>>a;
	long long ans=0;
	for(int i=1;i<=a;i++){
		ans=ans+i*f[i];
	}cout<<ans<<endl;
}

Measured memory_bytes: 42184
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>

int main() {
	int k, x; std::cin >> k >> x;
	if (k * 500 >= x) {
		std::cout << "Yes\n";
	}
	else {
		std::cout << "No\n";
	}
}

Measured memory_bytes: 888
//Dragon_warrior7(IITK)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define nl cout << '\n'
#define sor(x) sort(x.begin(), x.end())
#define rev(v) reverse(v.begin(), v.end())
#define lb(v, temp) lower_bound(v.begin(), v.end(), temp)
#define ub(v, temp) upper_bound(v.begin(), v.end(), temp)
#define fi first
#define se second
#define llmax 1000000000000000000
#define deb(x) cout << #x << " " << x << "\n"
#define pll pair<ll, ll> 
#define vll vector<ll> 
#define rub cout << "\n------------------------------------\n"
void read(vector<ll> &v)
{
	for (int i = 0; i < v.size(); i++)
		cin >> v[i];
}

void print(vector<ll> v)
{
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
}
ll n,m,a,b,temp,x,y;
string str;
set<ll> s;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
string a,b;
cin>>a>>b;
str=a;
string s=b;
for(int i=0;i<b[0]-'0'-1;i++)
a+=str;
for(int i=0;i<str[0]-'0'-1;i++)
b+=s;
if(a<b)
cout<<a;
else
cout<<b;

}

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


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

    int ans=0;

    for(int i =0 ;i<4;i++){
        if(S.at(i) == '+') ans++;
        else ans--;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
N, M = tuple(map(int, input().split()))
A = set(map(int, [input() for _ in range(M)]))
MOD = 10 ** 9 + 7

dp = [0] * (N + 1)

#0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in A else 0 


for i in range(2, N + 1):
    if i in A:
        continue
    else:
        dp[i] = (dp[i - 1] + dp[i - 2])

print(dp[-1] % MOD)

Measured memory_bytes: 460020
#include<stdio.h>

int main(void){
  int n,i,j;
  double x[4],y[4],t;

  scanf("%d",&n);

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

    for(j=0;j<4;j++)
      scanf("%lf%lf",&x[j],&y[j]);

    for(j=0;j<4;j+=2){
      if(x[j]<x[j+1]){
	t=x[j];
	x[j]=x[j+1];
	x[j+1]=t;
	t=y[j];
	y[j]=y[j+1];
	y[j+1]=t;
      }
    }

    if((x[0]-x[1])/(y[0]-y[1])==(x[2]-x[3])/(y[2]-y[3]))printf("YES\n");
    else printf("NO\n");
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000000000;

int i,j,k,n,m,c[17],N[20001],dp[256][20001],x;

int main(){
  
  while(1){
    cin >> n >> m;
    if( n == 0 && m ==  0 ) break;
  
    for( i = 0; i < m; i++ ) cin >> c[i];
    for( i = 0; i < n; i++ ) cin >> N[i];
    
    for( i = 0; i < 256; i++ ){
      for( j = 0; j <= n; j++ ){
	dp[i][j] = MAX;
      }
    }
    
    dp[128][0] = 0;
    //  int data[20000];
      for( j = 0; j < n; j++ ){
    for( i = 0; i <= 255; i++ ){
	//	int Min = 100000;
	for( k = 0; k < m; k++ ){
	  x = ( i + c[k] );
	  if( x < 0 ) x = 0;
	  if( x > 255 ) x = 255;
	  //dp[x][0] = 0;
	  dp[x][j+1] = min( dp[x][j+1], dp[i][j] + (x - N[j]) *( x - N[j] ) );

	  /*  if( Min > ( x - N[j] ) * ( x - N[j] ) ){
	    Min = ( x - N[j] ) * ( x - N[j] );
	    cout << "Min" << " " << Min << endl;
	    data[j] = x;
	  }
	  */
	}
      }
    }
    
      /* for( i = 0; i < 256; i++ ){
      cout << "i" << " " << i << " ";
      for( j = 0; j <= n; j++ ){
	cout <<  dp[i][j] << " ";
      }
      cout << endl;
      }*/
    int Min = 1000000000;

     for( i = 0; i < 256; i++ ){
       if ( Min > dp[i][n] ){
	 Min = dp[i][n];
	 }
     }
     cout << Min << endl;
  }
  
  return 0;
}

Measured memory_bytes: 21240
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define intarr(arr, n)  ll arr[n];  for (ll i = 0; i < n; i++)  cin >> arr[i]
#define inpvec(vec,n) for(ll i=0;i<n;i++){ll var;cin>>var;vec.push_back(var);}
#define ff first
#define ss second
#define pb push_back
#define mkp make_pair
#define vec vector<ll>
#define pi pair<ll,ll>
#define changeline cout<<endl
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define rev(i,a,b) for(ll i=a;i>=b;i--)
#define all(v) v.begin(),v.end()
#define mod2 998244353
#define NO cout << "NO" <<endl
#define YES cout << "YES" <<endl
#define mem(arr,val) memset(arr,val,sizeof(arr));
const ll mod=1e9+7;
#define piii 3.14159265358979323846264338327950
#define print(a, n, m)     for (ll i = n; i < m; i++) {  cout << a[i] << " "; }  cout << endl
#define con continue

bool prime(ll n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
}
bool isPerfectSquare(ll x) {   
  long double sr = sqrt(x); 
  return ((sr - floor(sr)) == 0); 
} 
bool subsequence_checker(string str1, string str2, ll m, ll n) 
{ 
    if (m == 0) return true; 
    if (n == 0) return false; 
    if (str1[m-1] == str2[n-1]) 
        return subsequence_checker(str1, str2, m-1, n-1); 
    return subsequence_checker(str1, str2, m, n-1); 
}
bool cmp(const pair<int,int> &a,  const pair<int,int> &b) 
{ 
    if(a.ff == b.ff)
        return a.ss < b.ss;
    return (a.ff > b.ff); 
}
//////////////////////////////////////////////////// Lets Do It ////////////////////////////////////////////////////////
int gcd(int p, int q){
if(p % q == 0)return q;
return gcd(q, p % q);
}

void solve()
{

    ll n,k;
    cin>>n>>k;

    cout<< min(n%k, k-n%k);

    return;
}
 
int main()
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
    IOS;
    ll t;
    //cin>>t;
    t=1;

    while(t--){
        solve();
        cout<<endl;
    }

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
} 

Measured memory_bytes: 3680