akhauriyash/Code-Regression huggingface dataset:
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println(calc(s.nextBigInteger(), s.nextBigInteger(),
				s.nextBigInteger(), s.nextBigInteger()));

	}

	public static BigInteger calc(BigInteger a, BigInteger b, BigInteger c,
			BigInteger d) {
		BigInteger zenKosu = b.subtract(a).add(BigInteger.ONE);
		return zenKosu.subtract(calcBiasuKosu(a, b, c, d));
	}

	public static BigInteger calcBiasuKosu(BigInteger a, BigInteger b, BigInteger c,
			BigInteger d) {
		BigInteger cKosu = calcBiasuKosu(a, b, c);
		BigInteger dKosu = calcBiasuKosu(a, b, d);
		BigInteger cdKosu = calcBiasuKosu(a, b, calcKoBaisu(c, d));
		return cKosu.add(dKosu).subtract(cdKosu);
	}

	public static BigInteger calcKoBaisu(BigInteger x, BigInteger y) {
		BigInteger a = x;
		BigInteger b = y;
		BigInteger mult = x.multiply(y);
		if (a.compareTo(b) < 0) {
			BigInteger tmp = a;
			a = b;
			b = tmp;
		}
		BigInteger r = a.mod(b);
		while (!r.equals(BigInteger.ZERO)) {
			a = b;
			b = r;
			r = a.mod(b);
		}
		return mult.divide(b);
	}

	public static BigInteger calcBiasuKosuFrom1(BigInteger n, BigInteger to) {
		return n.divide(to);
	}

	public static BigInteger calcBiasuKosu(BigInteger a, BigInteger b, BigInteger n) {
		BigInteger res = calcBiasuKosuFrom1(b, n).subtract(calcBiasuKosuFrom1(a, n));
		if (a.mod(n).equals(BigInteger.ZERO)) {
			res = res.add(BigInteger.ONE);
		}
		return res;
	}
}


Measured memory_bytes: 21588
N=int(input())
A=[]
for i in range(0,N):
    a=int(input())
    b=[]
    for j in range(0,a):
        b.append(list(map(int,input().split())))
    for B in b:
        B[0]-=1
    A.append(b)
import itertools
ans=0
for i in itertools.product([-1,1],repeat=N):
    OK=True
    for j in range(0,N):
        if i[j]==-1:
            OK=True
        else:
            for a in A[j]:
                if a[1]==0:
                    if i[a[0]]==1:
                        OK=False
                else:
                    if i[a[0]]==-1:
                        OK=False
        if not OK:
            break
    if i.count(1)>ans and OK:
        ans=i.count(1)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dp[2][2001];
int n;
int ar[2001];
int go(int turn, int now){
    if(dp[turn][now]!=-1){
        return dp[turn][now];
    }
    int ret = abs(ar[now-1]-ar[n]);
    for(int i = now+1; i<=n; i++){
        if(turn==0){
            ret = max(ret,go(1-turn,i));
        }
        else{
            ret = min(ret,go(1-turn,i));
        }
    }
    dp[turn][now] = ret;
    return ret;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    
    int z, w;
    cin >> n >> z >> w;
    ar[0] = w;
    for(int i = 1; i<=n; i++){
        cin >> ar[i];
    }
    for(int a = 0; a<2; a++){
        for(int b = 0; b<=2000; b++){
            dp[a][b] = -1;
        }
    }
    cout << go(0,1) << endl;
    
    return 0;
}

Measured memory_bytes: 384
import sys
readline = sys.stdin.buffer.readline
k, n = readline().rsplit()
A = readline().rsplit()
far = int(k) + int(A[0]) - int(A[-1])
for x, y in zip(A[1:], A):
    if far < int(x) - int(y):
        far = int(x) - int(y)
print(int(k)-far)

Measured memory_bytes: 21492
#include <iostream>

using namespace std;

int main() {
    int n;
    unsigned long height = 0ul;
    unsigned long max = 0ul;
    cin >> n;

    for (int i = 0; i < n; i++) {
        unsigned long a;
        cin >> a;
        if (max > a) {
            height += (max - a);
        } else
        {
            max = a;
        }
        
    }

    cout << height << endl;

    return 0;
}

Measured memory_bytes: 3140
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Node u[] = new Node[n];
		for(int i=0; i<n; i++){
			int id = sc.nextInt();
			u[id] = new Node();
			u[id].id = id;
			u[id].left = sc.nextInt();
			u[id].right = sc.nextInt();
			u[id].p = -1;
			u[id].s = -1;
			u[id].deg = 0;
			u[id].type = "leaf";
			if(u[id].left != -1){
				u[id].deg++;
				u[id].type = "internal node";
			}
			if(u[id].right != -1){
				u[id].deg++;
				u[id].type = "internal node";
			}
		}

		for(int i=0; i<n; i++){
			if(u[i].left != -1){
				u[u[i].left].p = u[i].id;
			}
			if(u[i].right != -1){
				u[u[i].right].p = u[i].id;
			}
			if(u[i].left != -1 && u[i].right != -1){
				u[u[i].left].s = u[i].right;
				u[u[i].right].s = u[i].left;
			}
		}

		for(int i=0; i<n; i++){
			if(u[i].p == -1){
				u[i].type = "root";
				if(u[i].left != -1){
					setDep(u, u[i].left, 1);
				}
				if(u[i].right != -1){
					setDep(u, u[i].right, 1);
				}
			}
			if(u[i].deg == 0){
				if(u[i].p != -1){
					setH(u, u[i].p, 1);
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++){
			sb.append("node "      + u[i].id   + ": ");
			sb.append("parent = "  + u[i].p    + ", ");
			sb.append("sibling = " + u[i].s    + ", ");
			sb.append("degree = "  + u[i].deg  + ", ");
			sb.append("depth = "   + u[i].dep  + ", ");
			sb.append("height = "  + u[i].h    + ", ");
			sb.append(               u[i].type + "\n");
		}
		System.out.print(sb.toString());
	}

	static void setDep(Node u[], int c, int dep){
		u[c].dep = dep;
		dep++;
		if(u[c].left != -1){
			setDep(u, u[c].left, dep);
		}
		if(u[c].right != -1){
			setDep(u, u[c].right, dep);
		}
	}

	static void setH(Node u[], int p, int h){
		if(h < u[p].h) h = u[p].h;
		else           u[p].h = h;
		h++;
		if(u[p].p != -1){
			setH(u, u[p].p, h);
		}
	}
}

