akhauriyash/Code-Regression huggingface dataset:
/* Great things never come from comfort zones,
"whatever the mind of a man can conceive and believe,it can achieve." */
 
#include <bits/stdc++.h>
#define ll long long
#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define pb push_back
#define pf push_front
#define mp make_pair
#define F first
#define S second
#define all(x)     x.begin(),x.end()
#define tc   int tt; scf(tt); while(tt--)
#define inf INT_MAX
#define ninf INT_MIN
#define gcd __gcd
#define bitcount(n) __builtin_popcount(n)
typedef double dd;
using namespace std;
const ll M =1e9+7;
const int N = 2e5+7;

set<int>s[N];

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

int sum[N]={0};

bool vis[N]={0};

void dfs(int x)
{
    vis[x]=1;
    sum[x]=1;
        
	for(auto it:s[x])   
    {
        if(!vis[it])
        {dfs(it);
        
    sum[x]+=sum[it];
    }   
        
    }
}



int main()
{
   
    int n,m;
    scf(n),scf(m);
    

    rep(i,0,m)
    {
        int a,b;
        scf(a),scf(b);
        
        s[a].insert(b),s[b].insert(a);

    }
    
    int l=0,id=0;
    

    
    rep(i,1,n+1)
    {
        if(vis[i]==0)
        dfs(i);
    }
    
    rep(i,1,n+1)
    l=max(sum[i],l);
    
    if(m==0)
    prin(1);
    
    else
    prin(l);
    
    
 

     
}

Measured memory_bytes: 45244
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s;
		while((s=br.readLine())!=null)
		{
			String binary = Integer.toBinaryString(Integer.parseInt(s));	

			int n = binary.length();
			for(int i=n-1;i>0;i--){
				if(binary.charAt(i)=='0') continue;
				System.out.print((int)Math.pow(2, n-i-1)+" ");
			} 
			char last = binary.charAt(0);
			System.out.print(Integer.parseInt(last+"")*(int)Math.pow(2,n-1));
			System.out.println();
		}
	}
}

Measured memory_bytes: 9376
n = int(input())
a = list(map(int, input().split()))
ma = max(a)
dp = [0]*(ma+1)

