akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>

int main(){
    int N,K;
    std::cin>>N>>K;
    std::vector<unsigned long long> maxs(N+2),mins(N+2);
    maxs[N+1]=N*((unsigned long long)N+1)/2;
    mins[0]=0;
    for(unsigned long long i=1;i<=N+1;++i){
        mins[i]=(i-1)+mins[i-1];
        maxs[N-i+1]=maxs[N-i+2]-(i-1);
    }

    // for(int i=0;i<=N+1;++i){
    //     std::cout<<maxs[i]<<" ";
    // }
    // std::cout<<std::endl;
    // for(int i=0;i<=N+1;++i){
    //     std::cout<<mins[i]<<" ";
    // }
    // std::cout<<std::endl;
    
    unsigned long long ans=0;
    for(int i=K;i<=N+1;++i){
        // std::cout<<maxs[i]<<" "<<mins[i]<<std::endl;
        ans=(ans+(maxs[i]-mins[i])+1)%1000000007;
    }
    std::cout<<ans<<std::endl;
}

Measured memory_bytes: 6408
N, M = map(int, input().split())
nums = list(map(int, input().split()))

if M <= N:
    ans = 0
elif N == 1:
    ans = max(nums) - min(nums)
else:
    nums.sort()
    diffNums = [nums[i+1] - nums[i] for i in range(M-1)]
    diffNums.sort()
    ans = sum(diffNums[:-(N-1)])

print(ans)

Measured memory_bytes: 13968
#include<iostream>
#include<vector>
using namespace std;
int N;
string S;
void solve()
{
	vector<int> west(N), east(N);
	for(int i = 1; i < N; i++){
		if(S[i-1] == 'E')
			east[i] = east[i-1] + 1;
		else
			east[i] = east[i-1];
	}
	for(int i = N-2; i >= 0; i--){
		if(S[i+1] == 'W')
			west[i] = west[i+1] + 1;
		else
			west[i] = west[i+1];
	}
	int ans = 300000;
	for(int i = 0; i < N; i++){
		ans = min(ans, N-1-west[i]-east[i]);
	}
	cout << ans << endl;
}
int main()
{
	cin >> N >> S;
	solve();
	return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
#define ll long long int
const ll mod=1e9+7;
#define loop(i,a,n) for(i=a;i<n;i++)
#define pool(i,n,a) for(i=n;i>=a;i--)
#define fastinout     ios_base::sync_with_stdio(false); cin.tie(NULL);

using namespace std;

void myfun()
{
	ll n,i,x,k,d,ans;
	cin>>x>>k>>d;
	n=abs(x)/d;
	if(n>k)
	{
	  ans=abs(x)-k*d;	
	}
	else
	{
		  if(x<0)
		  i=x+n*d;
		  else
		  i=x-n*d;
		  if((k-n)%2==0)
		  {
		  	ans=abs(i);
		  }
		  else
		  {
		  	if(i>0)
		  	i=i-d;
		  	else
		  	i=i+d;
		  	
		  	ans=abs(i);
		  }
		  
		 	
		
	}
	cout<<ans;
	
}


int main()
{
	 fastinout;
	ll t=1;
	//cin>>t;
	while(t--)
	myfun();
	return 0;
}

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

int main() {
	vector<int> a(4), b(4);
   
	while(true){
		for( int i=0; i<4; ++i ) cin >> a[i];
		for( int i=0; i<4; ++i ) cin >> b[i];

if(cin.eof()) break;
		
		int hit = 0, blow = 0;
		for( int i=0; i<4; ++i ){
			for( int j=0; j<4; ++j ){
				if( a[i] == b[j] ){
					( i==j ? hit : blow ) += 1;	
				}
			}
		}
		cout << hit << ' ' << blow << endl;
	}
}

Measured memory_bytes: 3084
#include<cstdio>
#include<map>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>

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

using namespace std;

int main(){
	int a[3];cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	cout<<a[0]+a[1]<<endl;
	return 0;
}


Measured memory_bytes: 884
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        String[] ary = br.readLine().split(" ");
        int num = Integer.parseInt(ary[0]);
        int min=num,max=num;
        long sum=num;
        for(int i=1;i<N;i++){
            num=Integer.parseInt(ary[i]);
            if(num<min) min=num;
            if(num>max) max=num;
            sum+=num;
        }
        System.out.println(min+" "+max+" "+sum);
	}
}

Measured memory_bytes: 28664
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
  int n, l; cin >> n >> l;
  string s[n]; for(int i=0; i<n; i++) cin >> s[i];
  sort(s, s+n);
  for(int i=0; i<n; i++) cout << s[i];
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define mp make_pair
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using ll = long long;
using namespace std;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int N;
int main(){
    cin >> N;
    vector<int> a(N);
    rep(i,N) cin >> a[i];
    sort(ALL(a));
    vector<int> alice,bob;
    rep(i,N){
        if(!(i%2)) alice.pb(*(a.end()-1-i));
        else bob.pb(*(a.end()-1-i));
    }
    cout << accumulate(ALL(alice),0) - accumulate(ALL(bob),0) << '\n';
}

Measured memory_bytes: 256
from collections import Counter
n=int(input())
s=[]
for i in range(n):
    s.append(input())
c=Counter(s)

max=max(c.values())

ans=[]
for i,j in c.items():
    if j == max:
        ans.append(i)
ans=sorted(ans)
print('\n'.join(ans))

Measured memory_bytes: 37612
#include <bits/stdc++.h>
#define INF 100000000
using namespace std;
using ll = long long;
using p = pair <int, int>;