class Node{
	int id;
	int left;
	int right;
	int p;
	int s;
	int deg;
	int dep;
	int h;
	String type;
}

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

int w, a, b;

void solve() {
    cin >> w >> a >> b;
    if(a > b) swap(a, b);
    cout << (a + w >= b ? 0 : b - (w + a)) << "\n";
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    solve();
    
}

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

int n;
vector<ll> h;
ll dp[101010];
int k;
int h1;
ll big = 1e15;
int main(){
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> h1;
		h.push_back(h1);
	}
	for(int i = 1; i <= n; i++) dp[i] = big;
	dp[0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = i; j < min(i+k+1, (int)h.size()); j++){
		//	cout << i << ", " << j << ": " << dp[j] << "," << dp[i] + abs(h[i]-h[j]) << "\n";
			dp[j] = min(dp[j], dp[i] + abs(h[i]-h[j]));
		}
	}
	for(int i = 0; i < n; i++){
	//	cout <<i << ": " <<  dp[i] << "\n";
	}
	cout << dp[n-1] << "\n";
}


Measured memory_bytes: 1908
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  la = list(map(int, input().strip().split()))
  la.sort(reverse=True)
  ans = sum(la[:(n+1)//2]) * 2 - la[0] - (la[(n+1)//2-1] if n%2==1 else 0)
  print(ans)

if __name__=='__main__':
  main()



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

int main()
{
    int member,point,quiz;
    cin >> member >> point >> quiz;
    int answer[100010]={};
    int current;
    for(int i=0;i<quiz;i++){
        cin >> current;
        answer[current] ++;
    }
    for(int i=1;i<=member;i++){
        if(point-quiz+answer[i]>0){
            cout << "Yes\n";
        }else{
            cout << "No\n";
        }
    }
    return 0;
}

Measured memory_bytes: 1272
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define MOD 1000000007
#define int int64_t

signed main() {
    int n, l;
    cin >> n >> l;
    vector<string> v(n);
    rep(i,n) cin >> v.at(i);
    sort(all(v));
    rep(i,n) cout << v.at(i) << flush;
    cout << endl;
}

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


/*
白黒において連結かどうか
*/

ll h,w,dp[410][410],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},ans=0;
string s[410];

int main(void){
	cin>>h>>w;
	rep(i,h)cin>>s[i];
	//
	rep(i,h)rep(j,w)dp[i][j]=-1;
	//
	rep(i,h)rep(j,w){
		if(dp[i][j]==-1 && s[i][j]=='#'){
			ll sumb=1,sumw=0;
			queue<mmp> Q;
			Q.push({{i,j},1});
			dp[i][j]=1;
			while(!Q.empty()){
				mmp p = Q.front();Q.pop();
				ll to_white = p.second;
				mp pos = p.first;
				ll x = pos.second, y = pos.first;
				// cout<<y<<","<<x<<","<<to_white<<endl;
				rep(k,4){
					if(0<=y+dy[k] && y+dy[k]<h && 0<=x+dx[k] && x+dx[k]<w && dp[y+dy[k]][x+dx[k]]==-1){
						if(to_white==1 && s[y+dy[k]][x+dx[k]]=='.'){
							sumw++;
							dp[y+dy[k]][x+dx[k]]=1;
							Q.push({{y+dy[k],x+dx[k]},1-to_white});
						}
						if(to_white==0 && s[y+dy[k]][x+dx[k]]=='#'){
							sumb++;
							dp[y+dy[k]][x+dx[k]]=1;
							Q.push({{y+dy[k],x+dx[k]},1-to_white});
						}
					}
				}
			}
			ans+=sumb*sumw;
			// cout<<i<<","<<j<<" : "<<sumb<<","<<sumw<<endl;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m); (i) > (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define R cin>>
#define i64 unsigned long long
#define repr(i, n) REPR(i, n, 0)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define in(a) insert(a)
#define P(p) cout<<(p)<<endl;
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SORT(a) sort((a).begin(), (a).end())
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long int> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll mod = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;
template<typename T> void co(T e){cout << e << "\n";}
template<typename T> void co(const vector<T>& v){for(const auto& e : v)
    { cout << e << " "; } cout << "\n";}
ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0) return a;
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}
ll lcm(ll a, ll b) {
    ll g = gcd(a, b);
    return a * b / g;
}
bool prime(ll n) {
    for (ll i = 2; i <= sqrt(n); i++) {
        if (n%i == 0)return false;
    }
    return n != 1;
}


int pow(int x, int y, int mod){
    int ret=1;
    for(;y;y>>=1,x=1ll*x*x%mod){
        if(y&1) ret=1ll*ret*x%mod;
    }
    return ret;
}
void kill()
{
    cout << "No" << endl;
    exit(0);
}

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(b<a){a=b;return 1;} return 0;}





int main(){
    sonic();
    int n, A=0, B=0, AB=0, ans=0;
    R n;
    rep(i, n) {
        string s;
        R s;
        int l = s.length();
        if (s[l - 1] == 'A' && s[0] == 'B')AB += 1;
        else {
            if (s[l - 1] == 'A')A += 1;
            else if (s[0] == 'B')B += 1;
        }
        rep(j, l - 1)if(s[j] == 'A' && s[j + 1] == 'B')ans += 1;
    }
    if(AB){
        ans+=AB-1;
        if(A){
            A-=1;
            ans+=1;
        }
        if(B){
            B-=1;
            ans+=1;
        }
    }
    ans+=min(A,B);
    co(ans);
}


Measured memory_bytes: 3648
//解説AC
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using ll = long long;
const int INF = 2147483647;
const ll MOD = 1000000007;
// const ll INF = 1000000000000000000LL;

int main(){
    ll n;
    cin >> n;
    ll ans=0;
    ll a=10;
    ll b=0;
    if(n%2==1)
        cout << ans << endl;
    else{
        while(n>=a){
            b++;
            ans+=n/a;
            a*=5;
        }
        cout << ans << endl;
    }

	return 0;
}

Measured memory_bytes: 3604
import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))

