akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 100005
#define INF 1000000005LL

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

int N,Q;
ll A[SIZE];

//しゃくとり法
void solve(ll x){
	int s=0,t=0,t0=0;
	ll sum=0,ans=0;
	for(s=0;s<N;s++){
		while(t<N && sum+A[t]<=x){
			sum += A[t++];
		}
		if(s==t){
			t++;sum=0;
			continue;
		}
		int f = max(t0,s);
		ans += (ll)((f-s+1)+(t-s))*(t-f)/2;
		t0=t;
		sum -= A[s];
	}
	printf("%lld\n",ans);
}

int main()
{
	scanf("%d%d",&N,&Q);
	for(int i=0;i<N;i++)scanf("%lld",&A[i]);
	ll x;
	for(int i=0;i<Q;i++){
		scanf("%lld",&x);
		solve(x);
	}
	return 0;
}



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

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

  int ans = 0;
  int total = 0;
  for(int i = 0; i <= a; i++){
    total = 0;
    for(int j = 0; j <= b; j++){
      for(int k = 0; k <= c; k++){
        total = 500 * i + 100 * j + 50 * k;
        if(total == x){
          ans++;
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n)　for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    y /= gcd(x,y);
    return (x*y);
}

int main()
{
    ll n,a;
    cin >> n >> a;
    cout << pow(n,2) -a  << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

const int INF=1000100010;
int main(){
    int h,w;
    int aw;
    while(cin>>h>>w,h|w){
        pint c={h*h+w*w,h};
        pint mn={INF,INF};
        FOR(i,1,151)FOR(j,i+1,151){
            pint tc={i*i+j*j,i};
            if(tc>c&&mn>tc) mn=tc,aw=j;
        }
        cout<<mn.second<<" "<<aw<<endl;
    }
    return 0;
}


Measured memory_bytes: 3080
# -*- coding: utf-8 -*-

List = [int(x) for x in input().split()]
N = List[0]
L = List[1]

if L - 1 + N <= 0:
    Choose = L-1+N
elif 0 <= L:
    Choose = L
else:
    Choose = 0

print(int(N*L-N+N*(N+1)/2-Choose))

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;
using console = System.Console;

namespace AtCoderTemplate
{
    public class App
    {
        public static void Main(string[] args)
        {
            var k = int.Parse(console.ReadLine().Split()[1]);
            var p = console.ReadLine().Split().Select(i=>int.Parse(i));
            console.WriteLine(p.Skip(k-1).Zip(p,(upper,lower)=>Math.Min(Math.Abs(upper),Math.Abs(lower))+upper-lower).Min());
        }
    }
}


Measured memory_bytes: 18272
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef vector<int> vint;
typedef vector<float> vfloat;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vstr> vvstr;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int x, a;
    cin >> x >> a;
    if (x < a) printf("0\n");
    else printf("10\n");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
  int a=0 ,b=0 ,n ,m ,t ,set ,high=0 ,low=0 ,dif ,tmp=0;
  scanf( "%d" ,&t );
  
  for( int k=0 ; k<t ; k++ ){
    cin >> n;
    cin >> m;
    tmp = m;
    set = m;
    
    for( int i=0 ; i<n-1 ; i++ ){
      cin >> m;
      
      if( m > tmp ){        // 次の段差が今より高いとき
	if( m - tmp > high ){
	  high = m - tmp;
	  a++;
	}
      }
      
      else if( m < tmp ){   // 次の段差が今より低いとき
	if( tmp - m > low ){
	  low = tmp - m;
	  b++;
	}
      }
      
      tmp = m;
    }
    
    if( a == n || b == n ){
	cout << "0 0" << endl;
    }
    
    else{
      cout << high << " " << low << endl;
    }
    
    a = 0;
    b = 0;
    high = 0;
    low = 0;
    tmp = 0;
  }
  
  return 0;
}

Measured memory_bytes: 1240
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author anand.oza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DAxisParallelRectangle solver = new DAxisParallelRectangle();
        solver.solve(1, in, out);
        out.close();
    }

    static class DAxisParallelRectangle {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();

            long[] x = new long[n];
            long[] y = new long[n];
            for (int i = 0; i < n; i++) {
                x[i] = in.nextInt();
                y[i] = in.nextInt();
            }

            long answer = Long.MAX_VALUE;
            for (int l = 0; l < n; l++) {
                for (int r = 0; r < n; r++) {
                    if (x[l] > x[r])
                        continue;
                    List<Long> ys = new ArrayList<>();
                    for (int i = 0; i < n; i++) {
                        if (x[i] <= x[r] && x[i] >= x[l]) {
                            ys.add(y[i]);
                        }
                    }
                    Collections.sort(ys);
                    for (int i = 0; i + k - 1 < ys.size(); i++) {
                        answer = Math.min(answer, (x[r] - x[l]) * (ys.get(i + k - 1) - ys.get(i)));
                    }
                }
            }

            out.println(answer);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}



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

namespace _0577
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[,] a = new int[n, 4];
            for (int i = 0; i < n; i++)
            {
                int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
                for (int j = 0; j < 3; j++)
                {
                    a[i, j] = x[j];
                }
            }
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    bool b = true;
                    for (int k = 0; k < n; k++)
                    {
                        if (k != j)
                        {
                            if (a[j, i] == a[k, i])
                            {
                                b = false;
                            }
                        }
                    }
                    if (b)
                    {
                        a[j, 3] += a[j, i];
                    }
                }
            }
            for (int i = 0; i < n; i++)
            {
                Console.WriteLine(a[i, 3]);
            }
        }
    }
}

