akhauriyash/Code-Regression huggingface dataset:
#n=int(input())
a,b=map(int,input().split())
#al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(m)]

import fractions
gcd=fractions.gcd(a,b)#最大公約数
lcm=(a*b)//fractions.gcd(a,b)#最小公倍数
print(lcm)


Measured memory_bytes: 5304
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;
#define downque(que)  priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;


int main(){
  int n; cin>>n;
  ll t[n];
  ll a[n];
  REP(i,n)cin>>t[i]>>a[i];

  for(int i=1;i<n;i++){
  
    ll ft=t[i-1]; ll fa=a[i-1]; 
    ll pt=t[i]; ll pa=a[i]; 
     ll p=ft/pt+(ft%pt==0? 0:1);
     ll q=fa/pa+(fa%pa==0? 0:1);
    if(ft>pt&&fa>pa){
      t[i]=t[i]*max(p,q);
      a[i]=a[i]*max(p,q);
    }else if(ft>pt){
      t[i]=t[i]*p;
       a[i]=a[i]*p;

    }else if(fa>pa){
      a[i]=a[i]*q;
       t[i]=t[i]*q;
    }
    //cout<<i<<':'<<t[i]<<' '<<a[i]<<endl;
  }

  cout<<t[n-1]+a[n-1]<<endl;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
    ll n;cin>>n;
    vl a(n);
    rep(i,n){
        cin>>a[i];
    }
    map<int,int>b;
    rep(i,n){
        b[a[i]]++;
    }
    sort(all(a));
    a.erase(unique(all(a)),a.end());
    int ans=0;
    rep(i,a.size()){
        if(b[a[i]]%2==1)ans++;
    }
    cout<<ans<<endl;
}

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

using ll = long long;

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

ll lcm(ll a, ll b)
{
  ll g = gcd(a, b);
  return (a / g) * b;
}

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

  ll ans = 1LL;
  for (int i = 0; i < N; i++) {
    ll t;
    cin >> t;
    ans = lcm(ans, t);
  }
  cout << ans << endl;

  return 0;
}


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

void solve() {
	int n;
	cin >> n;
	ll a[n], base[65];
	memset(base, 0, sizeof base);
	for(int i = 0; i < n; ++i)cin >> a[i];
	string s; cin >> s;
	for(int i = n - 1; ~i; --i) {
		bool contains = true;
		for(int bit = 0; bit < 61; ++bit) {
			if(a[i] >> bit & 1) {
				if(!base[bit]) {
					contains = false;
					base[bit] = a[i];
					break;
				}
				a[i] ^= base[bit];
			}
		}
		if(!contains) {
			if(s[i] == '1') {
				cout << "1\n";
				return;
			}
		}
	}
	cout << "0\n";
}

int main() {
	int t; cin >> t;
	while(t--) {
		solve();
	}
}

Measured memory_bytes: 3512
while True:
    a, op, b = input().split()   # 3変数ともに文字列として読み込む
    a =int(a)                   # a を整数に変換
    b =int(b)                   # b を整数に変換


    if op=="?": # opが"?"の時は終了
        break
    else:    #opが"?"以外の時
        # ここ処理を書いてください
        # else のなかです。この通りのインデントを付けてください。
        if op =="+":
            print(a+b)

        elif op=="-":
              print(a-b)

        elif op=="*":
              print(a*b)

        elif op=="/":
              import math
              print(math.floor(a/b))
        else:
          print()


Measured memory_bytes: 5664
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
  uint32_t N = 0;
  std::cin >> N;

  std::vector<uint32_t> a(N);
  for (uint32_t n = 0; n < N; n++) std::cin >> a[n];
  std::sort(a.begin(), a.end(), std::greater<uint32_t>());

  uint32_t alice = 0, bob = 0;
  for (uint32_t i = 0; i < N; i++) {
    if (i % 2 == 0) {
      alice += a[i];
    } else {
      bob += a[i];
    }
  }

  std::cout << alice - bob << std::endl;

  return 0;
}

Measured memory_bytes: 256
from bisect import bisect_left
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
t = [[] for _ in range(n)]
for p, y in data:
  t[p - 1].append(y)
for i in range(n):
  t[i].sort()
for p, y in data:
  nth = bisect_left(t[p - 1], y) + 1
  print("%06d%06d" % (p, nth))


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

using namespace std;

int main(){
	int n;
  	double d;
  	cin >> n >> d;
  	int cnt = 0;
  	int x,y;
  	for(int i=0;i<n;i++){
    	cin >> x >> y;
      	if(sqrt(pow(x,2) + pow(y,2)) <= d){
        	cnt++;
        }
    }
  	cout << cnt << endl;
}

