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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

int main(){
    ll n;
    cin>>n;
    ll ans=n;
    vector<ll> a(3), b(3);
    for (int i = 0; i < 3; i++)
    {
        cin>>a[i];
    }
    for (int i = 0; i < 3; i++)
    {
        cin>>b[i];
    }

    vector<pll> p(3);
    for (int i = 0; i < 3; i++)
    {
        p[i]=make_pair(a[i],b[i]);
    }
    sort(all(p));
    reverse(all(p));
    for (int i = 0; i < 3; i++)
    {
        a[i]=p[i].first;
        b[i]=p[i].second;
    }
    
    for (ll x = 0; x*a[0] <= n; x++)
    {
        for (ll y = 0; x*a[0]+y*a[1] <= n; y++)
        {
            ll z = (n -x*a[0] - y*a[1])/a[2];
            ll tmp=n;
            tmp+=x*(b[0]-a[0]) + y*(b[1]-a[1]);
            ans=max(ans,tmp);
            tmp+=z*(b[2]-a[2]);
            ans=max(ans,tmp);
            if(a[1]>b[1]) break;
        }
        if(a[0]>b[0]) break;
    }
    n=ans;

        
    for (int i = 0; i < 3; i++)
    {
        p[i]=make_pair(b[i],a[i]);
    }
    sort(all(p));
    reverse(all(p));
    for (int i = 0; i < 3; i++)
    {
        b[i]=p[i].first;
        a[i]=p[i].second;
    }

    for (ll x = 0; x*b[0] <= n; x++)
    {
        for (ll y = 0; x*b[0]+y*b[1] <= n; y++)
        {
            ll z = (n -x*b[0] - y*b[1])/b[2];
            ll tmp=n;
            tmp+=x*(a[0]-b[0]) + y*(a[1]-b[1]);
            ans=max(ans,tmp);
            tmp+=z*(a[2]-b[2]);
            ans=max(ans,tmp);
            if(a[1]<b[1]) break;

        }
        if(a[0]<b[0]) break;
    }
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(a+b+c <= 21) printf("win\n");
  else printf("bust\n");
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int f[510][510],n,mod,a[510],b[510];
ll ans;
void upd(int&a,ll b){a=(a+b)%mod;}
int main(){
	cin>>n>>mod;
	for(int i=0;i<2*n;i++){
		a[i]=b[i]=-1;
		for(int j=0;j<2*n;j++)
			if(j*j+i*i<=4*n*n) b[i]=j;
		for(int j=2*n-1;~j;j--)
			if(j*j+i*i>=n*n) a[i]=j;
	}
	for(int k=0;k<=2*n;k++){
		memset(f,0,sizeof(f));f[0][0]=1;
		int s1=0,s2=0,k1=n-1,k2=2*n-1;
		for(int i=0;i<2*n;i++){
			int now;
			if(k2<n||k1>=0&&a[k1]<b[k2]+1) now=k1--,s1++;
			else now=k2--,s2++;
			for(int j=0;j<=k&&j<=i;j++){
				if(now<n){
					upd(f[i+1][j+1],1ll*f[i][j]*(a[now]-j-s2));
					upd(f[i+1][j],1ll*f[i][j]*(b[now]+1-k-n-s1+j+1));
				}
				else upd(f[i+1][j],1ll*f[i][j]*(b[now]+1-j-s2+1));
			}
		}
		ans=(ans+(k&1?-1:1)*f[2*n][k])%mod;
	}
	cout<<(ans+mod)%mod<<'\n';
	return 0;
}


Measured memory_bytes: 1280
#encoding utf-8

n = list(str(input()))

for i in range(len(n)):
    if n[i] == "1":
        n[i] = "to9"
    if n[i] == "9":
        n[i] = "to1"

for i in range(len(n)):
    if n[i] == "to9":
        n[i] = "9"
    elif n[i] == "to1":
        n[i] = "1"

print("".join(n))


Measured memory_bytes: 3060
k = int(input())
dp = [0 for _ in range(k+100)]
good = False
for i in range(1, k+1):
    dp[i] = (dp[i-1] * 10 + 7) % k
    if dp[i] % k == 0:
        print(i)
        good = True
        break
if not(good):
    print(-1)
        
    
    


Measured memory_bytes: 48528
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> cnt(6, 0);
    for(int i = 0; i < n; i++)
    {
        double h; cin >> h;
        if(h >= 185) cnt[5]++;
        else if(h >= 180) cnt[4]++;
        else if(h >= 175) cnt[3]++;
        else if(h >= 170) cnt[2]++;
        else if(h >= 165) cnt[1]++;
        else cnt[0]++;
    }
    for(int i = 0; i < 6; i++)
    {
        cout << i + 1 << ":";
        for(int j = 0; j < cnt[i]; j++)
        {
            cout << "*";
        }
        cout << endl;
    }
    return 0;
}


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