Measured memory_bytes: 9500
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
using namespace std;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> vp;
typedef vector<tuple<ll, ll, ll>> vt;
//vector<vector<ll>> vv(n, vector<ll>(n));

int main()
{
	ll n,ans=0;
	cin >> n;
	set<ll> st;
	REP(i,n)
	{
		ll a;
		cin >> a;
		if(st.count(a))
		{
			st.erase(a);
			ans--;
		}
		else
		{
			st.insert(a);
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 4864
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    N = int(input())
    if N == 1:
        print(0)
        return

    ans = pow(10, N, mod) - pow(9, N, mod) * 2 + pow(8, N, mod)
    print(ans % mod)


if __name__ == "__main__":
    main()


Measured memory_bytes: 61724
// スタックサイズ: 100MB

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <random>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }




int main() {
	fastio;

	ll N, A, B;
	cin >> N >> A >> B;
	cout << N / (A + B) * A + min(A, N % (A + B)) << endl;

	return 0;
}

Measured memory_bytes: 256
/*
 * Author   :   jignesh16
 * College  :   SVNIT
 */


#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

#define pb push_back
#define sz size()
#define ff first
#define ss second
#define ll long long int
#define ld long double
#define bp __builtin_popcountll
#define FOR(i,a,b) for(i=a;i<b;i++)
#define ROR(i,a,b) for(i=a;i>b;i--)
#define FORE(i,a,b) for(i=a;i<=b;i++)
#define RORE(i,a,b) for(i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
const int M=1e9+7;

int main()
{
    FAST;
    int n,i,j;
    cin>>n;
    long long int a[n],c=0;
    for(i=0;i<n;i++)    cin>>a[i];

    for(i=0;i<n;i++)
    {
        FOR(j,i+1,n)
            c+=a[i]*a[j];
    }
    cout<<c;
}

Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args){
		
		boolean[] hurui = new boolean[1000001];
		
		for(int i = 0; i <= 1000000; i++){
			if(i == 0 || i == 1){
				hurui[i] = false;
			}else{
				hurui[i] = true;
			}
		}
		
		for(int i = 2; i <= 1000000; i++){
			if(hurui[i] == true){
				int sum = i;
				while(sum <= 1000000){
					sum = sum + i;
					if(sum < 1000000){
						hurui[sum] = false;
					}
				}
			}
		}
		
		Scanner sc = new Scanner(System.in);
		
		while(true){
			
			int count = 0;
			int count2 = 0;
			
			for(int i = 0; i <= 100; i++){
				if(hurui[i] == true){
					count++;
				}
			}
			
			for(int i = 0; i <= 1000000; i++){
				if(hurui[i] == true){
					count2++;
				}
			}

			
			int a = sc.nextInt();
			int d = sc.nextInt();
			int n = sc.nextInt();
			
			if(a == 0 && d == 0 && n == 0){
				break;
			}
			
			int sum2 = 0;
			
			while(true){
				if(hurui[a] == true){
					sum2++;
					if(sum2 == n){
						System.out.println(a);
						break;
					}
				}
				a = a + d;
			}
			
			
		}
	}

}

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

using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
int mod = 998244353;

long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}

/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  

double eps = .000000001;

int main ()
{
  prep();
  long long n;
  cin >> n;
  
  long long sum = n*(n-1)/2;
  cout << sum;
  return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>

struct Edge {
    int v{};
    int w{};
    Edge(int v, int w) : v(v), w(w) {};
};

using Graph = std::vector<std::vector<Edge>>;

int main() {
    int n{};
    std::cin >> n;
    Graph graph(n, std::vector<Edge>());
    for (int i = 0; i < n - 1; i++) {
        int u{}, v{}, w{};
        std::cin >> u >> v >> w;
        u--;
        v--;
        graph[u].emplace_back(v, w % 2);
        graph[v].emplace_back(u, w % 2);
    }
    std::vector<int> result(n, -1);
    result[0] = 0;
    std::queue<int> queue({ 0 });
    while (!queue.empty()) {
        const auto v = queue.front();
        queue.pop();
        for (auto&& edge1 : graph[v]) {
            if (result[edge1.v] != -1) continue;
            if (edge1.w > 0) result[edge1.v] = edge1.w - result[v];
            else result[edge1.v] = result[v];
            queue.push(edge1.v);
        }
    }
    for (auto x : result) {
        std::cout << x << std::endl;
    }
    return 0;
}

Measured memory_bytes: 9476
#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
int head[1010101],tot,b[1010101];
struct edge{
	int to,nxt;
}g[1010011];
inline void made(int from,int to){
	g[++tot].to=to;g[tot].nxt=head[from];head[from]=tot;
}
int mat[1010101],n,ans;
void dfs(int u,int faa){
	if (faa&&!g[head[u]].nxt){
		if (!mat[faa]) mat[faa]=u,mat[u]=faa,ans++;
		return;
	}
	for (int i=head[u];i;i=g[i].nxt){
		int v=g[i].to;
		if (v==faa) continue;
		dfs(v,u);
	}
	if (!mat[u]){
		if (faa&&!mat[faa]) mat[faa]=u,mat[u]=faa,ans++;
	}
}
signed main(){
	n=read();
	if (n&1){
		printf("First");return 0;
	}
//	return 1;
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		made(x,y),made(y,x);
	}
	dfs(1,0);
	printf(ans!=n/2?"First":"Second");
//	for (int i=1;i<=n;i++){
//		for (int j=head[i];j;j=g[j].nxt){
//			int v=g[j].to;
//			if (indo[v]==1) b[i]++;
//		}
//		if (b[i]>=2){
//			puts("First");return 0;
//		}
//		if (indo[i]>=3){
//			puts("First");return 0;
//		}
//	}
//	puts("Second");
    return 0;
}