for i in sorted(a):
  if 1 <= dp[i]:
    dp[i] += 1
    continue

  for j in range(1, ma//i + 1):
    dp[j * i] += 1

ans=0
for i in a:
  if dp[i] == 1:
    ans += 1
print(ans)

Measured memory_bytes: 132836
#include <stdio.h>
  
int main() {
int i, tmp, max;
int count[101] = {0};
while( scanf("%d",&tmp) != EOF ) {
count[tmp]++;
}
  
max = 0;
for(i = 1; i < 101; i++ ) {
if(max < count[i]) {
max = count[i];
}
}
for(i = 1; i < 101; i++ ) {
if(count[i] == max ) {
printf("%d\n",i) ;
}
}
return 0;
}

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

int main() {
  long x,y,ans,c,m,mod=1000000007;
  cin >> x >> y;
  if ((x+y)%3==0&&min(x,y)*2>=max(x,y)) {
    ans=1;
    for(int i=0;i<min(x,y)-(x+y)/3;i++) {
      ans=ans*((x+y)/3-i)%mod;
      m=i+1;
      c=1;
      for(long j=1;j<=(mod-2);j=j*2) {
        if((mod-2)/j%2==1) c=c*m%mod;
        m=m*m%mod;
      };
      ans=ans*c%mod;
    };
  } else {
    ans=0;
  };
  cout << ans << endl;
}

Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)















 
int main(){
    ll n;
    cin >> n;
    vector<ll> a(n), b(n);
    REP(i, n){
        cin >> a[i];
    }
    REP(i, n){
        cin >> b[i];
    }
    
    vector<pair<ll, ll>> v(n);
    REP(i, n){
        v[i] = {a[i], b[i]};
    }
    sort(v.begin(), v.end(), [](pair<ll, ll> a, pair<ll, ll> b){
        return a.second < b.second;
    });
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    REP(i, n){
        if(a[i] > b[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    
    set<pair<ll, ll>> st;
    REP(i, n){
        st.insert({v[i].first, i});
    }
    
    ll cnt = 0;
    REP(i, n){
        if(v[i].first > v[i].second){
            auto itr = --st.lower_bound({v[i].second + 1, 0});
            ll aa = itr->first, idx = itr->second;
            st.erase(itr);
            st.insert({v[i].first, idx});
            swap(v[i].first, v[idx].first);
            cnt++;
        }
        else{
            st.erase({v[i].first, i});
        }
    }
    if(cnt <= n - 2){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 9600
#include <iostream>
#include <iomanip>

#include <cmath>

using namespace std;



int main(){
    cout << setprecision(20) << fixed;
    
    long double r;
    cin >> r;

    cout << r * r * M_PI << " " << 2 * r * M_PI << "\n";

    return 0;
}



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

int main() {
	int N, K, X, Y;
	cin >> N >> K >> X >> Y;

	int result = 0;

	if( N > K ) {
		result = X*K + Y*(N-K);
	}
	else {
		result = X*N;
	}

	cout << result << endl;
}


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

using namespace std;

typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++)
  {
  cin>>a[i];
  }
  bool dp[k+1];
  dp[0]=false;
  for(int i=1;i<a[0];i++)
  {
  dp[i]=false;
  }
  dp[a[0]]=true;
  for(int i=a[0]+1;i<=k;i++)
  {
  dp[i]=false;
  for(int j=0;j<n;j++)
  {
  if(i>=a[j])
  {
  if(dp[i-a[j]]==false) dp[i]=true;
  }
  }
  }
  if(dp[k]) cout<<"First";
  else cout<<"Second";
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int64_t a, b;
    int64_t c, d;
    cin>>a>>b>>c>>d;
    int64_t lcm = c * d / __gcd(c , d);
    //cout<<lcm<<endl;
    int64_t x = b/c - (a-1)/c;
    //cout<<x<<endl;
    int64_t y = b/d - (a-1)/d;
    //cout<<y<<endl;
    int64_t z = b/lcm - (a-1)/lcm;
    //cout<<z<<endl;
    int64_t ans = b - (a-1) - x - y + z;
    cout<<ans<<endl;
    return 0;
}


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

using namespace std;

using ll = long long;

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

    std::vector<ll> H(N);
    std::for_each(H.begin(), H.end(), [](auto &x) { cin >> x; });

    for (ll i = 1; i < N; ++i) {
        if (H[i - 1] < H[i]) {
            --H[i];
        } else if (H[i - 1] == H[i]) {
        } else {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 1024
N = int(input())
LR = [list(map(int,input().split())) for _ in range(N)]

LR.sort(key=lambda x:[-x[0],x[1]])
ML = LR[0][0]
MR = LR[0][1]
LR.sort(key=lambda x:[x[1],-x[0]])
mR = LR[0][1]
mL = LR[0][0]

ans = max(mR-ML+1,0)
for i in range(N):
    if LR[i] not in [[ML,MR],[mL,mR]]:
        ans = max(ans,max(mR-ML+1,0)+max(LR[i][1]-LR[i][0]+1,0))

LR.sort(key=lambda x:[x[1],x[0]])

L_ = [0]*N
for i in range(N):
    L_[i] = max(LR[i][0],L_[i-1])

for i in range(1,N):
    ans = max(ans,max(LR[i][1]-ML+1,0)+max(mR-L_[i-1]+1,0))

print(ans)

Measured memory_bytes: 94808
Scanf.scanf "%d %d %d" (fun n m q ->
    let mat = Array.make_matrix n n 0 in
    for i = 1 to m do
        Scanf.scanf " %d %d" (fun l r ->
            mat.(l - 1).(r - 1) <- mat.(l - 1).(r - 1) + 1;
        )
    done;
    for y = n - 2 downto 0 do
        for x = 0 to n - 1 do
            mat.(y).(x) <- mat.(y).(x) + mat.(y + 1).(x)
        done
    done;
    for y = 0 to n - 1 do
        for x = 1 to n - 1 do
            mat.(y).(x) <- mat.(y).(x) + mat.(y).(x - 1)
        done
    done;
    for i = 1 to q do
        Scanf.scanf " %d %d" (fun p1 q1 ->
            Printf.printf "%d\n" @@ mat.(p1 - 1).(q1 - 1)
        )
    done
)

Measured memory_bytes: 7992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vector<T>>;
using vl = vector<ll>;

const ll MOD = 1e9 + 7;
const ll INF = 1e14;
const ld EPS = 1e-11;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (int i = (l); i < (r); i++)
#define reper(i, l, r) for (int i = (r)-1; i >= (l); i--)

void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
}
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll N, M;
    cin >> N >> M;
    if (N == M)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

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

int main() {
    string a, s, c;
    string ans;
    cin >> a >> s >> c;
    ans += a.at(0);
    ans += s.at(0);
    ans += c.at(0);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX_V 100050
#define MAX_LOG_V 50
vector<int> G[MAX_V];
int root=0;
int parent[MAX_LOG_V][MAX_V];
int depth[MAX_V];

void dfs(int v,int p,int d){
  parent[0][v]=p;
  depth[v]=d;
  for(int i=0;i<G[v].size();i++){
    if(G[v][i]!=p) dfs(G[v][i],v,d+1);
  }
}

void init(int V){
  dfs(root,-1,0);
  for(int k=0;k+1<MAX_LOG_V;k++){
    for(int v=0;v<V;v++){
      if(parent[k][v]<0) parent[k+1][v]=-1;
      else parent[k+1][v]=parent[k][parent[k][v]];
    }
  }
}

int lca(int u,int v){
  if(depth[u]>depth[v]) swap(u,v);
  for(int k=0;k<MAX_LOG_V;k++){
    if((depth[v]-depth[u])>>k&1){
      v=parent[k][v];
    }
  }
  if(u==v) return u;
  for(int k=MAX_LOG_V-1;k>=0;k--){
    if(parent[k][u]!=parent[k][v]){
      u=parent[k][u];
      v=parent[k][v];
    }
  }
  return parent[0][u];
}


signed main(){
  int n,i,j,k=0;cin>>n;
  for(i=1;i<n;i++){
    cin>>j;j--;
    G[j].push_back(i);
    G[i].push_back(j);
  }
  init(n);
  bool used[n];
  memset(used,0,sizeof(used));
  queue<int> q;
  vector<int> v;
  q.push(0);
  while(!q.empty()){
    j=q.front();q.pop();
    if(used[j]) continue;
    used[j]=1;v.push_back(j);
    for(i=0;i<G[j].size();i++) q.push(G[j][i]);
  }
  for(i=0;i<v.size()-1;i++) k+=depth[v[i]]+depth[v[i+1]]-depth[lca(v[i],v[i+1])]*2;
  cout << k << endl;
  return 0;
}

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

int main() {
	ll n, m, k;
	cin >> n >> m >>k;
	vector<ll> a(1,0);
	vector<ll> b(1,0);
	int as, bs;
	for (int i = 1; i < n+1; i++){
		cin >> as;
		a.push_back(as);
		a[i] = a[i] + a[i-1];
	}
	for (int i = 1; i < m+1; i++){
		cin >> bs;
		b.push_back(bs);
		b[i] = b[i] + b[i-1];
	}

	int tot = 0;
	int bnum = m;
	for (int i = 0; i < n+1; i++){
		if(a[i] > k) break;
		while (b[bnum] > k - a[i]) bnum--;
		tot = max(tot, i + bnum);
	}
	cout << tot;



}
			



Measured memory_bytes: 7968
using System;
using System.Numerics;
class Program
{
	static void Main(string[] args)
	{
		// スペース区切りの整数の入力
		string[] input = Console.ReadLine().Split(' ');
		long N = int.Parse(input[0]);
		long M = int.Parse(input[1]);
        long LARGE = (long)Math.Pow(10, 9)+7;
        long res = 1;
        if (N==1){
            //出力
		    Console.WriteLine(res);
        } else {
            long L6 = (long)Math.Pow(10, 6);
            long L5 = (long)Math.Pow(10, 5);
            long[] NCRS = new long[L6];
            NCRS[0] = 1;
            for (int i=1; i<L6; i++){
                NCRS[i] = (NCRS[i-1]*(N-1+i)%LARGE)*ModPow(i, LARGE-2, LARGE)%LARGE;
            }

            for (int p=2; p<L5; p++){
                int q = 0;
                while (M % p == 0){
                    M = M / p;
                    q++;
                }
                if (q > 0){
                    res = res * NCRS[q] % LARGE;
                }
            }
            if (M > 1){
                res = res * NCRS[1] % LARGE;
            }

            //出力
            Console.WriteLine(res);
        }

	}
    // modular inverse
    public static long ModPow(long a, long b, long p)
    {
        if (b == 0) return 1;
        if (b % 2 == 0)
        {
            long d = ModPow(a, b / 2, p);
            return d * d % p;
        }
        else
        {
            return a * ModPow(a, b - 1, p) % p;
        }
    }
}

Measured memory_bytes: 18656
n = gets.to_i
a = gets.split.map(&:to_i)
sum = 0;
(n).times do |i|
    sum += a[i]
end
half = 0
rec = 0
(n).times do |i|
    half += a[i]
    rec = i
    break if half >= sum/2
end
if half >= sum - half
    ans = [half-(sum-half), (sum-half)+a[rec]-(half-a[rec])].min
else
    ans = [(sum-half)-half, half+a[rec+1]-(sum-half-a[rec+1])].min
end
puts ans


Measured memory_bytes: 16140
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;
int main(){
    int N,M;
    cin>>N>>M;
    vector<int>cnt(M,0);
    for(int i=0;i<N;i++){
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            --a;
            ++cnt[a];
        }
    }
    int ans=0;
    for(int i=0;i<M;i++){
        if(cnt[i]==N){
            ans++;
        }
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 256
import java.util.*;

fun Eratos(n:Int):List<Int>{
    var h=BooleanArray(n,{true})
    h[0]=false
    h[1]=false
    for(i in h.indices){
        if(h[i]==true){
            var j=i+i
            while(j<n){
                h[j]=false
                j+=i
            }
        }
    }
    return h.indices.filter{i->h[i]==true}
}

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val K = sc.nextInt()
    val S=sc.nextInt()
    
    var ans=0
    
    for(x in 0..K){
        for(y in 0..K){
            val z=S-(x+y)
            if(z<0||z>K){
                continue
            }
            
            ans++;
        }
    }
    
    print(ans);
}

Measured memory_bytes: 31404
a[9][9][11],b,f,r,v,n;
main(){for(scanf("%d",&n);n--;scanf("%d%d%d%d",&b,&f,&r,&v),a[b][f][r]+=v);for(b=0;b++<4;b>3?:puts("####################"))for(f=0;f++<3;puts(""))for(r=0;r++<10;printf(" %d",a[b][f][r]));exit(0);}

Measured memory_bytes: 612
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int dig(int here, int N, int *map, int *been, int *connection) {
	int i;
	connection[here] = 1;
	been[here] = 1;
	for(i = 0; i < N; i += 1) {
		if(been[i] == 1) {
			continue;
		}
		if(map[here + i * N] == 1) {
			dig(i, N, map, been, connection);
		}
	}
	been[here] = 0;
	return 0;
}

int is_bridge(int N, int M, int *map, int *been, int *connection, int *a, int *b, int burn) {
	int i, j;
	//burn burn-th bond and check connection from vertex 0 to others
	map[a[burn] + N * b[burn]] = 0;
	map[b[burn] + N * a[burn]] = 0;
	for(i = 0; i < N; i += 1) {
		connection[i] = 0;
		been[i] = 0;
	}
	dig(0, N, map, been, connection);
	j = 0;
	for(i = 0; i < N; i += 1) {
		j += connection[i];
	}
	map[a[burn] + N * b[burn]] = 1;
	map[b[burn] + N * a[burn]] = 1;
	if(j != N) {
		return 1;
	} else {
		return 0;
	}
}

int main(void) {
	int test = 0;
	int i;
	int N, M;
	int *a, *b;
	int *map, *been;
	int *connection;
	int bridges;
	int burn;
	char buf[128], *ch;
	FILE *file;
	if(test == 1) {
		file = fopen("input.txt", "r");
	}

	if(test == 1) {
		fgets(buf, sizeof(buf), file);
	} else {
		fgets(buf, sizeof(buf), stdin);
	}
	ch = strtok(buf, " ");
	N = atoi(ch);
	ch = strtok(NULL, " ");
	M = atoi(ch);

	connection = (int *)calloc(N, sizeof(int));
	map = (int *)calloc(N * N, sizeof(int));
	been = (int *)calloc(N, sizeof(int));
	a = (int *)calloc(M, sizeof(int));
	b = (int *)calloc(M, sizeof(int));
	for(i = 0; i < N * N; i += 1) {
		map[i] = 0;
	}
	
	for(i = 0; i < M; i += 1) {
		if(test == 1) {
			fgets(buf, sizeof(buf), file);
		} else {
			fgets(buf, sizeof(buf), stdin);
		}
		ch = strtok(buf, " ");
		a[i] = atoi(ch);
		a[i] -= 1;
		ch = strtok(NULL, " ");
		b[i] = atoi(ch);
		b[i] -= 1;

		map[a[i] + b[i] * N] = 1;
		map[b[i] + a[i] * N] = 1;
	}

	bridges = 0;
	for(i = 0; i < M; i += 1) {
		bridges += is_bridge(N, M, map, been, connection, a, b, i);
	}
	printf("%d\n", bridges);

	free(connection);
	free(map);
	free(been);
	free(a);
	free(b);
	if(test == 1) {
		fclose(file);
	}
	return 0;
}


Measured memory_bytes: 2116
import java.util.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int ans = 0;
    for (int i = 1; i <= N; i++) {
      if (String.valueOf(i).length() % 2 == 1) {
        ans++;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 27604
N, M = map(int, input().split())

V = [[] for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
    
Log = [0]*N

def DFS(now_V, now_Log, ans):
    #print(now_V, now_Log, ans, sum(now_Log))
    
    if sum(now_Log)==N:
        ans = ans+1
        #print('cc')
        return ans
    
    for i in V[now_V]:
        if now_Log[i]<1:
            now_Log[i]=1
            ans = DFS(i, now_Log, ans)
            now_Log[i]=0
    
    return ans
          

count = 0  

Log[0] = 1

print(DFS(0, Log, count))

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

typedef struct {
	int x, idx;
} Rec;

int compare(const void *a, const void *b) {
	return ((const Rec *)a)->x - ((const Rec *)b)->x;
}

Rec rec[200000];
int order[200000];

int main(void) {
	int n;

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &rec[i].x);
		rec[i].idx = i;
	}

	qsort(rec, n, sizeof(Rec), &compare);

	for (int i = 0; i < n; i++)
		order[rec[i].idx] = i;

	for (int i = 0; i < n; i++)
		printf("%d\n", rec[order[i] < n / 2 ? n / 2 : n / 2 - 1].x);

	return 0;
}


Measured memory_bytes: 4448
/* Any person standing on mountain was not fallen there. 
               Author: Maskman_lucifer                   */
               
#include <bits/stdc++.h>   
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long 
#define pll pair<ll,ll>
#define pb push_back
#define M 1000000007
#define lc '\n'
using namespace std;
struct aman 
{
    ll l;
    ll r;
    ll ind;
};
aman b[600000];
bool comp(aman &p1,aman &p2)
{
    return p1.r<p2.r;
}
const int N=600000;
int bit[N];
ll last[600000];
int pres(int idx)
{
	int ans=0;
	while(idx>0)
	{
		ans=ans+bit[idx];
		
		idx=idx-(idx&-idx);
	}
	return ans;
}


void update(int idx,int  val,int n)
{
	while(idx<=n)
	{
		bit[idx]=bit[idx]+val;
		idx=idx+(idx&-idx);
	}
}

int rsm(int l, int r)
{
	return pres(r) - pres(l-1);
}

int main()
{
    IO
    ll n,q;
    cin>>n>>q;
    memset(last,-1,sizeof(last));
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    ll ans[q];
    for(ll i=0;i<q;i++)
    {
        cin>>b[i].l>>b[i].r;
        b[i].ind=i;
    }
    sort(b,b+q,comp);
    ll p=0;
    for(ll i=0;i<n;i++)
    {
        if(last[a[i]]!=-1)
        {
            update(last[a[i]]+1,-1,n);
        }
        last[a[i]]=i;
        update(i+1,1,n);
        while(p<q and b[p].r==i+1)
        {
            ans[b[p].ind]=rsm(b[p].l,b[p].r);
            p++;
        }
    }
    for(ll i=0;i<q;i++)
    {
        cout<<ans[i]<<lc;
    }
    return 0;
}

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

int main() {
  int64_t L, R;
  cin >> L >> R;
  if(L == 0) {
    cout << 0 << endl;
    return 0;
  }
  else if(R - L == 1) {
    cout << R * L % 2019 << endl;
    return 0;
  }
  else if(R / 673 != L / 673) {
    cout << 0 << endl;
    return 0;  
  }
  else {
    int64_t ans = L * (L + 1) % 2019;
    for(int64_t i = L; i < R; i++) {
      for(int64_t j = i + 1; j <= R; j++) {
        int64_t keep = i * j % 2019;
        if(keep < ans) {
          ans = keep;
        }
      }
    }
    cout << ans << endl;
  }
}

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

int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if(A+B > C+D){
    cout << "Left" << endl;
  }
  else if(A+B == C+D){
    cout << "Balanced" << endl;
  }
  else{
    cout << "Right" << endl;
  }
}

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

const ll INF = 1LL << 50;
ll land[200][200];
ll sea[200][200];
ll dp[1010][200];
int z[1000];

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

	int N, M, R;
	while(cin >> N >> M, N) {
		fill((ll*)begin(land), (ll*)end(land), INF);
		fill((ll*)begin(sea), (ll*)end(sea), INF);
		for(int i = 0; i < N; i++) {
			land[i][i] = sea[i][i] = 0;
		}

		for(int i = 0; i < M; i++) {
			int x, y;
			ll t;
			char sl;
			cin >> x >> y >> t >> sl;
			x--, y--;
			if(sl == 'L') {
				t = min(t, land[x][y]);
				land[x][y] = land[y][x] = t;
			}
			else{
				t = min(t, sea[x][y]);
				sea[x][y] = sea[y][x] = t;
			}
		}

		for(int k = 0; k < N; k++) {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					land[i][j] = min(land[i][j], land[i][k] + land[k][j]);
					sea[i][j] = min(sea[i][j], sea[i][k] + sea[k][j]);
				}
			}
		}

		cin >> R;
		for(int i = 0; i < R; i++) {
			cin >> z[i];
			z[i]--;
		}

		fill((ll*)begin(dp), (ll*)end(dp), INF);
		dp[0][z[0]] = 0;
		for(int i = 0; i < R - 1; i++) {
			for(int j = 0; j < N; j++) {
				if(dp[i][j] == INF) continue;
				int A = z[i], B = z[i + 1];

				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + land[A][B]);

				for(int u = 0; u < N; u++) {
					ll cost = land[A][j] + sea[j][u] + land[u][B];
					if(cost < INF) {
						dp[i + 1][u] = min(dp[i + 1][u], dp[i][j] + cost);
					}
				}
			}
		}

		ll ans = INF;
		for(int j = 0; j < N; j++) {
			ans = min(ans, dp[R - 1][j]);
		}
		cout << ans << endl;
	}
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  
  ll n, m;
  cin >> n >> m;
  vector<ll> a(n); rep(i, 0, n) cin >> a[i];
  sort(all(a));
  vector<pair<ll, ll> > cb(m);
  rep(i, 0, m) cin >> cb[i].second >> cb[i].first;
  sort(allr(cb));

  ll i = 0;
  rep(j, 0, n) {
    ll b = cb[i].second;
    ll c = cb[i].first;
    
    if(j+b-1 > n-1) {
      rep(k, j, n) {
        if(a[k] < c) a[k] = c;
        else break;
      }
      break;
    }
    else if(a[j+b-1] >= c) {
      rep(k, j, j+b) {
        if(a[k] < c) a[k] = c;
        else break;
      }
      break;
    }
    else {
      rep(k, j, j+b) a[k] = c;
      j += b-1;
      i++; 
    }
    if(i > m-1) break;
  }
    
  ll sum = 0;
  rep(i, 0, n) sum += a[i];
  cout << sum << "\n";
}

Measured memory_bytes: 2560
n, m = map(int, input().split())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l.append((a, b))

l = sorted(l)


r = 0
for i in l:
    if i[1] < m:
        r += i[0]*i[1]
        m -= i[1]
    else:
        r += i[0]*(m)
        break
print(r)


Measured memory_bytes: 17788
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
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; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;

signed main(){
	//cout << fixed << setprecision(10);
	while(1){
		string s; cin>>s;
		if(s=="0")return 0;
		ll ans=0;
		rep(i,0,s.size()){
			ans+=(s[i]-'0');
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
#define N 100005
#define P 1000000007
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
int n,k;
vector<int>G[N];
long long ans=0;
void dfs(int x,int fa,int t){
	int flag=0;
	for(int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if(y==fa)continue;
		ans=(ans*(k-t-flag))%P;
		flag++;
		dfs(y,x,t==2?2:t+1);
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	ans=k;
	dfs(1,0,1);
	cout<<ans;
	return 0;
}


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

using namespace std;

map<int,int> cnt[3];
int n,res=0,sz=0,a[maxn];
vector<pair<int,int> > ma[3];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    bool ck=true;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        cnt[i%2][a[i]]++;
        ck &= (i==1||a[i]==a[i-1]);
    }
    int mx=-1;
    for (int type=0;type<2;type++) {
        for (auto &p1 : cnt[type]) ma[type].push_back(make_pair(-p1.second,p1.first));
        sort(ma[type].begin(),ma[type].end());
    }
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++)
            if (i<ma[0].size() && j<ma[1].size()
                && ma[0][i].second != ma[1][j].second) mx = max(mx,-ma[0][i].first - ma[1][j].first);
    if (mx==-1) cout<<n/2;
    else cout<<n-mx;
}


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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

int f(int N) {
  int res = 1;
  while(res * (res + 1) / 2 < N) {
    ++res;
  }
  return res;
}

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

  vector<int> res;
  while(N) {
    int tmp = f(N);
    res.push_back(tmp);
    N -= tmp;
  }
  for(int e: res) {
    cout << e << endl;
  }

  return 0;
}



Measured memory_bytes: 384
from collections import deque
d=deque(input())
q=int(input())
ans=1
for i in range(q):
    a=input()
    if int(a[0])==1:
        ans=ans*(-1)
    else:
        if ans==1:
            if int(a[2])==1:
                d.appendleft(a[4])
            else:
                d.append(a[4])
        else:
            if int(a[2])==1:
                d.append(a[4])
            else:
                d.appendleft(a[4])
if ans==1:
    for i in range(len(d)):
        print(d[i],end="")
else:
    d.reverse()
    for i in range(len(d)):
        print(d[i],end="")
        

Measured memory_bytes: 11768
N = int(input())
ans = 0
l0 = 0
l1 = 0
if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    for i in range(N+1):
        if i == 0:
            ans = 2
        elif i == 1:
            ans = 1
            l0=2
            l1=1
        else:
            ans = l1 + l0
            l0 = l1
            l1 = ans
    print(ans)

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

int main()
{
    int n, m, sum=0;
    double b;
    cin >> n >> m;
    int a[n];
    rep(i, n) cin >> a[i];

    rep(i, n) sum += a[i];
    b = sum * (1.0/(4.0*m));
    sort(a, a + n, greater<int>());

    for (int i = 0; i < m; ++i)
    {
        if (a[i] < b)
        {
            cout << "No" << endl;
            return 0;
        }
    }

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

Measured memory_bytes: 256
/*Flamenco Sketches*/
#include<bits/stdc++.h>
using namespace std;
 
#define NL '\n'
#define xx first
#define yy second
#define ll long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define sz(x) x.size()
#define all(x) (x).begin(), (x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define async() ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 
//#define FayeValentine 
void dbg(){cerr<<NL;}template<typename H,typename... T> void dbg(H h,T... t){cerr<<' '<<h;dbg(t... );}
#ifdef  FayeValentine
#define debug(...) cerr<<"("<<#__VA_ARGS__<<"):",dbg(__VA_ARGS__)
#else
#define debug(...) 
#endif


void absinthe() {
	int n, m, g = 1; cin >> n >> m;
	for(int d = 1; d*d <= m; d++) {
		if(m%d==0) {
			if(m/d >= n) g = max(d, g);
			if(d >= n) g = max(m/d, g);

		}
	} 
	cout << g << NL;
}
 
 
int main(){
  //freopen("input.txt", "r", stdin);
  async();
  int __t = 1; //cin >> __t;
  for(int __c = 1; __c <=__t; __c++) {
    //cout << "Case #" << __c << ": "; 
    absinthe();
  }
}  

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

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

    int W, A, B;
    cin >> W >> A >> B;

    int a = min(A, B), b = max(A, B);

    if (b < a+W) {
        cout << 0 << endl;
    } else {
        cout << b-(a+W) << endl;
    }
    return 0;
}

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

using namespace std;
#define loop(i,a,b) for(int i=a; i<int(b); i++)
#define rep(i,a) loop(i,0,a)

bool chk(string &s){
    bool l=true, r=true;
    char last='a';
    rep(i,s.size()){
        if(s[i]==last)return false;
        last = s[i];
        if((i%2==0 && s[i]=='R') || (i%2!=0 && s[i]=='L')) l = false;
        if((i%2==0 && s[i]=='L') || (i%2!=0 && s[i]=='R')) r = false;
        if(!l && !r)return false;
    }
    return true;
}

int main(){
    int n; cin>>n;
    rep(i,n){
        string s;cin>>s;
        puts(chk(s) ? "Yes" : "No");
    }
}

Measured memory_bytes: 1304
#-*-coding:utf-8-*-
#階差数列において-1の後,-1が来る前に必ず1以上が来なければならない
import sys
n = int(input())
lst=list(map(int,input().split()))

differences=[]
for i in range(1,n):
    if lst[i]-lst[i-1]==0:#0はリストに加えず,-1の連続の有無のみを調べる
        continue
    elif lst[i]-lst[i-1]<=-2:#階差数列に-2以下が出てくればアウト
        print("No")
        sys.exit()
    else:differences.append(lst[i]-lst[i-1])


if len(differences)>=2:
    for i in range(len(differences)-1):#-1の連続があればアウト
        if differences[i]==-1 and differences[i+1]==-1:
            print("No")
            sys.exit()
 
 
print("Yes")


Measured memory_bytes: 14396
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int x_max = x;
    int y_min = y;
    int tmp;
    for(int i = 0; i < n; i++){
        cin >> tmp;
        x_max = max(tmp, x_max);
    }
    for(int i = 0; i < m; i++){
        cin >> tmp;
        y_min = min(tmp, y_min);
    }
    if(x_max + 1 <= y_min){
        cout << "No War" << endl;
    } else {
        cout << "War" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ctr = 0;
    int pena = 0;
    rep (i, n) {
        if (s[i] == ')') {
            if (ctr > 0) {
                ctr--;
            } else {
                pena++;
            }
        } else {
            ctr++;
        }
    }
    ctr = 0;
    int penb = 0;
    for (int i = n - 1; i >= 0; --i){
        if (s[i] == '(') {
            if (ctr > 0) {
                ctr--;
            } else {
                penb++;
            }
        } else {
            ctr++;
        }
    }
    string t = "";
    rep (i, pena) {
        t += '(';
    }
    s = t + s;
    t = "";
    rep (i, penb) {
        t += ')';
    }
    s = s + t;
    cout << s << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int N = 310;
int n, cnt[4], q1[N * N * N], q2[N * N * N], q3[N * N * N];
bool mp[N][N][N];
double g[N][N][N], f[N][N][N];
int main(){
	read(n);
	for (int i = 1; i <= n; i++){
		int x; read(x);
		cnt[x]++;
	} 
	mp[cnt[1]][cnt[2]][cnt[3]] = true;
	g[cnt[1]][cnt[2]][cnt[3]] = 1;
	q1[1] = cnt[1], q2[1] = cnt[2], q3[1] = cnt[3];
	int pl = 1, pr = 1; 
	while (pl <= pr){
		int x = q1[pl], y = q2[pl], z = q3[pl], nx, ny, nz;
		f[x][y][z] /= g[x][y][z];
		pl++;
		double t = 1.0 * n / (x + y + z);
		if (x > 0){
			nx = x - 1, ny = y, nz = z;
			if (!mp[nx][ny][nz]){
				pr++;
				q1[pr] = nx, q2[pr] = ny, q3[pr] = nz;
				mp[nx][ny][nz] = true;
			} 
			double p = 1.0 * x / (x + y + z);
			g[nx][ny][nz] += p * g[x][y][z];
			f[nx][ny][nz] += p * g[x][y][z] * (f[x][y][z] + t);
		}
		if (y > 0){
			nx = x + 1, ny = y - 1, nz = z;
			if (!mp[nx][ny][nz]){
				pr++;
				q1[pr] = nx, q2[pr] = ny, q3[pr] = nz;
				mp[nx][ny][nz] = true;
			} 
			double p = 1.0 * y / (x + y + z);
			g[nx][ny][nz] += p * g[x][y][z];
			f[nx][ny][nz] += p * g[x][y][z] * (f[x][y][z] + t);
		}
		
		if (z > 0){
			nx = x, ny = y + 1, nz = z - 1;
			if (!mp[nx][ny][nz]){
				pr++;
				q1[pr] = nx, q2[pr] = ny, q3[pr] = nz;
				mp[nx][ny][nz] = true;
			} 
			double p = 1.0 * z / (x + y + z);
			g[nx][ny][nz] += p * g[x][y][z];
			f[nx][ny][nz] += p * g[x][y][z] * (f[x][y][z] + t);
		}
	}
	printf("%.10lf\n", f[0][0][0]);
	return 0;
}



Measured memory_bytes: 540800
import java.util.Scanner;

// B - Foods Loved by Everyone
// https://atcoder.jp/contests/abc118/tasks/abc118_b
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = Integer.parseInt(scanner.next());
        int M = Integer.parseInt(scanner.next());

        int[] A = new int[M];
        for (int i = 0; i < N; i++) {
            int count = Integer.parseInt(scanner.next());
            for (int j = 0; j < count; j++) {
                int index = Integer.parseInt(scanner.next()) - 1;
                A[index]++;
            }
        }
        scanner.close();

        int sum = 0;
        for (int a : A) {
            if (a == N) sum++;
        }

        System.out.println(sum);
    }
}



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

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define foreach(it, v) for(typeof(v.begin()) it=v.begin(); it!=v.end(); ++it)
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second

