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

using namespace std;

int q_sort(int d[],int left,int right){
	if(left >= right) return 0;
	int pipot = d[(left+right)/2], l = left, r = right, tmp;
	while(l<r){
		while(d[l] < pipot) l++;
		while(d[r] > pipot) r--;
		if( l <=  r){
			tmp = d[l];
			d[l] = d[r];
			d[r] = tmp;
			l++;
			r--;
		}
	}
	q_sort(d,left,r);
	q_sort(d,l,right);
}

long long int rui(int num,int k){
	long long int re = 1;
	int i = 0;
	for(i = 0; i < k;i++){
		re = num * re % wow;
		re = re % wow;
	}
	return re;
}
int main(void){
	int N;
	cin >> N;
	int D[N];
	long long int ans = 1;
	long long int k = 0;
	int kosuu,j,ue_num,i;
	int flag = 0;
	for(i = 0; i < N;i++){
		cin >> D[i];
	}
	if(D[0] != 0){
		cout<<"0"<<endl;
		return 0;
	}
	q_sort(D,0,N-1);
	if(D[0] != 0 || D[1] != 1){
		cout <<"0"<<endl;
		return 0;
	}
	if(N == 1 && D[0] == 0)
	{
		cout << "1"<<endl;
		return 0;
	}
	if(N == 0){
		cout <<"1"<<endl;
		return 0;
	}
	j = 1;
	i = 1;
	ue_num = 1;
	while(1){
		kosuu = 0;
		while(j == D[i]){
			i++;
			kosuu++;
		}
		j++;
		k = rui(ue_num,kosuu);
		k = k % wow;
		ans = ans * k % wow;
		ue_num = kosuu;
		ans = ans % wow;
		if(i >= N) break;
	}
	int renban = 0;
	while(1){
		if(renban != D[i]){
			flag == 1;
			break;
		}
		while(renban == D[i])
		{
			i++;
		}
		renban++;
		if(i >= N) break;
	}
	int koko = 0;
	if(flag == 0) printf("%lld\n",ans);
	else cout<<koko<<endl;
	return 0;
}




Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int const nax = 2e5 + 10;
const int INF = 1e8;
int n, m;
int l[nax];
int r[nax];
int sg[nax * 4];
int tag[nax * 4];

void push(int v, int l, int r) {
    if (!tag[v]) return ;
    if (l != r) {
        tag[v << 1] = tag[v];
        sg[v << 1] = tag[v << 1];
        tag[v << 1 | 1] = tag[v] + (l + r >> 1) - l + 1;
        sg[v << 1 | 1] = tag[v << 1 | 1];
    }
    tag[v] = 0;
}

void update (int v, int x, int y, int l, int r, int val) {
    push(v, x, y);
    if (l == x && r == y) {
        sg[v] = val;
        tag[v] = val;
        return push(v, x, y);
    }

    int mid = x + y >> 1;
    if (r <= mid) {
        update(v << 1, x, mid, l, r, val);
    } else if (l > mid) {
        update(v << 1 | 1, mid + 1, y, l, r, val);
    } else {
        update(v << 1, x, mid, l, mid, val);
        update(v << 1 | 1, mid + 1, y, mid + 1, r, val + mid - l + 1);
    }
    sg[v] = min(sg[v << 1], sg[v << 1 | 1]);
}

int get(int v, int x, int y, int l, int r) {
    push(v, x, y);
    if (l == x && r == y) {
        return sg[v];
    }
    int mid = x + y >> 1;
    if (r <= mid) return get(v << 1, x, mid, l, r);
    else if (l > mid) return get(v << 1 | 1, mid + 1, y, l, r);
    return min(get(v << 1, x, mid, l, mid)
               , get(v << 1 | 1, mid + 1, y, mid + 1, r));
}

void print_sg (int v, int x, int y) {
    if (x == y) {
        printf("i %d %d\n", x, sg[v]);
    } else {
        int mid = x + y >> 1;
        print_sg(v << 1, x, mid);
        print_sg(v << 1 | 1, mid + 1, y);
    }
}


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

    for (int i = 1 ; i <= n ; ++ i) {
        scanf("%d %d", l + i, r + i);
        int x = l[i] == 1 ? INF : get(1, 1, m, l[i] - 1, l[i] - 1);
        update(1, 1, m, l[i], r[i], x + 1);
       // print_sg(1, 1, m);
        if (sg[1] + i >= INF) {
            puts("-1");
        } else printf("%d\n", i + sg[1]);
    }

}


Measured memory_bytes: 9368
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std ;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define mod 1000000007

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int n ;
pii arr[500005] ;
int dp[2005][2005] ;
string str ;
int hf(int i,int l,int r)
{
    if(i == n+1)
    {
        return 0 ;
    }
    if(dp[i][l]!=-1)
        return dp[i][l] ;
    int a = (abs(arr[i].se-l))*arr[i].fi + hf(i+1,l+1,r) ;
    int b = (abs(arr[i].se-r))*arr[i].fi+hf(i+1,l,r-1) ;
    return dp[i][l] = max(a,b) ;
}
void solve()
{
    cin >> n ;
    memset(dp,-1,sizeof(dp)) ;
    for(int i=1 ; i<=n ; i++)
    {
        cin >> arr[i].fi ;
        arr[i].se = i ;
    }
    sort(arr+1,arr+n+1) ;
    reverse(arr+1,arr+n+1) ;
    cout << hf(1,1,n) ;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int tt = 1;
	//cin >> tt ;
	while(tt--)
	{
	     solve() ;
	}
}