Measured memory_bytes: 6108
h,w=map(int,input().split())
a=[]
for _ in range(h):
	b=[]
	s=input()
	for i in range(w):
		b.append(s[i])
	a.append(b)
	
#タテのチェック
for i in range(w):
	tmp=0
	for j in range(h):
		if a[j][i]=="#":
			tmp=1
	if tmp==0:
		for j in range(h):
			a[j][i]="0"

#ヨコのチェック
for i in range(h):
	if not "#" in a[i][:]:
		a[i][:]=[0]*w

for i in range(h):
	tmpl=[]
	for j in range(w):
		if not a[i][j]=="0":
			tmpl.append(a[i][j])
	if "#" in tmpl or "." in tmpl:
		print("".join(tmpl))		#listを詰めて表示

Measured memory_bytes: 3192
import collections
N = int(input())
D = list(map(int,input().split()))

if D[0] != 0 or 0 in D[1:]:
    print(0)
    exit()

A = collections.Counter(D)
A = list(A.items())
A.sort()

if len(A) != max(D) + 1:
    print(0)
    exit()

ans = 1
for i in range(max(D)):
    ans *= A[i][1]**A[i+1][1]
    if ans >= 998244353:
        ans %= 998244353
print(ans)

Measured memory_bytes: 25916
#include<iostream>
#include<algorithm>
using namespace std;
int *line;
bool **check;
bool search(int, int);
int main() {
	int n;
	while (cin >> n&&n > 0) {
		line = new int[n];
		check = new bool*[n];
		for (int i = 0; i < n; ++i) {
			cin >> line[i];
			check[i] = new bool[n] {0};
		}
		for (int i = 0, nmax = n - 1; i < nmax; ++i) {
			if (abs(line[i] - line[i + 1]) <= 1) {
				check[i][i + 1] = true;
			}
		}
		for (int wide = 3; wide < n; wide += 2) {
			for (int i = 0, nmax = n - wide; i < nmax; ++i) {
				if (search(i, i + wide)) {
					check[i][i + wide] = true;
				}
			}
		}
		int *dp;
		dp = new int[n + 1]{ 0 };
		for (int i = 0; i < n; ++i) {
			dp[i + 1] = max(dp[i + 1], dp[i]);
			for (int j = i + 1; j < n; j += 2) {
				if (check[i][j]) {
					dp[j + 1] = max(dp[j + 1], dp[i] + j - i + 1);
				}
			}
		}
		cout << dp[n] << endl;
	}
	return 0;
}
bool search(int ps, int pe) {
	if (abs(line[ps] - line[pe]) <= 1 && check[ps + 1][pe - 1])return true;
	for (int i = ps + 1; i < pe; i += 2) {
		if (check[ps][i] && check[i + 1][pe]) {
			return true;
		}
	}
	return false;
}

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

long long pmod(int p) {
	long long modpow = 1, mod=1000000007;

	for (int i = 0; i < p; i++) {
		modpow *= 2;
		modpow %= mod;
	}

	return modpow;
}