const int N = 1000010;
vector<vector<int>> shiev(N);

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  vector<int> a(n);
  rep(i,n) cin >> a[i];

  for (int i = 2; i <= N; i++) {
    if(!shiev[i].empty()) continue;
    for (int j = i; j <= N; j += i) {
      shiev[j].push_back(i);
    }
  }

  bool flag = true;

  set<int> st;
  for (int i = 0; i < n; i++) {
    int x = a[i];
    for (int it : shiev[x]) {
      int v = it;
      if(st.count(v)) flag = false;
      st.insert(v);
    }
    if(!flag) break;
  }

  int GCD = gcd(0, a[0]);
  for (int i = 1; i < n; i++) {
    GCD = gcd(GCD, a[i]);
  }

  if(GCD == 1 && flag) {
    cout << "pairwise coprime" << endl;
  } else if(GCD == 1) {
    cout << "setwise coprime" << endl;
  } else {
    cout << "not coprime" << endl;
  }

}


Measured memory_bytes: 62564
#include <bits/stdc++.h>
#define REP(i, a, n) for (ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

class ConvexHullTrick {
  vector<pll> deq;
  ll s, t;

public:
  ConvexHullTrick(ll n) { /* n: number of lines */
    deq.resize(n);
    s = 0, t = 0;
  }

  void add(ll a, ll b) { /* a must decrease monotonously */
    const pll p(a, b);
    while(s + 1 < t && check(deq[t - 2], deq[t - 1], p)) t--;
    deq[t++] = p;
  }

  ll query(ll x) { /* O(log n) */
    ll low = s - 1, high = t - 1;
    while(low + 1 < high) {
      ll mid = (low + high) / 2;
      if(isright(deq[mid], deq[mid + 1], x)) low = mid;
      else high = mid;
    }
    return f(deq[high], x);
  }

private:
  bool isright(const pll &p1, const pll &p2, ll x) {
    return (p1.second - p2.second) >= x * (p2.first - p1.first);
  }

  bool check(const pll &p1, const pll &p2, const pll &p3) {
    return (p2.first - p1.first) * (p3.second - p2.second) >= (p2.second - p1.second) * (p3.first - p2.first);
  }

  ll f(const pll &p, ll x) {
    return p.first * x + p.second;
  }
};

int main(void) {
  ll N, C;
  cin >> N >> C;
  vector<ll> H(N);
  REP(i, 0, N) cin >> H[i];

  vector<ll> dp(N);
  dp[0] = 0;

  ConvexHullTrick cht(N);
  REP(i, 1, N) {
    cht.add(-2 * H[i - 1], dp[i - 1] + H[i - 1] * H[i - 1]);
    dp[i] = H[i] * H[i] + C + cht.query(H[i]);
  }

  cout << dp[N - 1] << endl;
}

Measured memory_bytes: 6528
package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	var ans int
	s := getNextString(scanner)
	t := getNextString(scanner)
	n := len(s)
	for i := 0; i < n; i++ {
		if s[i] != t[i] {
			ans++
		}
	}
	fmt.Fprintln(writer, ans)
}


Measured memory_bytes: 2608
#pragma GCC optimize("O1")

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int is_sum(int sum){
    int res = 0;
    while(sum > 0){
        res += sum%10;
        sum/=10;
    }
    return res;
}
signed main()
{   
    gearup;
    int n,l;cin>>n>>l;
    vector<string> s(n);
    rep(i,n)cin>>s[i];
    sort(all(s));
    rep(i,n)cout<<s[i];
    cout<<endl;
}


Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
    	int N = sc.nextInt();
    	int a = 0;
    	int[] ary = new int[N];
    	double sum = 0;
    	for(int i = 0; i < N; i++){
    		ary[i] = sc.nextInt();
    		sum += ary[i];
    	}
    	double average = sum / (double)N;
    	double num = 100;
    	for(int i = N-1; i >= 0; i--){
    		double n = Math.abs((double)ary[i] - average);
    		if(n < num || n == num){
    			a = i;
    			num = n;
    		}
    	}

        System.out.println(a);
    }
}

Measured memory_bytes: 22740
#include<stdio.h>
int f(int a,int b,int n){return b&&(n-a)%b==0?1:0;}  
int i,j,d[5010][5010]={};
int main(){
  int n,m,a[5010],b[5010],M=(1e9)+7;
  scanf("%d %d",&n,&m);
  for(i=0;i<n;i++)scanf("%d",&a[i]);
  for(i=0;i<n;i++)scanf("%d",&b[i]);
  d[0][a[0]]=1;
  for(i=a[0]+1;i<m;i++)d[0][i]=(d[0][i-1]+f(a[0],b[0],i))%M;
  for(i=1;i<n;i++){
    d[i][a[i]]=d[i-1][a[i]-1];
    for(j=a[i]+1;j<m;j++)d[i][j]=(d[i][j-1]+d[i-1][j-1]*f(a[i],b[i],j))%M;
  }
  printf("%d\n",d[n-1][m-1]);
  return 0;
}

Measured memory_bytes: 97224
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
   long N,A,B;
   cin >> N >> A >> B;
   long ans;
   if((A+B)%2==0){
       ans=(B-A)/2;
   }else{
   	   ans=min(A-1,N-B)+1+(B-A-1)/2;
   }
   cout << ans << endl;
}


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

int main(){
  
  int N;
  int A;
  int B;
  
  cin >> N >> A >> B;
  
  int num = A + B - N;
  
  if(A <= B){
    cout << A << " ";
  }
  else{
    cout << B << " ";
  }
  
  if(num < 0){
    cout << 0 << endl;
  }
  else{
    cout << num << endl;
  }

}


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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, a[N], b[N];