Measured memory_bytes: 35208
def main():
    from math import gcd
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    adb = dict()
    ans = 0
    mod = 10**9+7
    for a, b in ab:
        if a == b == 0:
            ans += 1
            continue
        if b != 0:
            g = gcd(a, b)
            a = a//g
            b = b//g
            if b < 0:
                a *= -1
                b *= -1
            if a == 0:
                b = 1
            adb[(a, b)] = adb.get((a, b), 0)+1
        else:
            adb[(1, 0)] = adb.get((1, 0), 0)+1
    ans2 = 1
    for i, j in adb.items():
        if i[0] <= 0:
            k = (i[1], -i[0])
        else:
            k = (-i[1], i[0])
        if k not in adb:
            ans2 = ans2*pow(2, j, mod) % mod
        else:
            if i[0] > 0:
                ans2 = ans2*(pow(2, j, mod)+pow(2, adb[k], mod)-1) % mod
    ans2 = (ans2-1) % mod
    print((ans+ans2) % mod)


main()

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>a(n);
	for(int i=0;i<n;++i){
		cin>>a.at(i);
		a.at(i)-=i+1;
	}
	sort(a.begin(),a.end());
	int num=a.at(n/2);
	int64_t ans=0;
	for(int i=0;i<n;++i){
		ans+=abs(a.at(i)-num);
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<math.h>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, x, n) for (int i = x; i < (n); ++i)
using namespace std;

/**
 * 各桁の和を計算します
 */
int sumOfdigit(int n) {
    int res = 0;
    while(true) {

        res+= n % 10; // 余りを追加
        if (n / 10 > 0) n /= 10;
        else break;
    }
    return res;
}

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

    int sum = sumOfdigit(N);


    if ((N % sum == 0) && (N / sum > 0)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[210][10010];
int main(){
    int M = 1000000007;
    while (true) {
        int n, ww, w[210];
        cin >> n >> ww;
        if (!n) break;
        
        for (int i = 0; i < n; ++i) {
            cin >> w[i];
        }
        sort(w, w + n);
        if (w[0] > ww) {
            cout << "1\n";
            return 0;
        }
        
        dp[n][0] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < w[i]; ++j) {
                dp[i][j] = dp[i + 1][j];
            }
            for (int j = w[i]; j <= ww; ++j) {
                dp[i][j] = (dp[i + 1][j] + dp[i + 1][j - w[i]]) % M;
            }
        }
        
        int pre = 0, sum = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (pre == w[i]){
                sum += w[i];
                continue;
            }
            if (sum > ww) break;
            
            for (int j = max(0, ww - w[i] + 1 - sum); j < ww - pre + 1 - sum; ++j) {
                ans = (ans + dp[i][j]) % M;
            }
            sum += w[i];
            pre = w[i];
        }
        cout << ans << "\n";
        
        return 0;
    }
    return 0;
}

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

const int INF = 1e8+1e8+1e8;