int		h, w;
char	given[1000][1000];
int		d[1000][1000];
queue<p> q;
int		vi[] = {-1, 0, 1, 0};
int		vj[] = {0, 1, 0, -1};

bool	check_coordi(p c){
	if (c.first < 0 || c.second < 0)
		return false;
	if (c.first >= h || c.second >= w)
		return false;
	return true;
}

int		main(void){
	cin >> h >> w;
	int		i, j;
	p		s;

	i = 0;
	while (i < h){
		j = 0;
		while (j < w){
			d[i][j] = INF;
			cin >> given[i][j];
			if (given[i][j] == '#'){
				q.push(p(i, j));
				d[i][j] = 0;
			}
			j++;
		}
		i++;
	}
	
	p		now;
	int		v;
	while (!(q.empty())){
		v = 0;
		while (v < 4){
			now.first = q.front().first + vi[v];
			now.second = q.front().second + vj[v];
			if (check_coordi(now)){
				if (d[now.first][now.second] > d[q.front().first][q.front().second] + 1){
					d[now.first][now.second] = d[q.front().first][q.front().second] + 1;
					q.push(now);
				}
			}
			v++;
		}
		q.pop();
	}
	
	int		max = 0;
	i = 0;
	while (i < h){
		j = 0;
		while (j < w){
			if (max < d[i][j])
				max = d[i][j];
			j++;
		}
		i++;
	}
	cout << max << endl;
}


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

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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


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

  int a, b;
  cin >> a >> b;
  cout << max({2*a-1, 2*b-1, a+b});
}


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

int main() {
  string b;
  cin >> b;
  if (b == "A") cout << "T" << endl;
  else if (b == "T") cout << "A" << endl;
  else if (b == "C") cout << "G" << endl;
  else cout << "C" << endl;
  return 0;
}


Measured memory_bytes: 3604
import collections
import fractions
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
if K in A:
    print("POSSIBLE")
    exit()
if max(A)<K or len(A)==1:
    print("IMPOSSIBLE")
    exit()
S=collections.Counter([A[i+1]-A[0] for i in range(N-1)])
gcd=S[0]
for s in S:
    gcd=fractions.gcd(gcd,s)


if K%gcd==A[0]%gcd:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")


Measured memory_bytes: 23852
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int t = sc.nextInt();

		int ans;
		if (n % x == 0) {
			ans = (n / x) * t;
		} else {
			ans = ((n / x) + 1) * t;
		}
		
		System.out.println(ans);

	}
}

Measured memory_bytes: 35656
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <queue>

typedef long long ll;
const ll LL_MAX (1LL<<60);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    ll n;
    cin >>n;
    vector<ll> a(n);
    rep(i,0,n) cin >> a[i];
    ll q;
    cin >> q;
    vector<ll> b(q), e(q), k(q);
    rep(i,0,q) cin >> b[i] >> e[i] >> k[i];

    rep(i,0,q) 
    {
        ll cnt(0);
        rep(j,b[i],e[i])
            if (k[i] == a[j]) cnt++;

        cout << cnt << endl;
    }

    return 0;
}



Measured memory_bytes: 3228
/*
    Zeolim - An AC a day keeps the bug away
*/
  
//#pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
#define pb(x) push_back(x)
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <int, int> pii;
typedef std::vector <int> vi;
void re(ll &x){x=0;char s=getchar();while(s<'0'||s>'9')s=getchar();while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}}
void wr(ll x){if(x>9) wr(x/10);putchar(x%10+'0');}
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 386910137;
const ull P = 13331;
const int MAXN = 1e6 + 100;

ll arr[MAXN] = {0};
ll pre[MAXN] = {0};
ll pow(ll x) { return x * x; }

int main()
{  
    //ios::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    //freopen("d:\out.txt","w",stdout);
    //freopen("d:\in.txt","r",stdin);
    
    ll n, m;
    
    set <int> ST;
    
    for(int i = 1; i < 10; ++i)
    {
    	for(int j = 1; j < 10; ++j)
    	{
    		ST.insert(i * j);
		}
	}
	
	cin >> n;
	
	if(ST.count(n))
		cout << "Yes\n";
	else
		cout << "No\n";
    
    return 0;
}

Measured memory_bytes: 256
# include "stdio.h"
# include "string.h"
int main(){
    int n,l;
    scanf("%d %d",&n,&l);
    char s[n][l+1],tmp[n];

    for(int i=0;i<n;i++){
        scanf("%s",s[i]);
    }

    for(int i=0;i<n-1;i++){
      for(int j=n-1;j>i;j--){
          if(strcmp(s[j-1],s[j])>0){
              strcpy(tmp,s[j]);
              strcpy(s[j],s[j-1]);
              strcpy(s[j-1],tmp);
          }
      }
    }

    for(int i=0;i<n;i++){
        printf("%s",s[i]);
    }
    printf("\n");
}


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

typedef long long LL;

int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    LL n, x;
    cin >> n >> x;
    LL ans = n;
    LL a = x, b = n-x;
    if(a > b) swap(a, b);
    while(a) {
        LL k = b/a;
        ans += 2*k*a;
        b %= a;
        if(b == 0) ans -= a;
        swap(a, b);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let mut result = String::new();
    loop {
        let n: usize = iterator.next().unwrap().parse().unwrap();
        let k: usize = iterator.next().unwrap().parse().unwrap();
        if n == 0 {
            break;
        }
        let a: Vec<i64> = (0..n).map(|_| iterator.next().unwrap().parse().unwrap()).collect();

        let mut s: Vec<i64> = vec![0; n + 1];
        for i in 0..n {
            s[i + 1] = s[i] + a[i];
        }

        let mut ans: i64 = std::i64::MIN;
        for i in 0..(n - k + 1) {
            ans = std::cmp::max(ans, s[i + k] - s[i]);
        }
        result.push_str(&format!("{}\n", ans));
    }
    return result.trim().to_string();
}



