akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
template<typename T> inline T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }




int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    while (cin >> n && n) {
        cin >> k;
        int dist[105][105];
        fill_n(*dist, 105 * 105, inf);
        rep(i, 105) dist[i][i] = 0;
        
        while (k--) {
            int q;
            cin >> q;
            if (q == 0) {
                int a, b;
                cin >> a >> b;
                a--; b--;
                if (dist[a][b] != inf) cout << dist[a][b] << endl;
                else cout << -1 << endl;
            } else {
                int c, d, e;
                cin >> c >> d >> e;
                c--; d--;
                chmin(dist[c][d], e);
                chmin(dist[d][c], e);
                rep(k, n) rep(i, n) rep(j, n) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
}





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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

int n,k,a[200001],ans;
vector<pair<int,int>> v;


signed main() {
    cin >> n >> k;
    rep1(i,n) {
        cin >> a[i];
        if (a[i]%k == 1) ans++;
        a[i]--;
        a[i] = (a[i]+a[i-1])%k;
        v.pb(mp(a[i], i));
    }
    v.pb(mp(INF,INF));
    sort(all(v));
    rep(i,n) {
        auto fitr = upper_bound(all(v), mp(a[i], i+1)), sitr = lower_bound(all(v), mp(a[i], i+k));
        ans += max(0LL, (int)(sitr-fitr));
    }
    cout << ans << endl;
}



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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;



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

  s[k-1] = s[k-1]+32;

  cout << s << endl;


  
  return 0;
}



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

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

#define INF  (int)1e9
#define LINF (long long)1e18

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

using Edge   = vector<vector<pair<int, int>>>; // src_vertex -> dst_vertex, weight
using Vertex = vector<int>;                    // index      -> cost

int graph_bfs(const int&  start,
              const int&  goal,
              const Edge& edge,
              Vertex&     vertex) {
    queue<int> queue;
    queue.push(start);

    while(!queue.empty()) {
        auto src = queue.front();
        queue.pop();

        REP(i, edge[src].size()) {
            auto dst = edge[src][i].first;

            if(vertex[src] + 1 < vertex[dst]) {
                vertex[dst] = vertex[src] + 1;
                queue.push(dst);
            }
        }
    }

    return vertex[goal];
}

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

    int N, M;
    std::cin >> N >> M;

    Edge   edge(N * 3);
    Vertex vertex(N * 3, INF);

    REP(i, M) {
        int l, r;
        std::cin >> l >> r;
        edge[(l - 1) * 3 + 0].emplace_back((r - 1) * 3 + 1, 0);
        edge[(l - 1) * 3 + 1].emplace_back((r - 1) * 3 + 2, 0);
        edge[(l - 1) * 3 + 2].emplace_back((r - 1) * 3 + 0, 0);
    }

    int S, T;
    std::cin >> S >> T;

    auto start = (S - 1) * 3;
    auto goal  = (T - 1) * 3;

    vertex[start] = 0;

    auto min_move_cost = graph_bfs(start, goal, edge, vertex);
    if(min_move_cost == INF) {
        std::cout << -1 << std::endl;
    }
    else {
        std::cout << min_move_cost / 3 << std::endl;
    }

    return 0;
}