Measured memory_bytes: 3784
/*{{{*/
#include <bits/stdc++.h>
#ifdef _GLIBCXX_DEBUG
int c_;
#define cout (c_?cerr:cout)
#define dbg(...) {if(!c_)cerr<<"\033[96;1m";++c_;\
__VA_ARGS__;--c_; if(!c_)cerr<<"\033[0m";}
#else
#define dbg(...)
#endif
#define st first
#define nd second
#define all(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()
#define dump(...) dbg(print(#__VA_ARGS__, __VA_ARGS__))
#define dump_range(...) dbg(cerr<<#__VA_ARGS__<<": ";print_range(__VA_ARGS__))
using namespace std; using ll = long long; 
template< typename t > using V = vector< t >; void print(){cout<<'\n';}
template< typename t, typename... v > void print(const t& a, v&&... b)
{cout << a << ' '; print(b...);}
template< typename t > void print_range(t a, const t& b)
{while (a!=b) cout << (*a++) << ' '; cout << '\n';}
/*}}}*/



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

    int a, b, c;
    cin >> a >> b >> c;
    ll k; cin >> k;
    print(k & 1? b - a : a - b);
}

Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    A = set(map(int, input().split()))


    cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    B = []
    for i in range(1, 10):
        if i in A:
            B.append((cost[i], i))

    B = B[::-1]
    dp = [[-1, -1] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        for x, y in B:
            if i >= x and dp[i-x][0] >= 0:
                if dp[i][0] < dp[i-x][0] + 1:
                    dp[i][0] = dp[i-x][0] + 1
                    dp[i][1] = y
    id = N
    ans = []
    # print(dp)
    while(id > 0):
        ans.append(dp[id][1])
        id -= cost[dp[id][1]]
    ans.sort(reverse=True)
    print("".join(map(str, ans)))
main()

Measured memory_bytes: 4692
#include <iostream>
#include <vector>
#include <cstdint>

int main()
{
	std::uint32_t n;
	while (std::cin >> n) {
		std::uint32_t num_prime = (n > 1) ? 1 : 0;
		std::vector<std::uint8_t> is_prime(n / 2, true);
		for (std::uint32_t i = 3; i < n + 1; i += 2) {
			if (is_prime[i / 2 - 1]) {
				++num_prime;
				for (std::uint32_t j = 3 * i; j < n + 1; j += i + i) {
					is_prime[j / 2 - 1] = false;
				}
			}
		}
		std::cout << num_prime << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1712
#include <stdio.h>

int main(void)
{
	int n;
	int c = 0;
	
	while (1) {
		scanf("%d", &n);
		
		if (n == 0) {
			break;
		}
		while (n != 1) {
			if (n % 2 == 0) {
				n = n / 2;
			}
			else if (n % 2 == 1) {
				n = (n * 3) + 1;
			}
			c++;
		}
		printf("%d\n", c);
		c = 0;
	}
	
	return (0);
}

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

const int MAX_N = 1e5 + 10;

int A[MAX_N], left_g[MAX_N], right_g[MAX_N];

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) {
        left_g[i] = calc_gcd(A[i], left_g[i - 1]);
    }
    for (int i = N; i >= 1; i--) {
        right_g[i] = calc_gcd(A[i], right_g[i + 1]);
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, calc_gcd(left_g[i - 1], right_g[i + 1]));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 


public class Main {
	private static Scanner sc = new Scanner(System.in);
	//result = Math.pow(num1, num3)
	//StringBuffer str = new StringBuffer(hoge1);
	//String hoge2 = str.reverse().toString();
	//map.containsKey(A)

	//Map<String, Integer> map = new HashMap<String, Integer>(n);
	/*for ( キーのデータ型 key : マップの名前.keySet() ) {
		データのデータ型 data = マップの名前.get( key );
		
		// keyやdataを使った処理;
	}*/
	//int i = Integer.parseInt(s);
	//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek
	//Deque<String> qq=new ArrayDeque<>();//push,pop,peek
	//ArrayList<String> cc = new ArrayList<>(n);
	//Collections.sort(list);
	//Array.sort(list);   cc.contains(tmp)
	//Arrays.asList(c).contains("a")
	//list.set(1,"walk");//1 1 2 3 5
	static long mod =1000000007;
	//static 	ArrayList<Integer> cc = new ArrayList<>(100);
	static int N;
	public static void main(String[] args) {
		//0 48 || 1 49 || B 66
		int N=sc.nextInt();
		int K=sc.nextInt();

		int ans=0;
		int g=0;
		while(true) {
			ans++;
			g+=K;
			if(g>=N)break;
			g--;
		}
		p(ans);
		
		
		
		
	}
	static int a,b,c;
	
	
	
	
	/*static boolean v(int i,long sum1,long sum2) {
		if(i==N) {
			long b=Math.abs(sum1-sum2);
			if(b==0) {
				if(sum1<=K) {
					return true;
				}else return false;
			}else if(b%D==0) {
				if(Math.max(sum1, sum2)<=K)return true;
				else return false;
			}
			else return false;
		}
		
		if(v(i+1,sum1,sum2+v[i]%D))return true;
		
		if(v(i+1,sum1+D-v[i]%D,sum2))return true;
		return false;
		
	}*/
	
	
	
	
	

	


	
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p() {System.out.println();};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
	public static int gcd(int a, int b) {
        return b == 0 ? a: gcd(b, a % b);
	}
	static String nextPermutation(String s) {
		ArrayList<Character> list=new ArrayList<>();
		for(int i=0;i<s.length();i++) {
			list.add(s.charAt(i));
		}
		int pivotPos=-1;
		char pivot=0;
		for(int i=list.size()-2;i>=0;i--) {
			if(list.get(i)<list.get(i+1)) {
				pivotPos=i;
				pivot=list.get(i);
				break;
			}
		}
		if(pivotPos==-1&&pivot==0) {
			return "Final";
		}
		int L=pivotPos+1,R=list.size()-1;
		
		
		
		int minPos=-1;
		char min =Character.MAX_VALUE;
		
		for(int i=R;i>=L;i--) {
			if(pivot<list.get(i)) {
				if(list.get(i)<min) {
					min=list.get(i);
					minPos=i;
				}
			}
		}
		
		Collections.swap(list, pivotPos, minPos);
		Collections.sort(list.subList(L, R+1));
		
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<list.size();i++) {
			sb.append(list.get(i));
		}
		return sb.toString();
	}
}
	


Measured memory_bytes: 23380
#include<bits/stdc++.h>
using namespace std;
string up = "QWERTYUIOPLKJHGFDSAZXCVBNM";
string down = "qwertyuioplkjhgfdsazxcvbnm";
signed main(){
    char x;
    cin>>x;
    for(int i=0;i<26;i++){
        if(x==up[i]){
            cout<<'A';
            return 0;
        }
        if(x==down[i]){
            cout<<'a';
            return 0;
        }
    }
}


Measured memory_bytes: 3616
from collections import defaultdict

N, K = map(int, input().split())
As = map(int, input().split())

counts = defaultdict(int)
for a in As:
    counts[a] += 1

counts = sorted(counts.values())

if len(counts) <= K:
    print(0)
else:
    total = 0
    for i in range(len(counts) - K):
        total += counts[i]
    print(total)

Measured memory_bytes: 41500
#include <iostream>
#include <vector>
#include <map>
#include <set>

int main()
{
	unsigned long long N, M;
	std::cin >> N >> M;

	std::vector<int> pi(M);
	std::vector<std::string> Si(M);
	std::set<unsigned long long> ACResults;
	for (int i = 0; i < M; ++i) {
		std::cin >> pi[i] >> Si[i];

		if (Si[i] == "AC") {
			ACResults.insert(pi[i]);
		}
	}



	unsigned long long WACount = 0;

	std::set<unsigned long long> ACs;
	for (int i = 0; i < M; ++i) {
		if (ACs.find(pi[i]) != ACs.end()) {
			continue;
		}

		if (Si[i] == "AC") {
			ACs.insert(pi[i]);
			continue;
		}

		if (ACResults.find(pi[i]) != ACResults.end()) {
			++WACount;
		}
	}

	std::cout << ACResults.size() << ' ' << WACount << std::endl;

	return 0;
}

Measured memory_bytes: 15488
n = int(input())
a = list(map(int, input().split()))
color = []
free = 0
for x in a:
    if x < 400:color.append("g")
    elif x < 800:color.append("b")
    elif x < 1200:color.append("gr")
    elif x < 1600:color.append("bl1")
    elif x < 2000:color.append("bl2")
    elif x < 2400:color.append("y")
    elif x < 2800:color.append("o")
    elif x < 3200:color.append("r")
    else: free += 1
color = list(set(color))
ans = len(color)
if ans == 0 and free > 0: ans = 1
print(ans, len(color) + free)

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define REP(i, start, end) for (ll i = start, i##Len = (end); i < i##Len; ++i)
#define REPR(i, start, end) for (ll i = start, i##Len = (end); i > i##Len; --i)
using ll = long long;
using namespace std;

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

    int L, R, d;
    cin >> L >> R >> d;
    cout << R / d - (L - 1) / d << endl;
}


Measured memory_bytes: 3648
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
v=[-1]*n
v[0]=0
q=deque([0])
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
z=0
for i in v:
    if i==0:
        z+=1
ans=[0]*n
if z<=n//3:
    j=3
    for i in range(n):
        if v[i]==0:
            ans[i]=j
            j+=3
    j=1
    for i in range(n):
        if ans[i]==0:
            ans[i]=j
            j+=1
            if j%3==0 and j//3<=z:
                j+=1
    print(*ans)
elif n-z<=n//3:
    j=3
    for i in range(n):
        if v[i]==1:
            ans[i]=j
            j+=3
    j=1
    for i in range(n):
        if ans[i]==0:
            ans[i]=j
            j+=1
            if j%3==0 and j//3<=n-z:
                j+=1
    print(*ans)
else:
    o=1
    t=2
    tt=3
    for i in range(n):
        if v[i]==0 and o<=n:
            ans[i]=o
            o+=3
        elif v[i]==0:
            ans[i]=tt
            tt+=3
        if v[i]==1 and t<=n:
            ans[i]=t
            t+=3
        elif v[i]==1:
            ans[i]=tt
            tt+=3
    print(*ans)


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

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

typedef long long ll;

typedef double T;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<T> vt;
typedef vector<vt> vvt;
typedef vector<pii> vpi;
typedef vector<pii> vpl;
typedef vector<vpi> graph;
typedef complex<T> Pt;
typedef pair<Pt, Pt> Line;

const ll MOD = 1e9 + 7; // 998244353;
const T EPS = 1e-10;
const int INF = 1e9 + 1;

/* Mod Library */

struct Mod {
    ll x;
    Mod (ll x = 0) : x(x) {}
    Mod operator+(Mod b) { return Mod((x + b.x)%MOD); }
    Mod operator-(Mod b) { return Mod((x - b.x + MOD)%MOD); }
    Mod operator*(Mod b) { return Mod((x * b.x)%MOD); }
    Mod operator/(Mod b) { return *this * inverse(b); }
    Mod operator%(Mod b) { return Mod(x % b.x); }

    static ll euclid(ll a, ll b, ll &x, ll &y) {
        if (b) {
            ll d = euclid(b, a%b, y, x);
            y -= a/b*x;
            return d;
        }
        x = 1; 
        y = 0;
        return a;
    }
    
    Mod inverse(Mod a) {
        ll x, y, g = euclid(a.x, MOD, x, y);
        assert(g == 1);
        return Mod((x + MOD)%MOD);
    }

    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this^(e/2);
        r = r*r;
        return e&1 ? *this*r : r;
    }
};