int main(){
	read(n);
	vector<pii> vec;
	for(int i = 1; i <= n; i++)	read(a[i]);
	for(int i = 1; i <= n; i++){
		read(b[i]);
		if(b[i] == a[i])
			vec.pb(mp(b[i], i));
	}
	sort(vec.begin(), vec.end());
	int sz = vec.size(), r = 0;
	vector<bool> o(sz, false);
	for(int l = 0; l < sz; l++){
		if(o[l])	continue;
		while(r < sz && vec[r].first == vec[l].first)	r++;
		if(r == sz)	break;
		swap(b[vec[l].second], b[vec[r].second]);
		o[r] = o[l] = true;
		r++;
	}
	int pt = 1;
	for(int i = 1; i <= n; i++){
		if(b[i] == a[i]){
			while(pt <= n && !(b[pt] != a[i] && b[i] != a[pt]))	pt++;
			if(pt == n + 1)	return puts("No"), 0;
			swap(b[i], b[pt]);
			pt++;
		}
	}
	for(int i = 1; i <= n; i++)
		if(b[i] == a[i])
			return puts("No"), 0;
	puts("Yes");
	for(int i = 1; i <= n; i++)	printf("%d ", b[i]); puts("");
	return 0;
}

Measured memory_bytes: 6560
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

//????????????????????????????????????
//ax+by=gcd(a,b) ???????????? x, y ????±???????
//http://mathtrain.jp/euclid (????¬???????????¨???????????????¨)
int extgcd(int a, int b, int &x, int &y) {
	int g = a; x = 1; y = 0;
	if (b != 0) {
		g = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	return g;
}

signed main() {
	int x, y;
	int a, b; cin >> a >> b;
	extgcd(a,b,x,y);
	cout << x << " " << y << endl;
	return 0;
}

Measured memory_bytes: 3080
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long


int main(){
    vector<int> a(3);
    cin>>a[0]>>a[1]>>a[2];
    sort(all(a));
    cout<<a[0]*a[1]/2<<endl;

    return 0;


}



Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

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

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll A, B, C;

int main()
{
  std::cin >> A >> B >> C;

  std::cout << std::min( B/A, C ) << std::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;
typedef long long ll;

int main() {
  
  string s;
  cin >> s;
  
  cout << s[0] << s.size()-2 << s[s.size()-1] << endl;

}


Measured memory_bytes: 3576
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int c11, c12, c13, c21, c22, c23, c31, c32, c33;
    cin >> c11 >> c12 >> c13 >> c21 >> c22 >> c23 >> c31 >> c32 >> c33;
    
    for (int i = 0; i <= c11; i++) {
        int a1 = i;
        int b1 = c11 - a1, b2 = c12 - a1, b3 = c13 - a1;
        int a2 = c21 - b1, a3 = c31 - b1;
        if (a2+b1==c21 && a2+b2==c22 && a2+b3==c23 && 
            a3+b1==c31 && a3+b2==c32 && a3+b3==c33) continue;
            else {
                cout << "No" << endl;
                return 0;
            }
    }
    
    cout << "Yes" << endl;
}


Measured memory_bytes: 3668
n = int(input())
s = ['']*n
for i in range(n):
  s[i] = input()
dict = {}
num = 0
for i in range(n):
  k = ''.join(sorted(s[i]))
  if k not in dict.keys():
    dict[k] = 1
  else:
    num += dict[k]
    dict[k] += 1  
print(num)

Measured memory_bytes: 24936
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());
            long[] lucas = new long[N + 1];
            lucas[0] = 2;
            lucas[1] = 1;

            for(int i = 2; i <= N; i++)
            {
                //配列で考える
                lucas[i] = lucas[i - 1] + lucas[i - 2];
            }
            Console.WriteLine(lucas[N]);
        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

//Console.WriteLine(ans);

Measured memory_bytes: 27480
/*
 * Author: FreeIdea
 * Created Time:  2011/10/22 17:01:43
 * File Name: I.cpp
 */
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

int n;
double v, X, Y, L[64], R[64], B[64], T[64], vx, vy;

bool solve();
bool check();
double get_y(double x);

int main() {
    while (solve());
    return 0;
}

bool solve() {
    if (scanf("%d%lf%lf%lf", &n, &v, &X, &Y) == EOF)
        return false;
    for (int i = 0; i < n; ++i) {
        scanf("%lf%lf%lf%lf", &L[i], &B[i], &R[i], &T[i]);
        if (L[i] > R[i])
            swap(L[i], R[i]);
        if (B[i] > T[i])
            swap(B[i], T[i]);
    }
    double step = 0.0001;
    for (vx = step; vx <= v; vx += step) {
        vy = sqrt(v * v - vx * vx);
        if (check()) {
            //printf("-- %lf %lf\n", vx, vy);
            puts("Yes");
            return true;
        }
    }
    puts("No");
    return true;
}