Measured memory_bytes: 6976
import numpy as np

A, B = map(int, input().split())

xa_min = 12.5 * A
xa_max = 12.5 * (A+1)
xb_min = 10 * B
xb_max = 10 * (B+1)

x_min = np.ceil(max(xa_min, xb_min))
x_max = np.floor(min(xa_max, xb_max))

if x_min >= x_max:
	print(-1)
else:
	print(int(x_min))




Measured memory_bytes: 13668
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100000000;

struct robot
{
	int x,l,L,R;
};

bool cmp(robot a,robot b)
{
	if(a.L!=b.L)return a.L<b.L;
	return a.x<b.x;
}

int main()
{
	int n;
	cin >> n;
	vector<robot> vec(n);
	rep(i,n)
	{
		int foo,fooo;
		cin >> foo >> fooo;
		vec[i].x=foo;
		vec[i].l=fooo;
		vec[i].L=foo-fooo;
		vec[i].R=foo+fooo;
	}
	int cnt = 1;
	sort(ALL(vec),cmp);
	robot now = vec[0];
	for(int i=1;i<n;i++)
	{

		if(vec[i].R<=now.R)
		{
			
			now = vec[i];
			continue;
		}
		if(now.R<=vec[i].L)
		{
			now=vec[i];
			cnt++;
			continue;
		}

	}
	cout<<cnt<<endl;

	return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using static kyoupuro.Input;
using static kyoupuro.MyMath;

namespace kyoupuro {

    class MainClass {
        
        public static void Main() {
            var N = NextInt();
            var K = NextInt();
            long count = 0;

            for (int mod = K + 1; mod <= N; mod++) {

                // a % b にて a < bの時
                count += mod - K - (K == 0 ? 1 : 0);

                // 上記以外
                if(mod + K <= N) {
                    count += (N / mod - 1) * (mod - K) + Math.Max(0, N % mod - K + 1);
                }
            }

            Console.WriteLine(count);
        }
    }

    class MyMath {
        static long Gcd(long a, long b) {
            return b == 0 ? a : Gcd(b, a % b);
        }
    }

    class Input {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line() {
            return Console.ReadLine();
        }

        public static int NextInt() {
            while (!enumerator.MoveNext()) {
                enumerator = StrArr().AsEnumerable().GetEnumerator();
            }
            return int.Parse(enumerator.Current);
        }

        public static long NextLong() {
            while (!enumerator.MoveNext()) {
                enumerator = StrArr().AsEnumerable().GetEnumerator();
            }
            return long.Parse(enumerator.Current);
        }

        public static string[] StrArr() {
            return Line().Split(' ');
        }

        public static List<int> IntList() {
            return StrArr().Select(int.Parse).ToList();
        }

        public static List<long> LongList() {
            return StrArr().Select(long.Parse).ToList();
        }

        public static void Skip(int line = 1) {
            enumerator.Reset();
            for (int i = 0; i < line; i++) Console.ReadLine();
        }

        public static void Reset() {
            enumerator.Reset();
        }
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n;
	cin>>n;
	ll ans = 0;
	ll cnt = 0;
	while(n%2==0)
	{
		n = n/2;
		cnt++;
	}
	for(ll i=1;i<=cnt;i++)
	{
		cnt-=i;
		ans++;
		if (cnt<0)
			break;
	}

	for(ll i=3;i*i<=n;i+=2)
	{
		ll cnt = 0;
		while(n%i==0)
		{
			n = n/i;
			cnt++;
		}
		for(ll i=1;i<=cnt;i++)
		{
			cnt-=i;
			ans++;
			if (cnt<0)
				break;
		}
	}

	if (n>2)
		ans++;
	cout<<ans;
}

Measured memory_bytes: 3652
import java.util.*

// https://atcoder.jp/contests/dp/tasks/dp_a
fun main(args: Array<String>) {

    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val heights = IntArray(n)
    for(i in 0 until n){
        heights[i] = sc.nextInt()
    }

    val dp = IntArray(n)
    dp[1] = Math.abs(heights[0] - heights[1])
    for(i in 2 until n) {
        dp[i] = Math.min(dp[i-1] + Math.abs(heights[i] - heights[i-1]), dp[i-2] + Math.abs(heights[i] - heights[i-2]))
    }

    println(dp[n-1])


}



Measured memory_bytes: 51876
#define KAKUSUKO
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000;
int N, K;
int h[MAX_N];


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

  cin >> N >> K;
  rep(i, N) cin >> h[i];

  int ans = 0;
  rep(i, N) {
    if (h[i] >= K) ++ans;
  }

  cout << ans << endl;

  return 0;
}


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

int  main()
{
	int s, k; cin >> k >> s;
	int cnt = 0;
	for (int i = 0; i <= k; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if (i + j == s || (s - (i+j) <= k && s -(i+j) >= 0))
				cnt++;
				// cout << i << " " << j << " " << s-(i+j) << endl;
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int A,B,C,D,E,ans;
    cin>>A>>B>>C>>D>>E;
    if(A<=0)ans=(A*-1)*C+D+B*E;
    else ans=(B-A)*E;
    cout<<ans<<endl;
}

Measured memory_bytes: 3084
n = gets.to_i
baggage = gets.split.map(&:to_i)
sorted = baggage.sort
cost = 0
used = [false] * n
n.times do |s|
  next if used[s]
  cur = s
  count = 0
  loop do
    count += 1
    used[cur] = true
    cost += baggage[cur]
    cur = sorted.index(baggage[cur])
    break if used[cur]
  end
  cost += [sorted[cur] * (count - 2), sorted[cur] + sorted[0] * (count + 1)].min
end
p cost

Measured memory_bytes: 8844
#include <stdio.h>

int main (void)

{

int W,H,x,y,r;

scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);

if(x>=r && y>=r && W>=x+r && H>=y+r){

printf("Yes\n");

}

else{

printf("No\n");

}

return 0;

}

Measured memory_bytes: 584
#include<functional>
#include<algorithm>
#include<iterator>
#include<cstring>
#include<cstdio>
using namespace std;
int b[222222];
const int T=262144;
int f[555555];
#define cmin(a,b) ((a)<(b)?:(a)=(b))
#define gmin(a,b) ((a)<(b)?(a):(b))
void C(int l,int x){for(l+=T;l;l>>=1)cmin(f[l],x);}
int Q(int l,int r){int d=233333;for(l+=T-1,r+=T+1;l^r^1;l>>=1,r>>=1)l&1?:cmin(d,f[l^1]),~r&1?:cmin(d,f[r^1]);if(l==0)cmin(d,f[T]);return d;}
struct pii{int l,r;}a[222222];
inline bool operator<(const pii&a,const pii&b){return a.l<b.l?1:a.l==b.l&&a.r<b.r;}
int main()
{
	int n;
	memset(f,0x3f,sizeof(f));
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&b[i]);
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
		scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+q+1);
	C(0,0);
	int j=1,ofs=0;
	for(int i=0;i<n;++i)
	{
		for(;a[j].l==i+1;++j)
			C(a[j].r,Q(i,a[j].r));
		if(b[i+1])
			C(i+1,f[i+T]+1);
		else
		{
			++ofs;
			C(i+1,f[i+T]-1);
		}
	}
	printf("%d",f[n+T]+ofs);
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int n;
  cin>>n;
  double ans = 0;
  while(n--){
    double x; string s;
    cin>>x>>s;
    if(s=="JPY"){
      ans += x;
    }else{
      ans += x * 380000.0;
    }
  }
  printf("%.9f\n",ans);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

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


	string S;
	cin >> S;

	map<char, int> MAP;
	rep(i, S.size()) {
		MAP[S[i]]++;
	}

	int OK = 1;
	for (auto itr : MAP) {
		if (itr.second == 2) OK = 0;
	}

	if (OK) co("yes");
	else co("no");

	Would you please return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << '\n';
