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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t,n,a;
    t = 1;
    while(t--) {
     a = 0;
     cin >> n;
     if(n > 9) 
      a = a + 9;
     else
      a = a + n;
     if(n > 99) {
      if(n > 999)
       a = a + 900;
      else
       a = a + n - 99;
	 }
	 if(n > 9999) {
      if(n > 99999)
       a = a + 90000;
      else
       a = a + n - 9999;
	 }
     cout << a << endl;
    }
    return 0;
}



Measured memory_bytes: 256
import itertools
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

L = [x for x in range(1, N+1)]

p_list = itertools.permutations(L)

a = -1
b = -1

for i, p in enumerate(p_list):
    if P == list(p):
        a = i
    if Q == list(p):
        b = i

print(abs(a-b))


Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;


class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int timeResult = 0;
    static int countA, countB;
    static long maxNum;

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

        int N = sc.nextInt();
        int M = sc.nextInt();
        long K = sc.nextLong();
        int[] timeTakenA = new int[N];
        int[] timeTakenB = new int[M];

        
        for (int i = 0; i <N; i++){
            timeTakenA[i] = sc.nextInt();
        }

        for (int i = 0; i <M; i++){
            timeTakenB[i] = sc.nextInt();
        }

        for(int i = 0; i < N; i++){
            if(timeResult + timeTakenA[i] > K) break;
            timeResult += (long)timeTakenA[i];
            countA++;
        }

        maxNum = countA;
        for (int i = 0; i <M; i++){
            while(timeResult + timeTakenB[i] > K){
                if(countA == 0) break;
                timeResult -= timeTakenA[countA - 1];
                countA--;
            }

            if(timeResult + timeTakenB[i] > K){
                break;
            }

            timeResult += timeTakenB[i];
            countB++;
            
            if(countA + countB >= maxNum){
                maxNum = countA + countB;
            }
        }
        
        System.out.println(maxNum);

    }


}

Measured memory_bytes: 61668
// No sorceries shall prevail. //           
import java.util.*;
import java.io.*;
public class Main {
	
	static long gcd(long a, long b) { 
	      if (b == 0) 
	        return a; 
	      return gcd(b, a % b);  
	    }
	static int gcd(int a, int b) { 
	      if (b == 0) 
	        return a; 
	      return gcd(b, a % b);  
	    }
	
	static long mod = 1000000007;
	public static void main(String args[]) {
		Scanner inp=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
		
		long n=inp.nextLong();
		long gg=0;
		gg+=n/500;
		gg*=1000;
		n%=500;
		gg+=n;
		gg-=n%5;
		out.println(gg);
		out.close();
		inp.close();
	}
}

Measured memory_bytes: 22740
n = int(input())
v_list = list(map(int,input().split()))
c_list = list(map(int,input().split()))

vc = []
for i in range(n):
    ans = v_list[i]-c_list[i]
    if ans >= 0:
        vc.append(v_list[i]-c_list[i])

print(sum(vc))


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL cost[4];
LL vol[] = {1, 2, 4, 8};
int ind[4];

bool cmp(int i, int j) {
    double a = cost[i]/ (double)vol[i];
    double b = cost[j] / (double)vol[j];
    return a < b;
}

int main() {
//    freopen("test.txt", "r", stdin);
    for (int i = 0; i < 4; i++) {
        scanf("%d", &cost[i]);
        ind[i] = i;
    }
    LL n;
    scanf("%lld", &n);
    n *= 4;
    sort(ind, ind+4, cmp);
    LL ret = 0;
    for (int j = 0; j < 4; j++) {
        int i = ind[j];
        LL tmp = n/vol[i];
        ret += tmp*cost[i];
        n -= tmp*vol[i];
    }
    cout << ret << endl;

}

Measured memory_bytes: 256
N = int(input())
S = list(input())
ans = 0
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans += r*g*b
m = 0
if N >= 3:
  for i in range(N-2):
    for j in range(i+1,N-1):
      k = 2*j-i
      if  k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        m += 1
print(ans-m)

Measured memory_bytes: 67932
str1 = gets.split
H,W = str1[0].to_i, str1[1].to_i

a,b = "0","0"
(0...W).each do
  a << "0"
  b << "1"
end
a << "0"
b << "0"
X,Y = "",""
X << a
Y << a

(0...H).each do
  X << "0"
  X << gets.chomp
  Y << b
  X << "0"
end

X.gsub!('#', '1')
X.gsub!('.', '0')

X << a
Y << a

X1 = X.to_i(2)
Y1 = Y.to_i(2)

i = 0
while X1 != Y1
  X1 = ( X1 | X1 << 1 | X1 << (W+2) | X1 >> 1 | X1 >> (W+2) ) & Y1
  i += 1
end
puts i

Measured memory_bytes: 92736
#include <stdio.h>

int main(void)
{
 int n,a=0,i=0;
 scanf("%d",&n);
 int m=n;
 do{
  a+=m%10;
  m/=10;
 }while(m!=0);
 if(n%a==0){
  printf("Yes\n");
 }else{
  printf("No\n");
 }
 return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main(){

    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);

    int ans = 3;

    if(a==b)ans--;
    if(b==c)ans--;
    if(ans>1 && a==c)ans--;

    printf("%d\n",ans);

    return 0;
}


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

bool bisa;
int n,i,ar[202],step;

int main(){
    bisa=true;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&ar[i]);
    }
    step=0;
    while(bisa){
        for(i=0;i<n;i++){
            if(ar[i]%2==1){bisa=false;}
            ar[i]/=2;
        }
        if(bisa){step++;}
    }
    printf("%d\n",step);
}