bool check() {
    double bx = X, by = get_y(X);
    if (by < Y)
        return false;
    for (int i = 0; i < n; ++i) {
        if (L[i] < X) {
            double l = L[i], r = min(X, R[i]);
            double y1 = get_y(l), y2 = get_y(r);
            //printf("-- %lf %lf %lf %lf\n", l, y1, r, y2);
            if (y1 >= B[i] && y1 <= T[i])
                return false;
            if (y2 >= B[i] && y2 <= T[i])
                return false;
            if (y1 <= B[i] && y2 >= B[i])
                return false;
            if (y1 >= B[i] && y2 <= B[i])
                return false;
            if (y1 <= T[i] && y2 >= T[i])
                return false;
            if (y1 >= T[i] && y2 <= T[i])
                return false;
        }
        if (L[i] <= bx && R[i] >= bx) {
            if (B[i] <= Y && T[i] >= Y)
                return false;
            if (B[i] >= Y && B[i] <= by)
                return false;
        }
    }
    return true;
}

double get_y(double x) {
    double t = x / vx;
    return vy * t - 0.5 * 9.8 * t * t;
}

Measured memory_bytes: 868
#include <iostream>
#include <algorithm>
#include <numeric>
#include <utility>
#include <map>
#include <vector>
#include <climits>
#include <cmath>
#include <stdlib.h>

#define max_n 100001

using namespace std;

int diff(string s1, string s2)
{
    int ans = 0; 
    for (int i = 0; i < s1.length(); i++)
    {
        ans += s1[i] != s2[i];
    }
    return ans;
}