int main() {
	int n, A[100000];

	for (int i = 0; i < 100000; i++)A[i] = 0;

	cin >> n;
	if (n % 2 == 0) {
		int fault = 0;

		for (int i = 0; i < n; i++) {
			int a;
			cin >> a;
			A[a]++;
		}

		for (int i = 1; i <= n / 2; i++) {
			if (A[i * 2 - 1] != 2) {
				fault = 1;
				break;
			}
		}

		if (fault == 1)cout << 0 << endl;
		else {
			int p = n / 2;
			cout << pmod(p) << endl;
		}
	}

	else if (n % 2 == 1) {
		int fault = 0;

		for (int i = 0; i < n; i++) {
			int a;
			cin >> a;
			A[a]++;
		}

		for (int i = 1; i <= (n - 1) / 2; i++) {
			if (A[i * 2] != 2) {
				fault = 1;
				break;
			}
		}

		if (A[0] != 1)fault = 1;

		if (fault == 1)cout << 0 << endl;
		else {
			int p = (n - 1) / 2;
			cout << pmod(p) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
const int mod = 998244353;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll c(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
#define MAX 100010
struct edge { int to; ll cost; };
vector<edge> G[MAX];
ll depth[MAX];
void dfs(int v, int p, ll d) {
	depth[v] = d;
	rep(i, 0, G[v].size()) {
		if(G[v][i].to != p)dfs(G[v][i].to, v, d + G[v][i].cost);
	}
}
void init(int root, int V) {
	dfs(root, -1, 0);
}
int main() {
	int N, Q, a, b, c, K;
	vector<ll> ans;
	scanf("%d", &N);
	rep(i, 0, N - 1)scanf("%d%d%d", &a, &b, &c), a--, b--, G[a].push_back({ b, c }), G[b].push_back({ a, c });
	scanf("%d%d", &Q, &K);
	K--;
	init(K, N);
	rep(i, 0, Q) {
		scanf("%d %d", &a, &b);
		a--, b--;
		ans.push_back(depth[a] + depth[b]);
	}
	rep(i, 0, Q)printf("%lld\n", ans[i]);
	return 0;
}

Measured memory_bytes: 16756
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define all(m) m.begin(), m.end()
#define uid uniform_int_distribution
#define init(m, x) memset(m, x, sizeof(m));
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    fast;
    ll a; cin>>a;
    ll d; cin>>d;
    d *= d;
    ll o  =0;
    for(; a--;){
        ll x,y; cin>>x>>y;
        ll t = x*x+y*y;
        o += t<=d;
    }
    cout<<o;
}

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

int main()
{
    // 入力
    string s;
    cin >> s;

    // 前から順々に判定
    for(int i = 0; i < s.length(); i++)
    {
        if(s[i] == 'B')
        {
            // まず、"B"の分、一個前にずらす
            for(int j = i; j < s.length()-1; j++)
            {
                s[j] = s[j+1];
            }
            s[s.length()-1] = '2'; // 削除の代わりに"2"を代入

            // 次に、"B"が先頭ではないなら、"B"の一個前を削除して、その分一個前にずらす
            if(i > 0)
            {
                for(int j = i; j < s.length(); j++)
                {
                    s[j-1] = s[j];
                }
            }
            s[s.length()-1] = '2';

            // また、先頭から判定
            i = -1;
        }

        // デバッグ
        //cout << s << endl;
    }

    // 出力する文字列を作成
    string result = "";
    for(int i = 0; i < s.length(); i++)
    {
        if(s[i] != '2') result += s[i];
    }

    cout << result;

    // デバッグ
    //cout << result.length();
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<stdio.h>

using namespace std;

int main(){
	int n;
	double x1, y1, x2, y2, x3, y3;
	double x, y, r;
	double a1, a2, b1, b2, c1, c2;

	cin >> n;
	while (n--){
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

		a1 = 2 * (x2 - x1);
		b1 = 2 * (y2 - y1);
		c1 = x1*x1 - x2*x2 + y1*y1 - y2*y2;

		a2 = 2 * (x3 - x1);
		b2 = 2 * (y3 - y1);
		c2 = x1*x1 - x3*x3 + y1*y1 - y3*y3;

		x = (b1*c2 - b2*c1) / (a1*b2 - a2*b1);
		y = (c1*a2 - c2*a1) / (a1*b2 - a2*b1);

		r = hypot(x - x1, y - y1);

		printf("%.3f %.3f %.3f\n", x, y, r);
	}

	return 0;
}

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

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define yes(c) cout << ((c) ? "yes" : "no") << endl;
 
#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;

int main() {

  int a,b,c,d;
  cin >> a >> b >> c >> d;
  
  if ( c >= b || a >= d ){
    cout << 0 << endl;
    return 0;
  }
  
  if ( d >= b && c >= a ){
    cout << b - c << endl;
  }else if ( b >= d && c >= a ){
    cout << d - c << endl;
  }else if ( b >= d && a >= c ){
    cout << d - a << endl;
  }else if ( d >= b && a >= c ){
    cout << b - a << endl;
  }else if ( b == d && a == c ){
    cout << b - a << endl;
  }

}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N, M = [int(x) for x in input().split()]
P_Y_li = []
for _ in range(M):
    P_Y_li.append([_] + [int(x) for x in input().split()])

prev_P = 0
num_x_li = {}
for i in sorted(P_Y_li, key=lambda x:(x[1], x[2])):
    if prev_P != i[1]:
        # init
        prev_P = i[1]
        counter = 1
    num_x_li[i[0]] = counter
    counter += 1

for i in P_Y_li:
    print(str(i[1]).rjust(6,'0') + str(num_x_li[i[0]]).rjust(6,'0'))





Measured memory_bytes: 40196
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  int a, b;
  cin >> a >> b;
  int ans = (a+b)/2;
  if((a+b)%2 != 0) ++ans;

  cout << ans << endl;
  return 0;
}


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

int main() {
  string S; cin >> S;
  int n = 3;
  int b;
  for (int bit = 0; bit < (1<<n); ++bit) {
    int sum = S[0] - '0';
    for (int i = 0; i < n; ++i) {
      if (bit & (1<<i)) sum += S[i+1] - '0';
      else sum -= S[i+1] - '0';
    }
    if (sum == 7) {
      b = bit;
      break;
    }
  }
  string ans = "";
  ans += S[0];
  for (int i = 0; i < n; ++i) {
    if (b & (1<<i)) {
      ans += "+";
      ans += S[i+1];
    }
    else {
      ans += "-"; 
      ans += S[i+1];
    }
  }
  ans += "=7";
  cout << ans << endl;
  return 0;
}        

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define INF 1e9
#define F first
#define S second
typedef pair<int, int> P;
int n, m, c, s, g;
int train[25][105][105];
int p[25], q[25][55], r[25][55];
int fare[105][105];
int flag[105];

void init(){
    for(int i = 0; i < 105; i++){
        flag[i] = -INF;           
    }
    for(int i = 0; i < 25; i++){
        for(int j = 0; j < 105; j++){
            for(int k = 0; k < 105; k++){
                train[i][j][k] = INF;
            }
        }
    }
    for(int j = 0; j < 105; j++){
        for(int k = 0; k < 105; k++){
            fare[j][k] = INF;
        }
    }
}
int culc_fare(int dist, int cmp){
    int re = 0;
    cmp--;
    for(int i = 1; i < p[cmp] + 1; i++){
        if(dist >= q[cmp][i]){
            re += (q[cmp][i] - q[cmp][i - 1]) * r[cmp][i - 1];
        }
        else{
            dist -= q[cmp][i - 1];
            re += dist * r[cmp][i - 1];
            return re;   
        }
    }
    return re;
}
void dijkstra(){
    priority_queue<P> pq;
    pq.push(MP(0, s)); //運賃,現在位置
    while(!pq.empty()){
        P p = pq.top();
        if(p.S == g) break;
        pq.pop();
        for(int i = 1; i <= n; i++){
            if(flag[i] < -fare[p.S][i] + p.F){
                pq.push(MP(-fare[p.S][i] + p.F, i));
                flag[i] = -fare[p.S][i] + p.F;
            }
        }
    }
}
int main(){
    while(cin >> n >> m >> c >> s >> g && n){
        init();
        for(int i = 0; i < m; i++){
            int x, y, d, c2;
            cin >> x >> y >> d >> c2;
            train[c2][x][y] = train[c2][y][x] = min(d, train[c2][x][y]);
        }
        for(int i = 0; i < c; i++){
            cin >> p[i];
        }
        for(int i = 0; i < c; i++){

            for(int j = 1; j < p[i]; j++){ 
                // 距離0の時を区切り点として入れるためj=1からスタートさせる
                cin >> q[i][j];
            }
            q[i][p[i]] = INF;
            for(int j = 0; j < p[i]; j++){
                cin >> r[i][j];
            }
        }
        for(int i = 1; i <= c; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    for(int l = 1; l <= n; l++){
                        train[i][k][l] = min(train[i][k][j] + train[i][j][l], train[i][k][l]);
                    }
                }
            }
        }
        for(int i = 1; i <= c; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    if(train[i][j][k] != INF){
                        fare[j][k] = min(fare[j][k], culc_fare(train[i][j][k], i));
                    }
                }
            }
        }
        dijkstra();
        if(flag[g] == -INF)
            cout << -1 << endl;
        else
            cout << -flag[g] << endl;
    }   
}