#else
	#define DBG(X)
#endif

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::pair;
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;

using int64 = long long int;
using pii   = pair<int, int>;
using pii64 = pair<int64, int64>;

const int NIL = -1;
const int INF = (int)2e9;
const int64 INF64 = (int64)2e18;

void init_IO() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}

int64 get(int64 r) {
	int64 rez = 0;

	while((r & 3) != 3) {
		rez ^= r;
		--r;
	}

	return rez;
}

void solve() {
	int64 l, r;
	cin >> l >> r;

	int64 answ = get(r) ^ (l == 0 ? 0 : get(l - 1));
	cout << answ << '\n';
}

int main() {
	init_IO();
	solve();

	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = int(1e9);
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int n;
    cin >> n;
    double xrmin(INF), xrmax(-INF), xlmin(INF), xlmax(-INF), xudmin(INF), xudmax(-INF);
    double yumin(INF), yumax(-INF), ydmin(INF), ydmax(-INF), ylrmin(INF), ylrmax(-INF);
    for (int i = 0; i < n; ++i) {
        double x, y;
        char d;
        cin >> x >> y >> d;
        if (d == 'R') {
            chmin(xrmin, x);
            chmax(xrmax, x);
            chmin(ylrmin, y);
            chmax(ylrmax, y);
        } else if (d == 'L') {
            chmin(xlmin, x);
            chmax(xlmax, x);
            chmin(ylrmin, y);
            chmax(ylrmax, y);
        } else if (d == 'U') {
            chmin(xudmin, x);
            chmax(xudmax, x);
            chmin(yumin, y);
            chmax(yumax, y);
        } else if (d == 'D') {
            chmin(xudmin, x);
            chmax(xudmax, x);
            chmin(ydmin, y);
            chmax(ydmax, y);
        }
    }
    double ret = ll(INF) * ll(INF);
    for (int i = 0; i <= 4 * 100000000; ++i) {
        double d = 0.5 * i;
        double xmin = min({xrmin + d, xudmin, xlmin - d});
        double xmax = max({xrmax + d, xudmax, xlmax - d});
        double ymin = min({yumin + d, ylrmin, ydmin - d});
        double ymax = max({yumax + d, ylrmax, ydmax - d});
        chmin(ret, (xmax - xmin) * (ymax - ymin));
    }
    cout << fixed << setprecision(10) << ret << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include<math.h>
int main()
{
 long int x,y,z,sum,i=0,k;
 
 scanf("%ld%ld%ld",&x,&y,&z);
 if(abs(x-y)<=abs(x-z))
 {
     printf("A");
 }else{
     printf("B");
 }

    return 0;
}


Measured memory_bytes: 128
n = int(input())
x = [0 for i in range(n)]
y = [0 for i in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

a = {}
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        v = x[j] - x[i], y[j] - y[i]
        if v not in a:
            a[v] = 1
        else:
            a[v] += 1
ans = n
# print("a =", a)
if len(a.values()) > 0:
    ans -= max(a.values())
print(ans)

Measured memory_bytes: 9284
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <time.h>
#include <cstdio>
using namespace std;

long long dp[11][1001];

int main(){
	dp[0][0] = 1;
	for(int i = 0 ; i <= 100 ; i++){
		for(int k = 10 ; k > 0 ; k--){
			for(int j = 1000 ; j >= i ; j--){
				dp[k][j] += dp[k-1][j-i];
			}
		}
	}
	int n,s;
	while(cin >> n >> s && (n||s) ){
		cout << dp[n][s] << endl;
	}
}

Measured memory_bytes: 1236
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast","no-stack-protector","unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx")
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
#define int long long
#define F(i,L,R) for(int i=L;i<R;++i)
#define FE(i,L,R) for(int i=L;i<=R;++i)
#define getI(a) scanf("%lld",&a)
#define getII(a,b) scanf("%lld%lld",&a,&b)
#define getIII(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define VgetI(n) int (n); scanf("%lld",&(n))
#define VgetII(n,m) int (n),(m); scanf("%lld%lld",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%lld%lld%lld",&(n),&(m),&(k))
#define debug(x) cout<<(#x)<<"="<<x<<"\n";
#define qq cout<<"QQ\n";
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
#define INF 2000000000
main(){
	int a,b,c,d;
	while(~getII(a,b)){
		getII(c,d);
		int ans1=a*c,ans2=a*d;
		int ans3=b*c,ans4=b*d;
		int ans=max(ans1,max(ans2,max(ans3,ans4)));
		printf("%lld\n",ans);
	}
}


Measured memory_bytes: 3828
nums = input().split()
x1 = int(nums[0])
y1 = int(nums[1])
x2 = int(nums[2])
y2 = int(nums[3])

X = x2 - x1
Y = y2 - y1

x3 = x2 - Y
y3 = y2 + X

x4 = x3 - X
y4 = y3 - Y

print(x3, y3, x4, y4)

Measured memory_bytes: 3064
S = input()
T = input()

n_s = len(S)
n_t = len(T)
ans = float('inf')
for i in range(n_s-n_t+1):
    tmp = 0
    for j in range(n_t):
        if S[i+j] != T[j]:
            tmp += 1
    ans = min(ans, tmp)
print(ans)

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


int main() {
	
	int n;
	scanf("%d",&n);
	
	vector<int> h(n);
	
	for(int i=0 ; i<n ; i++){
		scanf("%d",&h[i]);
	}
	
	int* dp = new int[n];
	
	for(int i=0 ; i<n ; i++ ){
		dp[i] = INF;
	}
	
	dp[0] = 0;
	dp[1] = abs(h[0]-h[1]);
	
	for(int i=2 ; i<n ; ++i){
		for(int j : {i-1, i-2}){
			dp[i] = min( dp[j] + abs(h[j]-h[i]), dp[i]);
		}
	}
	
	cout<<dp[n-1]<<endl;
	
	return 0;
}

Measured memory_bytes: 4056
#include<iostream>
#include<string>
#include<cstring>
#include<stdio.h>

using namespace std;

int main()
{
   char s[100], p[100], a[100];
   scanf("%s",s);
   scanf("%s",p);
   strcpy(a, s);
   
   int n = strlen(s);
   int m = strlen(p);
   
   int x = 0;
   int y = 0;
   
   for(int i = 0; i < n; i++)
   {
       if(i != 0)
       {
           for(int j = 0; j < n; j++)
           {
                  a[j] = s[j + i];
             
                   if((j + i) >= n)
                   {
                       a[j] = s[j - (n - i)];
                   }
           }
       }
       
       for(int k = 0; k < m; k++)
       {
           if(p[k] == a[k])
           {
               x++;
           }
       }
       
       if(x == m)
        {
            y++; 
        }
        
        x = 0;
   }
   
 
   
   if(y != 0)
   {
       cout << "Yes" << endl;
   }
   else
   {
       cout << "No" << endl;
   }
   
}


Measured memory_bytes: 3260
import java.util.*;

public class Main {
    static int[] d;
    static int k;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        k = sc.nextInt();
        d = new int[k];
        for(int i=0;i<k;i++)d[i]=sc.nextInt();
        for (int i = n; ; i++){
            if(like(i)){
                System.out.println(i);
                break;
            }
        }
    }

    private static boolean like(int n){
        String s = String.valueOf(n);
        for(int i=0;i<k;i++){
            String disnum = String.valueOf(d[i]);
            for(int j=0;j<s.length()-disnum.length()+1;j++){
                if(s.substring(j,j+disnum.length()).equals(disnum)){
                    return false;
                }
            }
        }
        return true;

    }
}


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

int main(){
    int n;
    cin >> n;
    for(int i=1; i<10; i++){
        if(n%i == 0 && n/i < 10){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

Measured memory_bytes: 256
var
 a,b,c,x,i,j,k,s:longint;
begin
 readln(a,b,c,x);
 for i:=0 to a do
  for j:=0 to b do
   for k:=0 to c do
    if 500*i+100*j+50*k=x then inc(s);
 write(s);
end.

Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>

#define MAX_a 100005
 
int isprime[MAX_a];
int add[MAX_a];
 
void eratosthenes(){
 
	int i,j;
 
	for(i=0;i<=MAX_a;i++){
		isprime[i] = 1;
	}
	isprime[0] = isprime[1] = 0;
	for(i=0;i<=sqrt((double)MAX_a)+1;i++){
		if(isprime[i]==1){
			for(j = i + i; j <= MAX_a; j+=i){
				isprime[j] = 0;
			}
		}
	}
}
int main() {

	eratosthenes();

	int i;

	for(i=3;i<=MAX_a;i++){
		if(isprime[i]==1 && isprime[(i+1)/2]==1){
		add[i]+=add[i-1]+1;
		}
		else{add[i]=add[i-1];}
	}

	int Q;

	scanf("%d",&Q);

	for(i=0;i<Q;i++){
	int l,r;
	scanf("%d %d",&l,&r);
	printf("%d\n",add[r]-add[l-1]);
	}


	return 0;
}

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

int main(){
    int x;
    cin >> x;
    int ans = 1;
    for(int i = 2; i*i <= x; i++){
        for(int j = i*i; j <= x; j *= i){
            ans = max(ans, j);
        }
    }
    cout << ans << endl;
    return 0;
}

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

ll solvee(ll * dp,vector<int> arr[], ll n,ll i){
    if(arr[i].size() == 0){
        return 0;
    }

    if(dp[i] != -1){
        return dp[i];
    }

    ll big = INT_MIN;
    for(ll j=0;j<arr[i].size();j++){
        ll yy = solvee(dp,arr,n,arr[i][j]);
        if( yy > big){
            big = yy;
        }
    }
    dp[i] = big + 1;
    return dp[i];
}

ll solve(ll * dp,vector<int> arr[],ll n){
    ll maxx = INT_MIN;
    for(ll i=1;i<=n;i++){
        ll kk = solvee(dp,arr,n,i);
        if(kk > maxx){
            maxx = kk;
        }
    }
    return maxx;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m;
    cin>>n>>m;
    ll dp[n + 1];
    for(ll i=0;i<=n;i++){
        dp[i] = -1;
    }
    vector<int> arr[n + 1];
    
    for(ll i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        arr[x].push_back(y);
    }
    
    cout<<solve(dp,arr,n)<<endl;
    return 0;
}

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

int main() {
	int n, max_num = -1000001, min_num = 1000001, tmp;
	long long int sum = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &tmp);
		sum += tmp;
		max_num = max(max_num, tmp);
		min_num = min(min_num, tmp);
	}
	printf("%d %d %lld\n", min_num, max_num, sum);
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,-1,0,1},dy={1,0,-1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}


vector<string> t{"KIHBR","AKIHBR","KIHABR","AKIHABR","KIHABAR","AKIHABAR","KIHBAR","AKIHBAR","KIHABARA","AKIHABARA","KIHBRA","AKIHBRA","KIHABRA","AKIHABRA","KIHBARA","AKIHBARA"};


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;cin >> s;
	bool ok = false;
	rep(i,t.size()){
		if(s == t.at(i)) ok = true;
	}
	cout << (ok ? "YES" : "NO") << endl;
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

#define MAXKN 100001

// x^n in mod
ll modpow(ll x, ll n, ll mod){
  if(n==0) return 1;

  if(n%2==0){
    return modpow(x*x%mod, n/2, mod) % mod;
  }else{
    return x * modpow(x, (n-1), mod) % mod;
  }
}

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

  ll result = 0;
  vector<ll> counts(1);
  rep1(a, k) counts.push_back( modpow(k/a, n, MOD) );

  rrep1(a, k){
    for(int i=a*2; i<=k; i+=a) counts[a]=(counts[a]-counts[i]+MOD)%MOD;
    result += a*counts[a];
    result %= MOD;
  }

  cout<<result<<endl;

  return 0;
}



Measured memory_bytes: 4260
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

void solve() {
  long N;
  cin >> N;
  long ans = N;
  if (ans % 2) ans *= 2;
  cout << ans << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


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

vector<int> vi;

int main(){
   int n;
   scanf("%d",&n);
   if(n<3){
    printf("0");
   }else{
    for(int i=0;i<n;i++){
        int s;
        scanf("%d",&s);
        vi.push_back(s);
    }
    int cnt=0;
    sort(vi.begin(),vi.end());
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                if(vi[i]+vi[j]>vi[k]&&vi[i]-vi[j]&&vi[j]-vi[k]&&vi[k]-vi[i]){
                    cnt++;
                }
            }
        }
    }
    printf("%d",cnt);
   }


    return 0;
}

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