Measured memory_bytes: 256
import sys
import math
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(1, n):
        if i == 1:
            ans = math.gcd(a[i-1], a[i])
        else:
            ans = math.gcd(ans, a[i])
    print(ans)
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 20396
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

int main() {
  int N,M; cin>>N>>M;
  vector<pint> data(M);
  REP(i,M) {
    int	a, b; cin>>a>>b;
    data[i] = make_pair(a, b);
  }
  sort(data.begin(), data.end());
  int ans = 0;
  int right_left = 1<<30;
  REP(i,M) {
    if(data[i].first < right_left) {
      right_left = min(right_left, data[i].second);
    } else {
      ans ++;
      right_left = data[i].second;
    }
  }
  ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
import math
from operator import mul
from functools import reduce

def comb(n, r):
  r = min(r, n-r)
  if r==0: return 1
  over = reduce(mul, range(n, n-r, -1))
  under = reduce(mul, range(1, r+1))
  return over//under

n, k = map(int, input().split())
mod = 10**9+7

for i in range(1, k+1):
  if i <= n-k+1:
    ans = comb(n-k+1, i) * comb(k-1, i-1)
    ans %= mod
  else:
    ans = 0
  print(ans)

Measured memory_bytes: 3956
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = getLine >>= putStrLn . solve

solve :: String -> String
solve = br . filter (> 1) . map length . group
    where
        br [] = "Good"
        br _ = "Bad"

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

Measured memory_bytes: 380
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	long int ans = 0;
    long int N, a,b,c,d,f;
	cin >> N >> a >> b >> c >> d >> f;
    long int K = min({ a,b,c,d,f});
	long int m = (N-1)/K;
	ans = m + 5;
	
	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define MOD 1000000007
#define MAXN 100005
void solve() {
	int a, b, c;
  	cin >> a >> b >> c;
  	cout << min(a+b, min(b+c, a+c)) << endl;
  	return ;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
random_device rnd;
mt19937 mt(rnd());

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;
int main()
{

    int n, m;
    cin >> n >> m;
    VL x(n), y(m);
    rep(i, n) cin >> x[i];
    rep(i, m) cin >> y[i];
    sort(ALL(x));
    sort(ALL(y));
    ll sx = 0;
    rep(i, n)
    {
        sx += MOD * n + i * x[i];
        sx %= MOD;
        sx -= (MOD * n + (n - 1 - i) * x[i]) % MOD;
        while (sx < 0)
            sx += MOD;
    }
    ll sy = 0;
    rep(i, m)
    {
        sy += MOD * m + i * y[i];
        sy %= MOD;
        sy -= (MOD * m + (m - 1 - i) * y[i]) % MOD;
        while (sy < 0)
            sy += MOD;
    }
    cout << (sx * sy) % MOD << endl;
    ;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <unordered_set>
#include <stack>

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  long long int ans = K * pow(K - 1, N - 1);
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main(void)
{
	int H, W;
	int i, j;

	while (1)
	{
		scanf("%d%d", &H, &W);
		if (H == 0 && W == 0)
			break;
	
		for (j = 0; j < W; j++)
			putchar('#');
		
		putchar('\n');

		for (i = 1; i < H - 1; i++)
		{	
			putchar('#');
			
			for (j = 1; j < W - 1; j++)
			putchar('.');

			putchar('#');
		
		putchar('\n');
		}
		
		for (j = 0; j < W; j++)
			putchar('#');
		putchar('\n');
                putchar('\n');
	}	
	
	return 0;
}

Measured memory_bytes: 572
#include<stdio.h>
int main()
{
	int n,k,ridi=0;
	scanf("%d %d",&n,&k);
	int ara[n];
	for (int r=0;r<n;r++)
	{
		scanf("%d",&ara[r]);
	}
	int i,  temp;
 for( i=0;i<n;i++)
 
 {
 	for(int j=0;j<n-i-1;j++)
 	{
 	
 	 if(ara[j]>ara[j+1]){
 	 	temp=ara[j];
 	 	ara[j]=ara[j+1];
 	 	ara[j+1]=temp;
 	 }
 	}
 }
 for(int q=0;q<k;q++)
 { ridi+=ara[q];
 }
 printf("%d\n",ridi);
 return 0;
}

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

#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define eb emplace_back
#define MOD (ull)(double)(1e9 + 7)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pull pair<ull, ull>
#define m_p make_pair
#define debug(x) cout << #x << " " << x << endl;

const double pi = 3.14159;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int r;
	cin >> r;
	
	cout << 2 * pi * r;
}


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

typedef long long int lli;
string s;

int main() {
	ios_base::sync_with_stdio(false);
	cin >> s;
	int n = s.length();

	lli sum = 0;
	for(int i = 0; i < (1 << (n-1)); i++) {
		lli curr = s[0] - '0';
		for(int j = 1; j < n; j++) {
			if(i & (1 << (j-1))) {
				sum += curr;
				curr = s[j] - '0';
			} else {
				curr *= 10;
				curr += s[j] - '0';
			}
		}
		sum += curr;
	}

	cout << sum << endl;

	return 0;
}

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;


int main(){

    int n;
    cin>>n;
    string ans="APPROVED";
    rep(i,n){
        int a;
        cin>>a;
        if(a%2==0){
            if(a%3!=0 &&a%5!=0)ans="DENIED";
        }
    }
    cout<<ans<<endl;

    return 0;

}
/*


*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, m;
	cin>>n>>m;
	vector<int> p(m), pen(n+1);
	vector<string> verdict(m);
	vector<bool> ac(n+1);
	int cnt=0;
	for(int i=0; i<m; ++i) {
		cin>>p[i]>>verdict[i];
		if(verdict[i]=="WA" && !ac[p[i]]) {
			pen[p[i]]++;
		}
		else if(verdict[i]=="AC") {
			if(!ac[p[i]]) {
				ac[p[i]]=1;
				cnt++;
			}
		}
	}
	int total=0;
	for(int i=1; i<=n; ++i) {
		if(ac[i]) {
			total+=pen[i];
		}
	}
	cout<<cnt<<' '<<total;
}


Measured memory_bytes: 6528
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define MOD 1000000007
#define INF ((1LL<<62)-(1LL<<31))

int main(void) {
	int n,a[401];
	//dp[j][j+i]:a[j]~a[j+i]をまとめるためのmin
	long dp[402][402] = {0};
	long tmp;
	long sum;
	scanf("%d",&n);
	for (int i=0;i<n;i++)scanf("%d",&a[i]);
	

	for (int i=1;i<n;i++){
	    for (int j=0;j<n-i;j++){
	        tmp = INF;
	        sum = 0;
	        for (int k=j;k<j+i;k++){
	            tmp = min(tmp,dp[j][k]+dp[k+1][j+i]);
	            sum += a[k];
	        }
	        sum += a[j+i];
	        dp[j][j+i] = tmp+sum;
	    }
	}

	printf("%lld\n",dp[0][n-1]);

	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
#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 Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
#define m_p make_pair
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if  (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  int q;
  while(cin>>q,q){
    using D = deque<int>;
    auto mv=
      [&](D &a,D &b,D &ax,D &ay,D &bx,D &by){
	if(!bx.empty()&&bx.back()==b.back()) bx.pop_back();
	if(!by.empty()&&by.back()==b.back()) by.pop_back();	  
	
	a.emplace_back(b.back());
	b.pop_back();
	
	if(ax.empty()||ax.back()>a.back()) ax.emplace_back(a.back());
	if(ay.empty()||ay.back()<a.back()) ay.emplace_back(a.back());
      };

    D a,b;
    D ax,ay,bx,by;
    
    while(q--){
      int t,x=-1;
      cin>>t;
      if(t==0||t==4||t==5||t==8||t==9) cin>>x;     

      if(t==0){	
	while(!bx.empty()&&bx.front()>x) bx.pop_front();
	while(!by.empty()&&by.front()<x) by.pop_front();
	b.emplace_front(x);
	bx.emplace_front(x);
	by.emplace_front(x);
      }
      
      if(t==1){
	if(!ax.empty()&&ax.back()==a.back()) ax.pop_back();
	if(!ay.empty()&&ay.back()==a.back()) ay.pop_back();
	cout<<a.back()<<endl;
	a.pop_back();
      }

      if(t==2) cout<<ax.back()<<endl;
      if(t==3) cout<<bx.back()<<endl;

      if(t==4) cout<<ax[ax.size()-x]<<endl;
      if(t==5) cout<<bx[bx.size()-x]<<endl;
            
      if(t==6) cout<<ay.back()<<endl;
      if(t==7) cout<<by.back()<<endl;
      
      if(t==8) cout<<ay[ay.size()-x]<<endl;
      if(t==9) cout<<by[by.size()-x]<<endl;
      
      while(a.size()<b.size())   mv(a,b,ax,ay,bx,by);
      while(a.size()>b.size()+1) mv(b,a,bx,by,ax,ay);

    }
    cout<<"end"<<endl;
  }
  return 0;
}



Measured memory_bytes: 3360
#include <iostream>
using namespace std;
int n, a, b, s, ans;
int main() {
	int i, j;
	cin>>n>>a>>b;
	for(i=1; i<=n; i++) {
		for(j=i, s=0; j; j/=10) s += j%10;
		if(a<=s && s<=b) ans += i;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
/*
 _ _ _   _    _   _    _   _ _ _   _    _   _ __ _   __       __
|  _ _| | |  | | | |  | | |  _  | | |  | | |  __  | |   \   /   |
| |_ _  | |__| | | |  | | | |_| | | |__| | | |__| | | |\ \_/ /| |
|_ _  | |  __  | | |  | | |  _ <  |  __  | |  __  | | | \   / | |
 _ _| | | |  | | | |__| | | |_| | | |  | | | |  | | | |  \_/  | |  _   _   _
|_ _ _| |_|  |_| |_ __ _| |_ _ _| |_|  |_| |_|  |_| |_|       |_| |_| |_| |_|

*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << " = " << a << " ";
#define endl "\n"
const int  MOD=1000000007;
const int N=1000100;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

void solve(){
    ll n,k;
    cin>>n>>k;
    ll x=1,p=0;
    while(x<=n){
        p++;
        x=x*k;
    }
    cout<<p;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long int t = 1;
    // cin>>t;
    for (long int tt = 1; tt <= t; tt++) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a.at(i);
    
    cout<<((n-1)/(k-1)+!!((n-1)%(k-1)))<<endl;

}

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

int main() {
  int n,a[101],b[101],count=0;
  cin>>n;
  rep(i,n) cin >> a[i]>>b[i];
  for(int i=0;i<n-2;i++){
    if(a[i]==b[i]&a[i+1]==b[i+1]&a[i+2]==b[i+2]){
      count++;
    }
  }
    if(count>0){
      cout<<"Yes"<<endl;
    }
  else{
    cout<<"No"<<endl;
  }
}
      

Measured memory_bytes: 3636
def solve(n, A):
    num, count = 0, 0
    for a in A:
        if a == num + 1:
            num += 1
        else:
            count += 1
    return count if num > 0 else -1

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))


Measured memory_bytes: 26268
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct ed{int t,n,w;}e[6010],e2[6010];
int n,m,k,h[2510],l,d[2510],h2[2510],cn[2510],t,w,q;
bool v[2510],g[2510];
queue<int> que;
void bfs()
{
	que.push(n);
	g[n]=1;
	while(!que.empty())
	{
		l=que.front();
		que.pop();
		for(int i=h2[l];i;i=e2[i].n)
		if(!g[e2[i].t])
		{
			g[e2[i].t]=1;
			que.push(e2[i].t);
		}
	}
}
bool aspeFA()
{
    for(int i=2;i<=n;i++) d[i]=-1e9;
    v[1]=1;
    que.push(1);
    int c;
    while(!que.empty())
    {
       	c=que.front();
   	 	v[c]=0;
   	 	cn[c]++;
   		que.pop();
   	 	if(cn[c]>=n+(n==1))
		{
			if(g[c]) return 1;
			else continue;
		}
    	for(int i=h[c];i;i=e[i].n)
        {
       	  	if(d[e[i].t]<d[c]+e[i].w)
            {
                d[e[i].t]=d[c]+e[i].w;
                if(!v[e[i].t])
                {
                    que.push(e[i].t);
                   	v[e[i].t]=1;
                }
            }
    	}
    }
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    q=0;
    for(int i=1;i<=n;i++) h[i]=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&k,&l,&w);
        e[i].t=l;
        e[i].n=h[k];
        e[i].w=w-t;
        h[k]=i;
        e2[i].t=k;
        e2[i].n=h2[l];
        e2[i].w=w-t;
        h2[l]=i;
    }
    bfs();
    if(aspeFA()) printf("-1\n");
	else printf("%d\n",d[n]<0?0:d[n]);
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#define N 100000
#define NIL -1

typedef struct{
    int p;
    int l;
    int r;
} Node;

void Preorder(int);
void Inorder(int);
void Postorder(int);

int n;
Node node_all[N];

int main(){
    int i,id,l,r,root;

    scanf("%d",&n);

    for(i=0;i<n;i++){
        node_all[i].p = NIL;
    }

    for(i=0;i<n;i++){
        scanf("%d%d%d",&id,&l,&r);
        node_all[id].l = l;
        node_all[id].r = r;
        if(l != NIL){
            node_all[l].p = id;
        }
        if(r != NIL){
            node_all[r].p = id;
        }
    }

    for(i=0;i<n;i++){
        if(node_all[i].p == NIL){
            root = i;
        }
    }

    printf("Preorder\n");
    Preorder(root);
    printf("\n");
    printf("Inorder\n");
    Inorder(root);
    printf("\n");
    printf("Postorder\n");
    Postorder(root);
    printf("\n");

    return 0;
}

void Preorder(int u){
    if(u == NIL){
        return;
    }
    printf(" %d",u);
    Preorder(node_all[u].l);
    Preorder(node_all[u].r);
}

void Inorder(int u){
    if(u == NIL){
        return;
    }
    Inorder(node_all[u].l);
    printf(" %d",u);
    Inorder(node_all[u].r);
}

void Postorder(int u){
    if(u == NIL){
        return;
    }
    Postorder(node_all[u].l);
    Postorder(node_all[u].r);
    printf(" %d",u);
}


Measured memory_bytes: 2036
n, m, l = map(int, input().split())
def warshall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

inf = 10 ** 15
d = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = min(d[a-1][b-1], c)
    d[b-1][a-1] = min(d[b-1][a-1], c)

warshall_floyd(d, n)

e = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        if d[i][j] <= l:
            e[i][j] = min(e[i][j], 1)
            e[j][i] = min(e[j][i], 1)

warshall_floyd(e, n)


q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    print(e[s-1][t-1] - 1 if e[s-1][t-1] < inf else -1)

Measured memory_bytes: 60248
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int h,n;
  cin>>h>>n;
  int sum=0;
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    sum+=x;
  }
  if(sum>=h)cout<<"Yes\n";
  else cout<<"No\n";
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<int32_t mod>
struct ModInt{
	int32_t a;
	inline int32_t normalize(int64_t x){
		x%=mod;
		if(x<0)x+=mod;
		return x;
	}
	ModInt(const int64_t a=0):a(normalize(a)){}

	ModInt& operator+=(const ModInt &x){
		a+=x.a;
		if(a>=mod)a-=mod;
		return *this;
	}
	ModInt& operator-=(const ModInt &x){
		a-=x.a;
		if(a<0)a+=mod;
		return *this;
	}
	ModInt& operator*=(const ModInt &x){
		a=(int64_t)a*x.a%mod;
		return *this;
	}
	ModInt& operator/=(const ModInt &x){
		*this*=x.inv();
		return *this;
	}

	ModInt operator+(const ModInt x){return ModInt(*this)+=x;}
	ModInt operator-(const ModInt x){return ModInt(*this)-=x;}
	ModInt operator*(const ModInt x){return ModInt(*this)*=x;}
	ModInt operator/(const ModInt x){return ModInt(*this)/=x;}
	bool operator==(const ModInt x){return a==x.a;}
	bool operator!=(const ModInt x){return a!=x.a;}

	ModInt operator-(){return ModInt(0)-ModInt(*this);}
	ModInt pow(int64_t ex)const{
		int64_t x=a;
		int64_t res=1;
		while(ex){
			if(ex&1)res=res*x%mod;
			x=x*x%mod;
			ex>>=1;
		}
		return ModInt(res);
	}
	ModInt inv()const{return pow(mod-2);}
};

template<int32_t mod>
istream& operator>>(istream& in,ModInt<mod>& a){
	return (in>>a.a);
}
template<int32_t mod>
ostream& operator<<(ostream& out,const ModInt<mod>& a){
	return (out<<a.a);
}
/*
C[g]=sum{A[i]*B[j] | 1<=i,j && gcd(i,j)=g}
time:O(NloglogN)
space:O(N)
*/
template<class M>
vector<M>GCDConvolution(vector<M>A,vector<M>B){
	int m=max(A.size(),B.size());
	A.resize(m);
	B.resize(m);
	
	vector<int>isprime(m,1);
	for(int i=2;i<m;i++){
		if(!isprime[i])continue;
		for(int k=m/i;k>=1;k--){
			isprime[k*i]=false;
			A[k]+=A[k*i];
			B[k]+=B[k*i];
		}
	}

	for(int i=1;i<m;i++)A[i]*=B[i];

	fill(isprime.begin(),isprime.end(),1);
	for(int i=2;i<m;i++){
		if(!isprime[i])continue;
		for(int k=1;k*i<m;k++){
			isprime[k*i]=false;
			A[k]-=A[k*i];
		}
	}
	return A;
}






using mint=ModInt<998244353>;

int N;
int A[222222];

signed main(){
	cin>>N;
	rep(i,N)cin>>A[i];

	vector<mint>X(1000001);
	rep(i,N)X[A[i]]+=A[i];

	X=GCDConvolution(X,X);
	mint ans=0;
	for(int i=1;i<=1000000;i++){
		ans+=X[i]/i;
	}

	rep(i,N)ans-=A[i];
	ans/=2;
	cout<<ans<<endl;	
	return 0;
}


Measured memory_bytes: 21376
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] num = new int[3];
		for(int i = 0;i < 3;++i)
			num[i] = sc.nextInt();
		int K = sc.nextInt();
		sc.close();
		
		Arrays.sort(num);
		int ans = num[0] + num[1] + (num[2]<<K);
		System.out.println(ans);
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

int n;
map<pair<int,int>,int >M;
set<pair<int,int> >st;
multiset<int>ed[maxn],ned;

void add(int u,int v){
	if(u > v) swap(u,v);
	ed[u].insert(v);
	ed[v].insert(u);
	if(++M[make_pair(u,v)] == 2)
		st.insert(make_pair(u,v));
}
void del(int u,int v){
	if(u > v) swap(u,v);
	ed[u].erase(ed[u].find(v));
	ed[v].erase(ed[v].find(u));
	if(--M[make_pair(u,v)] == 1)
		st.erase(make_pair(u,v));
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<n;i++){
		if(st.empty()){
			puts("NO");
			return 0;
		}
		pair<int,int>t = *st.begin();
		int u = t.first , v = t.second;
		if(ed[u].size() > ed[v].size()) swap(u,v);
		ned = ed[u];
		for(int p:ned) del(u,p);
		for(int p:ned) if(p != v)
			add(p,v);
	}
	puts("YES");
}