int main()
{
    string s, t; cin >> s >> t;
    int ans = INT_MAX;
    for (int i = 0; i < s.length() - t.length() + 1; i++)
    {
        ans = min(ans, diff(s.substr(i, t.length()), t));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
using namespace std;
#define  max 200

int main()
{
    string s;
    cin>>s;
    cout<<s[0]<<s[1]<<s[2];
    return 0;
}


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

int main()
{
  int N;
  cin >> N;
  int64_t a = 2, b = 1;
  for (int i = 0; i < N; i++)
  {
    b += a;
    a = b - a;
  }
  cout << a << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cmath>

int main(){
    int n;
    std::cin >> n;

    int count = 0, curr = 0, next, ans = 0;
    while(std::cin >> next){
        if(next <= curr){
            ++count;
            ans = std::max(ans, count);
        }else{
            count = 0;
        }
        curr = next;
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 384
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
Sabun = 0
for i in range(len(A)):
    if i % 2 == 0:
        Sabun += A[i]
    elif i % 2 == 1:
        Sabun -= A[i]
print(Sabun)

Measured memory_bytes: 8944
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

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

int main(){
    ll a,b;
    cin>>a>>b;
    ll g=gcd(a,b);
    ll ans=1;
    for(ll i=2;i*i<=g;i++){
        if(g%i==0){
            ans++;
            while(g%i==0){
                g/=i;
            }
        }
    }
    if(g!=1)ans++;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
ll c[100010],n,s;
int main(){
    cin>>n>>s;
    c[0]=0;
    lol(i,n){
	ll a;cin>>a;
	c[i+1]=c[i]+a;
    }
    if(c[n]<s){
	cout<<"0"<<endl;
	return 0;
    }
    int r=0;
    while(r<=n){
	if(c[r]>=s)break;
	r++;
    }
    int ans=mod,l=0;
    while(r<=n){
	while(l<=r){
	    if(c[r]-c[l]<s){
		l--;
		break;
	    }
	    l++;
	}
	ans=min(ans,r-l);
	r++;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3876
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb emplace_back
#define pi pair<int,int>
using namespace std;
const int maxn = 1e5 + 4;

int n, k;
int a[maxn], dp[maxn];

int main(){
	cin>>n>>k;
	for (int i = 0; i < n; ++i){
		cin>>a[i];
	}
	for (int i = 1; i < n; ++i){
		int val = max(0, i-k);
		dp[i] = 1e9;
		for (int j = i-1; j >= val; --j){
			dp[i] = min(dp[i], dp[j]+abs(a[i]-a[j]));
		}
	}
	cout<<dp[n-1]<<'\n';

}

Measured memory_bytes: 1024
package main

import (
	"fmt"
)

func main() {
	var s, ans string
	fmt.Scan(&s)

	if s == "Sunny" {
		ans = "Cloudy"
	} else if s == "Cloudy" {
		ans = "Rainy"
	} else {
		ans = "Sunny"
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int A,B,C,K;
    cin>>A>>B>>C>>K;
    int ans=0;
    if(A>=K) ans=K;
    else if(A+B>=K) ans=A;
    else{
        ans=A-(K-A-B);
    }
    cout << ans << endl;



}


Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<list>
using namespace std;

typedef long long ll;

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    if(a*b < n || a+b-1 > n){
        cout << -1 << endl;
        return 0;
    }
    list<int> ans;
    int now = 1;
    for(int i = 0; i < b; i++){
        int len = max(1ll, min(a, (n-now+1)-(b-1-i)));
        for(int j = now+len-1; j >= now; j--)   ans.push_front(j);
        now += len;
    }
    for(auto it = ans.begin(); it != ans.end(); it++){
        cout << *it << " \n"[it==--ans.end()];
    }
    return 0;
}

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

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef pair <ll ,ll> pll;
typedef pair <int ,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define print(a) {for (auto iiiiiiiiii : a) cout << iiiiiiiiii << ' '; cout << '\n';}
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()

ll next() {ll x; cin >> x; return x;}

const ll inf = 1e18 , mod = 998244353;
const int intf = 2e9 , maxn = 3e5;
const double PI = 3.141592653589 , eps = 1e-9;


void solve(){
    int n; cin >> n;
    vector <ll> a(n);
    for (auto &x : a) cin >> x;

    ll mx = *max_element(all(a));
    a.erase(max_element(all(a)));
    ll mn = *min_element(all(a));
    a.erase(min_element(all(a)));

    vector <pii> ans;

    for (int i = 0; i < a.size(); i ++){
        if (a[i] >= 0){
            ans.eb(mn , a[i]);
            mn -= a[i];
        } else {
            ans.eb(mx , a[i]);
            mx -= a[i];
        }
    }
    ans.eb(mx , mn);
    mx -= mn;

    cout << mx << '\n';
    for (auto x : ans) cout << x.fi << ' ' << x.se << '\n';
}


int main()
{
    #ifdef HERE
        freopen("input.txt" , "r" , stdin);
    #else
        //freopen(".in" , "r" , stdin); freopen(".out" , "w" , stdout);
        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
    #endif

    for (int t = 1; t--;) solve();

    #ifdef HERE
        cout << setprecision(3) << fixed << "\n\nRuntime: " << (long double)(clock()) / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0;
}
/*

*/


Measured memory_bytes: 3572
N = int(input())
data = [[int(__) for __ in input().split()] for _ in range(N)]


data.insert(0, [0, 0, 0])
canTravel = True


def diff(nowData, oldData):
    absT = abs(nowData[0] - oldData[0])
    absX = abs(nowData[1] - oldData[1])
    absY = abs(nowData[2] - oldData[2])
    return [absT, absX, absY]


for index, d in enumerate(data):
    if index == 0:
        continue
    else:
        absT, absX, absY = diff(d, data[index - 1])
        distance = absX + absY
        if absT < distance or absT % 2 != distance % 2:
            canTravel = False
            break

if canTravel:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 21180
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
A??C
'''

test_data2 = '''\
ACACAC
'''

test_data3 = '''\
????C?????B??????A???????
'''

test_data4 = '''\
?AC?AC
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    if index==4:
        return test_data4
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        s=f.readline()
        # End Input code ---------------------------------------
else:
    # Start Input code ---------------------------------------
    s=input()
    # End Input code ---------------------------------------
n=len(s)
lc_a=[0]*n
lc_c=[0]*n
lc_w=[0]*n
rc_a=[0]*n
rc_c=[0]*n
rc_w=[0]*n
rc_a0=s.count('A')
rc_c0=s.count('C')
rc_w0=s.count('?')
c_a=0
c_c=0
c_w=0
for i in range(n-1):
    ch=s[i]
    if ch=='A':
        c_a+=1
    if ch=='C':
        c_c+=1        
    if ch=='?':
        c_w+=1
    lc_a[i+1]=c_a
    #lc_c[i+1]=c_c
    lc_w[i+1]=c_w
    #rc_a[i+1]=rc_a[0]-c_a
    rc_c[i]=rc_c0-c_c
    rc_w[i]=rc_w0-c_w
      
ans=0
mo=10**9+7
#mo=2291979612924+1
#print(ans,'n,s=',n,s,'lc(a,w)=',lc_a,lc_w,'rc(c,w)=',rc_c,rc_w)
for i in range(1,n-1):
    ch=s[i]
    if ch=='B' or ch=='?':
        ans+=(lc_a[i]*pow(3,lc_w[i],mo)+pow(3,max(0,lc_w[i]-1),mo)*lc_w[i])*(rc_c[i]*pow(3,rc_w[i],mo)+pow(3,max(0,rc_w[i]-1),mo)*rc_w[i])%mo
    #print('i,ans',i,ans)
#print(ans,'n,s=',n,s,'lc(a,w)=',lc_a,lc_w,'rc(c,w)=',rc_c,rc_w)
print(ans%mo)
#ans=count(0)+2^(count(n)-1)

Measured memory_bytes: 16188
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<numeric>
#include<vector>
#include<tuple>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
typedef long long ll;
const int MOD = 1e9 + 7;

int N, a[200];
int main(void)
{
	cin >> N;
	int ans=0;
	FOR(i, 0, 2*N)cin >> a[i];
	sort(a, a + 2*N);
	FOR(i, 0, N) {
		ans += min(a[2 * i], a[2 * i + 1]);
	}
	cout << ans << endl;
	system("pause");
	return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c;
  cin >> c;
  if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
  
}

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

typedef struct {
  int left, right;
  int parent, sibling, degree, depth, height;
} node;

vector<node> vs;

void calc_parent(int id)
{
  node v = vs[id];
  if (v.left != -1) {
    vs[v.left].parent = id;
    calc_parent(v.left);
  }
  if (v.right != -1) {
    vs[v.right].parent = id;
    calc_parent(v.right);
  }
}

void calc_sibling(int id)
{
  if (vs[id].parent == -1)
    return;
  int pid = vs[id].parent;
  if (vs[pid].left == id)
    vs[id].sibling = vs[pid].right;
  else
    vs[id].sibling = vs[pid].left;
}
void calc_degree(int id)
{
  int deg = 0;
  if (vs[id].left != -1) deg++;
  if (vs[id].right != -1) deg++;
  vs[id].degree = deg;
}

void calc_depth(int id, int depth)
{
  vs[id].depth = max(vs[id].depth, depth);
  if (vs[id].left != -1)
    calc_depth(vs[id].left, depth+1);
  if (vs[id].right != -1)
    calc_depth(vs[id].right, depth+1);
}

int calc_height(int id)
{
  if (vs[id].height != -1)
    return vs[id].height;
  int ans = 0;
  if (vs[id].left != -1)
    ans = max(ans, calc_height(vs[id].left)+1);
  if (vs[id].right != -1)
    ans = max(ans, calc_height(vs[id].right)+1);
  vs[id].height = ans;
  return ans;
}
void kind(int id)
{
  if (vs[id].parent == -1) {
    printf("root");
  } else if (vs[id].left == -1 && vs[id].right == -1) {
    printf("leaf");
  } else {
    printf("internal node");
  }
  printf("\n");
}
int main()
{
  int n; cin >> n;
  vs = vector<node>(n);
  for (int i = 0; i < n; i++) {
    int id, l, r;
    cin >> id >> l >> r;
    vs[id].left = l;
    vs[id].right = r;
    vs[id].parent = -1;
    vs[id].sibling = -1;
    vs[id].depth = -1;
    vs[id].height = -1;
  }
  for (int i = 0; i < n; i++) calc_parent(i);
  for (int i = 0; i < n; i++) calc_sibling(i);
  for (int i = 0; i < n; i++) calc_degree(i);
  for (int i = 0; i < n; i++) calc_depth(i, 0);
  for (int i = 0; i < n; i++) calc_height(i);
  for (int i = 0; i < n; i++) {
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",
           i,
           vs[i].parent,
           vs[i].sibling,
           vs[i].degree,
           vs[i].depth,
           vs[i].height);
    kind(i);
  }
  return EXIT_SUCCESS;
}




Measured memory_bytes: 3260
s_list1 = list(input())
n = len(s_list1)
s_list2 = s_list1.copy()
dic = {"0": "1", "1": "0"}
# first0
ans1 = 0
for i in range(n):
    if i == 0:
        if s_list1[i] == 1:
            s_list1[i] = 0
            ans1 += 1
    else:
        if s_list1[i - 1] == s_list1[i]:
            s_list1[i] = dic[s_list1[i - 1]]
            ans1 += 1

# first1
ans2 = 0
for i in range(n):
    if i == 0:
        if s_list2[i] == 0:
            s_list2[i] = 1
            ans2 += 1
    else:
        if s_list2[i - 1] == s_list2[i]:
            s_list2[i] = dic[s_list2[i - 1]]
            ans2 += 1
print(min(ans1, ans2))


Measured memory_bytes: 4776
/*
                                Bismillahi-r-Rahmani-r-Rahim
                                        RhIeyAaD
                                    IIT-7th Batch,JU
*/
#include<bits/stdc++.h>
using namespace std;

#define pf(a)           printf("%lld\n", a)
#define sf(a)           scanf("%lld", &a)
#define line(a)         getline(cin,(a))
#define ll              long long int
#define MAX             2134567891
#define MID(l,r)        (l+r)>>1
#define fr(i,n)         for(i=0;i<n;i++)
#define rep(i,n)        for(i=1;i<=n;i++)
#define per(i,a,n)      for(i=n;i>=a;i--)
#define FOR(i,a,n)      for(i=a;i<=n;i++)
#define ALL(n)          n.begin(),n.end()
#define mem(x,n)        memset(x,n,sizeof(x))
#define T_C(t)          printf("Case %lld: ",t)
#define TC(t)           printf("Case %lld:\n",t)
#define ans(t,c)        printf("Case %lld: %lld\n",t,c)
#define SETP(n)         cout<<setprecision(n)<<fixed
#define READ            freopen("F:\\Project\\Test_Case.txt","r",stdin)
#define WRITE           freopen("F:\\Project\\Output_Test.txt","w",stdout)
#define IO              ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define PAIR            pair<ll,ll>
#define MP              make_pair
#define pb(a)           push_back(a)
#define ff              first
#define ss              second
#define MOD             1000000007///10^9
#define p6              1000007 ///10^6->6 zero after 1 **
#define hlw             printf("hlw\n");
#define SN              4*p6
#define NN              111
#define N               p6

ll x[N],y[N],z[N],n;
string s,S;
vector<ll>v;
//map <ll,ll> mp;

int main()
{
    //IO;
    //while(1)
    //READ;WRITE;
{
    ll a=0,b=0,c=0,d,e,f,g,i,j,k,l,m,p,q,r,u,w,t,tc,in,mod,loc,diff,val,sz,lo,hi,mid,mn=MAX,mx=0,sum=0,ans=0;
    cin>>a;
    b=(a/500)*1000;
    //cout<<b<<endl;
    a%=500;
    b+=(a/5)*5;
    cout<<b<<endl;
}
    return 0;
}

/*

*/
/// Check for constraint 0 or 1?
/// long long or double? sqrt or division will work fine??


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

using namespace std;

int main(){
	int n;
	long long dp[31][50];
	while(cin >> n, n){
		memset(dp, 0, sizeof(dp));
		for(int i=0;i<n;i++) dp[0][i] = (1LL << i);
		vector< vector<int> > vi(30, vector<int>());
		for(int i=0;i<n;i++){
			int m, d; cin >> m;
			for(int j=0;j<m;j++){
				cin >> d;
				vi[d-1].push_back(i);
			}
		}
		for(int i=1;i<=30;i++){
			long long S = 0LL;
			for(int j=0;j<n;j++) dp[i][j] = dp[i-1][j];
			for(int j=0;j<vi[i-1].size();j++)
				S |= dp[i][vi[i-1][j]];
			for(int j=0;j<vi[i-1].size();j++)
				dp[i][vi[i-1][j]] = S;
		}
		int ans = -1;
		for(int i=1;i<=30;i++){
			for(int j=0;j<n;j++)
				if(dp[i][j]==(1LL<<n)-1) ans = i;
			if(ans != -1) break;
		}
		cout << ans << endl;
	}
}

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

int p[210];

int main(int argc, char const *argv[]) {
    int a, b, c;
    cin >> a >> b >> c;
    cout << c << " " <<  a << " " <<  b << endl;
    return 0;
}


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

#define FORR(i,b,e) for(int i=(b);i<(int)(e);++i)
#define FOR(i,e) FORR(i,0,e)
#define dump(var) cerr << #var ": " << var << "\n"
#define dumpc(con) for(auto& e: con) cerr << e << " "; cerr<<"\n"

typedef long long ll;
typedef unsigned long long ull;

const double EPS = 1e-6;
const int d4[] = {0, -1, 0, 1, 0};

using namespace std;

typedef pair<int,int> Pii;


const int INF = 1e9;

int edge[1010][1010];


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

    int V, E, r;
    cin >> V >> E >> r;
    FOR(i, V) FOR(j, V) edge[i][j] = INF;
    FOR(i, V) edge[i][i] = 0;
    FOR(i, E) {
        int s, t, d;
        cin >> s >> t >> d;
        edge[s][t] = d;
    }

    FOR(k, V) FOR(i, V) FOR(j, V) {
        if (edge[i][k] != INF && edge[k][j] != INF) {
            edge[i][j] = min(edge[i][j], edge[i][k]+edge[k][j]);
            if (i == j && edge[i][j] < 0 && edge[r][j]<INF) goto NC;
        }
    }
    FOR(i, V) {
        if (edge[r][i] == INF) cout << "INF";
        else cout << edge[r][i];
        cout << '\n';
    }
    return 0;

    NC:
    cout << "NEGATIVE CYCLE" << endl;
    
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);

    int x;
    cin >> x;

    int t = 0;
    while (x > 0) {
        t += 1;
        x -= t;
    }
    cout << t << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include<string.h>
int main()
{
    char str[4];
    scanf("%s",str);
    if(strlen(str)==2)
    printf("%s",str);
    else
    {
        for(int i=2;i>=0;i--)
        printf("%c",str[i]);
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;

int		main(void)
{
	string S, T, U;
	int A, B;
	cin >> S >> T;
	cin >> A >> B;
	cin >> U;
	if (U == S)
		A--;
	else
		B--;
	cout << A << " " << B << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
const ll MOD=1e9+7;

/*

*/

int main(void){
	ll mdp[1000010],cdp[1000010],p[1000010];//累積和
	mdp[0]=0;
	cdp[0]=0;
	p[0]=0;
	int n,q,x[110];
	vector<int>d,m,c;
	string s;
	cin>>n;
	cin>>s;
	cin>>q;
	rep(i,q)cin>>x[i];
	s=" "+s;
	reg(i,1,n){
		mdp[i]=mdp[i-1];
		cdp[i]=cdp[i-1];
		p[i]=p[i-1];
		if(s[i]=='D'){
			d.push_back(i);
		}else if(s[i]=='M'){
			m.push_back(i);
			mdp[i]++;
		}else if(s[i]=='C'){
			c.push_back(i);
			cdp[i]++;
			p[i]+=mdp[i];
		}
	}
	// cout<<"d ";
	// rep(i,d.size())cout<<d[i]<<" ";
	// cout<<endl;
	// cout<<"m ";
	// rep(i,m.size())cout<<m[i]<<" ";
	// cout<<endl;
	// cout<<"c ";
	// rep(i,c.size())cout<<c[i]<<" ";
	// cout<<endl;
	//DMC
	rep(i,q){
		ll ans=0;
		rep(k,d.size()){
			ans+=p[min(d[k]+x[i]-1,n)] - p[d[k]] - (mdp[d[k]]) * (cdp[min(d[k]+x[i]-1,n)]-cdp[d[k]]);
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 29608
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;

const ll mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  V<ll> a(n);
  rep(i, n) cin >> a[i];

  ll sum = 0;
  rep(i, n) sum += a[i];

  V<ll> s(n);
  rep(i, n) {
    sum -= a[i];
    s[i] = sum;
  }

  ll ans = 0;
  rep(i, n) {
    ll wa = s[i] % mod;
    ll se = wa * a[i] % mod;
    ans += se;
    ans %= mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 6360
n = int(input())
v = list(map(int, input().split()))


for i in range(0, n-1):
    min1 = min(v)
    v.remove(min1)
    min2 = min(v)
    v.remove(min2)
    fusion = (min1 + min2) / 2
    v.append(fusion)


print(v[0])

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

int main() {
 char b;
  cin >> b;
  if(b == 'A') cout << "T" << endl;
  if(b == 'T') cout << "A" << endl;
  if(b == 'C') cout << "G" << endl;
  if(b == 'G') cout << "C" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long n,k;
    cin >> n >> k;
    vector <int> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    vector <long double> expValSum(n);
    for(long i = 0; i < n; i++){
        if(i==0){
            expValSum[i]=((long double)1+(long double)p[i])*(long double)p[i]/(long double)2;;
            expValSum[i]/=(long double)p[i];
        }else{
            long double value = ((long double)1+(long double)p[i])*(long double)p[i]/(long double)2;
            expValSum[i]=value/(long double)p[i];
            expValSum[i]+=expValSum[i-1];
        }
    }
    #if 0
    for(long i = 0; i < n; i++){
        cout << expValSum[i] << " ";
    }
    cout << endl;
    #endif
    long double ans = 0;
    for(long i = 0; i < n; i++){
        if(k==1){
            if(i==0){
                long double tmp = expValSum[i];
                //cout << tmp << " ";
                if(tmp>ans){
                    ans = tmp;
                }
            }else{
                long double tmp = expValSum[i]-expValSum[i-1];
                //cout << tmp << " ";
                if(tmp>ans){
                    ans = tmp;
                }
            }
        }else{
            if((i-k)>=0){
                long double tmp = expValSum[i]-expValSum[i-k];
                //cout << tmp << " ";
                if(tmp>ans){
                    ans = tmp;
                }
            }else if(i==k-1){
                long double tmp = expValSum[i];
                //cout << tmp << " ";
                if(tmp>ans){
                    ans = tmp;
                }
            }
        }
    }
    //cout << endl;
    cout << std::fixed << std::setprecision(13) << ans << endl;

    return 0;
}

Measured memory_bytes: 4096
def dns(n):
    fact = [0, 0, 1]
    for i in range(2, n+1):
        fact.append(fact[-1]+i)
    return fact


N = int(input())
S = [input() for _ in range(N)]

hoge = dns(100008)

anagram_dict = {}

new_S = []

for s in S:
    tmp = "".join(sorted(list(s)))
    new_S.append(tmp)

for s in new_S:
    anagram_dict.setdefault(s, 0)
    anagram_dict[s] += 1

ans = 0
for v in anagram_dict.values():
    ans += hoge[v]

print(ans)


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()

const int MAX = 1e5+10;
const int MOD = 998244353;

int main() {
    int r; cin >> r;
    cout << r*r << endl;
}

Measured memory_bytes: 256
# Grid Coloring

h, w = map(int, input().split())
n = int(input())
a = [int(_) for _ in input().split()]

# 開始座標
x, y = 0, 0
# x座標に関するステータス
# 0のとき0→(w-1), 1のとき(w-1)→0
status = 0

# 答え入れる配列
ans = [[0] * w for _ in range(h)]

for i in range(n):
    for j in range(a[i]):
        #print(x, y, i, j)
        ans[y][x] = i+1
        if status == 0:
            x += 1
        else:
            x -= 1
        if x == w:
            status = 1
            x -= 1
            y += 1
        if x == -1:
            status = 0
            x += 1
            y += 1

for i in ans:
    for j in i:
        print(j, end=' ')
    print()

Measured memory_bytes: 3920
N = int(input())
lst1 = []
lst2 = []
for i in range(N):
    lst1.append(list(map(int, input().split())))
for i in range(N):
    lst2.append(list(map(int, input().split())))
lst1.sort()
lst2.sort()
cnt = 0
for i in lst2:
    ans = []
    for j in lst1:
        if i[0] <= j[0]:
            break
        else:
            if i[1] > j[1]:
                ans.append(j[::-1])
    if not ans:
        continue
    else:
        lst1.remove(max(ans)[::-1])
        cnt += 1
print(cnt)

Measured memory_bytes: 3188
while 1:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    count = 0

    for i in range(1, n + 1):
        for j in range(i+1, n + 1):
            for k in range(j + 1, n + 1):
                if i + j + k == x:
                    count += 1

    print(count)

    count = 0



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

int main() {
	int h, w; cin >> h >> w;
	char a[105][105];
	char b[105][105];

	for (int y = 0; y < h; y++) {
		scanf("%s", a[y]);
	}

	for (int y = 0; y < h + 2; y++) {
		for (int x = 0; x < w + 2; x++) {
			b[y][x] = '#';
		}
	}

	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			b[y+1][x+1] = a[y][x];
		}
	}

	for (int y = 0; y < h+2; y++) {
		for (int x = 0; x < w+2; x++) {
			printf("%c", b[y][x]);
		}
        printf("\n");
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, l, r) for(ll i = l; i < r; i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll MOD = 1000000007;

int main() {
    int N; cin >> N;
    vector<ll> ans(N+1,0);
    for(int x = 1;x < sqrt(N)+1;x++){
        for(int y = 1; y < sqrt(N)+1; y++){
            for(int z = 1; z < sqrt(N)+1; z++){
                ll tmp = x*x+y*y+z*z+x*y+y*z+z*x;
                if(tmp <= N) ans[tmp]++;
            }
        }
    }

    rep(i,N) cout << ans[i+1] << "\n";
    return 0;
}


Measured memory_bytes: 3720