Measured memory_bytes: 17792
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
aをsort,bをsortして大小関係を比較したときa[i]>b[i]の場合:No.
a,bをsortする前のindexをai,biとし,a,bをsortした後の同じindexのペアについて
aiからbiへの辺をもったグラフを作る.(aiからbiへswapで移動)
このグラフのサイクルの数(連結成分の数)をxとするとswap回数はn-x回(max:n-1,min:0).これは,最小全域森の辺の数.
よってx>=2の場合:Yes.
x=1の場合,sort後のa,bについてa[i+1]<=b[i]を満たすとき、a[i+1],a[i]を入れ替えても条件を満たす.
よって,これが出来るときx=2になるため,Yes
x=1かつこれが出来ないとき:No
"""
n = I()
a = LI()
b = LI()
a = [(a[i],i) for i in range(n)]
b = [(b[i],i) for i in range(n)]
a.sort()
b.sort()
for i in range(n):
    if b[i][0] < a[i][0]:
        print('No')
        quit()

edges = [None]*n
for i in range(n):
    edges[a[i][1]] = b[i][1]

lst = [None]*n

def dfs(s):
    if lst[s] == None:
        lst[s] = tmp
        dfs(edges[s])
    return

tmp = 0
for i in range(n):
    if lst[i] == None:
        dfs(i)
        tmp += 1

lst = list(Counter(lst).values())
if len(lst) >= 2:
    print('Yes')
    quit()

for i in range(n-1):
    if b[i][0] >= a[i+1][0]:
        print('Yes')
        quit()

print('No')


Measured memory_bytes: 133904
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI 3.14159265358979
#define EPS 1e-8
#define mod 1000000007
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
	 
const ll INF=(ll)2e18;	
const int N=1e5+5;
 

 
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll modinverse(ll a,ll m)
{
	return binpow(a,m-2,m);
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(0);
	
	int sv[10000050]={0};
	sv[1]=0;
	sv[2]=0;
	ll n;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
	
		if(sv[i]!=0)
			continue;
		for(int j=1;(i*j)<=n;j++)
		{
			if(sv[i*j]==0)
				sv[i*j]=i;
		}
		
	}
	ll ans=1;
	
	for(ll i=2;i<=n;i++)
	{
		map<ll,ll> cnt;
		ll j=i;
		ll val=sv[i];
		cnt[val]++;
		while(j!=1)
		{
			j/=val;
			val=sv[j];
			if(val!=0)
			cnt[val]++;
		}
		ll ans1=i;
		for(auto j:cnt)
		{
			ans1*=(j.se+1);
		}
		
		ans+=ans1;
	}
	cout<<ans;
}


Measured memory_bytes: 42696
N=int(input())
TA=[list(map(int,input().split())) for i in range(N)]
x,y=1,1
for t,a in TA:
    if -(-x//t)*a>=y:
        x,y=-(-x//t)*t,-(-x//t)*a
    else:
        x,y=-(-y//a)*t,-(-y//a)*a
print(x+y)

Measured memory_bytes: 3188
from math import pow

N = int(input())
X = list(map(int, input().split(' ')))
Y = list(map(int, input().split(' ')))

for i in range(1, 4):
    print('{:.5f}'.format(
        pow(sum([abs(X[j] - Y[j])**i for j in range(N)]), 1/i)
    ))

print('{:.5f}'.format(
    max([abs(X[j] - Y[j]) for j in range(N)])
))

Measured memory_bytes: 7840
#include <bits/stdc++.h>
#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()
using namespace std;
typedef long long ll;
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);}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	int n, k;
	cin >> n >> k;
	ll cnt1 = 0;
	ll cnt2 = 0;
	
	if (k%2){
		FOR(i, 1,  n+1){
			if (i % k == 0) cnt1++;
		}
	}
	else { 
		FOR(i, 1, n+1){
			if (i % k == 0) cnt1++;
			else if (i % k == (k/2)) cnt2++;
		}
	}
	cout << (ll)pow(cnt1, 3) + (ll)pow(cnt2, 3) << endl;

}


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

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;

    if((abs(b-a) <= d && abs(c-b) <= d) || abs(c-a) <= d ){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int a;
	scanf("%d",&a);
	int b;
	scanf("%d",&b);
	int c;
	scanf("%d",&c);
	int d;
	scanf("%d",&d);
	int t,x,y;
	t=a+b+c+d;
	x=t/60;
	y=t%60;
	printf("%d\n",x);
	printf("%d\n",y);
	return 0;
}


Measured memory_bytes: 2072
use std::io::stdin;

fn main() {
    let mut is = String::new();
    stdin().read_line(&mut is).ok();
    let mut n: usize = is.trim().parse::<usize>().unwrap();
    let mut ans = String::new();
    let a = ('a' as u8..='z' as u8)
        .map(|e| e as char)
        .collect::<Vec<char>>();

    while n > 0 {
        n -= 1;
        let t = n % 26;
        n /= 26;

        ans.push(a[t]);
    }

    println!("{}", ans.chars().rev().collect::<String>());
}


Measured memory_bytes: 2140
#include<stdio.h>
#define MAX 2000001
#define VMAX 10000
int main()
{
  int i,n;
  scanf("%d",&n);
  int A[n+1],B[n+1];
  int j,C[VMAX+1];
  int k=VMAX;
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
  }
  for(i=0;i<=k;i++){
    C[i]=0;
  }
  for(j=1;j<=n;j++){
    C[A[j]]++;
  }
  for(i=1;i<=k;i++){
    C[i]=C[i]+C[i-1];
  }
  for(j=n;j>0;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
  for(i=1;i<=n;i++){
    printf("%d",B[i]);
    if(i!=n)printf(" ");
  }
  printf("\n");
  return 0;
}




Measured memory_bytes: 17404
N,M=[int(x) for x in input().split()]
S=[]
for i in range(N):
    a,b=[int(x) for x in input().split()]
    S.append((a,b))
S.sort()
a=0
s=0
while M>0:
    a+=S[s][0]*min(S[s][1],M)
    M-=S[s][1]
    s+=1
print(a)


Measured memory_bytes: 16952
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 100005

using namespace std;
typedef long long int ll;

int main()
{
	int n;
	scanf("%d",&n);
	ll ret=0;
	int low=1;
	for(int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		if(i==0)
		{
			ret+=a-1;
			low=2;
		}
		else
		{
			if(a==low) low++;
			else
			{
				if(a%low==0) a--;
				ret+=a/low;
			}
		}
	}
	printf("%lld\n",ret);
	return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main(int argc, char *argv[]) {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> d(N);
    rep(i, N) cin >> d[i];
    sort(all(d));
    cout << d[N/2] - d[N/2-1] << endl;
    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

const ll MOD = 1000000007;
const int MAX = 200001;

// fac[n]: n!
// finv[n]: (n!)^-1
// inv[n]: nの逆元
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void comb_init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算 (combination)
// nCk = (n!) * (k!)^-1 * ((n-k)!)^-1 として計算
ll comb(int n, int k) {
  if (n < k) {
    return 0;
  }
  if (n < 0 || k < 0) {
    return 0;
  }
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// 負の数にも対応した MOD 演算
ll mod(ll val) {
  ll res = val % MOD;
  if (res < 0) res += MOD;
  return res;
}

ll n;
vector<ll> a;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  a.resize(n + 1);
  for (int i = 0; i <= n; i++) {
    cin >> a[i];
  }
  comb_init();

  vector<ll> a2 = a;
  sort(a2.begin(), a2.end());
  ll dup = 0;
  for (ll i = 0; i < n; i++) {
    if (a2[i] == a2[i + 1]) {
      dup = a2[i];
      break;
    }
  }

  ll idx1 = -1, idx2 = -1;
  for (ll i = 0; i <= n + 1; i++) {
    if (a[i] == dup) {
      if (idx1 == -1) {
        idx1 = i;
      } else {
        idx2 = i;
        break;
      }
    }
  }

  ll r = idx1;
  r += (n - idx2);
  cout << n << endl;
  for (ll i = 2; i <= n; i++) {
    ll ans = comb(n+1, i);
    if (i <= r+1) {
      ans = mod(ans - comb(r, i-1));
    }
    cout << ans << endl;
  }
  cout << 1 << endl;
  return 0;
}

Measured memory_bytes: 7424
#include "bits/stdc++.h"
using namespace std;

int main(){
    int N,X;
    cin >>  N >> X;
    int sum=0;

    int i;
    for(i=0;i<N;i++) {
        int l;
        cin >> l;
        sum+=l;
        if(sum>X) break;
    }
    cout << i+1 << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, W, H;
  int row[100001] = {}, col[100001] = {};
  cin >> N >> W >> H;
  for(int i = 0; i < N; i++){
    int x, y, w;
    cin >> x >> y >> w;
    ++row[max( 0, x - w)];
    ++col[max( 0, y - w)];
    --row[min( W, x + w)];
    --col[min( H, y + w)];
  }
  int sum1 = 0, sum2 = 0;
  bool ok1 = true, ok2 = true;
  for(int i = 0; i < W; i++) ok1 &= ((sum1 += row[i]) > 0);
  for(int i = 0; i < H; i++) ok2 &= ((sum2 += col[i]) > 0);
  if(ok1|ok2) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 1944
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <cmath>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9+7;


int main()
{
	
	cin.tie(0); ios_base::sync_with_stdio(false);
	int w,h;
	cin >>w >>h;
	vector<ll> p(w+h);
	rep(i,w+h){
		int z; cin >>z;
		p[i] = z*10 + (i>=w);
	}
	w++;h++;
	sort(all(p));
	ll ans =0;
	for(auto x: p){
		if( x%10 ) ans += w * (x/10),  h--;
		else ans += h * (x/10), w--;
		//printf("%d:%d:%d::%d\n", w,h,x,ans);
	}
	cout << ans <<endl;
	return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 1000;
static const int VMAX = 10000;

int A[MAX], n, s;
int B[MAX], T[VMAX + 1];

int solve() {
    int ans = 0;

    bool V[MAX];
    for (int i = 0; i < n; i++) {
        B[i] = A[i];
        V[i] = false;
    }
    sort(B, B + n);
    for (int i = 0; i < n; i++) {
        T[B[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        if (V[i]) continue;
        int cur = i;
        int an = 0;
        int S = 0;
        int m = VMAX;
        while (1) {
            int v = A[cur];
            V[cur] = true;
            S += v;
            an++;
            m = min(m, v);
            cur = T[A[cur]];
            if (V[cur]) break;
        }
        ans += min(S + m + (an + 1) * s, S + (an - 2) * m);
    }
    return ans;
}


int main(int argc, char const *argv[])
{
    cin >> n;
    s = VMAX;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        s = min(s, A[i]);
    }
    int ans = solve();
    cout << ans << endl;

    return 0;
}




Measured memory_bytes: 3160
#include<stdio.h>
#include<string.h>
int main(){
	char s[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
	char m[26]={'D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C'};
	char bm[1024],bs[1024];
	int i,j;
	scanf("%s",bm);
	strcpy(bs,bm);
	for(i=0;i<strlen(bm);i++){
		for(j=0;j<26;j++){
			if(m[j]==bm[i]){
				bs[i]=s[j];
				break;
			}
		}
	}
	printf("%s\n",bs);
	return 0;
}

Measured memory_bytes: 2664
import java.math.*

fun main(args: Array<String>) {
    val n = Integer.parseInt(readInputLine())
    val (a, b) = readInputLine().split(" ").map { Integer.parseInt(it) }
    
    val ps = mutableListOf<Int>()
    
    val inputs = readInputLine().split(" ").map { Integer.parseInt(it) }
    
    for (i in 0 until n) {
        ps.add(inputs[i])
    }
    
    val aProblem = ps.count { it <= a }
    val bProblem = ps.count { it > a && it <= b }
    val cProblem = ps.count { it > b }
    
    println("${Math.min(aProblem, Math.min(bProblem, cProblem))}")
}
 
fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 37844
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;



int main(){
    
    int N;
    cin >> N;
    vector<vector<int> > a;
    a.assign(N,vector<int>(3, 1));
    rep(i,N) cin >> a[i][0] >> a[i][1] >> a[i][2];
    
    vector<vector<int> > dp;
    dp.assign(N+1, vector<int>(3, 0));
    
    for (int i = 0; i < N; i++) {
        dp[i+1][0] = max(dp[i][1]+a[i][0],dp[i][2]+a[i][0]);
        dp[i+1][1] = max(dp[i][2]+a[i][1],dp[i][0]+a[i][1]);
        dp[i+1][2] = max(dp[i][1]+a[i][2],dp[i][0]+a[i][2]);
    }
    
    cout << max(max(dp[N][0],dp[N][1]),dp[N][2]) << endl;
    
    return 0;
}


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

using namespace std;

#define PB push_back
#define f first
#define s second
#define what_is(x) cerr << #x << " is " << x << endl;

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

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int x, y;
    cin >> x >> y;
    if(4*x >= y && y >= 2*x && (4*x-y)%2 == 0 && (y - 2*x)%2 == 0)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
    return 0;
}


Measured memory_bytes: 3636
package main

import "fmt"

func alphabetical(b byte) int {
	if 65 <= b && b <= 90 {
		return 1
	}
	if 97 <= b && b <= 122 {
		return 2
	}
	return 0
}

func main() {
	var b byte
	fmt.Scanln(&b)
	fmt.Println(alphabetical(b))
}


Measured memory_bytes: 1104
#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()
#define sz(x) (int)(x).size()
#define Min(...) min({__VA_ARGS__})
#define Max(...) max({__VA_ARGS__})
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
static inline ll sgn(ll x) { return (x>0)-(x<0); }
static inline bool vowel(char c) { c = (char)tolower(c); return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u' or c == 'y'; }
static inline vi rvi(int N) { vi res(N); rep(i,0,N) cin >> res[i]; return res; }
static inline int ri() { int N; cin >> N; return N; }
static inline void pvi(const vi& r) { trav(it,r) cout << it << " "; cout << endl; }
template<class S, class T> static inline void smax(S& s, const T& t) { if (t > s) s = t; }
template<class S, class T> static inline void smin(S& s, const T& t) { if (t < s) s = t; }
template<class S> static inline void in(S& s) { cin >> s; }
template<class S> static inline void ut(const S& s) { cout << s << " "; }
static inline void nl() { cout << endl; }

typedef vector<pii> vpi;
typedef vector<vpi> graph;
const pii inf(1 << 29, -1);
#define RMQ_HAVE_INF /** exclude-line */

#ifndef RMQ_HAVE_INF /** exclude-line */
const int inf = numeric_limits<int>::max();
#endif /** exclude-line */

template <class T>
struct RMQ {
	vector<vector<T>> jmp;

	RMQ(const vector<T>& V) {
		int N = sz(V), on = 1, depth = 1;
		while (on < sz(V)) on *= 2, depth++;
		jmp.assign(depth, V);
		rep(i,0,depth-1) rep(j,0,N)
			jmp[i+1][j] = min(jmp[i][j],
			jmp[i][min(N - 1, j + (1 << i))]);
	}

	T query(int a, int b) {
		if (b <= a) return inf;
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};


struct LCA {
	vi time;
	vector<ll> dist;
	RMQ<pii> rmq;

	LCA(graph& C) : time(sz(C), -99), dist(sz(C)), rmq(dfs(C)) {}

	vpi dfs(graph& C) {
		vector<tuple<int, int, int, ll> > q(1);
		vpi ret;
		int T = 0, v, p, d; ll di;
		while (!q.empty()) {
			tie(v, p, d, di) = q.back();
			q.pop_back();
			if (d) ret.emplace_back(d, p);
			time[v] = T++;
			dist[v] = di;
			trav(e, C[v]) if (e.first != p)
				q.emplace_back(e.first, v, d+1, di + e.second);
		}
		return ret;
	}

	int query(int a, int b) {
		if (a == b) return a;
		a = time[a], b = time[b];
		return rmq.query(min(a, b), max(a, b)).second;
	}
	ll distance(int a, int b) {
		int lca = query(a, b);
		return dist[a] + dist[b] - 2 * dist[lca];
	}
};

signed main() {
	cin.sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int N;
	cin >> N;

	graph g(N);
	rep(i,0,N-1) {
		int a, b, c;
		cin >> a >> b >> c;
		--a; --b;
		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}
	LCA lca(g);
	int Q, K;
	cin >> Q >> K;
	--K;
	rep(i,0,Q) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		cout << (lca.distance(x, K) + lca.distance(K, y)) << endl;
	}
}


Measured memory_bytes: 23876
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define pb push_back
#define mk make_pair
ll issign(ll x) {
	return (x > 0) - (x < 0);
}
int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	vector<ll>a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll ans = 1e18 ;
	for (int possible = -1; possible <= 1; possible += 2) {
		ll sum = 0;
		ll cost = 0;
		for (int i = 0; i < n; i++) {
			sum += a[i];
			ll have;
			if (i & 1)
				have = -possible;
			else
				have = possible;
			if (issign(sum) != have) {
				cost += abs(sum - have);
				sum = have;
			}
		}
		ans = min(ans, cost);
	}
	cout << ans << endl;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL n,k,p[5010],c[5010],vis[5010],ans=-1e18;
vector <int> v;

int main()
{
	cin>>n>>k;
	rep(i,n) cin>>p[i],p[i]--;
	rep(i,n) cin>>c[i];
	rep(i,n)
	{
		v.clear();
		rep(j,n+5) vis[j]=-1;
		LL cur=i,sta;
		while(true)
		{
			cur=p[cur];
			if(vis[cur]!=-1)
			{
				sta=vis[cur];
				break;
			}
			vis[cur]=v.size();
			v.pb(c[cur]);
		}
		LL res=-1e18,sum=0,sum2=0;
		rep(j,min(sta,k))
		{
			sum+=v[j];
			res=max(res,sum);
		}
		if(k>sta)
		{
			for(int j=sta;j<v.size();j++) sum2+=v[j];
			cur=0;
			for(int j=sta;j<v.size();j++)
			{
				if(j+1>k) break;
				cur+=v[j];
				res=max(res,sum+cur+(sum2>0 ? (k-j-1)/((LL)v.size()-sta)*sum2:0LL));
			}
		}
		ans=max(ans,res);
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

/********** TEMPLATE STARTS HERE ***********/

#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define test int t; cin >> t; while(t--)
#define skip continue
#define stop break
#define sz(v) v.size()
#define endl '\n'
#define PI 3.1415926535897932384626433832795
#define EPS 1e-9
#define FR(i, l, r) for(int i = (l); i <= (r); i++)
#define gcd __gcd 
#define FO(i, a) for(auto & i : a)
#define debug(a) cout << #a << ": " << a << endl
#define debug1(a, l, r) FR(i, l, r) cout << a[i] << " "; cout << endl
#define SET(a, b) memset(a, b, sizeof(a));
#define refresh fflush(stdout);

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

const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3f3f;

template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
//template <typename T> inline void out(T x) { cout << x; }

/*********** TEMPLATE ENDS HERE *************/

bool v[103][103];
bool b[103][103];


main()
{
	int n, m;
	cin >> n >> m;
	
//	if(n == 1 || m == 1)
//		return 0;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			char c;
			cin >> c;
			if(c == '#')
				v[i][j] = 1;
		}
	
	for(int i = 1; i <= n; i++)
	{
		if(v[i][1])
			continue;
		bool ok = true;
		for(int j = 2; j <= m && ok; j++)
			if(v[i][j] != v[i][j - 1])
				ok = false;
		if(ok == true)
			for(int j = 1; j <= m; j++)
				b[i][j] = true;
	}
	
	for(int j = 1; j <= m; j++)
	{
		if(v[1][j])
			continue;
		bool ok = true;
		for(int i = 2; i <= n && ok; i++)
			if(v[i][j] != v[i - 1][j])
				ok = false;
				
		if(ok == true)
			for(int i = 1; i <= n; i++)
				b[i][j] = true;
	}
	
	for(int i = 1; i <= n; i++)
	{
		bool ok = false;
		for(int j = 1; j <= m; j++)
			if(b[i][j] == false)
			{
				ok = true;
				if(v[i][j] == 1)
					cout << '#';
				else
					cout << '.';
			}
		if(ok == true)
			cout << endl;
	}
	
}

Measured memory_bytes: 256
a,b,k=map(int,input().split())
ans=[]
num_min=a+k
num_max=b-k+1
if (b-a+1)>2*k:
    for i in range(a,num_min):
        ans.append(i)
    for i in range(num_max,b+1):
        ans.append(i)
else:
    for i in range(a,b+1):
        ans.append(i)
ans=sorted(set(ans))
for i in ans:
    print(i)

Measured memory_bytes: 9132
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

signed main(){
	cout<<fixed<<setprecision(10);
	
	int N, A, B, C;
	vector<int> con(3);
	vector<string> S;
	vector<char> ans;
	bool flag = true;
	
	cin>>N>>A>>B>>C;
	
	con[0] = A;
	con[1] = B;
	con[2] = C;
	
	S.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>S[i];
	}
	for(int i = 0; i < N; i++){
		if(con[S[i][0] - 'A'] <= 0 && con[S[i][1] - 'A'] <= 0) {
			flag = false;
		} else if(con[S[i][0] - 'A'] == con[S[i][1] - 'A'] && i != N-1){
			if(S[i][0] == S[i+1][0] || S[i][0] == S[i+1][1]) {
				con[S[i][0] - 'A']++;
				con[S[i][1] - 'A']--;
				ans.push_back(S[i][0]);
			} else {
				con[S[i][0] - 'A']--;
				con[S[i][1] - 'A']++;
				ans.push_back(S[i][1]);
			}
		} else if(con[S[i][0] - 'A'] < con[S[i][1] - 'A']){
			con[S[i][0] - 'A']++;
			con[S[i][1] - 'A']--;
			ans.push_back(S[i][0]);
		} else {
			con[S[i][0] - 'A']--;
			con[S[i][1] - 'A']++;
			ans.push_back(S[i][1]);
		}
	}
	
	if(flag) {
		cout<<"Yes"<<endl;
		
		for(int i = 0; i < N; i++){
			cout<<ans[i]<<endl;
		}
	} else {
		cout<<"No"<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 6696
//Contest with Drinks Easy
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin>>N;
    vector<int>time(N);
    for(int i=0;i<N;i++)cin>>time.at(i);
    int M;
    cin>>M;
    vector<vector<int>>problem(M,vector<int>(2));
    for(int i=0;i<M;i++){
        cin>>problem.at(i).at(0);
        cin>>problem.at(i).at(1);
    }

    int time_sum=0;
    for(int i=0;i<N;i++)time_sum+=time.at(i);

    for(int i=0;i<M;i++){
        cout<<time_sum-time.at(problem.at(i).at(0)-1)+problem.at(i).at(1)<<endl;
    }


    /*
    cout<<N<<endl;
    for(int i=0;i<N;i++)cout<<time.at(i);
    cout<<endl;
    cout<<M<<endl;
    for(int i=0;i<M;i++){
        cout<<problem.at(i).at(0);
        cout<<problem.at(i).at(1);
        cout<<endl;
    }
    */

    return 0;
}

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

class Dice {
public:
  int label[6];
  string rotation = "EEENEEENEEESEEESEEENEEEN";

  void E(int label[]) {
    int rotate = label[0];
    label[0] = label[3];
    label[3] = label[5];
    label[5] = label[2];
    label[2] = rotate;
  }
  void N(int label[]) {
    int rotate = label[0];
    label[0] = label[1];
    label[1] = label[5];
    label[5] = label[4];
    label[4] = rotate;
  }
  void S(int label[]) {
    int rotate = label[0];
    label[0] = label[4];
    label[4] = label[5];
    label[5] = label[1];
    label[1] = rotate;
  }
  void W(int label[]) {
    int rotate = label[0];
    label[0] = label[2];
    label[2] = label[5];
    label[5] = label[3];
    label[3] = rotate;
  }
};

int main() {
  Dice dice;
  for (int i = 0; i < 6; i++) cin >> dice.label[i];
  int q; cin >> q;

  for (int i = 0; i < q; i++) {
    int up, front; cin >> up >> front;

    if (dice.label[0] == up && dice.label[1] == front) {
      cout << dice.label[2] << endl;
      continue;
    }

    for (int i = 0; i < dice.rotation.size(); i++) {
      if (dice.rotation[i] == 'E') dice.E(dice.label);
      else if (dice.rotation[i] == 'N') dice.N(dice.label);
      else if (dice.rotation[i] == 'S') dice.S(dice.label);
      else if (dice.rotation[i] == 'W') dice.W(dice.label);

      if (dice.label[0] == up && dice.label[1] == front) {
        cout << dice.label[2] << endl;
        break;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/
int main(){
    ll n, k; cin >> n >> k;
    vector<ll> num(k, 0);
    for(int i = 1; i <= n; ++i) num[i % k]++;
    ll ans = 0;
    rep(a, k){
        ll b = (k - a) % k;
        ll c = (k - a) % k;
        if((b + c) % k == 0){
            ans += num[a] * num[b] * num[c];
        }
    }
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
#define MOD 1000000007
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

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

    for(int i=0; i<S.length(); i++) {
        int d = S[i] - 'A';
        d = (d + N) % 26;

        S[i] = 'A' + d;
    }

    cout << S << endl;

    return 0;
}

Measured memory_bytes: 256
def yuk(a, b):
    ans = int(a / b)
    amari = a % b
    if amari != 0:
        ans = yuk(b, amari)
    else:
        ans = b
    return ans

N = int(input())
alst = list(map(int, input().split()))
ans = alst[0]
for i in range(1, N):
    if ans > alst[i]:
        ans = yuk(ans, alst[i])
    else:
        ans = yuk(alst[i], ans)
print(ans)

Measured memory_bytes: 14252
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if (n == 1) {
		    System.out.println(sc.nextInt());
		    return;
		}
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = arr[0];
        right[n - 1] = arr[n - 1];
        for (int i = 1; i < n; i++) {
            left[i] = gcd(arr[i], left[i - 1]);
            right[n - i - 1] = gcd(arr[n - i - 1], right[n - i]);
        }
        int max = 1;
        for (int i = 1; i < n - 1; i++) {
            max = Math.max(max, gcd(left[i - 1], right[i + 1]));
        }
        max = Math.max(max, left[n - 2]);
        max = Math.max(max, right[1]);
		System.out.println(max);
	}
	
	static int gcd(int x, int y) {
	    if (x % y == 0) {
	        return y;
	    }
	    return gcd(y, x % y);
	}
}


Measured memory_bytes: 50060
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;
using ll = long long;
#define REP(i, n) for (ll i = 0; i < n; ++i)

using P = pair<ll, ll>;
int main() {
	ll n, l;
	cin >> n >> l;
	vector<P> v(n);
	REP(i, n) cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end());
	map<ll, ll> mp;
	{
		set<ll> st;

		REP(i, n) {
			st.insert(v[i].first);
			st.insert(v[i].second);
		}
		int i = 0;
		for (auto &&a : st) {
			mp[a] = i++;
		}
	}
	int k = mp.size();
	ll left = 0, right = 0, x = 0;
	int i = 0;
	while (left < k - 1) {
		while (i < n && mp[v[i].first] <= left) {
			right = max(right, mp[v[i].second]);
			++i;
		}
		left = right;
		x++;
	}
	vector<int> cnt(k, 0);
	REP(i, n) {
		cnt[mp[v[i].first]]++;
		cnt[mp[v[i].second]]--;
	}
	REP(i, k - 1) cnt[i + 1] += cnt[i];
	ll y = 1e9;
	REP(i, k - 1) y = min(y, (ll)cnt[i]);

	cout << x << " " << n - y + 1 << endl;
}


Measured memory_bytes: 47872
d = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(d)]
t = [int(input()) for i in range(d)]

def calc_score(day, contest, score, last):
  last[contest] = day + 1

  contest_score = s[day][contest]
  score += contest_score

  dis = 0
  for i in range(26):
    dis += c[i] * ((day + 1) - last[i])
  score -= dis

  return score, last


score = 0
last = [0 for i in range(26)]
for day in range(d):
  contest = t[day]
  contest -= 1
  score, last = calc_score(day, contest, score, last)
  print(score)

Measured memory_bytes: 9288
//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e15);

vector<ll> v[MAXn];
ll dp[MAXn][2];

void dfs(ll now,ll f)
{
    ll a = 1, b = 1;
    for(ll k:v[now])if(k != f)
    {
        dfs(k, now);
        a = a * dp[k][0] % MOD;
        b = b * (dp[k][0] + dp[k][1]) % MOD;
    }
    dp[now][0] = b;
    dp[now][1] = a; 
}

int main()
{
    IOS();
    ll n;
    cin>>n;
    REP(i,n-1)
    {
        ll a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(1, -1);
    cout<<(dp[1][0] + dp[1][1]) % MOD<<endl;
}


Measured memory_bytes: 14208
from collections import deque
import sys
import math

if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(list(map(int, input().split())))

    count = 0
    for t in T:
        left = 0
        right = n

        while left < right:
            mid = (left + right) // 2
            if t == S[mid]:
                count += 1
                break
            elif t < S[mid]:
                right = mid
            else:
                left = mid + 1
    print(count)



Measured memory_bytes: 17408
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <time.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
#define RAND (rand()*rand())
#define MAX(x, y) ((x) > (y) ? (x):(y)) 
#define MIN(x, y) ((x) > (y) ? (y):(x))
#define ABS(x) ((x) > 0 ? (x) : -(x))
#define CEIL(x, y) (((x) + (y) - 1)/(y))
using namespace std;
const int MAXN = 2e5 + 5;
const ll MOD = 998244353LL;
const double eps = 1e-7;
#define None -1
int N, M, K, Q, T;
ll gcd(ll a, ll b) {
	if (b == 0LL) return a;
	return gcd(b, a % b);
}
ll seg[4 * MAXN], lazy[4 * MAXN];
ll psumPowTens[MAXN];
ll powNum[11][MAXN];

ll binpow(ll a, ll b) {
	ll res = 1ll;
	while (b) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

ll getPsumPowTens(int l, int r) {
	ll num = 0;
	if (N - r - 1 >= 0) {
		num = psumPowTens[N - r - 1];
	}
	return (psumPowTens[N - l] - num + MOD) % MOD;
}

void lazy_check(int node, int l, int r) {
	if (lazy[node]!= None) { // when updated, first process pending, if it is not leaf, prpagate that pending down to children and clear my pending
		seg[node] = (lazy[node] * getPsumPowTens(l, r)) % MOD;
		if (l != r) {
			lazy[2 * node] = lazy[node];
			lazy[2 * node + 1] = lazy[node];
		}
		lazy[node] = None;
	}
}

ll update(int node, int l, int r, int ul, int ur, int d) {
	lazy_check(node, l, r);
	if (ur < l || ul > r) return seg[node];
	int mid = (l + r) >> 1;
	if (ul <= l && r <= ur) {
		// if range completly falls in, add val, my children will have pending updates, of course when myself is not leaf
		ll val = (d * getPsumPowTens(l, r)) % MOD;
		seg[node] = val;
		if (l == r) return seg[node];
		lazy[2 * node] = d;
		lazy[2 * node + 1] = d;
		return seg[node];
	}
	return seg[node] = (update(2 * node, l, mid, ul, ur, d) + update(2 * node + 1, mid + 1, r, ul, ur, d)) % MOD;
}

ll query(int node, int l, int r, int ql, int qr) {
	lazy_check(node, l, r);
	if (qr < l || ql > r) return 0LL;
	if (ql <= l && r <= qr) return seg[node];
	int mid = (l + r) >> 1;
	return (query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr)) % MOD;
}

int main()
{
	int i, j;
	scanf("%d%d", &N, &Q);
	for (i = 0; i <= 4 * (MAXN - 3); ++i) lazy[i] = None;
	for (i = 1; i <= 10; ++i) {
		powNum[i][0] = 1;
		for (j = 1; j <= N; ++j) {
			powNum[i][j] = (powNum[i][j - 1] * i) % MOD;
		}
	}
	psumPowTens[0] = 1;
	for (i = 1; i <= N; ++i) {
		psumPowTens[i] = (psumPowTens[i - 1] + powNum[10][i]) % MOD;
	}
	int l, r, d;
	update(1, 1, N, 1, N, 1);
	
	for (i = 1; i <= Q; ++i) {
		scanf("%d%d%d", &l, &r, &d);

		update(1, 1, N, l, r, 0);

		update(1, 1, N, l, r, d);
		printf("%lld\n", query(1, 1, N, 1, N));
	}

}

Measured memory_bytes: 31372
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
#define fin {cout<<"-1"<<endl;return 0;}
//template
//main
signed main(){
  int x,y,z;cin>>x>>y>>z;
  int N=x+y+z;
  std::vector<int> a(N),b(N),c(N);
  for(int i=0;i<N;i++)cin>>a[i]>>b[i]>>c[i];
  typedef pair<int,int> P;
  std::vector<P> so(N);
  for(int i=0;i<N;i++)so[i]=P(a[i]-b[i],i);
  sort(so.begin(),so.end());
  std::vector<int> left(N-1,-INF),right(N-1,-INF);
  priority_queue<int,vector<int>,greater<int>> que1,que2;
  int sum=0;
  for(int i=0;i<N-1;i++){
    int po=so[i].second;
    sum+=b[po];
    que1.push(b[po]-c[po]);
    if(que1.size()>y){
      int p=que1.top();sum-=p;
      que1.pop();
    }
    if(que1.size()==y)left[i]=sum;
  }
  sum=0;
  for(int i=N-2;i>=0;i--){
    int po=so[i+1].second;
    sum+=a[po];
    que2.push(a[po]-c[po]);
    if(que2.size()>x){
      int p=que2.top();sum-=p;
      que2.pop();
    }
    if(que2.size()==x)right[i]=sum;
  }
  int ans=0;
  for(int i=y-1;i<y+z;i++)ans=max(ans,left[i]+right[i]);
  cout<<ans<<endl;
}


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

int main(){
  int h,w,n;
  scanf("%d",&h);
  scanf("%d",&w);
  scanf("%d",&n);
  int count=0;
  int sum=0;
  if(h<w){
    for(int i=0;i<h;i++){
      count+=w;
      sum++;
      if(count>=n){
        break;
      }
    }
  }else{
      for(int i=0;i<w;i++){
        count+=h;
        sum++;
        if(count>=n){
          break;
        }
      }
    }
    printf("%d\n",sum);
    return 0;
  }


Measured memory_bytes: 128
class UnionFind:
    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N
        self.rank = [0] * N

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

    def find(self, x):
        """頂点xの根を見つける"""
        if self.root[x] < 0:
            return x
        else:
            while self.root[x] >= 0:
                x = self.root[x]
            return x

    def union(self, x, y):
        """x,yが属する木をunion"""
        # 根を比較する
        # すでに同じ木に属していた場合は何もしない.
        # 違う木に属していた場合はrankを見てくっつける方を決める.
        # rankが同じ時はrankを1増やす
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        """連結成分の数"""
        return len(self.roots())

    def all_group_members(self):
        """{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}