typedef unsigned int uint;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef set<int> si;

int N;

vi m[200010];

int d[200010];

int s;

int dq(int dep) {
  int ma = -1;
  int ma2 = -1;
  int cnt = 0;
  d[dep] = 1;
  for(const auto& x : m[dep]) {
    if (d[x]==0) {
      int n = dq(x);
      if (n > ma) {
        ma2 = ma;
        ma = n;
      } else {
        ma2 = max(ma2, n);
      }
      cnt++;
    }
  }
  int ret;
  if (cnt>=2) ret = ma+ma2+2;
  else if (cnt==1) ret = ma+1;
  else ret = 0;
  s = max(s, ret);
  return ma+1;
}

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

  cin >> N;
  int a, b;
  rep(i, N-1) {
    cin >> a >> b;
    m[a].pb(b);
    m[b].pb(a);
  }
  dq(1);
  if (s%3!=1) cout << "First\n";
  else cout << "Second\n";
  return 0;
}


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

int main(){
    string ans = "NO";
    int a, b, x;
    cin >> a >> b >> x;
    
    if (x >= a && x <= (a + b)) {
        ans = "YES";
    }
    
    cout << ans << endl;
    
    return 0;
}


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

using namespace std;

static const int INF = 1e9 + 7;

template<typename T>
using Vec = vector<T>;