/* Input Library */
template <typename A, typename B>
istream& operator>>(istream &in, pair<A, B> &p) {
    in >> p.first >> p.second;
    return in;
}

template <typename A, typename B>
ostream& operator<<(ostream &out, pair<A, B> &p) {
    out << p.first << " " << p.second;
    return out;
}

template <typename I>
istream& operator>>(istream &in, vector<I> &a) {
    trav(i, a) in >> i;
    return in;
}

template <typename I>
ostream& operator<<(ostream &out, vector<I> &a) {
    rep(i, 0, sz(a)) {
        if (i) out << " ";
        out << a[i];
    }
    return out;
}

void fast_io() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    //cout.tie(0);
    cin.exceptions(cin.failbit);
} 

void solve_test() {
  int n;
  cin >> n;
  vi a(n);
  cin >> a;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (i%2 == 0 && a[i]%2) {
      ++ans;
    }
  }
  cout << ans << endl;
}

void setup() {
}

int main() {
    setup();
    srand(time(0));
    fast_io();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve_test();
    }
}


Measured memory_bytes: 3660
INF = 10**12

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [INF]*(N)
dp[0]=0
for i in range(1,N,1):
    for j in range(max(0,i-K),i,1):
        dp[i]= min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[N-1])


Measured memory_bytes: 84756
#include <iostream>
#include <cstdio>