Measured memory_bytes: 37632
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int n,i,a;
    scanf("%d",&n);
    
    for(i=1;i<n+1;i++){//iが１からnまでの値を取るfor文
        if(i%3==0){
            printf(" %d",i);
            continue;
        }
        for(a=i;1<a;a=a/10){
            if(a%10==3){
                printf(" %d",i);
                break;
            }
        }
    }
    printf("\n");
    
    return 0;
}


Measured memory_bytes: 2104
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
using namespace std;

using INT = long long;
using UINT = unsigned long long;

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

	if ((B - A) <= 2)
	{
		cout << 1 + K << endl;
		return 0;
	}

	if (A > 1 + (K - 2))
	{
		cout << 1 + K << endl;
		return 0;
	}

	K -= (A - 1);

	INT bs = A;

	if ((K % 2) == 1)
	{
		bs++;
		K--;
	}

	cout << bs + (K / 2) * (B - A) << endl;
	return 0;
}


Measured memory_bytes: 256
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 3e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n, mxp = 0, mnp = M, mxn = -M, mnn = M, x, y;
    cin >> n;
    for (ll i = 0; i < n; i++)
        cin >> x >> y, mnp = min(mnp, x + y), mxp = max(mxp, x + y), mnn = min(mnn, x - y), mxn = max(mxn, x - y);
    cout << max(abs(mxp - mnp), abs(mxn - mnn)) << '\n';
}


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