using ll = long long;
#define mod 1000000007
#define max_index 10000000

ll modpow(ll n,ll m=mod-2){
  ll r=1;
  while(m){
    r=r*((m%2)?n:1)%mod,n=n*n%mod,m>>=1;
  }
  return r;
}

ll fact[max_index];//i! (mod)
ll inv[max_index];//i^(-1) (mod)
ll invfact[max_index];//i!^(-1) (mod)

void calc_fact_invfact(){
  if(fact[0]==0){
    fact[0]=inv[1]=invfact[0]=1;
    for(ll i=2;i<max_index;i++) inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    for(ll i=1;i<max_index;i++) fact[i] = fact[i-1]*i%mod,invfact[i]=invfact[i-1]*inv[i]%mod;
  }
}
ll nCk(int n,int k){
  if(n<k || k<0) return 0;
  else return fact[n]*invfact[k]%mod*invfact[n-k]%mod;
}

int main(){

  ll K;
  cin >> K;
  string s;
  cin >> s;

  ll len = s.length();
  ll ans=0;
  ll now;
  calc_fact_invfact();
  for(ll i=0;i<=K;i++){
    now=modpow(25,i)%mod;
    now=now*nCk(i+(len-1),len-1)%mod;
    now=now*modpow(26,K-i)%mod;
    now=(now+mod)%mod;
    ans=(ans+now+mod)%mod;
  }

  cout << (ans+mod)%mod << endl;
}