import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = UnionFind(n)
for i in range(q):
    t, u, v = map(int, input().split())
    if t:
        print(int(uf.same(u, v)))
    else:
        uf.union(u, v)


Measured memory_bytes: 74820
using System;

namespace ABC147B {
    class Program {
        static void Main(string[] args) {
            var s = Console.ReadLine();
            var n = 0;
            var sLength = s.Length;
            for (var i = 0; i < sLength / 2; i++) {
                if (s[i] != s[sLength - i - 1]) n++;
            }

            Console.WriteLine(n);
        }
    }
}

Measured memory_bytes: 13140
n = gets.to_i
s = gets.split(" ").map(&:to_i)
s.sort!

fir = []
sec = []

for i in 0..(n/2 -1) do
  fir << s[i]
  sec << s[i+(n/2)]
end

if fir[(n/2)-1] == sec[0]
  puts "0"
else
  nums = [*(fir[(n/2)-1]+1..sec[0])] 
  puts nums.size
end

Measured memory_bytes: 10736
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main()
{
	int N, M;
	cin >> N >> M;
	vector<int>p(M);
	vector<string>S(M);
	rep(i, M)cin >> p[i] >> S[i];
	int seitou = 0, pena = 0;
	vector<bool>judge(N, false);
	vector<int>WA(N, 0);
	rep(i, M)
	{
		if (judge[p[i]-1] == false)
		{
			if (S[i] == "WA")
			{
				WA[p[i]-1]++;
			}
			else judge [p[i]-1] = true;
		}
	}
	rep(i, N)
	{
		if (judge[i] == true)
		{
			seitou++;
			pena += WA[i];
		}
	}
	cout << seitou << " " << pena << endl;
}