import math

def main():
     a, b, n = map(int, input().split())
     # floor(A * x/B) - A * floor(x/B)
     # 前者も後者も単調増加関数

     # ans = 0
     # for i in range(n+1):
     #      first = math.floor((a * i) / b)
     #      second = a * math.floor(i / b)
     #      check = first - second
     #      print('x = {}, first = {}, second = {}, ans = {}'.format(i, first, second, check))
     #      if ans < check:
     #           ans = check

     # 上記チェックでの仮説
     # x が Bの倍数ごとに、first と second の 値が一致する
     # n が b より小さい場合 と b 以上の場合を調べる

     if n < b:
          ans = math.floor((a * n / b)) - a * math.floor(n / b)
     else:
          ans = math.floor((a * (b - 1) / b)) - a * math.floor((b - 1) / b)

     print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9056
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priotity_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n;
ll pos[100];

int main(){
	cin >> n;
	pos[0]=2; pos[1]=1;
	REP(i,0,n) pos[i+2]=pos[i]+pos[i+1];
	
	cout << pos[n] << endl;
	return 0;
}


Measured memory_bytes: 256
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from math import sqrt

def prime_division(x):
    q = int(sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def divisorlist(z): # z : output of prime_division
    #ddprint(f"dvl {z}")
    if len(z)==1:
        return [z[0][0]**i for i in range(z[0][1]+1)]
    y = divisorlist(z[1:])
    s = []
    for i in range(z[0][1]+1):
        for j in y:
            s.append((z[0][0]**i)*j)
    return s

n,k = inm()
d = [0]*(k+1)
d[1] = pow(k,n,R)
sm = 0
for i in range(k,1,-1):
    d[i] = (d[i]+pow(k//i,n,R))
    ps = divisorlist(prime_division(i))
    for p in ps:
        if p!=i:
            d[p] = (d[p]-d[i])%R
    sm = (sm+d[i]*i)%R
#ddprint(d)
print((sm+d[1])%R)


Measured memory_bytes: 73808
sa = list(input())
sb = list(input())
sc = list(input())

turn = "a"
while True:
  if turn == "a":
    if len(sa) == 0:
      print("A")
      break
    turn = sa[0]
    sa = sa[1:]
  if turn == "b":
    if len(sb) == 0:
      print("B")
      break
    turn = sb[0]
    sb = sb[1:]
  if turn == "c":
    if len(sc) == 0:
      print("C")
      break
    turn = sc[0]
    sc = sc[1:]

Measured memory_bytes: 3064
from copy import copy

p = []
while(1):
    try:
        p = [int(i) for i in input().split()]
        min_ = 10**10
        point = 0
        arrmin = []
        arr = [4,1,4,1,2,1,2,1]
        for _ in range(8):
            temp = copy(arr[0])
            repl = copy(arr[1:8])
            arr[0:7] = repl
            arr[7] = temp
            point = sum([j-i if i < j else 0 for i,j in zip(arr,p)])
            if point == min_:
                arrmin.append(copy(arr))
                min_ = point
            elif point < min_:
                arrmin = [copy(arr)]
                min_ = point
        arrmin = ["".join([str(i) for i in j]) for j in arrmin]
        amin = min([int(i) for i in arrmin])
        out = list(str(amin))
        print(" ".join(out))
    except EOFError:
        break


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

int main() {
  long long n;
  cin >> n;
  vector<int> a(n);
  for(long long i=0;i<n;i++){
    cin >> a[i];
  }
  
  long long m=1000, b=0;
  for(int i=0;i<n-1;i++){
    
    if(a[i] > a.at(i+1)){
      m += a.at(i) * b;
      b=0;
    }
    else{
      b += m / a.at(i);
      m %= a[i];
    }
      
  }
   m += b*a[n-1];
  cout << m << endl;
}


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

int main() {
    int n, x; cin >> n >> x;
    vector<int> a(n, 0);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    
    long long ans = 1e9;
    ans = ans * ans;
    
    vector<vector<int>> partMin(n, vector<int> (n, 1e9 + 5));

    for(int i = 0; i < n; ++i) {
        partMin[i][i] = a[i];
        for(int j = i + 1; j < n; ++j)
            partMin[i][j] = min(a[j], partMin[i][j - 1]);
    }

    for(int slides = 0; slides < n; ++slides) {
        long long temp = 0;

        for(int i = 0; i < n; ++i) {
            int lf = i - slides;
            if(lf < 0)
                lf += n;
            int rt = i;
            if(lf <= rt) {
                temp += partMin[lf][rt];
            } else {
                temp += min(partMin[0][rt], partMin[lf][n - 1]);
            }
        }

        ans = min(ans, 1LL * slides * x + temp);
    }

    cout << ans << "\n";
}

Measured memory_bytes: 16000
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
P=10**9+7

#DP[i][j]=子供iまでで飴j個を分ける(1<=i<=N,0<=j<=K)
DP=[[0]*(K+1) for _ in range(N+1)]
#DP[1][j]を作る
for index1 in range(0,A[1]+1):
    DP[1][index1]=1
#DP[i][0]=1である
for index2 in range(N+1):
    DP[index2][0]=1


for i in range(2,N+1):  #2<=i<=N
    #i固定下で累積和tableを作成
    #C[index]=DP[i-1][0]+...+DP[i-1][index-1](1<=index<=K+1)
    C=[0]*(K+2)
    C[1]=DP[i-1][0]%P
    for c in range(2,K+2):
        C[c]=(C[c-1]+DP[i-1][c-1])%P
    for j in range(1,K+1):  #1<=j<=K
        DP[i][j]=(C[j+1]-C[max(0,j-A[i])])%P




print(DP[N][K]%P)


#for index3 in range(N+1):
    #string=''
    #for index4 in range(K+1):
        #string+=str(DP[index1][index2])+' '
    #print(string)

        








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

int maxtime(int x){
  return (x+9)/10*10;
}
int remtime(int x){
  return maxtime(x)-x;
}

int main() {
  int a,b,c,d,e;
  cin>>a>>b>>c>>d>>e;
  int sum=maxtime(a)+maxtime(b)+maxtime(c)+maxtime(d)+maxtime(e);
  sum-=max({remtime(a),remtime(b),remtime(c),remtime(d),remtime(e)});
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long Int;
int n;
int cnt[10800];
int main(){
  cin >> n;
  for(int i = 1;i <= n;i++){
    int p = i;
    for(int j = 2;p > 1;j++){
      while(p % j == 0){
	cnt[j]++;
	p /= j;
      }
    }
  }
  Int res = 1;
  for(int i = 1;i <= n;i++){
    res *= cnt[i] + 1;
    res %= 1000000007;
  }
  cout << res << endl;
}


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

typedef long long ll;
typedef long double ld;
typedef double db; //
typedef string str; //
//
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; //
typedef pair<db,db> pd; //
//
typedef vector<int> vi;
typedef vector<ll> vl; //
typedef vector<db> vd; //
typedef vector<str> vs; //
typedef vector<pi> vpi;
typedef vector<pl> vpl; //
typedef vector<pd> vpd; //

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() //
#define rsz resize
#define ins insert //
#define ft front() //
#define bk back()
#define pf push_front //
#define pb push_back
#define eb emplace_back //
#define lb lower_bound //
#define ub upper_bound //

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; //
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); //
//
template<class T> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { //
	return a < b ? a = b, 1 : 0; } //
constexpr int pct(int x) { return __builtin_popcount(x); } //
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) //
constexpr int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 //
// IGNORE
int fstTrue(function<bool(int)> f, int lo, int hi) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		int mid = (lo+hi)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}
template<class T> void remDup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)),end(v)); }