Measured memory_bytes: 238608
N = int(input())
a = list(map(int, input().split()))

count = 0
pre = False
for i in range(N-1):
    if a[i] == a[i+1]:
        if not pre:
            count += 1
            pre = True
        else:
            pre = False
    else:
        pre = False
print(count)


Measured memory_bytes: 2940
#include<iomanip>
#include <string>
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
#include<math.h>
#include <ctype.h>
#include <algorithm> // sort
#include <map> // pair
using namespace std;
#define nin(n) int n; cin >> n;
#define kin(k) int k; cin >> k;
int main() {
  nin(n);
  vector<int> vec(n);
  int ans=0;
  for(int i=0;i<n;i++){
    cin >> vec.at(i);
    ans+=vec.at(i)-1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
A, B, C, D = gets.chomp.chars.map(&:to_i)

def dfs(ns, i, n, ret)
  if i == 3
    return n == 7 ? ret : nil
  end
  m = ns[i]
  dfs(ns, i + 1, n + m, ret + "+#{m}") || dfs(ns, i + 1, n - m, ret + "-#{m}")
end

ans = dfs([B, C, D], 0, A, A.to_s) + "=7"
puts ans


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

int main()
{
    int n;
    string t;
    string h;
    int tP;
    int hP;
 
    tP = hP = 0;

    cin >> n;                               // ターン数

    if (n < 1 || n > 1000) return -1;

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

        int cmp = t.compare(h);

        if (cmp > 0) {            // 太郎の勝ち
            tP += 3;
        } else if (cmp < 0) {     // 花子の勝ち
            hP += 3;
        } else {
            tP++;
            hP++;
        }
    }

    cout << tP << " " << hP << endl;

    return 0;
}


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

using namespace std;

class SegmentTree
{
public:
    SegmentTree(int n)
    {
        this->n = n;
        t = new int[(n + 1) * 4];
    }
    void Update(int pos, int val, int v, int tl, int tr)
    {
        if (tl == tr) {
            t[v] = 1 << val;
        } else {  
            int tm = (tl + tr) >> 1;
            if (pos <= tm)
                Update(pos, val, v << 1, tl, tm);
            else
                Update(pos, val, v << 1 | 1, tm + 1, tr);
            t[v] = t[v << 1] | t[v << 1 | 1];
        }
    }
    void Update(int pos, int val)
    {
        Update(pos, val, 1, 1, n);
    }
    int get(int l, int r, int v, int tl, int tr)
    {
        if (l > tr || tl > r) return 0;
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(l, r, v << 1, tl, tm) | get(l, r, v << 1 | 1, tm + 1, tr);
    }
    int get(int l, int r)
    {
        return get(l, r, 1, 1, n);
    }
private:
    int* t, n;
};

int bits(int x)
{
    int ret = 0;
    while (x)
    {
        ret += x & 1;
        x /= 2;
    }
    return ret;
}

int main()
{
    int n, q;
    string s;
    cin >> n >> s >> q;
    s = ' ' + s;
    SegmentTree T(n);
    for (int i = 1; i <= n; i++)
    {
        int c = s[i] - 'a';
        T.Update(i, c);
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int i;
            char ch;
            cin >> i >> ch;
            T.Update(i, ch - 'a');
        }
        if (type == 2)
        {
            int l, r;
            cin >> l >> r;
            int x = T.get(l, r);
            cout << bits(x) << endl;
        }
    }
}

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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = long long;