int main(void){
    int N, M; cin >> N >> M;
    vector< pair<int, int> > a(N), c(M);
    for(int i = 0; i < N; i++){
        cin >> a[i].first >> a[i].second;
    }
    for(int i = 0; i < M; i++){
        cin >> c[i].first >> c[i].second;
    }

    vector<int> ans(N);

    for(int i = 0; i < N; i++){
        int closest_idx = -1;
        int closest_dst = INF;
        for(int j = 0; j < M; j++){
            int dest = abs(a[i].first - c[j].first) + abs(a[i].second - c[j].second);
            if(dest < closest_dst){
                closest_idx = j;
                closest_dst = dest;
            }
        }
        ans[i] = closest_idx;
    }
    for(int i = 0; i < N; i++){
        cout << ans[i]+1 << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long int a[n];
    long long int mon=1000;
    for(int i=0;i<n;i++)cin >> a[i];
    for(int i=1;i<n;i++){
        if(a[i]>a[i-1])mon+=(mon/a[i-1])*(a[i]-a[i-1]);
    }
    cout << mon;
}

Measured memory_bytes: 3616
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
 
using namespace std;
 
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
 
const ll INF=1e9+7;

int main(){
    ll n;
    cin >> n;
    vector<ll> d(n);
    rep(i,n){
        cin >> d[i];
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        for(ll j=i+1;j<n;j++){
            ans+=d[i]*d[j];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
def is_palindrome(char) -> bool:
	char_reverse = char[::-1]

	if char == char_reverse:
		return True
	else:
		return False
	

def main():
	A, B = map(int, input().split())
	ans = 0

	for num in range(A, B + 1):
		result = is_palindrome(str(num))

		if result:
			ans += 1

	print(ans)

  
if __name__ == "__main__":
  	main()

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

int main() {
	int A, B;
	cin >> A >> B;
	if (A <= 5) {
		cout << "0" << endl;
	} else if (A <= 12) {
		cout << B / 2 << endl;
	} else {
		cout << B << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import sys
import copy
sys.setrecursionlimit(100000)
h, w = map(int, input().split())
mapping = [0]*h
for i in range(h):
  mapping[i] = input()
ans = [[[-1, -1, -1] for j in range(w)] for i in range(h)]
def dp(i, j):
  if ans[i][j][0] >= 0:
    pass
  else:
    if i == 0 and j == 0:
      if mapping[i][j] == ".":
        ans[i][j] = [0, 0, 0]
      else:
        ans[i][j] = [1, 0, 0]
    elif i == 0:
      if mapping[i][j] == ".":
        ans[i][j] = copy.deepcopy(dp(i, j-1))
        ans[i][j][1], ans[i][j][2] = i, j
      else:
        ans[i][j] = copy.deepcopy(dp(i, j-1))
        if mapping[i][j-1] == ".":
          ans[i][j][1], ans[i][j][2] = i, j
          ans[i][j][0] += 1
    elif j == 0:
      if mapping[i][j] == ".":
        ans[i][j] = copy.deepcopy(dp(i-1, j))
        ans[i][j][1], ans[i][j][2] = i, j
      else:
        ans[i][j] = copy.deepcopy(dp(i-1, j))
        if mapping[i-1][j] == ".":
          ans[i][j][1], ans[i][j][2] = i, j
          ans[i][j][0] += 1
    else:
      if mapping[i][j] == ".":
        k = min([dp(i-1, j)[0], dp(i, j-1)[0]])
        ans[i][j] = [k, i, j]
      else:
        p = copy.deepcopy(dp(i-1, j))
        if mapping[i-1][j] == ".":
          p[1], p[2] = i, j
          p[0] += 1
        q = copy.deepcopy(dp(i, j-1))
        if mapping[i][j-1] == ".":
          q[1], q[2] = i, j
          q[0] += 1
        if p[0] < q[0]:
          ans[i][j] = copy.deepcopy(p)
        elif p[0] > q[0]:
          ans[i][j] = copy.deepcopy(q)
        elif p[1]+p[2] < q[1]+q[2]:
          ans[i][j] = copy.deepcopy(q)
        else:
          ans[i][j] = copy.deepcopy(p)
  return ans[i][j]

answer = dp(h-1, w-1)
print(answer[0])

Measured memory_bytes: 4956
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
vector<int> e[2010];
char s[2010];
int sd;
pair<int, int> dp[2010];
int cnt[2010];
void go(int v, int d = 0, int p = -1) {
	vector<pair<int, int> > c;
	cnt[v] = 0;
	if (s[v]) {
		sd += d;
		cnt[v]++;
	}
	for (int i = 0; i < e[v].size(); i++) {
		int w = e[v][i];
		if (p == w) continue;
		go(w, d + 1, v);
		c.push_back(make_pair(dp[w].first + cnt[w], dp[w].second + cnt[w]));
		cnt[v] += cnt[w];
	}
	dp[v] = make_pair(0, 0);
	if (c.size()) {
		sort(c.begin(), c.end());
		reverse(c.begin(), c.end());
		int k = 0, t = 0;
		for (int i = 0; i < c.size(); i++) {
			k += c[i].second;
			if (i) {
				t -= c[i].second;
			} else {
				t += c[i].first;
			}
		}
		if (t < 0) t = t & 1;
		dp[v] = make_pair(t, k);
	}
}
int main() {
	int n;
	scanf("%d%s", &n, s);
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	int k = 0;
	for (int i = 0; i < n; i++) {
		s[i] -= '0';
		k += s[i];
	}
	if (k == 1) {
		puts("0");
		return 0;
	}
	int ans = 1001001001;
	for (int i = 0; i < n; i++) {
		sd = 0;
		go(i);
		if (dp[i].first == 0) {
			ans = min(ans, sd / 2);
		}
	}
	if (ans == 1001001001) {
		puts("-1");
	} else {
		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 640
h,n=map(int,input().split())
lis=[list(map(int,input().split())) for i in range(n)]

dp=[float('inf') for i in range(h+10**4+1)]
dp[0]=0

for i in range(1,h+10**4+1):
    for j in range(n):
        if i>=lis[j][0]:
            dp[i]=min(dp[i],dp[i-lis[j][0]]+lis[j][1])
        else:
            dp[i]=dp[i]
print(min(dp[h:]))

Measured memory_bytes: 43628
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFind(n)
for i, j in ab:
    uf.union(i-1, j-1)
print(uf.group_count()-1)

Measured memory_bytes: 29408
while True:
    record = input()
    
    if record=='0' :
        break
    
    rlist = list(record)
    
    rlen = len(rlist)
    
    A = 0
    B = 0
    
    for i in range(1,rlen,1):
        
        if rlist[i]=='A' :
            A += 1
        if rlist[i]=='B' :
            B += 1
        
        if i==rlen-1 :
            if A>B:
                A += 1
            if B>A:
                B += 1
    
    print(A,B)
    continue


Measured memory_bytes: 5556
n, k=map(int, input().split())
nums=input().split()
nums=[int(x) for x in nums]

def split_to1d(x):
  
  res=[]
  while True:
    
    y=x%10
    res.append(y)

    z=x//10
    if z<1:
      break
      
    x=z
  
  return res

while True:
  
  num_list=split_to1d(n)

  for i, num in enumerate(num_list):

    is_ok=True
    if num in nums:
      is_ok=False
      break
     
  if is_ok:
    break
  else:
    n+=1
    
print(n)


Measured memory_bytes: 3060
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string

def factors_nojit(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n0 = n
            n //= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

MAX = 10**5 + 100
mod = 10**9+7

fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod

rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod

def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod

N,M = map(int, input().split())

fs =  factors_nojit(M)
fs.sort()

dd = defaultdict(int)
ed = []
for f in fs:
    if dd[f] == 0:
        ed.append(f)
    dd[f] += 1

ans =1
for e in ed:
  k = dd[e]
  ans *= Comb(k+N-1,k)
  ans %= mod

print(ans)


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

using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  bool flag[n];int seito = 0,pena[n],ansp = 0;;
  fill(flag,flag+n,0);
  fill(pena,pena+n,0);
  for(int i = 0;i < m;i++){
    int p;string s;
    cin >> p >> s;
    if(s == "AC"){
      if(flag[p-1] == true)continue;
      flag[p-1] = true;
      seito++;
    }else{
      if(flag[p-1] == true)continue;
      pena[p-1]++;
    }
  }
  for(int i = 0;i < n;i++){
    if(flag[i])ansp += pena[i];
  }
  cout << seito << " " << ansp;
  return 0;
}

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

int main()
{
	int a, b, c, d, p, x, y;

	cin >> a >> b >> c >> d >> p;

	x = a * p;

	if (p <= c)
		y = b;
	else
		y = b + (p - c)*d;

	if (x < y)
		cout << x << endl;
	else
		cout << y << endl;


	return 0;
}


Measured memory_bytes: 3056
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(void){
    int n;
    pair<int,int> a[110000];
    cin>>n;
    rep(i,n){
        cin>>a[i].first;
        a[i].second=i+1;
    }
    sort(a,a+n);
    rep(i,n){
        cout<<a[i].second<<endl;;
    }
    
    
    
}



Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

struct mint {
    const int mod = 1e9 + 7;
    long long x;
    
    mint (long long x = 0) : x((x % mod + mod) % mod) {
        
    }
    
    mint& operator=(const long long a) {
        x = a % mod;
        return *this;
    }
    
    mint& operator=(const mint a) {
        x = a.x % mod;
        return *this;
    }
    
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    
    mint& operator-=(const mint a) {
        if ((x += (mod - a.x)) >= mod) x -= mod;
        return *this;
    }
    
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    
    mint inv() const {
        return pow(mod - 2);
    }
    
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

map<ll, ll> factorize2(ll n) {
    map<ll, ll> res;
    for (ll i = 2; (i * i) <= n; i++) {
        if (n % i) continue;
        res[i] = 0;
        while((n % i) == 0) {
            n /= i;
            res[i]++;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    const ll mod = 1e9 + 7;
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    map<ll, ll> fac;
    vector<map<ll, ll>> fm(n);
    rep(i, n) {
        fm[i] = factorize2(a[i]);
        for(auto x : fm[i]) {
            ll v = x.first, c = x.second;
            fac[v] = max(fac[v], c);
        }
    }
    mint lcm = 1;
    for(auto x : fac) {
        rep(i, x.second) {
            lcm *= x.first;
        }
    }
    mint ans = 0;
    rep(i, n) {
        ans += lcm / a[i];
    }
    cout << ans.x << endl;
    return 0;
}


Measured memory_bytes: 3968
x1,y1,x2,y2=gets.chomp.split(" ").map(&:to_i)
x3=x2-(y2-y1)
y3=y2-(x1-x2)
x4=x3+(x1-x2)
y4=y3+(y1-y2)
puts ("#{x3} #{y3} #{x4} #{y4}")

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <functional>

using namespace std;

typedef long long int ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
	int n, x;
	while (true)
	{
		cin >> n >> x;
		if (n == 0 && x == 0)
		{
			break;
		}
		int sum = 0;
		FOR(i, n + 1, 1)
		{
			FOR(j, n + 1, i + 1)
			{
				if (i + j >= x)break;
				if (x - i - j <= n&&x - i - j > j)sum++;
			}
		}
		cout << sum << endl;
	}
	return 0;
}


Measured memory_bytes: 3108
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto nm = readln.split.to!(int[]);
    auto N = nm[0];
    auto M = nm[1];
    int as;
    foreach (a; readln.split.to!(int[])) as += a;
    writeln(max(-1, N - as));
}

Measured memory_bytes: 2756
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#include <string>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")

#define DEBUG(x) cout << ">> " << #x << ": " << x << endl;
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
typedef long long ll;
typedef long double ld;

int main() { _
  int n; cin >> n;
  int a = n/1.08;
  int b = a+1;
  if (int (a*1.08) == n) cout << a << endl;
  else if (int (b*1.08) == n) cout << b << endl;
  else cout << ":(" << endl;
  return 0;
}

Measured memory_bytes: 256
def main():
    from collections import Counter

    N = int(input())
    *V, = map(int, input().split())

    ctr_odd = Counter(V[::2])
    ctr_odd[-1] = 0  # 番兵

    ctr_even = Counter(V[1::2])
    ctr_even[-1] = 0  # 番兵

    ans = N
    for odd_n, odd_c in ctr_odd.most_common(2):
        for even_n, even_c in ctr_even.most_common(2):
            if odd_n == even_n: continue
            ans = min(ans, N - odd_c - even_c)
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
  double a, b, h, m;
  cin >> a >> b >> h >> m;
  double pi = acos(-1);
  auto hc = polar<double>(a, (h * 60 + m) * pi / 360);
  auto mc = polar<double>(b, m * pi / 30);
  printf("%.20f\n", abs(hc - mc));
}

Measured memory_bytes: 4144
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

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

int main() {
  int k;
  cin >> k;

  long sum = 0;
  for (int a = 1; a <= k; a++) {
    for (int b = 1; b <= k; b++) {
      for (int c = 1; c <= k; c++) {
        sum += gcd(gcd(a, b), c);
      }
    }
  }

  cout << sum << endl;
}


Measured memory_bytes: 3160
while ((n,x = gets.split(" ").map(&:to_i)).inject(:+) != 0) do
  max = 3*(n-1)
  if !((6..max).include?(x))
    puts 0
    next
  end
  count = 0
  n.downto(1) do |n1|
    (n1-1).downto(1) do |n2|
      n3 = x - n1 - n2
      count += 1 if (n3 < n2) && (n3 > 0)
      break if (n3 > n2)
    end
  end
  puts count
end

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

using namespace std;
using namespace std::chrono;

#define rep(i,a,b) for(int i = a;i<(b);++i)
#define trav(a,v) for(auto& a : v)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;

ll big = 1000000007ll;
ll big2 = 1000000009ll;
ll n,m,T,k,q,p,w,h;

int main()
{
   // freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,d,e;

    cin >> n;
    vector<ll> A;
    for(ll c1 = 0; c1 < n; c1++){
        cin >> a;
        a--;
        A.push_back(a);
    }
    ll ans = 0;
    for(ll c1 = 0; c1 < n; c1++){
        if(A[c1] == c1){
            ans++;
            if(c1 < n-1){
                a = A[c1];
                A[c1] = A[c1+1];
                A[c1+1] = a;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 1400
#include <iostream>
using namespace std;
int main(){
	
string s;
getline(cin,s);
for(int i=0;i<s.length();i++){
	if(i==0){
		s[0]-=32;
		cout<<s[0];
	}
	if(s[i]==' '){
		s[i+1]-=32;
		cout<<s[i+1];
	}
}
	
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define int long long
#define eps 0.0000000001
using namespace std;
char str[1005];
int n;
void dfs(int pos,int maxx){
	 if(pos==n+1){
	 	for(int i=1;i<=n;i++){
            cout<<str[i];
	 	}
	 	cout<<endl;
	 	return ;
	 }
	 for(int i=1;i<=maxx;i++){
	 	str[pos]=i+'a'-1;
	 	if(i==maxx){
	 		dfs(pos+1,maxx+1);
	 	}
	 	else{
	 		dfs(pos+1,maxx);
	 	}
	 }
}
signed main(){
	
	cin>>n;
	dfs(1,1);
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iomanip>
using namespace std;
 
#define REP(i,n) for(long long (i)=0;(i)<(long long)(n);(i)++)
#define RREP(i,n) for(long long (i)=(long long)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

struct UnionFind {

    vector<int> node;
    UnionFind(int n) : node(n,-1) {}

    bool unite(int x, int y) {
        x = root(x); 
        y = root(y);
        if (x != y) {
        if (node[y] < node[x]) swap(x, y);
            node[x] += node[y]; 
            node[y] = x;
        }
        return x != y;
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int root(int x) {
        return node[x] < 0 ? x : node[x] = root(node[x]);
    }

    int size(int x) {
        return -node[root(x)];
    }
    
};

int N,M;
vector<int> a,b;

int main() {

	cin >> N >> M;
	a.resize(M);
	b.resize(M);
	REP(i,M) cin >> a[i] >> b[i];

	int ans = 0;
	REP(i,M) {
		UnionFind inst(100);
		REP(j,M) {
			if (i != j) {
				inst.unite(a[j], b[j]);
			}
		}
		if (!inst.same(a[i], b[i])) ans++;
	}

	cout << ans << endl;

	return 0;
}






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

int main() {
    ll n,a[200];
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    //print
    for(int k=0;k<n;k++){
        cout << a[k];
        if(k != n-1) cout << " ";
        else cout << endl;
    }
    //insertion sort
    for(int i=1;i<n;i++){
        ll v = a[i];
        int j = i - 1;
        while(j>=0 && a[j] > v){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = v;
        for(int k=0;k<n;k++){
            cout << a[k];
            if(k != n-1) cout << " ";
            else cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3084
#include <stdio.h>
 
int main()
{
  char a[4];
  scanf("%s",&a);
  int i = 0;
  int y = 700;
  while (a[i])
  {
    if (a[i] == 'o')
      y += 100;
    i++;
  }
  printf("%d",y);
}

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

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

map<char, bool> is_removed;
int baggage_cnt = 0;
int h,w;
char c = '*';

bool is_rectangle(int si, int sj, int gi, int gj, char c, string s[]){

    rep(h){
        repp(j, w){
            if(si <= i && i <= gi && sj <= j && j <= gj){
                if(s[i][j] != c && !is_removed[s[i][j]]){
                    return false;
                }
            }else{
                if(s[i][j] == c) return false;
            }
        }
    }
    return true;
}

string solve(string s[]){
    set<char> st;
    rep(h){
        repp(j, w){
            if(s[i][j] != '.') st.insert(s[i][j]);
        }
    }
    baggage_cnt = (int)st.size();
    if(!baggage_cnt) return "SAFE";

    bool change = true;
    while(change){
        change = false;
        for(char c: st){
            if(is_removed[c]) st.erase(c);
        }
        for(char c: st){
            int si = INT_MAX, sj = INT_MAX, gi = -1, gj = -1;
            rep(h){
                repp(j, w){
                    if(s[i][j] == c){
                        si = min(i, si);
                        sj = min(j, sj);
                        gi = max(i, gi);
                        gj = max(j, gj);
                    }
                }
            }
            if(gi == -1) continue;

            if(is_rectangle(si, sj, gi, gj, c, s)){
                is_removed[c] = true;
                change = true;
                baggage_cnt--;
                if(!baggage_cnt) return "SAFE";
            }
        }
    }
    return "SUSPICIOUS";
}

int main() {
    int t;
    cin >> t;

    repp(tt, t){
        cin >> h >> w;
        string s[h];
        rep(h) cin >> s[i];
        is_removed.clear();
        baggage_cnt = 0;
        cout << solve(s) << endl;
    }
}


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

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int N = 3e5 + 10;

typedef long long LL;

int n, m;
int A[N];
LL S[N], F[N];
int stk[N], top;

double sect(int i, int j){
	return 1.0 * (F[i] - F[j]) / (i - j);
}

void pop(int i){
	while(top > 1 && sect(stk[top], stk[top - 1]) < i) --top;
}

void push(int i){
	while(top > 1 && sect(i, stk[top]) > sect(stk[top], stk[top - 1])) --top;
	stk[++top] = i;
}

void work(LL *dp){
	For(i, 1, n) S[i] = S[i - 1] + A[i];
	dp[0] = 0;
	stk[top = 1] = 0;

	For(i, 1, n){
		dp[i] = dp[i - 1];
		LL C = 1ll * i * (i + 1) / 2 - S[i];
		pop(i);
		
		int j = stk[top];
		dp[i] = max(dp[i], F[j] + C - 1ll * i * j);

		F[i] = 1ll * i * (i - 1) / 2 + dp[i] + S[i];
		push(i);
	}
}

LL val[N], tmp[N];

void solve(LL *dp, LL *rdp, int l, int r){
	if(l == 0 && r == n) For(i, 1, n) S[i] = S[i - 1] + A[i];
	if(l == r) return;
	
	int mid = (l + r) >> 1;
	top = 0;
	For(i, l, mid){
		F[i] = 1ll * i * (i - 1) / 2 + dp[i] + S[i];
		push(i);
	}
	For(i, mid + 1, r){
		pop(i);
		int j = stk[top];
		LL C = 1ll * i * (i + 1) / 2 - S[i];
		tmp[i] = F[j] + C - 1ll * i * j + rdp[i + 1];
	}
	Forr(i, r - 1, mid + 1) tmp[i] = max(tmp[i], tmp[i + 1]);
	For(i, mid + 1, r) val[i] = max(val[i], tmp[i]);
	solve(dp, rdp, l, mid), solve(dp, rdp, mid + 1, r);
}

LL fl[N], fr[N];

#define rev(x) reverse(x + 1, x + n + 1)

int main(){
	scanf("%d", &n);
	For(i, 1, n) scanf("%d", &A[i]), val[i] = -1e18;

	work(fl);
	rev(A);
	work(fr);
	rev(A), rev(fr);
	solve(fl, fr, 0, n);
	rev(fl), rev(fr), rev(A), rev(val);
	solve(fr, fl, 0, n);
	rev(fl), rev(fr), rev(A), rev(val);

	scanf("%d", &m);
	while(m--){
		int p, x;
		scanf("%d%d", &p, &x);
		printf("%lld\n", max(fl[p - 1] + fr[p + 1], val[p] + A[p] - x));
	}

	return 0;
}

Measured memory_bytes: 18944
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<climits>
#include<numeric>
#include<cmath>
#include<cstring>
#include<deque>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define VE vector<int>
#define VEP vector<pair<int,int>>
#define llong long long
#define pb(a) push_back(a)
using namespace std;
int main() {
	int num, lim;
	cin >> num >> lim;
	VE pos(num);
	
	REP(i, num) {
		cin >> pos[i];
	}
	int ball = 0;
	REP(i, num) {
		ball += pos[i];
		if (ball > lim) {
			cout << i+1 << endl;
			return 0;
		}
	}
	cout << num + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define  all(v)            v.begin(), v.end()
#define  sz(x)             (int)x.size()
#define  debug(x)         cout << '>' << #x << ':' << x << endl;
#define  rep(i,n)         for(int i = 0; i < n; i++)
#define  reps(i,n)        for(int i = 1; i<=n ; i++)
#define  make_unique(v)   sort(all(v));v.erase(unique(all(v)), v.end());
#define  rot(v)           rotate(v.begin(), v.begin() + k, v.end());
#define  rmv(v,a)         v.erase(remove(v.begin(),v.end(), a), v.end());
#define  max(x,y)         ((x>y)?x:y)
#define  min(x,y)         ((x<y)?x:y)
#define  pb               push_back
#define  eb               emplace_back
#define  mp               make_pair
#define  endl             '\n'
#define  fi               first
#define  se               second
#define  ajs(a)           (a<0)?(-1*a):a
using namespace std;
typedef long long          ll;
// use count() instead of find() in sets.
const ll MOD = 1e9 + 7;
const double PI  = acos(-1.0);
const double EPS = (1e-10);
const int dx4[4] = {0, 1, 0, -1};
const int dy4[4] = { -1, 0, 1, 0};
const int dx8[8] = { -1, -1, -1, 0, 1, 1, 1, 0};
const int dy8[8] = { -1, 0, 1, 1, 1, 0, -1, -1};
bool cmp(int X, int Y) {return X > Y;}
int dcp(double A, double B){return fabs(A-B)<=EPS ? 0 : A<B ? -1:1;}


ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b);}
ll lcm(ll a, ll b) {return (a / gcd(a, b)) * b;}
ll modpow(ll a, ll b, ll m ){a %= m; ll res = 1; while (b) {if (b & 1)res = (res * a) % m; a = (a * a) % m; b >>= 1;} return res;}
ll bpow(ll a, ll b){ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a, ll m = MOD) {return modpow(a, m - 2, m);}




int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n,k ; cin>>n>>k;

ll h[n+1];
h[0] = 0;
reps(i,n){cin>>h[i];}
ll dp[n+1];
memset(dp,MOD,sizeof(dp));
dp[0] = 0;
dp[1] = 0;

for(ll i = 2; i<=n ; i++){
        for(ll j = 1; j<=k;j++){
                if(i-j > 0)
                dp[i] = min(dp[i] , dp[i-j]+ abs(h[i] - h[i-j]));
        }

}
cout<<dp[n];
}





Measured memory_bytes: 5172
#include <bits/stdc++.h>
using namespace std;
  int main () {
  int A ,B;
    
  cin >> A >> B;
  
  if((A + B) % 2 == 0 && B > A){
  cout << B - (B - A) / 2;
  }
  
  else if ((A + B) % 2 == 0 && A > B){
  cout << A - (A - B) / 2;
  }
    
  else{
  cout << "IMPOSSIBLE";
  }
  }

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

using namespace std;

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

	long long ans = 0;
	for (int i = 1; i < n; i++) {
		if (a[i] + a[i - 1] > x) {
			if (a[i - 1] > x) {
				ans += a[i] + a[i - 1] - x;
				a[i] = 0;
			} else {
				ans += a[i] - (x - a[i - 1]);
				a[i] = x - a[i - 1];
			}
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 768
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int count = scanner.nextInt();
			scanner.nextLine();
			int result = 0;
			for (int i = 0; i < count; i++) {
				int number = scanner.nextInt();
				if (0 == i) {
					result = number;
				} else {
					result = getGreatestCommonDivisor(result, number);
				}
			}
			scanner.nextLine();
			System.out.println(result);
		}
	}

	/**
	 * 最大公約数を計算
	 * 
	 * @param x
	 * @param y
	 * @return 最大公約数
	 */
	private static int getGreatestCommonDivisor(int x, int y) {
		int tmp = 0;
		int bigNumber = (x > y) ? x : y;
		int smallNumber = (x > y) ? y : x;
		while (0 != (tmp = bigNumber % smallNumber)) {
			bigNumber = smallNumber;
			smallNumber = tmp;
		}
		return smallNumber;
	}
}


Measured memory_bytes: 49140
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;
	re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0'){
		t=(t<<3)+(t<<1)+v-48;
		v=getchar();
	}
	return t;
}
long long n,m,a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main(){
	n=read();m=read();
	if(n>1&&m>1)
	printf("%lld",(n*m+1)/2);
	else puts("1");
}


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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

LL N, K;
int bb[4010][4010];
int ww[4010][4010];

int bacc[4010][4010];
int wacc[4010][4010];
int bsum(int x1, int y1, int x2, int y2){
  return bacc[y2][x2] - bacc[y2][x1] - bacc[y1][x2] + bacc[y1][x1];
}
int wsum(int x1, int y1, int x2, int y2){
  return wacc[y2][x2] - wacc[y2][x1] - wacc[y1][x2] + wacc[y1][x1];
}

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

  cin >> N >> K;

  int K2 = K * 2;
  REP(i,N){
	int x, y;
	char c;
	cin >> x >> y >> c;
	x %= K2;
	y %= K2;
	if(c == 'B'){
	  bb[y][x]++;
	  bb[y+K2][x]++;
	  bb[y][x+K2]++;
	  bb[y+K2][x+K2]++;
	}
	else{
	  ww[y][x]++;
	  ww[y+K2][x]++;
	  ww[y][x+K2]++;
	  ww[y+K2][x+K2]++;
	}
  }

  REP(y,K2*2) REP(x,K2*2){
	bacc[y+1][x+1] += bb[y][x] + bacc[y+1][x] + bacc[y][x+1] - bacc[y][x];
	wacc[y+1][x+1] += ww[y][x] + wacc[y+1][x] + wacc[y][x+1] - wacc[y][x];
  }

  int ans = 0;
  REP(y1,K2) REP(x1,K2){
	int x2 = x1 + K, y2 = y1 + K;
	int sum = bsum(x1, y1, x2, y2) + bsum(x2, y2, x2+K, y2+K);
	sum += wsum(x2, y1, x2+K, y2) + wsum(x1, y2, x2, y2+K);

	//cout<<x1<<","<<y1<<":"<<sum<<endl;
	maxi(ans, sum);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 254156
N = int(input())
sum = 1
keta = 0

numbers = input().split()
if not ("0" in numbers):
    for num in numbers:
        keta += len(num) - 1
        if keta > 19:
            print(-1)
            exit()
        sum *= int(num)
        if len(str(sum)) > 19:
            print(-1)
            exit()
        
    if len(str(sum)) == 19:
        if str(sum).count("1") == 1 and str(sum).count("0") == 18:
            pass
        else:
            print(-1)
            exit()
else:
    print(0)
    exit()
print(sum)

Measured memory_bytes: 20008
N = int(input())
c = input()
li = list(c)
count = li.count('R')
num = 0

#for i in range(count):
    #if li[i] == 'W':
        #for j in range(len(li)-count):
            #if li[j*(-1)-1] == 'R':
                #li[i] = "R"
                #li[j*(-1)-1] = 'W'
                #num += 1

#for i in range(int(N/2)):
    #if li[i] == 'W' and li[j*(-1)-1] == 'R':
        #li[i] = 'R'
        #li[j*(-1)-1] = 'W'
        #num += 1

#for i in range(count):
    #if li[i] == 'W':
        #li[i] == 

for i in range(count):
    if li[i] == 'W':
        num += 1

print(num)

Measured memory_bytes: 10676
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = (int)1e9;
const double pi = acos(-1.0);
template <class A>ostream & operator<<(ostream & o, const vector<A> & p) { o << "{"; for (int i = 0; i < (int)p.size(); ++i)o << (i > 0 ? ", " : "") << p[i]; o << "}"; return o; }
template <class A, class B>ostream & operator<<(ostream & o, const pair<A, B> & p) { o << "{" << p.first << ", " << p.second << "}"; return o; }
template <class A, class B>ostream& operator<<(ostream & o, const map<A, B> & p) { o << "{"; for (auto it = p.begin(); it != p.end(); ++it) o << (it != p.begin() ? ", " : "") << *it; o << "}"; return o; }
template <class A>ostream & operator<<(ostream & o, const set<A> & p) { o << "{"; for (auto it = p.begin(); it != p.end(); ++it) o << (it != p.begin() ? ", " : "") << *it; o << "}"; return o; }
void print() { cerr << endl; }
template <class H> void print(H && h) { cerr << h << endl; }
template <class H, class... T> void print(H && h, T && ... t) { cerr << h << " "; print(forward<T>(t)...); }

long long Pow(long long a, long long n) {
	long long ans = 1;
	while (n > 0) {
		if (n & 1)ans *= a;
		a *= a; n >>= 1;
	}
	return ans;
}

int main() {
	LL x; cin >> x;
	cout << Pow(2, x + 2) - 2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

int main(int argc, char *argv[]) {
	
	int N,K; cin >> N >> K;
	
	double ans = 0.0;
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		int t = i;
		while(t < K) {
			t *= 2;		
			cnt++;
		}
		ans += (1 / (double)N) * pow(0.5, cnt);
	}
	cout << setprecision(10) << ans << endl;


	return 0;
}


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

using namespace std;

#define FOR(i,a,b) for(int i=a;i<=b;i++)

int main() {
	// your code goes here
	int n,m;
	cin >> n >> m;
	if (n<m) FOR(i,1,m) cout << n;
	else FOR(i,1,n) cout << m;
	return 0;
}

Measured memory_bytes: 256
n, y = tuple(map(int , input().split(" ")))
cnt = 0

for idx in range(n + 1):
    for jdx in range(n + 1 - idx):
        kdx = n - idx - jdx
        if (kdx * 10000 + jdx * 5000 + idx * 1000 == y):
            print(kdx, jdx, idx)
            exit(0)
print('-1 -1 -1')

Measured memory_bytes: 3060
MOD = 1000000007

n = int(input())

cnt = [0 for _ in range(1010)]
for i in range(1, n + 1):
    j = 2
    while j * j <= i:
        while i % j == 0:
            i //= j
            cnt[j] += 1
        j += 1
    
    if i > 1:
        cnt[i] += 1

ans = 1
for x in cnt:
    ans = ans * (x + 1) % MOD

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int p[100];
int main(){
	int n,count=0;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> p[i];
	}
	for(int i=1;i<n-1;i++){
		if(p[i]<p[i-1] && p[i]>=p[i+1]){
			 count++;
			 continue;
		}
		if(p[i]>=p[i-1] && p[i]<p[i+1]){
			 count++;
			 continue;
		}
	}
	cout << count << '\n';
return 0;
}


Measured memory_bytes: 256
import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(0,n-1):
  for j in range(i+1,n):
    x=l[i]+l[j]
    y=bisect.bisect_left(l,x)-1
    ans+=max((y-j),0)
    
print(ans)    
    


Measured memory_bytes: 3188
def main():
    h, w = map(int, input().split())
    if h == 1 or w == 1:
        print(1)
    elif w % 2 == 0 or h % 2 == 0:
        print(h*w//2)
    else:
        print(h*(w//2)+h//2+1)


main()


Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int n,i,ans = 0;cin >> n;int a[n];
  for(i=0;i<n;i++) cin >> a[i];
  for(i=1;i<n;i++){
    if(a[i]==a[i-1]){
      ans++;a[i] = -1;
    }
  }
  cout << ans << endl;
}

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

int main(void){
    int n, k;
    cin >> n >> k;
    
    int input, ans = 0, i;
    for(i = 1; i <= n; i++){
        cin >> input;
        if(input == 1){
            ans = (i - 2) / (k - 1) + 1;
            n -= ans * (k - 1) + 1;
            break;
        }
    }
    
    if(n >= 1){
        ans += (n - 1) / (k - 1) + 1;
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
N = gets.to_i
H = gets.chomp.split(" ").map(&:to_i)

def block_subtraction(f, t)
  mi = H[f..t].min
  (f..t).each{|i| H[i] -= mi}
  ret = mi
  w_f = -1
  (f..t).each{|i|
    w_f = i if w_f == -1 && H[i] > 0
    (ret += block_subtraction(w_f, i-1); w_f = -1) if w_f > -1 && H[i] == 0
  }
  ret += block_subtraction(w_f, t) if w_f > -1
  ret
end

puts block_subtraction(0, N-1)


Measured memory_bytes: 2044
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define INF (1LL << 60)
using namespace std;
typedef long long ll;

ll N, K;
vector<ll> E[2000];

ll dfs(ll v, ll p, ll d) {
  ll ret = 0;
  if(d > K / 2) ret++;
  for(ll u : E[v]) if(u != p) ret += dfs(u, v, d + 1);
  return ret;
}

int main(void) {
  cin >> N >> K;
  REP(i, 0, N - 1) {
    ll A, B; cin >> A >> B; A--; B--;
    E[A].push_back(B);
    E[B].push_back(A);
  }

  ll ans = INF;
  if(K % 2 == 0) {
    REP(i, 0, N) ans = min(ans, dfs(i, -1, 0));
  } else {
    REP(i, 0, N) REP(j, 0, E[i].size()) ans = min(ans, dfs(i, E[i][j], 0) + dfs(E[i][j], i, 0));
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
signed main(void){
	string s;
	int tot=0;
	cin>>s;
	for(int i=0;i<s.size();i++) tot+=int(s[i]-'0');
	if(tot%9==0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3724
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int theta = 90;
		double x = 0;
		double y = 0;
		int a = 0;
		int b = 0;
		while(scan.hasNext()){
			String[] str = scan.nextLine().split(",");
			a = Integer.parseInt(str[0]);
			b = Integer.parseInt(str[1]);
			if(a == 0 && b == 0){
				break;
			}
			x += (double)a * Math.cos((double)theta/180*Math.PI);
			y += (double)a * Math.sin((double)theta/180*Math.PI);
			theta -= b;
		}
		System.out.println((int)x + "\n" + (int)y);
	}
}

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

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  
  double d;
  cin >> d;
  
  double ans = d * sqrt(2.0);
  for (int i = 1; i <= (int)d; i++) {
    double theta = asin(1. * i / d);
    double dx = d * cos(theta);
    if (-1e-10 < dx && dx < 1 - 1e-10) {
      ans = max(ans, i + 1.);
    }
  }
  printf("%.10f\n", ans);

  return 0;
}


Measured memory_bytes: 3492