vector<ll> least_prime(10000000 + 1, 0);

void leastPrimeFactor(int n) 
{ 
    // We need to print 1 for 1. 
    least_prime[1] = 1; 
  
    for (int i = 2; i <= n; i++) 
    { 
        // least_prime[i] == 0 
        // means it i is prime 
        if (least_prime[i] == 0) 
        { 
            // marking the prime number 
            // as its own lpf 
            least_prime[i] = i; 
  
            // mark it as a divisor for all its 
            // multiples if not already marked 
            for (int j = 2*i; j <= n; j += i) 
                if (least_prime[j] == 0) 
                   least_prime[j] = i; 
        } 
    } 
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	leastPrimeFactor(N);
	vector<ll> numfact(N + 1, 0);
	numfact[1] = 1;
	ll ans = 1;
	for(ll a = 2; a <= N; a++){
		ll num = 0;
		ll temp = a / least_prime[a];
		while(temp % least_prime[a] == 0){
			temp /= least_prime[a];
			num++;
		}
		temp = a / least_prime[a];
		ll t = numfact[temp] / (num + 1);
		numfact[a] = t * (num + 2);
		ans += numfact[a] * a;
	}
	cout << ans << endl;
}

Measured memory_bytes: 159488
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int H, W, D;
  cin>>H>>W>>D;
  map<int, pair<int, int> > amap;
  int tmp;
  for(int i=0;i<H;++i) {
    for(int j=0;j<W;++j) {
      cin>>tmp;
      amap[tmp] = mp(i, j);
    }
  }
  vector<vector<int> > arr(D);
  for(int i=1;i<=H*W;++i) {
    if(i<=D) arr[i%D].push_back(0);
    else arr[i%D].push_back(abs(amap[i].fi-amap[i-D].fi)+abs(amap[i].se-amap[i-D].se));
  }
  /**
  for(int i=0;i<D;++i) {
    for(int j=0;j<arr[i].size();++j) {
      cout<<arr[i][j]<<" ";
    }
    cout<<endl;
  }
  **/
  for(int i=0;i<D;++i) {
    for(int j=1;j<arr[i].size();++j) {
      arr[i][j] += arr[i][j-1];
    }
  }
  int Q;
  cin>>Q;
  int L, R;
  for(int i=0;i<Q;++i) {
    cin>>L>>R;
    if(R%D==0) cout<<arr[R%D][(R-D)/D] - arr[L%D][(L-D)/D]<<endl;
    else cout<<arr[R%D][(R-R%D)/D] - arr[L%D][(L-L%D)/D]<<endl;
  }
}