template<typename T, typename T2>
using P = pair<T, T2>;

template<typename... Args>
using Tup = tuple<Args...>;

template<typename T>
using qp = priority_queue<T, Vec<T>, greater<T> >;

template<typename T>
using pq = priority_queue<T>;

using llong = long long;
using ullong = unsigned long long;
using uint = unsigned int;

template<typename T>
T gcd(T x, T y)
{
	return y ? gcd(y, x % y) : x;
}

void hawawa()
{
	int n, m;
	map<string, int> info;
	cin >> n;
	while (n--) {
		string str;
		cin >> str;
		info[str]++;
	}
	cin >> m;
	while (m--) {
		string str;
		cin >> str;
		info[str]--;
	}
	int ans = 0;
	for (auto&& i : info) {
		ans = max(ans, i.second);
	}
	cout << ans << "\n";
}


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


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {

        // ?¨??????\???
        Scanner sc = new Scanner(System.in);

        List<Integer> mountains = new ArrayList<>();

        // ??\?????????????????????
        for (int i = 0; i < 10; i++) {

            mountains.add(sc.nextInt());

        }

        // ?????????????????§??????????????????????????????????????????????????????
        mountains.stream().sorted((mount1, mount2) -> mount2 - mount1).limit(3)
                .forEach(mountain -> System.out.println(mountain.toString()));

        sc.close();
    }

}

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