void solve() {
  vector<vector<int>> c(3, vector<int>(3));
  int ck = 0;
  for (auto& in : c) {
    for (auto& a : in) {
      cin >> a;
      ck += a;
    };
  }
  const int sum = c[0][0] + c[1][1] + c[2][2];
  if (sum * 3 != ck) {
    cout << "No" << endl;
    return;
  }

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (i == j) break;
      int k = i + j;
      if (k == 1)
        k = 2;
      else if (k == 3)
        k = 0;
      else if (k == 2)
        k = 1;

      if (c[i][j] != sum - c[j][i] - c[k][k]) {
        cout << "No" << endl;
        return;
      }
    }
  }
  cout << "Yes" << endl;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);

  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define R register
typedef long long ll;

inline int read() {
	R int x; R bool f; R char c;
	for (f = 0; (c = getchar()) < '0' || c > '9'; f = c == '-');
	for (x = c ^ '0'; (c = getchar()) >= '0' && c <= '9'; x = (x << 1) + (x << 3) + (c ^ '0'));
	return f ? -x : x;
} 

const int MN = 3e5 + 5;

int n, a[MN];

inline void check(int l, int r) {
	R int min = n + 1, max = 0;
	for (R int i = l; i <= r; ++i)
		min = std::min(min, a[i]), max = std::max(max, a[i]);
	if (min != l || max != r) {
		puts("No");
		exit(0);
	}

	min = max = 0;
	for (R int i = l; i <= r; i += 2) 
		if (a[i] > max) max = a[i];
		else if (a[i] > min) min = a[i];
		else {
			puts("No");
			exit(0);
		}
}