Measured memory_bytes: 13664
#include<iostream>
using namespace std;
#include<string>
#include<utility>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bits/stdc++.h>
#include<stdio.h>
 
int main(){
    long long int N;
    cin >> N;
    long long int num=0;
        num=(N-1)*N/2;
    cout << num;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

string s;
int main() {
	cin >> s;
	bool f = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == 'C') f = 1;
		if (f == 1 && s[i] == 'F') {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))
c = [0] * 100
k = bin(K)[2:]
kl = len(bin(K)) - 2
for a in A:
    a = list(bin(a)[2:])
    a.reverse()
    for i, b in enumerate(a):
        if b == '1':
            c[i] += 1
X = ''
C = c[:kl]
C.reverse()
for ck in C:
    if ck * 2 <= N:
        if int(k[:len(X)+1]) >= int(X + '1'):
            X += '1'
        else:
            X += '0'
    else:
        X += '0'
X = '0b' + X
X = int(X, base=2)
ans = sum([X ^ a for a in A])
print(ans)

Measured memory_bytes: 14620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;

int main() {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int ans = A * X + B * Y;
    ans = min(ans, max(X, Y) * 2 * C);
    int mi = min(X, Y);
    X -= mi, Y -= mi;
    ans = min(ans, mi * 2 * C + A * X + B * Y);
    cout << ans << endl;
    return 0;
}


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