typedef long long int lli;
#define pb push_back
#define gcd __gcd
#define MOD 1000000007
#define mod2 998244353
#define forz(i,n) for(long long int i=0;i<n;i++)
char A[51][51];
set<pair<lli,lli>> s1,s2;
set<pair<lli,lli>>::iterator i1,i2;

lli mod(lli a){
    if(a<0) return -1*a;
    return a;
}

bool comp(pair<lli,lli> a,pair<lli,lli> b){
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli t=1,u,j;
    //cin>>t;
    for(u=1;u<=t;u++){
        lli n,m,i,j,p=0,c,q,k,a,b,ne=0,p1=0,p2=0,p3=0,p4=0,q1=0,k1,k2,a1,a2,x,y;
        cin>>x>>y>>n;
        for(i=x;i<=y;i++) if(i%n==0) p++;
        cout<<p<<endl;
    }
}

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

using namespace std;
using ll = long long;
constexpr int mod = 1e9+7;
constexpr int md = mod;
ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}
int main(){
    ll n ;
    cin>>n;
    vector<ll> a(n);
    for(auto & b : a) cin>>b;
    sort(a.begin(),a.end());
    ll ret = a[0];
    for(int i=1;i<n;++i){
        if(a[0] != a[i]){
            ret = min(ret,gcd(a[0],a[i]));
        }
    }
    cout << ret << endl;
    return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
int MOD=1000000007;

int main(){
    string S; cin >> S;
    if(S[2]!='1' && S[2]!='0' || S[2]=='1' && S[3]!='0' && S[3]!='1' && S[3]!='2' || S[2]=='0' && S[3]=='0'){
        if(S[0]!='1' && S[0]!='0' || S[0]=='1' && S[1]!='0' && S[1]!='1' && S[1]!='2' || S[0]=='0' && S[1]=='0'){
            cout << "NA" << endl;
        }else{
            cout << "MMYY" << endl;
        }
    }else if(S[0]!='1' && S[0]!='0' || S[0]=='1' && S[1]!='0' && S[1]!='1' && S[1]!='2' || S[0]=='0' && S[1]=='0'){
        cout << "YYMM" << endl;
    }else{
        cout << "AMBIGUOUS" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define int long long
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=1000+10;
int K,len,ret,as;
char str[N];

il int read()
{
	rc ch=gc;ri x=0;rb y=1;
	while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
	if(ch=='-')ch=gc,y=0;
	while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
	return y?x:-x;
}

signed main()
{
	//freopen("A.in","r",stdin);freopen("A.out","w",stdout);
	scanf("%s",str+1);len=strlen(str+1);K=read();if(len==1)return printf("%lld\n",K/2),0;
	ri nw=1;while(nw<=len && str[nw]==str[nw+1])++nw;
	rp(i,2,len)if(str[i]==str[i-1])++ret,str[i]='z'+1;;if(K==1)printf("%lld\n",ret);
	if(nw&1 && str[len]==str[1])as=K-1;if(nw==len && len&1)as=K/2;printf("%lld\n",ret*K+as);
	return 0;
}



Measured memory_bytes: 384
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = int(input())
a = list(map(int, input().split()))
c = a[0] + a[1]

t = 0
flg = 0

for ai in a[2:]:
    t = t ^ ai

b1 = c - t
if b1 < 0 or b1 % 2:
    flg = 1

b1 //= 2
a1 = b1

if a1 > a[0]:
    print(-1)
    sys.exit()

for i in reversed(range((a[0] + a[1]).bit_length())):
    if t & (1 << i):
        if b1 & (1 << i):
            print(-1)
            sys.exit()
        if a1 + 2 ** i <= a[0]:
            a1 += 2 ** i

if a1 == 0:
    flg = 1

print(a[0] - a1 if flg == 0 else -1)











Measured memory_bytes: 81396
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        int ans = 1;
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        for (int i = 0;i < 3;i++){
        ans = ans * x;
        }
    System.out.println(ans);
    }
}


Measured memory_bytes: 26132
//#define LOCAL

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <climits>
#include <set>

//#define int long long
//typedef long long ll;
using ll = long long;
//using R = double;

//#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

#define MOD 1000000007

const int INF = int(1e9);

using namespace std;

typedef vector<int> V;
typedef vector<V> VV;

int N, W;
int v[110], w[110];
int dp[100][10001];

signed main()
{
    cin >> N >> W;
    REP(i,N) cin >> v[i] >> w[i];

    REP(i,W+1) {
        dp[0][i] = i / w[0] * v[0];
    }
    for (int i=1; i<N; i++) {
        for (int j=0; j<=W; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
            }
        }
    }

    /*
    REP(i,N) {
        REP(j,W+1) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    */
    
    cout << dp[N-1][W] << endl;

    return 0;
}