Measured memory_bytes: 4280
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h, w, n;
    cin >> h >> w >> n;
    int max, min;
    if (h >= w)
    {
        max = h;
        min = w;
    }
    else
    {
        min = h;
        max = w;
    }

    int tong = 0;
    for (int i = 1; i <= min; i++)
    {
        tong += max;
        if (tong >= n)
        {
            cout << i;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long N;long K;cin>>N>>K;
  vector<long> A(N+1,0);
  for(int i=1;i<=N;i++){
    cin>>A[i];
  }
  vector<long> st(N+1,-1);
  vector<long> pos(N+1,-1);
  long cnt=0,now=1;
  pos[0]=1;
  st[1]=0;
  bool path=false;
  while(true){
    now=A[now];
    cnt++;
    if(cnt==K){
      path=true;
      break;
    }
    if(st[now]!=-1)break;
    pos[cnt]=now;
    st[now]=cnt;
  }
  if(path){
    cout<<now<<endl;
  }else{
    long x=st[now]+(K-st[now])%(cnt-st[now]);
    if(x<0)x+=cnt-st[now];
    cout<<pos[x]<<endl;
  }
}


Measured memory_bytes: 7976
using namespace std;
using ll=long long;
#include <string>
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
#define out(S) cout<<(S)<<endl;


int main()
{
	int H, W;
	cin >> H >> W;
	string str = "";
	for (size_t i = 0; i < H; i++)
	{
		string g;
		cin >> g;
		str += g + "\n";
		str += g +"\n";
	}
	out(str);
	return 0;
}



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

int main()
{
    ll n,m,k;
    cin >> n >> m >> k;
    vector<ll> a(n+1);
    vector<ll> b(m+1);
    rep(i,n) cin >> a[i+1];
    rep(i,m) cin >> b[i+1];
    rep(i,n) a[i+1] += a[i];
    rep(i,m) b[i+1] += b[i];
    int ans = 0;
    rep(i,n+1){
        ll t = k-a[i];
        if(t<0) break;
        int tmp;
        tmp = i + 1 + upper_bound(ALL(b), t) - b.begin();
        ans = max(tmp - 2, ans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6404
#include <iostream>

int main(){
  std::string str;

  std::cin >> str;
  for(std::string::iterator it=str.begin(); it!=str.end(); ++it){
    char c;
    c = *it;
    if(c != ','){
      std::cout << c;
    }else std::cout << " ";
  }

  std::cout << std::endl;

  return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn.readLine
import scala.collection.mutable.ArrayBuffer

object Main {
  def hitblow(a:List[String],b:List[String],hit:List[String]):(Int,Int) =
    (a,b) match {
      case (Nil,Nil) => (hit.length, (a intersect b).length)
      case (hd::tl,hd2::tl2) => hitblow(tl,tl2,if(hd==hd2) hd::hit else hit)
      case (_,_) => (0,0)
    }


  def play(sb:StringBuilder):Unit = {
    val r = readLine

    if(r==null)  print(sb.result)
    else {
      val buf = ArrayBuffer.empty[String]
      val a = r.split(" ")
      val b = readLine.split(" ")
      for( i <- 0 until a.length)  if(a(i) == b(i)) buf += a(0)

      val x = buf.toArray.length
      val y = a.intersect(b).length - x
      sb.append(x + " " + y + "\n")
      play(sb)
    }
  }

  def main(args:Array[String]) = play(new StringBuilder)
}

Measured memory_bytes: 43796
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<stack>
#include<list>
#include<unordered_map>
#include<unordered_set>
#include<cctype>
#include<iomanip>
#include<limits>
#include<bitset>

using namespace std;
typedef long long int ll; typedef pair<int, int> P; typedef unsigned long long int ull;
const ll mod = 1e9 + 7;
const int inf = 1e9 + 7;
const ll linf = 1LL << 60;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define REP(i,m,n) for(int i=(m);i<(int)n;i++)
#define all(a) (a).begin(),(a).end()
#define allg(a) (a).begin(),(a).end(),greater<>()
#define SUM(a) accumulate((a).begin(),(a).end(),0)
#define d10 std::setprecision(10)
#define d20 std::setprecision(20)
#define sz size()
#define vec vector<int>
using str = string;
const double PI = 3.14159265359;
ll gcd(ll a, ll b) { ll t; while (b != 0) { t = a % b; a = b; b = t; }return a; }
int gcd(int a, int b) { int t; while (b != 0) { t = a % b; a = b; b = t; }return a; }
ll recfact(ll start, ll n) {
	ll i;
	if (n <= 16) {
		ll r = start;
		for (i = start + 1; i < start + n; i++) r = r * i % mod;
		return r % mod;
	}
	i = n / 2;
	return recfact(start, i) % mod * recfact(start + i, n - i) % mod;
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
ll fct(ll n) { return recfact(1, n); }
ll ncm(ll n, ll m) {
	if (n < m)return 0;
	ll x = (fct(n) % mod / (fct(m) * fct(n - m)) % mod) % mod;
	return x;
}
std::string sreverse(string str, int firstItr, int secondItr) {
	if (firstItr < 0 || secondItr>int(str.size() - 1))return str;
	while (firstItr < secondItr) {
		swap(str[firstItr], str[secondItr]);
		firstItr++; secondItr--;
	}
	return str;
}
std::string RunLengthEncoding(std::string str) {
	int itr = 0; std::string res;
	while (itr < int(str.size())) {
		char tmp = str[itr++];
		int length = 1;
		while (itr <int( str.size()) && str[itr] == tmp) { ++itr; ++length; }
		res.push_back(tmp);
		res += to_string(length);
	}
	return res;
}

bool dfs(int depth, int now) {
	/*if (depth == n)return !now;
	for (int i = 0; i < k; i++) {
		if (dfs(depth + 1, now ^ t[depth][i]))return true;
	}
	/**/
	return false;
}


int main() {
	int n; cin >> n;
	cout << n * n << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

struct node{
	int data;
	node* prev;
	node* next;
};

void printforward(node* head);
void insert(node*& head, node*& tail, node*& e);
void deleteFirst(node*& head, node*& tail);
void deleteLast(node*& head, node*& tail);
void deleteElement(node*& head, node*& tail, int e);

int main(){

	node* head = NULL;
	node* tail = NULL;
	node* nw;

	int n;
	cin >> n;

	string s;
	for (int i=0; i<n; i++){
		cin >> s;
		if (s.length() > 6){
			if (s[6] == 'F'){
				deleteFirst(head, tail);
			}
			else{
				deleteLast(head, tail);
			}
		}
		else{
			int t;
			cin >> t;
			if (s[0] == 'i'){
				nw = new node;
				nw->data = t;
				insert(head, tail, nw);
			}
			else{
				deleteElement(head, tail, t);
			}
		}
	}
/*	node* n;

	n = new node;
	n->data = 1000000000;
	insert(head, tail, n);

	n = new node;
	n->data = 999999999;
	insert(head, tail, n);

	deleteLast(head, tail);

	n = new node;
	n->data = 1234566890;
	insert(head, tail, n);

	n = new node;
	n->data = 5;
	insert(head, tail, n);

	deleteFirst(head, tail);

	n = new node;
	n->data = 7;
	insert(head, tail, n);

	if (tail->next == NULL){
		cout << "hello" << endl;
	}

	deleteElement(head, tail, 5);
*/
	printforward(head);	

	return 0;
}

void printforward(node* head){
	node* tmp;
	tmp = head;
	while (tmp != NULL){
		if (tmp==head){
			cout << tmp->data;
		}
		else{
			cout << " " << tmp->data;
		}
		tmp = tmp->next;
	}
	cout << endl;
}

void insert(node*& head, node*& tail, node*& e){
	if (head != NULL){
		e->next = head;
		e->prev = NULL;
		head->prev = e;
		head = e;
	}
	else{
		e->prev = NULL;
		e->next = NULL;
		head = e;
		tail = e;
	}
}

void deleteFirst(node*& head, node*& tail){
	if (head != tail){
		head = head->next;
		head->prev = NULL;
	}
	else{
		head = NULL;
		tail = NULL;
	}
}

void deleteLast(node*& head, node*& tail){
	if (head != tail){
		tail = tail->prev;
		tail->next = NULL;
	}
	else{
		head = NULL;
		tail = NULL;
	}
}

void deleteElement(node*& head, node*& tail, int e){
	node* tmp;
	tmp = head;
	bool flag = true;
	while (tmp->data != e && flag){
		if (tmp->next==NULL){
			flag = false;
		}
		else{
			tmp = tmp->next;
		}
	}
	if (flag){
		if (tmp == head){
			deleteFirst(head, tail);
		}
		else if (tmp == tail){
			deleteLast(head, tail);
		}
		else{
			tmp->prev->next = tmp->next;
			tmp->next->prev = tmp->prev;
		}
	}
}
















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

int main()
{
    int K, S;
    cin >> K >> S;

    vector<int> sum;
    rep(i, K+1) rep(j, K+1) sum.push_back(i+j);
    int ans = 0;
    rep(i, sum.size()) {
        int z = S - sum[i];
        if (z >= 0 && z <= K) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 34788
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
const double EPS=1e-8;
struct data{
    double b;string Name;
    data(double b_,string Name_):b(b_),Name(Name_){}
    data(){}
    bool operator<(const data &d)const{
        return (b-d.b<EPS&&b-d.b>-EPS)?Name>d.Name:b<d.b;
    }
};
int main(){
    int n;
    while(cin>>n,n){
        vector<data>V;
       for(int i=0;i<n;i++){
            string l;
            int p,a,b,c,d,e,f,s,m;
            cin>>l>>p>>a>>b>>c>>d>>e>>f>>s>>m;
            int t=a+b+c+(d+e)*m;
            int val=f*s*m-p;
            V.push_back(data(1.0*val/t,l));
       }
        sort(V.rbegin(),V.rend());
        for(int i=0;i<n;i++){
            cout<<V[i].Name<<endl;
        }
        cout<<"#"<<endl;
    }
    return 0;
}

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

int main(){
  string s, p; cin >> s >> p;
  int n = s.size();
  int m = p.size();
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(s[(i + j) % n] != p[j]) break;
      if(j == m - 1){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}



Measured memory_bytes: 3220
#include<bits/stdc++.h>
using namespace std;
#define print(x) cout<<"["#x<<" :";printx(x);cout<<"]\n"
template <typename T> void printx(T x){ cout<<x; }
template <typename T> void printx(vector<T> &v){ for(int x:v){ cout<<x<<" ";}}
template <typename T> void printx(vector<vector<T>> &v){ for(size_t i=0;i<v.size();i++){cout<<"\t";
										for(size_t j=0;j<v[i].size();j++){cout<<v[i][j]<<" ";}if(i!=v.size()-1) cout<<endl;}}

int gcd(int x,int y){
	if(y==0){
		return x;
	}
	return gcd(y,x%y);
}

void solve(){
	int n;
	cin>>n;
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				ans += gcd(gcd(i,j),k);
			}
		}
	}
	cout<<ans<<endl;
}

int main(){
		std::ios::sync_with_stdio(0);
		cin.tie(0);
		solve();
		return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
using ipair = pair<int, int>;
using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

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

const double PI=3.14159265358979323846;

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

  vector<vector<int>> path(N, vector<int>()); 

  rep(i, M){
    int a, b;
    cin >> a >> b;
    a--; b--;
    path[a].push_back(b);
    path[b].push_back(a);
  }

  vector<int> parent(N, -1);
  parent[0] = 0;
  queue<int> q;
  q.push(0);
  while(!q.empty()){
    int node = q.front(); q.pop();
    for(int next_node: path[node]){
      if(parent[next_node]==-1){
        parent[next_node] = node;
        q.push(next_node);
      }
    }
  }

  cout << "Yes" << endl;
  for(int i=1; i<N; i++){
    cout << parent[i]+1 << endl;
  }


  return 0;
}


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

#define int long long
#define endl '\n'

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #ifdef LOCAL
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    int n; cin>>n;
    string s; cin>>s;
    int l = 0;
    while(l < n && s[l] == 'R') l++;
    int r = n-1;
    while(r >= 0 && s[r] == 'W') r--;
    int c = 0;
    for (int i = l; i <= r; i++) {
        c += (s[i] == 'R');
    }
    int c1 = 0;
    int c2 = 0;
    for (int i = l; i < l+c; i++) {
        c1 += (s[i] == 'W');
    }
    cout<<min(c1, c);
}

Measured memory_bytes: 3752
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <limits>
#include <iterator>
#include <cmath>
#include <numeric>
#include <stack>
#include <queue>
#include <cassert>
#include <forward_list>
#include <chrono>
#include <deque>
#include <list>
#include <random>
#include <cstdio>
#include <sstream>

using namespace std;

int main()
{
	string s; string t;
	cin >> s; cin >> t;
	std::vector<string> ans;
	bool st = false;
	for (int i = 0; i < s.size(); i++)
	{
		int num = 1;
		if (s[i] == t[0] || s[i] == '?')
		{
			for (int j = 1; j < t.size(); j++)
			{
				if (i + j > s.size() - 1) break; //範囲外
				if (s[i + j] == '?' || s[i + j] == t[j]) //?か文字一致
				{
					num++;
				}
			}
		}

		if (num == t.size())
		{
			string pl = s;
			for (int j = 0; j < t.size(); j++)
			{
				pl[i + j] = t[j];
			}

			for (int j = 0; j < pl.size(); j++)
			{
				if (pl[j] == '?') { pl[j] = 'a'; }
			}

			ans.emplace_back(pl);
			st = true;
		}
	}

	if (st == true)
	{
		sort(ans.begin(), ans.end());
		cout << ans[0] << endl;
	}
	else
	{
		cout << "UNRESTORABLE" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007
// typedef
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

void ans(unordered_map<int, set<int>> &tree, VI &cnt, int t, int parent) {
    // if (tree[t].empty()) return;

    for (int s : tree[t]) {
        if (s == parent) continue; // 親で出てたらcontinue
        cnt[s-1] += cnt[t-1];
        ans(tree, cnt, s, t);
    }
}

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

int N, Q; cin >> N >> Q;
VP ab(N-1), px(Q);
rep(i,0,N-1) cin >> ab[i].first >> ab[i].second;
rep(i,0,Q) cin >> px[i].first >> px[i].second;

unordered_map<int, set<int>> tree;
rep(i, 0, N-1){
    tree[ab[i].first].insert(ab[i].second);
    tree[ab[i].second].insert(ab[i].first); // 親か子かわからないので，双方向に記録
}

// sort(ALL(px));

VI cnt(N, 0);
rep(i, 0, Q){
    cnt[px[i].first - 1] += px[i].second;
}

ans(tree, cnt, 1, -1);

rep(i, 0, N) cout << cnt[i] << ' ';
cout << endl;

return 0;
}

// 境界，出力文字列 チェック



Measured memory_bytes: 55240
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
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 (a>b) { a = b; return 1; } return 0; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;


int main(){
    ll c[3][3];
    REP(i, 3) REP(j, 3) cin >> c[i][j];

    REP(a1, 101) {
        ll b[3];
        REP(i, 3) b[i] = c[0][i] - a1;
        if (b[0]<0) continue;
        if (b[1]<0) continue;
        if (b[2]<0) continue;
        REP(a2, 101) {
            REP(a3, 101) {
                bool can = true;
                REP(i, 3) {
                    if (a1+b[i] != c[0][i]) can = false;
                    if (a2+b[i] != c[1][i]) can = false;
                    if (a3+b[i] != c[2][i]) can = false;
                }
                if (can) {
                    cout << "Yes\n";
                    return 0;
                }
            }
        }
    }
    cout << "No\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }



int main() {
    int N; cin >> N;
    if(N % 2 == 0){
        cout << N / 2 << endl;
    }
    else{
        cout << (N + 1) / 2 << endl;
    }
}

Measured memory_bytes: 256
D = int(input())
c = list(map(int, input().split()))
s = []
for k in range(D):
    s.append(list(map(int, input().split())))

ans = 0


scheduled = [0 for _ in range(26)]

for k in range(D):
    t = int(input())
    scheduled[t-1] = -1
    for j in range(26):
        scheduled[j] +=1
        ans -= c[j]*scheduled[j]
    ans += s[k][t-1]
    

    print(ans)

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

using namespace std;

#define long long long
#define INF 2e18
#define MOD (long) (1e9 + 7)
#define umap unordered_map

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

    long t = 1;
    //cin >> t;

    while (t--) {
        long n;
        cin >> n;

        vector<long> a(n);
        long total = 0;
        for (auto &x : a) {
            cin >> x;
            total += x;
        }
        long p = round(double(total) / n);
        long ans = 0;
        for (auto &x : a) {
            ans += (x - p) * (x - p);
        }
        printf("%lld\n", ans);
    }
}


Measured memory_bytes: 3816
n=gets.chomp.to_i
ary=Array.new(n)

maxv = -1*10**10

for m in 0..n-1
	ary[m]=gets.chomp.to_i
end
minv=ary[0]
for j in 1..n-1
	maxv=[maxv,ary[j]-minv].max
	minv=[minv,ary[j]].min
end
puts maxv

Measured memory_bytes: 10220