int main() {
  	int n, m;
  	cin >> n >> m;
  	vector<P> p(m);
  	rep(i,m) cin >> p[i].first >> p[i].second;
  	rep(x,1000) {
    	int keta = 1;
    	int nx = x/10;
    	vector<int> d(1,x%10);
    	while (nx) {
      		keta++;
      		d.push_back(nx%10);
      		nx /= 10;
    	}
    	if (keta != n) continue;
    	bool ok = true;
    	reverse(d.begin(), d.end());
    	rep(i,m) {
    		if (d[p[i].first-1] != p[i].second) ok = false;
    	}
    	if (ok) {
      		cout << x << endl;
      		return 0;
    	}
  	}
  	cout << -1 << endl;
  	return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <limits>
#include <math.h>

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

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

  vector< vector<P> > xy;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    vector<P> tmp;
    for (int j = 0; j < a; ++j) {
      int x, y;
      cin >> x >> y;
      x--;
      tmp.push_back(P(x, y));
    }
    xy.push_back(tmp);
  }

  int ans = 0;
  for (int i = 0; i < 1 << n; ++i) {
    bool is_valid = true;
    for (int j = 0; j < n; ++j) {
      if (i >> j & 1) {
	for (int x = 0; x < xy[j].size(); ++x) {
	  if ((i >> xy[j][x].first & 1) != xy[j][x].second) is_valid = false;
	}
      }
    }
    if (is_valid) {
      int cnt = 0;
      for (int j = 0; j < n; ++ j) {
	if (i >> j & 1) cnt++;
      }
      ans = max(cnt, ans);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static int[][] bingo = new int[3][3];

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

		int n = Integer.parseInt(sc.next());
		int a = Integer.parseInt(sc.next());

		while (n >= 500) {
			n -= 500;
		}

		if (n <= a) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL

using namespace std;

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL) x = x->left;
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL) x = x->right;
  return x;
}

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