using namespace std;

int compare (string s, string t )
{
	int slen = s.length();
	int tlen = t.length();
	int res = 0;

	// sÍ»ÌÜÜ t ð¸ç·
	for (int i = 0; i < slen; i++ ){
		int curr = 0;
		for (int j = 0; j < tlen; j++ ){
			if (i+j == slen )
				break;
			if (s[i+j] == t[j] ){
				curr++;
			}else{
				if (res < curr ) res = curr;
				curr = 0;
			} // end if
		} // end for
		if (curr && res < curr ) res = curr;
	} // end for

	return res;
}

int main()
{
	string s,t;
	while (cin >> s >> t ){
		int res1 = compare (s, t );
		int res2 = compare (t, s );
		printf ("%d\n", (res1 < res2 ? res2 : res1 ) );
	} // end loop
		
	return 0;
}

Measured memory_bytes: 944
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <functional>
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;

    set<int> a[26];

    for(int i = 0;i < n;i++){
        a[s[i]-'a'].insert(i);
    }

    int q;
    cin >> q;
    vector<int> ans;
    for(int i = 0;i < q;i++){
        int kind;
        cin >> kind;
        if(kind == 1){
            int pos;
            cin >> pos;
            pos--;
            char c;
            cin >> c;
            for(int j = 0;j < 26;j++){
                if(a[j].find(pos) != a[j].end()){
                    a[j].erase(pos);
                    a[c-'a'].insert(pos);
                }
            }
        }
        else{
            int l,r;
            cin >> l >> r;
            l--,r--;
            int cnt = 0;
            for(int j = 0;j < 26;j++){
                auto p = a[j].lower_bound(l);
                if(p != a[j].end() && *p <= r)cnt++;
            }
            ans.push_back(cnt);
        }
    }

    for(int num:ans)cout << num << endl;
}


Measured memory_bytes: 24452
#include <bits/stdc++.h>
const int INF = 1e9;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;

#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define ALL(obj) (obj).begin(),(obj).end()