Measured memory_bytes: 7296
from itertools import permutations

N, M = [int(i) for i in input().split()]
edge_dict = dict()
for i in range(M):
    _from, _to = [int(i) for i in input().split()]
    if edge_dict.get(_from) is None:
        edge_dict[_from] = list()
    if edge_dict.get(_to) is None:
        edge_dict[_to] = list()
    edge_dict[_from].append(_to)
    edge_dict[_to].append(_from)

cnt = 0
for combi in permutations(range(2,N+1)):
    flg = 0
    combi = [1] + list(combi)
    for i in range(N-1):
        candidate = edge_dict.get(combi[i])
        if candidate is None:
            flg = 1
            break
        if combi[i+1] not in candidate:
            flg = 1
            break
    if flg == 0:
        cnt += 1
print(cnt)

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

const int MAXN = 2e5;
int N;
int Q;
char S[MAXN];

int pref[MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> Q >> S;
	pref[0] = pref[1] = 0;
	for (int i = 1; i < N; i++) {
		pref[i+1] = pref[i] + (S[i] == 'C' && S[i-1] == 'A');
	}

	while (Q--) {
		int l, r; cin >> l >> r;
		cout << pref[r] - pref[l] << '\n';
	}

	return 0;
}


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

int main(){
    int n ;
    cin >> n ;
    vector<int> A(2e7,0) ;
    A[1] = 1 ;
    A[2] = 2 ;
    A[4] = 3 ;
    A[7] = 4 ;
    ll k  = 1 ;
    for(int i = 1 ; k < n + 1 ;i++){
        A[k] = i ;
        k += i   ;
    }
    for(int i = n ; i > 0 ;i-- ){
        if(A[i] != 0  && n - A[i] >= 0 ){
            n -= A[i] ;
            cout << A[i] <<endl;
        }
        if( n == 0 ) return 0 ;
    }
}