int main() {
	n = read();
	for (R int i = 1, x; i <= n; ++i) {
		a[i] = read();
		if ((a[i] ^ i) & 1)
			return 0 * puts("No");
	}

	for (R int i = 1, j; i <= n; i = j + 1) {
		for (j = i; j <= n - 2; j += 2)
			if (a[j + 1] != j + 1 || a[j + 2] == j + 2) break;
		check(i, j);
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 1408
n = gets.to_i
h = {}
for i in 1..9
  for j in 1..9
    h[[i,j]] = 0
  end
end
for k in 1..n
  i = k.to_s[0].to_i
  j = k.to_s[-1].to_i
  h[[i,j]] += 1 if j !=0
end
count = 0
for i in 1..9
  for j in 1..9
    count += h[[i,j]] * h[[j,i]]
  end
end
puts count


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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int h, w, a, b;
    cin >> h >> w >> a >> b;

    if(a > w/2 || b > h/2){
        cout << "No" << endl;
        return 0;
    }

    REP(i, h){
        REP(j, w){
            if((i < b) ^ (j < a)){
                cout << 0;
            }else{
                cout << 1;
            }
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 1280
function main(input) {
  const lines = input.split("\n");
  const N = lines[0]

  let total = 0;
  for (let i = 1; i <= N; i++ {
    if (i % 3 != 0 && i % 5 != 0)
      total += i;
  }

  console.log(total);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 35152
def min(x, y)
	return (x) if x < y
	y
end

s = gets.split(' ')
w, h, n = s[0].to_i, s[1].to_i, s[2].to_i

tx = -1
ty = -1
sum = 0

n.times {
	s = gets.split(' ')
	nx, ny = s[0].to_i, s[1].to_i
	if (tx < 0)
		tx = nx
		ty = ny
	end
	dx = nx - tx
	dy = ny - ty
	
	if (dx * dy >= 0)
		dx = -dx if (dx < 0)
		dy = -dy if (dy < 0)
		m = min(dx, dy)
		sum = sum + dx + dy - m
	else 
		dx = -dx if (dx < 0)
		dy = -dy if (dy < 0)
		sum = sum + dx + dy
	end
	tx = nx
	ty = ny
}

puts sum

Measured memory_bytes: 6108
#include<bits/stdc++.h>
#define   ll  long long int
#define   sz  1000100

using namespace std;




int main()
{

    string s;
    ll i,j,p;

    cin>>s;

    if(s=="AAA" || s=="BBB")cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)

int main() {
    int n;
    cin >> n;
    ll a[n],b[n];
    rep(i,n) cin >> a[i] >> b[i];
    ll ans=0;
    ans += (b[n-1]-a[n-1]%b[n-1])%b[n-1];
    for(int i=n-2;i>=0;i--){
        a[i] += ans;
        ans += (b[i]-a[i]%b[i])%b[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define INF 1000000000
#define mod 1000000007

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
	int n,a,b;
	cin>>n>>a>>b;
	VI P(n);
	REP(i,n)cin>>P[i];
	SORT(P);
	int ans=INF,co=0;
	REP(i,n)
		if(P[i]<=a)co++;
	ans=co;
	co=0;
	REP(i,n){
		if(a<P[i] && P[i]<=b)co++;
	}
	ans=min(ans,co);
	co=0;
	REP(i,n){
		if(b<P[i])co++;
	}
	ans=min(ans,co);
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
using System;

namespace ITP1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            double x1 = double.Parse(input[0]);
            double y1 = double.Parse(input[1]);
            double x2 = double.Parse(input[2]);
            double y2 = double.Parse(input[3]);

            double dis;
            dis = Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
            Console.WriteLine(dis.ToString("f4"));
        }
    }
}

Measured memory_bytes: 9228
#include <stdio.h>

void dfs(int disit);
int abs(int a);

int n=0,count=0,a=0,b=0;
int P[10]={},Q[10]={},flag[10]={},array[10]={};

int main(void)
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&P[i]);
    for(int i=0;i<n;i++) scanf("%d",&Q[i]);
    dfs(0);
    printf("%d",abs(a-b));
    return 0;
}

void dfs(int disit){
    int flaga=1,flagb=1;
    if(disit==n){
        // for(int s=0;s<n;s++) printf("%d",array[s]);
        // printf("\n");
        count+=1;
        for(int j=0;j<n;j++){
            if(P[j]!=array[j]) flaga=0;
            if(Q[j]!=array[j]) flagb=0;
        }
        if(flaga==1) a=count;
        if(flagb==1) b=count;
    } else {
        for(int i=1;i<=n;i++){
            if(flag[i]==0){
                flag[i]=1;
                array[disit]=i;
                dfs(disit+1);
                flag[i]=0;
            }
        }
    }
}

int abs(int a){
    if(a<0) a=(-1)*a;
    return 0;
}


Measured memory_bytes: 1736
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int i,j,n,a,b,c,d,no,he;
	cin>>n;
	for(i=0;i<n;i++) {
		cin>>a>>b>>c>>d;
		no=a*c+b*d;
		he=(a*c+b*d)*0.8;
		if(c<=5&&d<=2) he=(a*5+b*2)*0.8;
		else if(c<=5) he=(a*5+b*d)*0.8;
		else if(d<=2) he=(a*c+b*2)*0.8;
		if(he>no) cout<<no<<endl;
		else cout<<he<<endl;
	}
}	

Measured memory_bytes: 3064