d = dict(collections.Counter(a))
d = sorted(d.items(), key=lambda x:x[1])
l = len(d)

cnt = 0
for _, j in d:
    if l > k:
        l -= 1
        cnt += j
    else:
        break


print(cnt)

Measured memory_bytes: 113992
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int Size[N], parent[N], ans[N], G[N];
int findSet(int u)
{
    if (u == parent[u]) return u;
    return parent[u] = findSet(parent[u]);
}
void unionSet(int a, int b)
{
    a = findSet(a);
    b = findSet(b);
    if (a == b)
        return;
    if (Size[a] < Size[b])
        swap(a,b);
    parent[b] = a;
    Size[a] += Size[b];
}
int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i)
        parent[i] = i,Size[i] = 1,ans[i] = 0;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        u --,v --;
        G[u] ++,G[v]++;
        unionSet(u, v);
    }
    for (int i = 0; i < k; ++i)
    {
        int u, v;
        cin >> u >> v;
        u --,v --;
        if (findSet(u) == findSet(v))
            ans[u]++,ans[v]++;
    }
    for (int i = 0; i < n; ++i)
    {
        int s = Size[findSet(i)];
        cout << s-1-ans[i]-G[i]<< ' ';
    }
}


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

#define sp ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

int main() {
	sp;

	////////////////To Remove//////////////
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	///////////////////////////////////////

	int n;
	cin>>n;

	vector<int> dp_prev(3), dp(3);
	cin>>dp_prev[0]>>dp_prev[1]>>dp_prev[2];
	for(int i = 1; i < n; ++i){
		cin>>dp[0]>>dp[1]>>dp[2];
		dp[0] += max(dp_prev[1], dp_prev[2]);
		dp[1] += max(dp_prev[0], dp_prev[2]);
		dp[2] += max(dp_prev[0], dp_prev[1]);
		dp_prev = dp;
	}

	cout<<max(dp_prev[0], max(dp_prev[1], dp_prev[2]));

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>

const int MAXN = 1e5 + 10;

int N;
long long K;
long long freq[MAXN];

int main() {
  scanf("%d %lld", &N, &K);

  for (int i = 1; i <= N; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    freq[a] += b;
  }

  int i = 1;
  long long k = 0;

  while (k + freq[i] < K) {
    k += freq[i];
    i++;
  }

  printf("%d\n", i);
  return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 1> { using type = vector<T>; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

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

bool solve(ll A, ll B, ll C, ll D) {
  if (A < B) return false;
  if (B > D) return false;
  if (C >= B) return true;
  ll g = gcd(B, D % B);
  ll mx = A % B;
  if (g > 0) {
    ll x = (B - 1 - A % B) / g;
    mx += g * x;
  }
  return mx <= C;
}

int main() {
  int T;
  while (cin >> T) {
    for (int t = 0; t < T; t++) {
      ll A, B, C, D;
      cin >> A >> B >> C >> D;
      cout << (solve(A, B, C, D) ? "Yes" : "No") << endl;
    }
  }
  return 0;
}


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

int main (){
    int n ;
    cin >> n ;
    string s ;
    cin >> s ;
    int numr = 0 ;
    int numw = 0 ;
    int ans = 200001; 
    rep(i, n){
        if(s[i] == 'R'){
            numr++ ;
        }
    }
    ans = min(ans, max(numr,numw)) ;
    rep(i, n){

        if(s[i] == 'W'){
            numw++ ;
        }
        else{
            numr-- ;
        }
        ans = min(ans, max(numr,numw)) ;
    }
    cout << ans << endl ;
}

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

using namespace std;

#define x first
#define y second
typedef long long ll;

const int MOD = 1000000007;
const int oo = 1e9;
typedef pair<int,int> pii;

const int N = 1e6+10;

int n,q,k;
char s[N];
ll sum[N],pre[N],hv[N];

ll get(int l , int r , ll p[]){
  r = min(r,n);
  return p[r]-p[l-1];
}

int main(){
  cin >> n;
  scanf("%s",s+1);
  int numM = 0;
  for(int i = 1; i <= n ; ++i){
    if(s[i]=='M')numM++;
    sum[i] = numM;
    hv[i] = (s[i]=='C')+hv[i-1];
    if(s[i]=='C')pre[i] = numM;
    pre[i] += pre[i-1];
  }
  cin >> q;
  while(q--){
    scanf("%d",&k);
    ll res = 0;
    for(int i = 1 ; i <= n ; ++i){
      if(s[i]=='D'){
        ll cnt = get(i,i+k-1,hv);
        ll numC = sum[i];
        ll totalM = get(i,i+k-1,pre);
        res += totalM-numC*cnt;
      }
    }
    printf("%lld\n", res);
  }

  return 0;
}

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

#define lli long long int
#define ld long double
#define MAX_L lli max = 9000000000000000000;
#define MIN_L lli min = 9000000000000000000;
#define MAX_D ld max = 4500;
#define MIN_D ld min = -4500;
#define LLI(n) \
  lli n;       \
  cin >> n;
#define LD(n)  \
  ld n;        \
  cin > n;
#define LLIV(a, n)            \
  vector<lli> a(n);           \
  for (lli i = 0; i < n; i++) \
  {                           \
    cin >> a.at(i);           \
  };
#define LDV(a, n)            \
  vector<ld> a(n);           \
  for (lli i = 0; i < n; i++) \
  {                           \
    cin >> a.at(i);           \
  };
#define STR(n) \
  string n;    \
  cin >> n;
#define sum(n) accumulate(n.begin(), n.end(), 0);
#define Sort(n) sort(n.begin(), n.end());
#define Reve(n) reverse(n.begin(), n.end());
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define C45(n) (n + 1) / 2
#define OUT(n) cout << n << endl;
#define SRC(n, c)                    \
  for (lli i = 0; i < s.size(); i++) \
  {                                  \
    if (s.at(i) == c)                \
    {                                \
      n++;                           \
    }                                \
  };
//こぴー
/*#define ZISYO(s, S)                  \
  for (lli i = 0; i < s.size(); i++) \
  {                                  \
    S.at(i) = s.at(i);               \
  }                                  \
  Sort(S) Reve(S) for (lli i = 0; i < s.size(); i++) { s.at(i) = S.at(i); };
*/

//素数
bool IsPrime(lli num)
{
  if (num < 2)
    return false;
  else if (num == 2)
    return true;
  else if (num % 2 == 0)
    return false;
  long double sqrtNum = sqrt(num);
  for (lli i = 3; i <= sqrtNum; i += 2)
  {
    if (num % i == 0)
      return false;
  }
  return true;
}
//各桁の和
lli KSum(lli n)
{
  lli sum = 0;
  if (n < 0)
    return 0;
  while (n > 0)
  {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int main(void)
{
  ios::sync_with_stdio(false);
  LLI(N)LLI(X)LLIV(m, N)
  Sort(m);
  X = X - sum(m);
  lli flag = N;
  for(flag;X >= m[0];++flag) {
    X = X - m[0];
  }
  OUT(flag)
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>

using namespace std;
int main()
{
	int n;
	cin>>n;
	long long ans=1;
	for(int i=1;i<=n;i++)
	{
		ans=(ans*i)%1000000007;
	}
	cout<<ans%1000000007<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;


int main()
{
    vector<int> ans(1000000,0);
    int N;
    cin >> N;

    for(int x=1; x<=100; x++){
        for(int y=1; y<=100; y++){  
            for(int z=1; z<=100; z++){
                int tmp=x*x+y*y+z*z+x*y+y*z+z*x;
                ans[tmp]++;
            }
        }
    }
    for(int i=1; i<=N; i++){
        cout << ans[i] << endl;
    }




    return 0;
}

Measured memory_bytes: 6936
#include <bits/stdc++.h>
#define eps 1e-9
#define nmax 200
#define f(c,a,b) for(int c=a; c<=b; c++)

using namespace std;
typedef double db;
struct P{
    db x, y;
    P(){}
    P(db x, db y) : x(x) , y(y) {}
    P operator - (P a){ return P(x-a.x, y-a.y); }
    db times(P a){ return x*a.y-y*a.x; }
    db clen() { return x*x+y*y; }
    db dot(P a){ return a.x*x + a.y*y; }
    P operator * (db a) { return P(a*x, a*y); }
    P operator + (P a){ return P(x+a.x, y+a.y); }
    void swap(P& a){
        db tx = x, ty = y;
        x = a.x;  y = a.y;
        a.x = tx; a.y = ty;
    }
    bool operator < (const P a) const { return (x==a.x)?(y<a.y):(x<a.x); }
}po[nmax];

int sign(db x) { return (x<-eps) ? -1 : x>eps; }    

P projection(P a, P p, P q){ 
    P tl = q - p; 
    db ll = sqrt(tl.clen());  
    db k = (a-p).dot(tl)/ll/ll;  
    return P( p.x + k*tl.x, p.y + k*tl.y ); 
}

void isCL(P c1, db r1, P p1, P q1){
    if(q1<p1) p1.swap(q1);
    db dis = (p1-c1).times(p1-q1)/(p1-q1).clen();
    dis *= (p1-c1).times(p1-q1);
    dis = sqrt( r1*r1-dis );
    P pj = projection(c1, p1, q1);
    P a1, a2;
    a1 = pj+(p1-q1)*( dis/sqrt((p1-q1).clen()) );
    a2 = pj+(q1-p1)*( dis/sqrt((q1-p1).clen()) );
    printf("%.8lf %.8lf %.8lf %.8lf\n", a1.x, a1.y, a2.x, a2.y);
}

int main(){
    //freopen("owo.in","r",stdin);
    P c, ip, iq;
    db r;
    int q;
    cin >> c.x >> c.y >> r >> q;
    while(q--){
        scanf("%lf%lf%lf%lf", &ip.x, &ip.y, &iq.x, &iq.y);
        isCL(c, r, ip, iq);
    }
    return 0;
}


Measured memory_bytes: 3284
x,n = list(map(int,input().split()))
if n == 0:
  print(x)
  exit()

p = list(map(int,input().split()))
p = [-1] + p + [102]
import bisect
p.sort()
i = bisect.bisect_left(p,x)
if p[i] != x:
    print(x)
    exit()

for h in range(102):
  if p[i-h] != x-h:
    print(x-h)
    exit()
  elif p[i+h] != x+h:
    print(x+h)
    exit()    


Measured memory_bytes: 9160
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define REP(i,a,n) for(int i = a; i < n; ++i)
#define EPS 0.0001

typedef long long LL;

LL N, S;

LL f(LL b, LL n) {
	LL sum = 0;
	while (n > 0) {
		sum += n % b;
		n /= b;
	}
	return sum;
}

LL sub() {
	LL ret = -1;
	for (LL i = 1; i * i < N && S >= i; ++i) {
		LL remain = S - i;
		if ((N - remain) % i == 0 && (N - remain) / i > remain) {
			ret = (N - remain) / i;
		}
	}
	return ret;
}

int main() {
	cin >> N >> S;
	if (N == S) {
		cout << N + 1 << endl;
		return 0;
	}
	for (LL i = 2; i * i <= N; ++i){
		if (f(i, N) == S) {
			cout << i << endl;
			return 0;
		}
	}

	cout << sub() << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    string s, t;
    cin >> s >> t;
    int ans = 0;
    rep(i, 0, s.size()) {
        if (s[i] != t[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3920
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  string s;
  cin >> s;

  string r = s;
  reverse(all(r));

  int n = s.size();

  string ans = "No";
  if (s == r) {
    string z = s.substr(0, (n - 1) / 2);
    string zr = z;
    reverse(all(z));

    string k = s.substr((n + 3) / 2 - 1);
    string kr = k;
    reverse(all(k));

    if (z == zr && k == kr) {
      ans = "Yes";
    }
  }

  cout << ans << ln;

  return 0;
}

Measured memory_bytes: 256
n, x, m = map(int, input().split())

ans = []
flag = False
for i in range(n):
    if x in ans:
        v = x
        flag = True
        break
    ans.append(x)
    x = x**2 % m
if flag:
    p = ans.index(v)
    l = len(ans) - p
    d, e = divmod(n-p, l)
    print(sum(ans[:p]) + d*sum(ans[p:]) + sum(ans[p:p+e]))
else:
    print(sum(ans))


Measured memory_bytes: 67952
from math import log, ceil
def main():
    n = int(input())
    l = [int(j) for j in input().split()]
    x = 0
    for i in range(n):
        x = x^l[i]
    for i in range(n):
        print(x^l[i], end = " ")
    print()

    # for t in range(int(input())):
        # n = int(input())
        

# "Ashishgup" if he wins, and "FastestFinger"

# for #!/usr/bin/env python
# import os
# import sys
# from io import BytesIO, IOBase


# # region fastio

# BUFSIZE = 8192


# class FastIO(IOBase):
#     newlines = 0

#     def __init__(self, file):
#         self._fd = file.fileno()
#         self.buffer = BytesIO()
#         self.writable = "x" in file.mode or "r" not in file.mode
#         self.write = self.buffer.write if self.writable else None

#     def read(self):
#         while True:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             if not b:
#                 break
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines = 0
#         return self.buffer.read()

#     def readline(self):
#         while self.newlines == 0:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             self.newlines = b.count(b"\n") + (not b)
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines -= 1
#         return self.buffer.readline()

#     def flush(self):
#         if self.writable:
#             os.write(self._fd, self.buffer.getvalue())
#             self.buffer.truncate(0), self.buffer.seek(0)


# class IOWrapper(IOBase):
#     def __init__(self, file):
#         self.buffer = FastIO(file)
#         self.flush = self.buffer.flush
#         self.writable = self.buffer.writable
#         self.write = lambda s: self.buffer.write(s.encode("ascii"))
#         self.read = lambda: self.buffer.read().decode("ascii")
#         self.readline = lambda: self.buffer.readline().decode("ascii")


# sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
# input = lambda: sys.stdin.readline().rstrip("\r\n")

# # endregion

if __name__ == "__main__":
    main()



Measured memory_bytes: 104636
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N;
  cin >> N;
  set<string> S;
  for(int i=0;i<N;i++){
    string tmp;
    cin >> tmp;
    S.insert(tmp);
  }
  cout << S.size() << endl;

  return 0;
}

Measured memory_bytes: 19288
int main(void) {
    int A[10000],N=0, i;

    
	do{
		scanf("%d/n",&A[i]);
		i++;
		N++;
	}while(A[i-1]!=0);

    
    for(i=0;i<N-1;i++) {
    	
        printf("Case %d: %d\n",i+1,A[i]);
    	
    	
    }
  
    return 0;
}


Measured memory_bytes: 2036
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC122
{
    class B
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();

            List<char> acgt = new List<char>();
            acgt.Add('A');acgt.Add('C');acgt.Add('G'); acgt.Add('T');

            int max = 0;
            int count = 0;
            for(int i = 0; i < S.Length; i++)
            {
                if (acgt.Contains(S[i])) count++;
                else count = 0;
                if (count > max) max = count;
            }
            Console.WriteLine(max);
        }

    }
    }


Measured memory_bytes: 13148
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[] ans = new int[N];
        int[] pena = new int[N];

        for(int i = 0; i < M; i++) {
            int pi = scanner.nextInt() - 1;
            String si = scanner.next();
            if(ans[pi] == 0) {
                if (si.equals("WA")) {
                    pena[pi]++;
                } else {
                    ans[pi] = 1;
                }
            }
        }

        int totalAns = 0;
        int totalPena = 0;
        for(int i = 0; i < N; i++) {
            if(ans[i] == 1) {
                totalAns++;
                totalPena += pena[i];
            }
        }

        System.out.println(totalAns);
        System.out.println(totalPena);
    }
}

Measured memory_bytes: 64704
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <bitset>

using namespace std;

typedef long long ll;
typedef vector<ll> Vec;
typedef vector<pair<ll, ll>> Pair;
#define rep(i, n) for(ll i=0;i<n;i++)
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

//static const ll MOD = 1000000007;
//static const ll INF = 100000000;
//#define PI 3.14159265359


int main() {
    // input
    ll N, M, X;
    cin >> N >> M >> X;
    Vec C(N);
    vector<vector<ll>> A(N);
    rep(i, N) {
        cin >> C[i];
        A[i].assign(M, 0);
        rep(j, M) {
            cin >> A[i][j];
        }
    }

    // process
    ll ans = 1000000000000;
    bool yes_flag = false;

    for (unsigned int i = 0; i < pow(2, N); ++i) {
        vector<ll> skill(M, 0);
        ll cost = 0;
        for (unsigned int j = 0; j < N; ++j) {
            if (i & (1u << j)) {
                cost += C[j];
                rep(k, M) {
                    skill[k] += A[j][k];
                }
            }
        }

        bool flag = true;
        rep(j, M) {
            if (skill[j] < X) {
                flag = false;
                break;
            }
        }

        if (flag && cost < ans) {
            yes_flag = true;
            ans = cost;
        }
    }

    if (yes_flag) {
        cout << ans << endl;
    } else {
        cout << "-1" << endl;
    }
    return 0;
}



Measured memory_bytes: 3320
#include <stdio.h>

int main(void)
{
  int i,j;

  for(i=1; i<10; i++)
  {
    for(j=1; j< 10; j++)
	{
	  printf("%dx%d=%d\n",i,j,i*j);		
	}
  }

  return 0;		
}

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

int main() {
  long long A, B;
  cin >> A >> B;
  
  string result;
  if (A > 8 || B > 8) {
    result = ":(";
  } else {
    result = "Yay!";
  }
  
  cout << result << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N;
int table_index;
int table[362880][9];
int tmp_array[9];
bool used[10];
map<ll,int> MAP;

void recursive(int index){

	if(index == N){

		ll num = 0;

		for(int i = 0; i < N; i++){
			table[table_index][i] = tmp_array[i];
			num = 10*num+tmp_array[i];
		}

		MAP[num] = table_index++;
		return;
	}

	for(int i = 1; i <= N; i++){

		if(used[i])continue;
		tmp_array[index] = i;
		used[i] = true;
		recursive(index+1);
		used[i] = false;
	}
}

void output(int index){

	printf("%d",table[index][0]);
	for(int i = 1; i < N; i++){
		printf(" %d",table[index][i]);
	}
	printf("\n");
}


int main(){

	scanf("%d",&N);

	int tmp;

	if(N == 1){

		scanf("%d",&tmp);

		printf("1\n");
		return 0;
	}

	table_index = 0;

	for(int i = 1; i <= N; i++)used[i] = false;

	for(int i = 1; i <= N; i++){

		tmp_array[0] = i;
		used[i] = true;
		recursive(1);

		used[i] = false;
	}

	ll num = 0;
	for(int i = 0; i < N; i++){
		scanf("%d",&tmp);
		num = 10*num+tmp;
	}

	int index = MAP[num];

	if(index > 0){
		output(index-1);
	}
	output(index);
	if(index < table_index-1){
		output(index+1);
	}

	return 0;
}




Measured memory_bytes: 38640
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false); cin.tie(NULL);
#ifndef LOCAL
#define dbg(...) ;
#define endl '\n'
#endif

const int inf = 1e15;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;



signed main(){
    IOS;
    int n;
    int ans = 0;
    cin >> n;
    if (n >= 500) {
        ans += n / 500;
        n -= ans * 500;
        ans *= 1000;
    }
    if (n >= 5) {
        ans += (n / 5) * 5;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	N, C := ReadInt(), ReadInt()
	x := make([]int, N+1)
	v := make([]int, N+1)
	vSum := make([]int, N+1)
	for i := 1; i <= N; i++ {
		x[i], v[i] = ReadInt(), ReadInt()
		vSum[i] = vSum[i-1] + v[i]
	}

	// s1[i] = 時計回りにi個以下を食べる場合の最適値
	s1 := make([]int, N+1)
	max := 0
	for i := 1; i <= N; i++ {
		max = Max(max, vSum[i]-x[i])
		s1[i] = max
	}
	// s2[i] = 反時計回りにi個以下を食べる場合の最適値
	s2 := make([]int, N+1)
	max = 0
	for i := 1; i <= N; i++ {
		idx := N + 1 - i
		max = Max(max, vSum[N]-vSum[idx-1]-(C-x[idx]))
		s2[i] = max
	}

	ans := Max(Max(s1...), Max(s2...))
	for i := 1; i < N; i++ {
		// 時計回りにi個食べてからスタートに戻って、反時計周りにN-i個食べる場合の最適値
		localAns := vSum[i] - 2*x[i] + s2[N-i]
		ans = Max(ans, localAns)
	}
	for i := 1; i < N; i++ {
		// 反時計回りにi個食べてからスタートに戻って、時計回りにN-i個食べる場合の最適値
		idx := N + 1 - i
		localAns := vSum[N] - vSum[idx-1] - 2*(C-x[idx]) + s1[N-i]
		ans = Max(ans, localAns)
	}

	fmt.Println(ans)
}

func Max(xs ...int) int {
	max := xs[0]
	for _, x := range xs[1:] {
		if max < x {
			max = x
		}
	}
	return max
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }


Measured memory_bytes: 8524
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = (int)1e9+7;
const long long INF = MOD*MOD;
typedef pair<int,int> P;
typedef long long ll;
ll n,m,k,ans;
string s,t;
const long long powll = 1LL<<1;

int main(){
	ll n; cin >> n;
	ll a[n]; rep(i,n) cin >> a[i];
	ll bit[60] = {};
	rep(i,n){
		rep(j,60){
			if((a[i]>>j) & 1) bit[j]++;
		}
	}
	ll ans = 0;
	rep(i,60){
		ll tmp = (1ll<<i)%MOD;
		tmp = (tmp*bit[i])%MOD;
		tmp = (tmp*(n-bit[i]))%MOD;
		ans += tmp;
		ans %= MOD;
	}
	cout << ans << "\n";
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <numeric>
using namespace std;

int abs(int num){
   if (num > 0)
      return num;
   else
      return -num;
}

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

long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

int main(){
  int N;
  cin >> N;
  vector<string> title(N);
  vector<int> length(N);
  for(int i = 0;i<N;i++){
    cin >> title.at(i) >> length.at(i);
  }
  string asl;
  cin >> asl;
  int num = 0;
  for(int j = 0;j<N;j++){
    if(asl == title.at(j)){
      num = j;
      break;
    }
  }

  int ans = 0;

  for(int k = num+1;k<N;k++){
    ans = ans + length.at(k);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;}
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;}
    return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M; cin >> N >> M;
    vector<bool> v(N,false);
    vector<int> cnt(N,0);
    int cnt1=0,cnt2=0;
    rep(i,M){
        int p; string S; cin >> p >> S; --p;
        if (v[p]) continue;
        if (S=="AC") ++cnt1,v[p]=true,cnt2+=cnt[p];
        else ++cnt[p];
    }
    cout << cnt1 << ' ' << cnt2 << endl;
}

Measured memory_bytes: 640
n = gets.chomp.to_i
a = gets.chomp.split(' ').map(&:to_i)
if a.include?(0)
  puts "0"
  exit
end

ans = 1
a.each do |i|
  ans *= i
  if ans > 1000000000000000000
    puts "-1"
    exit
  end
end

puts ans


Measured memory_bytes: 23484
#include <bits/stdc++.h>
using namespace std;
long long n,m,k,b,c,ans=0,cnt=0;
int main(){
	cin >> n;
	long long a[n];
	for(int i=0;i<n;i++){
		cin >> a[i];
		while(1){
			if(a[i]%2==1){
				break;
			}
			a[i]/=2;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
r=lambda x:p[x]>0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=[-1]*-~n
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=x
 if(x==y)+(m>0):s[a]-=1;s[b]-=1
 m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Measured memory_bytes: 96856
#include<bits/stdc++.h>
#define MX 500000
using namespace std;
set<int>tr[4*MX+2];
int a[MX+2];
void merge(int pos)
{
    if(tr[2*pos].size() < tr[2*pos+1].size())
    {
        tr[pos] = tr[2*pos+1];
        for(auto u:tr[2*pos])
            tr[pos].insert(u);
    }
    else
    {
        tr[pos] = tr[2*pos];
        for(auto u:tr[2*pos+1])
            tr[pos].insert(u);
    }
}
void build(int pos, int st, int ed)
{
    if(st==ed)
    {
        tr[pos].insert(a[st]);
        return;
    }
    int mid = st+((ed-st)>>1);
    build(2*pos,st,mid);
    build(2*pos+1,mid+1,ed);
    merge(pos);
}
void update(int pos,int st, int ed, int x, int val)
{
    if(st==ed && st==x)
    {
        tr[pos].clear();
        tr[pos].insert(val);
        return;
    }
    int mid = st+((ed-st)>>1);
    if(x<=mid)update(2*pos,st,mid,x,val);
    else update(2*pos+1,mid+1,ed,x,val);
    merge(pos);
}
set<int>query(int pos, int st, int ed, int l, int r)
{
    if(st>r||ed<l)return {};
    if(st>=l && ed<=r)
    {
        return tr[pos];
    }
    int mid = st+((ed-st)>>1);
    set<int>st1 = query(2*pos,st,mid,l,r);
    set<int>st2 = query(2*pos+1,mid+1,ed,l,r);
    if(st1.size()<st2.size())
    {
        for(auto u:st1)st2.insert(u);
        return st2;
    }
    else
    {
        for(auto u:st2)st1.insert(u);
        return st1;
    }
}

string s,s2;
int main()
{
    int n; cin >> n >> s;
    s = "*" + s;
    for(int i=1; i<=n; i++)a[i] = s[i]-'a'+1;
    build(1,1,n);
    int q; cin >> q;
    while(q--)
    {
        int ty; cin >> ty;
        if(ty==1)
        {
            int p; cin >> p >> s2;
            int c = s2[0]-'a'+1;
            update(1,1,n,p,c);
        }
        else
        {
            int l,r; cin >> l >> r;
            set<int>ans = query(1,1,n,l,r);
            cout << ans.size() << "\n";
        }
    }
    return 0;
}



Measured memory_bytes: 235544
#include<bits/stdc++.h>
using namespace std;
struct edge{
  int x, y;
  bool operator<(const edge& a)const{
    if(x == a.x)
      return y < a.y;
    return x < a.x;
  }
};

int main(int argc, char *argv[]){
  int n, k;
  cin >> n >> k;
  int m;
  set<edge> e;
  vector<set<int> > v;
  for (int i = 0; i < k; i++) {
    cin >> m;
    set<int> s;
    for (int j = 0; j < m; j++) {
      int tmp;
      cin >> tmp;
      s.insert(tmp);
    }
    v.push_back(s);
  }
  int r;
  cin >> r;
  for (int i = 0; i < r; i++) {
    int x, y;
    cin >> x >> y;
    e.insert((edge){x, y});
  }
  set<int> ans;
  for (int i = 0; i < k; i++) {
    for (int j: v[i]) {
      for (int l: v[i]) {
        if(j == l)continue;
        if(e.count(edge{j, l})){
          ans.insert(j);
          ans.insert(l); 
        }
      }
    }
  }
  std::cout << ans.size() << std::endl;
  return 0;
}

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

int main() {
    int a, b; cin >> a >> b;
    string s1(b, a + '0'), s2(a, b + '0');
    if (s1 < s2) {
        cout << s1 << "\n";
    } else {
        cout << s2 << "\n";
    }
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int n;
void inc(int &a){(a += n) %= n;}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    ll ans = 0;
    multiset<pair<ll, int> > ms;
    vector<ll> a(n), b(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    for(int i=0;i<n;i++) ms.insert({b[i], i});
    while(!ms.empty()){
    	auto itr = ms.end();
    	itr--;
    	if(itr->first == a[itr->second]){
    		ms.erase(itr);
    		continue;
    	}
    	if(itr->first < a[itr->second]){
    		cout << -1 << endl;
    		return 0;
    	}
    	int le = itr->second - 1, ri = itr->second + 1;
    	inc(le);
    	inc(ri);
        ll num = b[le] + b[ri];
    	ll m = (itr->first - a[itr->second]) / num;
    	if(m == 0){
    		cout << -1 << endl;
    		return 0;
    	}
    	ans += m;
    	m *= num;
    	m = itr->first - m;
    	num = itr->second;
    	b[num] = m;
    	ms.erase(itr);
    	if(m > a[num])ms.insert({m, num});
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 18776
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxm = 6, maxd = 1 << 5 | 1, maxs = (int)1e3 + 1;
int dfs(int n, int tot, int upp, int sta, vector<int> &msk) {
	if((int)msk.size() == tot) {
		bool chk = 1;
		vector<int> perm(n);
		iota(perm.begin(), perm.end(), 0);
		static int tim = 0, vis[maxd] = {};
		++tim;
		for(int x : msk)
			vis[x] = tim;
		while(chk && next_permutation(perm.begin(), perm.end())) {
			bool same = 1;
			for(int x : msk) {
				int y = 0;
				for(int i = 0; i < n; ++i, x >>= 1)
					if(x & 1)
						y |= 1 << perm[i];
				if(vis[y] != tim) {
					same = 0;
					break;
				}
			}
			chk &= !same;
		}
		if(chk) {
			// for(int x : best) {
			// 	for(int j = 0; j < n; ++j, x >>= 1)
			// 		printf("%d", x & 1);
			// 	puts("");
			// }
			// puts("");
		}
		return chk;
	}
	int ret = 0;
	msk.push_back(0);
	for( ; sta < (1 << n) && ret < upp; ++sta) {
		msk.back() = sta;
		ret += dfs(n, tot, upp, sta + 1, msk);
	}
	msk.pop_back();
	return ret < upp ? ret : upp;
}
int solve1(LL n, int m) {
	if(n < m)
		return solve1(m, n);
	if(n > (1LL << m) - n)
		return solve1((1LL << m) - n, m);
	if(m > 5)
		return maxs;
	int prd = 1;
	for(int i = 1; i <= m; ++i)
		prd *= i;
	int upp = (maxs - 1) * prd + 1;
	vector<int> msk;
	int ret = dfs(m, n, upp, 0, msk);
	return ret < upp ? ret / prd : maxs;
}
set<vector<int> > Hash;
int dfs2(int n, int tot, int sta, vector<int> &msk, bool sp) {
	if((int)msk.size() == tot) {
		if(!sp)
			return 0;
		bool chk = 1;
		vector<int> perm(n), best = msk;
		iota(perm.begin(), perm.end(), 0);
		while(chk && next_permutation(perm.begin(), perm.end())) {
			vector<int> tmp;
			for(int x : msk) {
				int y = 0;
				for(int i = 0; i < n; ++i, x >>= 1)
					if(x & 1)
						y |= 1 << perm[i];
				tmp.push_back(y);
			}
			sort(tmp.begin(), tmp.end());
			chk &= msk != tmp;
			best = min(best, tmp);
		}
		chk &= !Hash.count(best);
		if(chk) {
			Hash.insert(best);
			// for(int x : best) {
			// 	for(int j = 0; j < n; ++j, x >>= 1)
			// 		printf("%d", x & 1);
			// 	puts("");
			// }
			// puts("");
		}
		return chk;
	}
	int ret = 0;
	msk.push_back(0);
	for( ; sta < (1 << n) && ret < maxs; ++sta) {
		msk.back() = sta;
		ret += dfs2(n, tot, sta, msk, sp || ((int)msk.size() > 2 && msk[msk.size() - 2] == sta));
	}
	msk.pop_back();
	return ret < maxs ? ret : maxs;
}
int solve2(int n, int m) {
	// printf("dangerous (%d, %d)\n", n, m);
	if(n == 4) {
		/*
			1100
			1100
			1010
		*/
		return 1;
	}
	if(n == 7) {
		/*
			1110000
			1110000
			1001100
			1101010

			1110000
			1101100
			1101100
			1011010
		*/
		return 2;
	}
	if(n == 8) {
		return 0;
	}
	// unreachable
	Hash.clear();
	vector<int> msk;
	return dfs2(n, m, 0, msk, 0);
}
int main() {
	LL n;
	int m = 0;
	scanf("%lld", &n);
	vector<int> dp = {0};
	for(int i = 1; i < n; ++i) {
		for(int j = 0; j < i; ++j)
			if((1 << j) - i >= dp[j]) {
				dp.push_back(j);
				break;
			}
		// assert((int)dp.size() == i + 1);
		if((1LL << i) - n >= dp.back()) {
			m = i;
			break;
		}
	}
	int ans = solve1(n, m);
	if(ans < maxs && n * 2 <= (1LL << m))
		ans += solve2(n, m);
	printf("%d\n", ans < maxs ? ans : -1);
	return 0;
}

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

#define INF ((1<<30)-1)  //int32_t
#define MOD 1000000007
#define MOD2  

#define all(a)  (a).begin(),(a).end()

#define mkp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;



int main(){
    bool flag=true;
    ll ans=0;

    int n;
    cin >>n;
    ll sum[n];
    map<ll,int> m;

    cin  >> sum[0];
    m[sum[0]]++;

    for (int i = 1; i < n; i++){
        int a;
        cin >> a;
        sum[i] = sum[i-1] + a;
        m[sum[i]]++;
    }
    

    for(pii s : m){
        ll x = s.second;
        ll add=0;
        if(s.first == 0)add = x*(x+1)/2;
        else add = x*(x-1)/2;
        ans += add;

        //cout <<s.first<<"::"<<x <<"-> "<<add<<endl;
    }


    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 14336
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const int MOD = 1000000007;
using namespace std;

int main(){
    int n; cin >> n;
    double ans = 0;
    vector<int> x(n), y(n);
    REP(i, n) cin >> x[i] >> y[i];
    REP(i, n){
        for(int j = i + 1; j < n; ++j){
            ans += 2 * sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j])) / n;
        }
    }
    
    cout << fixed << setprecision(10) << ans << "\n";
    return 0;
}

Measured memory_bytes: 256