Measured memory_bytes: 6992
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
 
long long int A,B,K;
long long int ans1,ans2;
 
void solve(){
	long long int diff = A-K;
	if(diff>=0){
		ans1 = diff;
		ans2 = B;
		return;
	}
	ans1 = 0;
	diff = B+diff;
	if(diff>=0){
		ans2 = diff;
		return;
	}
	ans2 = 0;
	return;
}
 
int main(){
	cin >> A >> B >> K;
 
	solve();
 
	cout << ans1 << ' ' << ans2;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  char a;cin>>a;
  if(a>='a'&&a<='z'){
    cout<<"a"<<endl;
  }
  else{
    cout<<"A"<<endl;
  }
  return 0;
}


Measured memory_bytes: 3636
# coding: utf-8

# min(sum_i (x_i-p)^2)
# d/dp = 0: sum_i -2(x_i-p) = 0, p = sum_i(x_i)/p

n = int(input().rstrip())
x_list = [int(x) for x in 
          input().rstrip().split(" ")]
p1 = sum(x_list)//n
if sum(x_list)%n == 0:
  print(sum((x-p1)**2 for x in x_list))
else:
  p2 = p1 + 1
  print(min(sum((x-p1)**2 for x in x_list),
            sum((x-p2)**2 for x in x_list)))

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i=0;i < N;i++){
        cin >> a[i];
    }
    vector<bool> add_flag(8,true);
    int rate_normal_num = 0;
    int over_rate_num = 0;
    for(int i=0;i < N;i++){
        for(int j=0;j < 8;j++){
            if(j*400 <= a[i] && a[i] <= ((j+1)*400 - 1) && add_flag[j]){
                rate_normal_num ++;
                add_flag[j] = false;
            }
        }
        if(3200 <= a[i]){
            over_rate_num++;
        }
    }
    if(rate_normal_num == 0){
        cout << "" << 1 << ' ' << over_rate_num;
    }else{
        cout << "" << rate_normal_num << ' ' << rate_normal_num+over_rate_num;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
struct pnt{
  double x,y;
  pnt operator+(pnt key){
      pnt res;res.x=x+key.x,res.y=y+key.y;
      return res;
  }
  pnt operator-(pnt key){
      pnt res;res.x=x-key.x,res.y=y-key.y;
      return res;
  } 
  pnt operator*(double key){
      pnt res;res.x=x*key,res.y=y*key;
      return res;
  }
  pnt operator/(double key){
      pnt res;res.x=x/key,res.y=y/key;
      return res;
  }
};
double gaiseki(pnt a,pnt b){
    double res=a.x*b.y-a.y*b.x;
    if(res<0)res*=-1;
    return res;
}
pnt cross(pnt a,pnt b,pnt c,pnt d){
    double d1=gaiseki(b-a,c-a);//cout<<"d1:"<<d1<<endl;
    double d2=gaiseki(b-a,d-a);//cout<<"d2:"<<d2<<endl;
    //cout<<"d-c:"<<cd.x<<" "<<cd.y<<endl;
    pnt res=c+(d-c)*d1/(d1+d2);
    return res;
}
void inn(pnt &a){
    cin>>a.x>>a.y;
}
int main(){
    ll q;cin>>q;
    while(q--){
	pnt a,b,c,d;
	inn(a);
	inn(b);
	inn(c);
	inn(d);
	pnt res=cross(a,b,c,d);
	cout<<fixed<<setprecision(9)<<res.x<<" ";
	cout<<fixed<<setprecision(9)<<res.y<<endl;
    }
    return 0;
}



Measured memory_bytes: 3276
s=input()
n=len(s)
ans=0
while s:
  if len(s)==n:
    si=s[0]
    s=s[1:]
  else:
    if si==s[0]:
      if len(s)==1:
        break
      else:
        si=s[:2]
        s=s[2:]
    else:
      si=s[0]
      s=s[1:]
  ans+=1
print(ans)

Measured memory_bytes: 3500
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m; cin >> n >> m;
  vector<int>a(m);
  for(int i; i<m; i++) cin >> a[i];
  int w=0;
  for(int i; i<m; i++) w += a[i];
  if(n < w) cout << -1 << endl;
  else cout << n-w << endl;
}



Measured memory_bytes: 3664