#define rt return
#define ENDL cout<<endl
#define s second
#define f first

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    LL from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};
int main(){
    LL N;cin >> N;
    for(LL a = 1;a <= 4000;a++){
        for(LL b = 1;b <= 4000;b++){
            if((4*a*b-N*b-N*a) == 0 )continue;
            if((N * a * b )/(4*a*b-N*b-N*a) <= 0)continue;
            if((N * a * b )%(4*a*b-N*b-N*a) == 0){
                cout<<a<<" "<<b<<" "<<(N * a * b )/(4*a*b-N*b-N*a)<<endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
from collections import Counter


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


n,p=map(int,input().split())
A=Counter(prime_factorize(p)).items()
cnt=1
for i,j in A:
    cnt *=pow(i,j//n)
print(cnt)

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

#define ll long long
#define MOD 1000000007
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define INF (ll)1e9
#define fora(i,a,b) for(ll i=a;i<b;i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp(x,y) make_pair(x,y)
#define mli map<ll,int>
#define mll map<ll,ll>

using namespace std;

int main()
{   ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n,pos,cnt=0;
    cin>>n;
    pos=n-1;
    vll v(n);
    fora(i,0,n)
    cin>>v[i];
    sort(all(v));
    fora(i,0,n-1)
    {
        if(i==0)
        {
            cnt+=v[pos];
            pos--;
        }
        else
        {
            cnt+=v[pos];
            if(i%2==0)
            pos--;
        }
        
    }
    cout<<cnt<<endl;
    return 0;
}




Measured memory_bytes: 4788
#include <iostream>
#include <functional>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int N, M;
vector<long long> X;
vector<tuple<long long, int, int>> edges;

class UnionFind {
    int n;
    vector<int> par;
    vector<int> rank;
public:
    vector<long long> sm;
    vector<long long> cnt;

    UnionFind(int a) : n(a), rank(a, 0) {
        par.reserve(n);
        for (int i = 0; i < a; i++) par.push_back(i);
        sm.resize(n, 0);
        cnt.resize(n, 0);
        for(int i=0; i<n; i++)
            sm[i] = X[i];
    }
    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if(x_root == y_root){
            cnt[x_root]++;
            return;
        }
        if (rank[x_root] > rank[y_root]) {
            par[y_root] = x_root;
            cnt[x_root] += cnt[y_root] + 1;
            sm[x_root] += sm[y_root];
        } else if (rank[x_root] < rank[y_root]) {
            par[x_root] = y_root;
            cnt[y_root] += cnt[x_root] + 1;
            sm[y_root] += sm[x_root];
        } else if (x_root != y_root) {
            par[y_root] = x_root;
            rank[x_root]++;
            cnt[x_root] += cnt[y_root] + 1;
            sm[x_root] += sm[y_root];
        }
    }
    bool same(int x, int y) { return find(x) == find(y); }
    long long get_sum(int x) { return sm[find(x)]; }
    long long get_cnt(int x) { return cnt[find(x)]; }
    void reset_cnt(int x) { cnt[find(x)] = 0; }
};

int main(){
    cin >> N >> M;
    X.resize(N);
    edges.resize(M);
    for(int i=0; i<N; i++)
        cin >> X[i];

    UnionFind uf(N);

    for(int i=0; i<M; i++){
        int A, B;
        long long Y;
        cin >> A >> B >> Y;
        A--; B--;
        edges[i] = make_tuple(Y, A, B);
    }
    sort(edges.begin(), edges.end());

    long long ans = 0;
    for(auto edge : edges){
        int A, B;
        long long Y;
        tie(Y, A, B) = edge;
        uf.unite(A, B);

        if(Y <= uf.get_sum(A)){
            ans += uf.get_cnt(A);
            uf.reset_cnt(A);
        }
    }
    cout << M - ans << endl;
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define fi        first
#define se        second
#define PI        acos(-1)
#define LC(a)     ((a<<1))
#define RC(a)     ((a<<1)+1)
#define MID(a,b)  ((a+b)>>1)
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<ll,ll>   PLL;
typedef pair<ll,int>  PLI;
const int INF = 0X3F3F3F3F;
const int MIN = -(1<<30);
const ll N = 2e5+7;
int a[N];
double b[N];
double c[N];
int main()
{
	IOS();

	int n,k;
	cin>>n>>k;
	double cnt = 0;
	c[0] = 0;
	double ans = 0;
	for(int i = 1; i<=n; i++)
	{
		cin>>a[i];
		b[i]=(1+a[i])/2.0;
		cnt += b[i];
		c[i] = cnt;
		if(i>=k)
		{
			ans = max(ans,c[i]-c[i-k]);
		}
	}
	printf("%.6lf\n",ans);










	return 0;
}



Measured memory_bytes: 4224
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
ll X,T;
int main() {
	cin>>X>>T;

	if(X>T)cout<<X-T<<endl;
	else cout<<0<<endl;

	return 0;
}


Measured memory_bytes: 256
N, A, B, C = map(int, input().split())
L = [int(input()) for i in range(N)]


def dfs(cur, a, b, c):
    if cur == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30\
            if 0 < min(a, b, c) else int(1e9+7)

    ret1 = dfs(cur + 1, a + L[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + L[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + L[cur]) + 10
    ret4 = dfs(cur + 1, a, b, c)

    return min(ret1, ret2, ret3, ret4)


def main():
    print(dfs(0, 0, 0, 0))


main()


Measured memory_bytes: 3064
using System;
using System.Linq;

namespace atcoder
{
    public class atcoder
    {
        public static void Main()
        {
            int[] input = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            int count = 0;
            for (int i = 1; i <= 3; i++) {
                if ((input[0] * input[1] * i) % 2 != 0) break;
                count++;
            }
            if (count < 3) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}
 

Measured memory_bytes: 13268
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define outl(x) cout<< (x) << '\n'
#define fi first
#define se second
using pii = pair<int,int>;
using ll = long long;
using vi = vector<int>;

int main()
{
    cin.tie(0), ios::sync_with_stdio(false);
    int x, a, b;
    cin >> x >> a >> b;

    if (abs(x-a) < abs(x-b)) {
        outl("A");
    }
    else {
        outl("B");
    }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int master[30];

int main()
{
	int n;
	read(n);
	if(n == 3){
		puts("2 5 63");
		return 0;
	} else if(n == 4){
		puts("2 5 20 63");
		return 0;
	}
	if(n <= 15000){
		if(n%3 == 0){
			for(int i=1; i<=(n-4); ++i) printf("%d ", 2*i);
			puts("3 9 15 21");
		} else {
			for(int i=1; i<=(n-2); ++i) printf("%d ", 2*i);
			puts("3 9");
		}
		return 0;
	}
	ll s = 0; int cnt = 0;
	for(int i=0; i<30; ++i) master[i] = -1;
	
	for(int i=2; i<=30000; ++i){
		if(i%2==0 || i%3==0 || i%5==0){
			if(master[i%30] == -1){
				master[i%30] = i;
			} else if(cnt < n-2){
				printf("%d ", i);
				(s += i) %= 30;
				++cnt;
			}
		}
	}
	for(int i=0; i<30; ++i) for(int j=i+1; j<30; ++j){
		if((s+i+j)%30 == 0 && master[i]!=-1 && master[j]!=-1){
			printf("%d %d\n", master[i], master[j]);
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 384
from bisect import bisect_right
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def pf(x):
    ee=[]
    pp=[]
    if x&1==0:
        k=(x&-x).bit_length()-1
        pp.append(2)
        ee.append(k)
        x>>=k
    d=3
    while d**2<=x:
        while x%d==0:
            x//=d
            if pp and pp[-1]==d:ee[-1]+=1
            else:
                pp.append(d)
                ee.append(1)
        d+=2

    if x>1:
        if pp and pp[-1] == x: ee[-1] += 1
        else:ee.append(1)

    return ee

def main():
    n=II()
    ss=[1]
    for a in range(2,45):ss.append(ss[-1]+a)
    #print(ss)
    ee=pf(n)
    #print(ee)
    ans=0
    for e in ee:
        i=bisect_right(ss,e)
        ans+=i
    print(ans)

main()

Measured memory_bytes: 9300
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);
using namespace std;
int main(){
	fast;
	int a,b,c;
	cin>>a>>b>>c;
	int i=a;
	while(c!=0){
		if(a%i==0&&b%i==0)c--;
		i--;
	}
	cout<<i+1;
}

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

int main() {
  int n;
  cin >> n;
  int ans = n * (n + 1) / 2;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin >> s;
  int s_size = s.size();
  for(int i=0;i<s_size/2+s_size%2;i++){
    cout << s[i*2];
  }
  cout<< endl;
}

Measured memory_bytes: 512
from sys import stdin
from collections import defaultdict
input = stdin.readline
# ~ T = int(input())
T = 1
for t in range(1,T + 1):
	n,k = map(int,input().split())
	_input = []
	for i in range(n):
		_input.append(int(input()))
	_input.sort()
	min_ans = 10000000000
	for i in range(k - 1,len(_input)):
		min_ans = min(min_ans,_input[i] - _input[i - k + 1])
	print(min_ans)


Measured memory_bytes: 13376
//
//  main.cpp
//  競技20190629

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <regex> //正規表現
#include <map>
#include <set>
#include <cassert> //assart
using namespace std;
#define ll long long int
#define FOR(i,min,max) for(int i=(min);i<(max);i++)
#define FOReq(i,min,max) for(int i=(min);i<=(max);i++)
#define FORREV(i,max,min) for(int i=(max)-1;i>=(min);i--)
const int  MOD=1000000007;
const int  INF=2000000000;
const int INF2=  10000000;
const double  Micro=1e-5;

int UnUsedVariable(){
    if(INF || Micro || MOD || INF2){;}
    return 0;
}

#define pf printf
#define sf scanf
#define inarray(array,min,max) FOR(i,min,max){in(array[i]);}
#define inarrayW(arrayA,arrayB,min,max) FOR(i,min,max){in(arrayA[i]);in(arrayB[i]);}
inline int isEven(int x){return x%2==0;}
inline int isOdd (int x){return x%2==1;}
#define br printf("\n");

//#define int long long int

/*
 1.困った時こそ冷静に問題文を見直す！制約条件を見ろ！乱択アルゴリズムとかO(N^3)とか！
 2.一度に大量のことをやろうとしない。デバッグしやすいように細かく！
 3.プログラミングは半分数学だし、もう半分は数学ではない！
 4.できない問題はできない！！！！！
 */

int tekitou(){
    int a,b,c;
    cin>>a>>b>>c;
    pf("%d\n",min(c,b/a));
    return 0;
}
signed main(){
    assert(1);
    tekitou();
    //Ap();
    //Bp();
    //Cp();
    //Dp();
    //Ep();
    //Fp();
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	
	int n, a, b;
	
	scanf("%d %d %d", &n, &a, &b);
	int sum = 0;
	for(int i = 1; i <= n; i++){
		int digitSum = 0;
		int temp = i;
		while (temp != 0){
			digitSum = digitSum + temp % 10;
			temp /= 10;
		}
		if(digitSum >= a && digitSum <= b){
			sum += i;
		}
	}
	printf("%d", sum);
	
	return 0;
}

Measured memory_bytes: 1704
i = input()
i = i.split(' ')
l = []
while len(l)<int(i[0]):
  l += [0]

lim = int(i[1])

i = input()
i = i.split(' ')
for j in list(range(len(l))):
    i[j]=int(i[j])


count=0
while count<lim:
    count += 1
    k = input()
    k = k.split(' ')
    if i[int(k[0])-1]==i[int(k[1])-1]:
        l[int(k[1])-1] = 1
        l[int(k[0])-1] = 1
    elif i[int(k[0])-1]>i[int(k[1])-1]:
        l[int(k[1])-1] = 1
    else:
        l[int(k[0])-1] = 1

count = 0
for j in l:
    if j==0:
        count += 1
print(count)
  


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

int main()
{
  string s;
  cin >> s;
  int n = s.size();
  long ans = 0;
  long tmp = 0;
  for (int i = 0; i < n - 2; i++)
  {
    if (s.at(i) == 'A')
    {
      tmp++;
    }
    else
    {
      tmp = 0;
    }
    if (s.at(i) == 'A' && s.at(i + 1) == 'B' && s.at(i + 2) == 'C')
    {
      s.at(i + 2) = 'A';
      ans += tmp;
      tmp--;
      i += 1;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
N=int(input())

answers=[]
counts=[]


for i in range(N):
    A=int(input())
    answer=[]
    for a in range(A):
        x,y=map(int,input().split())
        answer.append([x,y])
    answers.append(answer)

#print(answers)
for i in range(pow(2,N)):
    hypo=str(bin(i))[2:].rjust(N,"0")
    judge=True
    count=0
    #print(hypo)
    for n in range(N):
        if judge==False:
            break
        elif hypo[n]=="1":
            count+=1
            for ans in answers[n]:
                if hypo[ans[0]-1]==str(ans[1]):
                    pass
                else:
                    judge=False
                    break
    if judge==False:
        pass
    else:
        counts.append(count)
#print(counts)
print(max(counts))

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

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORTASC(c) sort((c).begin(),(c).end())
#define SORTDESC(c,t) sort((c).begin(),(c).end(), std::greater<t>());
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define VMAX(a) *max_element(ALL(a))
#define VMIN(a) *min_element(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double PI  = acos(-1.0);
const long long MOD = 1000000007;

template <class T, class S>
using umap = std::unordered_map<T, S>;
using ll = long long;
using namespace std;

int main() {
    ll n;
    ll p[200010];
    string s;

    cin >> n;

    n %= 10;
    if (n == 3){
        cout << "bon" << endl;
    } else if(n == 0 || n == 1 || n == 6 || n == 8){
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }

    return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <limits.h>
using namespace std;

int main(){
  int N, M, box = 1, check = 1, answer = 0;
  cin >> N >> M ;
  int ans[(N+1)] ;
  int S[M] ;
  int C[M] ;
  for(int i=0;i<M;i++){
      cin >> S[i] >> C[i] ;
  }
  for(int i=1;i<(N+1);i++){
      ans[i] = -1 ;
      for(int j=0;j<M;j++){
          if(S[j] == i){
              if(ans[i] == -1){
                  ans[i] = C[j] ;
              }
              if(ans[i] != C[j]){
                  check = 0 ;
                  break ;
              }
          }
      }
  }
  if( (N > 1) && (ans[1] == 0)) check = 0 ;
  if( (N > 1) && (ans[1] == -1)) ans[1] = 1 ;
  for(int i=N;i>0;i--){
      if(ans[i] != -1) answer += (box * ans[i]) ;
      box *= 10 ;
  }
  
  if( check == 0 ){
    cout << -1 << endl ;
  }  
  else{
    cout << answer << endl ;
  }  
  return 0 ;
}

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

using namespace std;

int main() {
	int n, x, max_h, res = 1;
	cin >> n;
	cin >> x;
	max_h = x;
	--n;
	for (int i = 0; i < n; ++i)
	{
		cin >> x;
		if (x >= max_h)
		{
			max_h = x;
			++res;
		}	
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
x = int(input())

ans = 0
a_lim = min(a, x // 500) + 1
total = x
for i in range(a_lim):
    a_total = total - 500 * i
    b_lim = min(b, a_total // 100) + 1
    for j in range(b_lim):
        b_total = a_total - 100 * j
        if b_total // 50 <= c:
            ans += 1
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll x, n, num;
  cin >> x >> n;
  sl p;
  while(n --> 0) {
    cin >> num;
    p.insert(num);
  }
  
  rep(i, INF) {
    if(!p.count(x-i)) {cout << x-i << newl; return 0;}
    if(!p.count(x+i)) {cout << x+i << newl; return 0;}
  }
}

Measured memory_bytes: 3640
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()
    r = 1
    c = collections.defaultdict(int)
    c[0] = 3
    for b in a:
        r *= c[b]
        r %= mod
        c[b] -= 1
        c[b+1] += 1

    return r


print(main())





Measured memory_bytes: 23040
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define mFOR(i, a, b) for (int i = a; i > b; i--)
#define MP make_pair
#define PB push_back
#define ALL(v) v.begin(), v.end()
#define N 100007
#define INF 1000000007
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll fceil(ll a, ll b) { return (a % b == 0 ? a / b : a / b + 1); }
int main()
{
   int n, k;
   string s;
   cin >> n >> k >> s;
   s[k - 1] = s[k - 1] + 32;
   cout << s << endl;
   return 0;
}


Measured memory_bytes: 256
S = input()
T = input()
Sn = len(S)
Tn = len(T)
ans = 0

for i in range(Sn-Tn+1):
    M = 0
    for j, k in zip(S[i:], T):
        if j == k:
            M += 1
    
    if M > ans:
        ans = M

print(Tn - ans)

Measured memory_bytes: 8972
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<28;
const long long MOD =1000000000+7;
void solve(int a){cout<<( a?"Yes":"No")<<endl;}

vector<int> positionZip(vector<int>zipped){
	vector<int> zip;
	vector<int> ziping;
	for (int i = 0; i < zipped.size(); i++){
		ziping.push_back(zipped[i]);
	}
	sort(ziping.begin(), ziping.end());
	ziping.erase(unique(ziping.begin(), ziping.end()), ziping.end());
	for (int i = 0; i < zipped.size(); i++){
		zip.push_back(lower_bound(ziping.begin(), ziping.end(), zipped[i]) - ziping.begin());
	}
return zip;
}

int main(){
	long long n;
	cin >>n;
	vector<long long>trans(5,0);
	for(int i=0;i<5;i++){
		cin >>trans[i];
	}
	sort(trans.begin(),trans.end());
	long long ans=0;
	cout<< (n+trans[0]-1)/trans[0]+4<<endl;;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <cstdio>
#include <bits/stdc++.h>
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORq(i, m, n) for(int i = m;i <= n;i++)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define PRINTD(n) printf("%d\n",n)
using namespace std;

int main() {
	int N;
	SCD(N);
	int l[1000];
	int r[1000];
	int ans = 0;
	
	FOR(i,0,N){
		SCD2(l[i],r[i]);
		ans += r[i]-l[i]+1;
	}
	
	PRINTD(ans);
}



Measured memory_bytes: 256
n,m=map(int,input().split())
abList= [list(map(int, input().split())) for _ in range(n)]
cdList= [list(map(int, input().split())) for _ in range(m)]

for ab in abList:
    i = 0
    bestPoint = 0
    bestScore = float('inf')
    for cd in cdList:
        dist = abs(ab[0] - cd[0]) + abs(ab[1] - cd[1])
        if dist < bestScore:
            bestScore = dist
            bestPoint = i + 1
        i += 1
    print(bestPoint)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
    int n,l;
    cin >> n >> l;
    vector<string> s(n);
    int i;
    for(i = 0;i < n;++i){
        cin >> s.at(i);
    }
    sort(s.begin(),s.end());
    for(i = 0;i < n;++i){
        cout << s.at(i);
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
c = [list(map(int, input().split())) for _ in range(3)]
flg = all(
    c[0][i + 1] - c[0][i] == c[1][i + 1] - c[1][i] == c[2][i + 1] - c[2][i]
    for i in range(2)
)
print(["No", "Yes"][flg])

Measured memory_bytes: 9140
#![allow(unused_imports)]
// use itertools::Itertools;
use proconio::{input, marker::*};

fn main() {
    input! {
        n: usize,
        k: usize,
        xx: [usize; n]
    };
    let sum = xx
        .iter()
        .fold(0, |acc, &x| acc + std::cmp::min(k - x, x) * 2);
    println!("{}", sum);
}


Measured memory_bytes: 2128
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>

int main()
{
    using namespace std;

    string w;
    cin >> w;
    vector<int> alphabetCounts(26);

    for (auto c : w)
    {
        alphabetCounts[c - 'a']++;
    }

    if (all_of(alphabetCounts.cbegin(), alphabetCounts.cend(), [](int i){return i % 2 == 0;}))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
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; }



int main() {
  int n;
  cin >> n;
  int p[n];
  int ans = 0;
  FOR(i,0,n-1) {
    cin >> p[i];
  }
  FOR(i,0,n-1){
    if(p[i]==i+1){
      ++ans;
    }
  }

  int ref = 0;
  while(ref<=n-2){
    if(p[ref]==ref+1 && p[ref+1]==ref+2){
      --ans;
      ref += 2;
    }
    else{
      ++ref;
    }
  }

  cout << ans << endl;
    






}



Measured memory_bytes: 768
#include <iostream>
using namespace std;
#include<string.h>
#include<set>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
#include<vector>
char a1[110][110];
int  a[110];
int main()
{
    int n,m;
    cin>>n>>m;
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a1[i][j];
            a[a1[i][j]-'a']++;
        }
    }
    int add4=(n/2)*(m/2);
    int addhe=n*m;
    int add2=0;
    if(add4!=addhe)
        add2=(addhe-add4*4)/2;
    int sum2=0;
    int sum4=0;
    for(int i=0;i<100;i++)
    {
        sum4+=a[i]/4;
        a[i]=a[i]%4;
    }
    for(int i=0;i<100;i++)
    {
        sum2+=a[i]/2;
        a[i]=a[i]%2;
    }
    if(sum4==add4&&sum2==add2)
    {
        cout<<"Yes"<<endl;
    }
    else if(sum4>add4)
    {
        sum2+=(sum4-add4)*4/2;
        if(sum2>=add2)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    else
        cout<<"No"<<endl;
    //cout<<add2<<"_"<<add4<<endl;
    return 0;
}


Measured memory_bytes: 256
h, w = gets.split.map(&:to_i)
a = (1..h).map { gets.split.map(&:to_i) }
p (0..h-1).to_a.product((0..w-1).to_a).map {|i, j|
    (0..h-1).to_a.product((0..w-1).to_a).map {|y, x|
        a[y][x] * [(i - y).abs, (j - x).abs].min
    }.inject(:+)
}.min


Measured memory_bytes: 9072
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define prtd(var, i) cout << fixed << setprecision(i) << var << endl;
#define ll long long
using namespace std;

int main(){
    ll h, w;
    cin >> h >> w;
    ll ans;
    if(h == 1 || w == 1){
        cout << 1 << endl;
        return 0;
    }
    if(w % 2 == 0){
        ans = (w/2) * h;
    }else{
        if(h % 2 == 0){
            ans = (w/2+1)*h/2 + (w/2)*h/2;
        }else{
            ll from = (w/2+1)*(h/2+1);
            ll to = (w/2)*(h/2);
            ans = from + to;
        }
    }
    cout << ans << endl;
}

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

inline int read()
{
	char c = getchar(); int f = 1, x = 0;
	while( c < '0' || c>'9' ) { if(c == '-') f = -1;  c = getchar(); }
	while( c >= '0'&&c<='9' ) { x = x * 10 + c - '0'; c = getchar(); }
	return f * x;
}

int tot = 0; 

struct tEdge {
	int u, v, w; 
} e[100];

int main()
{
	int l = read(); 
	
	int n = 1, lim = 2; 
	while( lim <= l ) 
		lim <<= 1, n ++; 
	lim >>= 1; n --; 
		
	int temp = lim >> 1, base = lim, add = lim - 1;
	 
	for( int i = 1; i <= n; i ++, temp >>= 1 )
	{
		e[++tot] = { i, i + 1, temp }; 
		e[++tot] = { i, i + 1, 0 };
	
		if( base + add < l )
			e[++tot] = { 1, i, base }, base += add + 1; 
		
		add -= temp; 
	}
	
	if( base + add < l )
		e[++tot] = { 1, n + 1, base };
		
	printf( "%d %d\n", n + 1, tot ); 
	
	for( int i = 1; i <= tot; i ++ )
		printf( "%d %d %d\n", e[i].u, e[i].v, e[i].w );
		
	return 0; 
}

Measured memory_bytes: 256