Measured memory_bytes: 78336
#include <iostream>

void merge(int A[], int left, int mid, int right, int &times)
{
    int n1 = mid - left;
    int n2 = right - mid;

    int* L = new int[n1+1];
    int* R = new int[n2+1];

    for (int i = 0; i < n1; i++) L[i] = A[left + i];
    for (int i = 0; i < n2; i++) R[i] = A[mid + i];

    L[n1] = 2e9;
    R[n2] = 2e9;

    int i = 0;
    int j = 0;

    for (int k = left; k < right; k++)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
            times++;
        }
        else
        {
            A[k] = R[j];
            j++;
            times++;
        }
    }
}

void mergeSort(int A[], int left, int right, int &times)
{
    if (left + 1 < right)
    {
        int mid = (left + right) / 2;

        mergeSort(A, left, mid, times);
        mergeSort(A, mid, right, times);
        merge(A, left, mid, right, times);
    }
}

int main()
{
    int n;
    std::cin >> n;

    int *S = new int[n];
    for (int i = 0; i < n; i++) std::cin >> S[i];

    int times = 0;
    mergeSort(S, 0, n, times);

    for (int i = 0; i < n - 1; i++) std::cout << S[i] << " ";
    std::cout << S[n-1] << std::endl;
    std::cout << times << std::endl;
}


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

const int N = 1e5 + 7;

int n, a[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] == i) {
			res++;
		if (a[i + 1] == i + 1)
			i++;
		}
	}
	cout << res;
	return 0;
}


Measured memory_bytes: 640