Node treeSuccessor(Node x){
  if(x->right != NIL) return treeMinimum(x->right);

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

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

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

  if(y->left != NIL) x = y->left;
  else x = y->right;

  if(x != NIL) x->parent = y->parent;
  
  if(y->parent == NIL) root = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;

  if(y != z) z->key = y->key;
}

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

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

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

  if(y == NIL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;

}

void inorder(Node x){
  if(x == NIL) return;
  inorder(x->left);
  cout << " " << x->key;
  inorder(x->right);
}
void preorder(Node x){
  if(x == NIL) return;
  cout << " " << x->key;
  preorder(x->left);
  preorder(x->right);
}

bool find(int k){
  Node x = treeSearch(root, k);
  return x != NIL;
}

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}


Measured memory_bytes: 21916
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

int main()
{
	int Q;
	long long A,B;
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		scanf("%lld%lld",&A,&B);
		long long pro=1LL*A*B;
		long long cnt=0;
		long long s=sqrt(pro)-1;
		cnt=2*s;
		cnt-=(A<=s)+(B<=s);
		s++;
		bool flag=false;
		if(s!=A&&(s+1)!=B&&s*(s+1)<pro)
			cnt++,flag=true;
		if((s+1)!=A&&s!=B&&s*(s+1)<pro)
			cnt++,flag=true;
		if(!flag&&s!=A&&s!=B&&s*s<pro)
			cnt++;
		
		printf("%lld\n",cnt);
	}
	
	return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(){
  int i,j,n,flag,result,tmp;
  int a[200001];
  int prime[2000000][2]={0,0};//0:input,1:prime filter
  
  scanf("%d",&n);
  if(1<n){
    for(i=0;i<n;i++){
      scanf("%d",&a[i]);
    
      //prime
      if(prime[(a[i])][0]==0 && prime[(a[i])][1]==0){
        prime[(a[i])][0]=1;
        tmp=a[i];
        while(tmp<=1000000){
          tmp+=a[i];
          prime[tmp][0]=1;
          prime[tmp][1]=1;
        }
      } else if(prime[(a[i])][0]==1){
        prime[(a[i])][1]=1;
      }
    }
    
    result=0;
    
    for(i=0;i<n;i++){
      flag=0;
        if(prime[(a[i])][1]==0){
          result++;
        }
    }
  } else {
    result=1;
  }
    
  printf("%d",result);
}

Measured memory_bytes: 18088
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
ww = [input() for i in range(N)]

if len(set(ww)) != N:
	print('No')
else:
	for i in range(N-1):
		a = ww[i]
		b = ww[i+1]
		if a[-1] != b[0]:
			print('No')
			sys.exit()
	print('Yes')


Measured memory_bytes: 4456
#include <iostream>
using namespace std;
int main(void) {
	int a,b,c,A,B,C;
	cin >> a >> b >> c;
	A = a;
	B = b;
	C = c;
	// b,a,c
	// c,a,b
	cout << c <<" " << a << " " << b << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(void){
  int m,n,i,j,k;
  int **vote;
  int *plnum;
  while(scanf("%d %d",&n,&m)&&(m!=0&&n!=0)){
    vote=(int **)calloc(n+1,sizeof(int *));
    for(i=0;i<n+1;i++){
      *(vote+i)=(int *)calloc(m,sizeof(int));
    }
    for(i=0;i<n+1;i++){
      for(j=0;j<m;j++){
	if(i<n){
	  scanf("%d",(*(vote+i)+j));
	}else{
	  *(*(vote+i)+j)=0;
	}
      }
    }
    for(i=0;i<m;i++){
     for(j=0;j<n;j++){
       *(*(vote+n)+i)+=*(*(vote+j)+i);
     }
    }
    plnum=(int *)calloc(m,sizeof(int));
    for(k=0;k<m;k++){
      *(plnum+k)=k+1;
    }
    k=m;
    for(i=n;i>=0;i--){
      for(j=0;j<m;j++){
	if(i==*(*(vote+n)+j)){
	  k--;
	  if(k!=0){
	    printf("%d ",*(plnum+j));
	  }else{
	    printf("%d\n",*(plnum+j));
	  }
	}
      }
    }
    free(plnum);
    for(i=0;i<n;i++){
      free(*(vote+i));
    }
    free(vote);
  }
  return 0;
}

Measured memory_bytes: 0