akhauriyash/Code-Regression huggingface dataset:
while 1:
    m,f,l = map(int,input().split())
    if m == f == l == -1:
        break
    elif (m == -1) or (f == -1):
        print("F")
    elif m + f >= 80:
        print("A")
    elif m + f >= 65:
        print("B")
    elif m + f >= 50:
        print("C")
    elif (m + f >= 30) and (l >= 50):
        print("C")
    elif m + f >= 30:
        print("D")
    else:
        print("F")

Measured memory_bytes: 7676
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)


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

int main() {
  int N;
  cin >> N;
  
  vector<int> card(N);
  for (int i = 0; i < N; i++) cin >> card.at(i);
  sort(card.begin(), card.end(), greater<int>());

  int aliceCard = 0, bobCard = 0;
  for (int i = 0; i < N; i+=2) {
    aliceCard += card.at(i);
    if (i+1 < N) bobCard += card.at(i+1);
  }

  int answer = aliceCard - bobCard;
  cout << answer << endl;  
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

// UnionFind 構造体 for tree
type UnionFind struct {
	par []int
}

/*コンストラクタ*/
func newUnionFind(N int) *UnionFind {
	u := new(UnionFind)
	u.par = make([]int, N)
	for i := range u.par {
		u.par[i] = -1
	}
	return u
}
func (u UnionFind) root(x int) int {
	if u.par[x] < 0 {
		return x
	}
	u.par[x] = u.root(u.par[x])
	return u.par[x]
}
func (u UnionFind) unite(x int, y int) {
	xr := u.root(x)
	yr := u.root(y)
	if xr == yr {
		return
	}
	u.par[yr] += u.par[xr]
	u.par[xr] = yr
}
func (u UnionFind) same(x, y int) bool {
	if u.root(x) == u.root(y) {
		return true
	}
	return false
}
func (u UnionFind) size(x int) int {
	return -u.par[u.root(x)]
}

var mod int = 1000000007

type pair struct {
	fi int
	se int
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	//入力用の準備終わり
	a := Scan()
	b := Scan()
	if a == "H" {
		fmt.Println(b)
	} else {
		if b == "H" {
			fmt.Println("D")
		} else {
			fmt.Println("H")
		}
	}
}


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

using namespace std;
string s,t;
int dp[3005][3005],n,m;
void trace(int n, int m)
{
    if (n>0 && m>0)
    {
        if (s[n]==t[m] && dp[n-1][m-1]+1==dp[n][m])
        {
            trace(n-1,m-1);
            cout<<s[n];
        }
        else
            if (dp[n][m]==dp[n-1][m]) trace(n-1,m);
            else trace(n,m-1);
    }
}
int main()
{
    cin>>s>>t;n=s.size();m=t.size();
    s=' '+s;
    t=' '+t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if (s[i]==t[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    trace(n,m);
    return 0;
}


Measured memory_bytes: 35712
import copy


def main():
    s = input()
    ss = s + s
    t = input()
    if not set(sorted(t)) <= set(sorted(s)):
        print(-1)
        return
    cnt_s = {}
    cnt_t = {}
    pos = {}  # [({}) for x in range(len(s))]
    for i in range(len(ss)):
        c = ss[i]
        if c not in cnt_s:
            cnt_s[c] = 0
            pos[c] = []
        cnt_s[c] += 1
        pos[c].append(i)
    # for k in pos.keys():
    #     pos[k].reverse()
    # org_pos = copy.deepcopy(pos)
    ret = 0
    tmp = -1
    for i in range(len(t)):
        c = t[i]
        if pos[c][0] > tmp:
            tmp = pos[c][0]
            continue
        l = 1
        r = len(pos[c]) - 1
        while not l == r:
            p = (l + r) // 2
            if pos[c][p] > tmp:
                r = p
            if pos[c][p] <= tmp:
                l = p + 1
        tmp = pos[c][l]
        if tmp >= len(s):
            ret += len(s)
            tmp -= len(s)
    ret += tmp + 1
    print(ret)
    return


if __name__ == "__main__":
    main()


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

using namespace std;


int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        for (int j = -1; j <= 1; ++j)
            ++cnt[a[i] + j];
    }
    int ans = 0;
    for (auto it : cnt)
        ans = max(ans, it.second);
    printf("%d", ans);
    
    return 0;
}

Measured memory_bytes: 5120
sx, sy, tx, ty = map(int, input().split())
d_x = tx - sx
d_y = ty - sy
ans = d_x * 'R' + d_y * 'U' + d_x * 'L' + d_y * 'D' + 'L' + (d_y + 1) * 'U' + (d_x + 1) * 'R' + 'D' + 'R' + (d_y + 1) * 'D' + (d_x + 1) * 'L' + 'U'
print(ans) 


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n;
    map<ll, ll> ans;
    cin >> n;
    for (ll i = 1; i < 101;i++){
        for (ll j = 1; j < 101;j++){
            for (ll k = 1; k < 101;k++){
                ans[i * i + j * j + k * k + i * j + j * k + k * i]++;
            }
        }
    }
    for (ll i = 1; i < n + 1; i++) cout << ans[i] << endl;
}

Measured memory_bytes: 6016
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};




int main(){
    string s;cin >> s;
    int n = s.length();
    for (int i = 0; i < n/2; i++) {
        if(s[i] != s[n-i-1]){
            puts("No");
            return 0;
        }
    }
    for (int i = 0; i < (n-1)/2; i++) {
        if(s[i] != s[(n-1)/2-i-1]){
            puts("No");
            return 0;
        }
    }
    for (int i = 0; i < (n-1)/2; i++) {
        if(s[(n-1)/2+i+1] != s[n-i-1]){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}


Measured memory_bytes: 256
# -*- coding:utf-8 -*-

def solve():
    N = input()
    X = int(N)

    total = 0
    while True:
        if len(N) == 0:
            break

        total += int(N[-1])
        N = N[:-1]
    
    if X%total == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    solve()


Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
    #define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
    #define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/

LL solve(deque<int> & dq, int num, bool b) {
    LL ret = 0;
    if (b) {
        ret = abs(dq.back() - num);
        dq.push_back(num);
    } else {
        ret = abs(dq.front() - num);
        dq.push_front(num);
    }
    return ret;
}

LL real_solve(deque<int> nums, bool b) {
    LL ret = 0;
    deque<int> dq;
    if (b) {
        dq.push_back(nums.front());
        nums.pop_front();
    } else {
        dq.push_back(nums.back());
        nums.pop_back();
    }

    while (!nums.empty()) {
        if (b) {
            int num = nums.back(); nums.pop_back();
            ret += solve(dq, num, true);
            if (nums.empty()) break;
            num = nums.back(); nums.pop_back();
            ret += solve(dq, num, false);
        } else {
            int num = nums.front(); nums.pop_front();
            ret += solve(dq, num, true);
            if (nums.empty()) break;
            num = nums.front(); nums.pop_front();
            ret += solve(dq, num, false);
        }
        b = !b;
    }
    return ret;
}



int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout.precision(10); cout << fixed;
#ifdef LOCAL
    freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
    deque<int> nums;
    int n; cin >> n;
    int val;
    for (int i = 0; i < n; i++) {
        cin >> val;
        nums.push_back(val);
    }
    sort(nums.begin(), nums.end());
    LL ret = real_solve(nums, true);
    ret = max(ret, real_solve(nums, false));
    cout << ret << endl;





/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
    return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


Measured memory_bytes: 1152
n=int(input())
digits=len(str(n))
dlst=['3','5','7']
ans=0

for d in range(3,digits+1):
    for i in range(3**d):
        cur=[dlst[k] for k in [i//(3**j)%3 for j in range(d)]]
    
        cnt=[0]*3

        for j in range(d):
            for k in range(3):
                cnt[k]+=1 if dlst[k]==cur[j] else 0
        
        if cnt[0]*cnt[1]*cnt[2]==0 or int(''.join(cur))>n:
            continue

        ans+=1

print(ans)

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

using namespace std;
const int MAXN = 100000 + 10;
typedef long long ll;
vector<int> q[MAXN];
int color[MAXN];
int flag[MAXN];
int n, m, k;
int v[MAXN], d[MAXN], c[MAXN];
void dfs(int x, int cnt, int c)
{
	if (!color[x])
		color[x] = c;
	if (flag[x] >= cnt)
		return;
	if (cnt == 0)
		return;
	flag[x] = cnt;
	for (int i = 0; i < q[x].size(); i++)
		dfs(q[x][i], cnt - 1, c);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		q[x].push_back(y);
		q[y].push_back(x);
	}
	
	cin >> k;
	for (register int i = 1; i <= k; i++)
		cin >> v[i] >> d[i] >> c[i];
	for (register int i = k; i >= 1; i--)
		dfs(v[i], d[i], c[i]);
	for (register int i = 1; i <= n; i++)
		cout << color[i] << "\n";
	return 0;
}

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	string s,t;
	cin >> s >> t;
	int n=s.length();
	int ans = 0;
	for(int i=0; i<n; i++){
		if(s[i]!=t[i])ans++;
	}
	cout << ans << '\n';
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 3792
#include<bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
signed main(){
  ll n,a;
  string s;
  cin>>n;
  vector<pair<pair<string,ll>,ll> > pp(n);
  rep(i,n){ 
    cin>>s>>a;
     a *= -1;
    pp[i] = make_pair(make_pair(s,a),i+1);
  }
  sort(pp.begin(),pp.end());
  for(ll i=0;i<n;i++){
    cout<<pp[i].second<<"\n";
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static long MOD = 1000000007;

    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final long[] array = new long[61];
        for (int i = 0; i < n; i++) {
            final long a = scanner.nextLong();
            final String s = Long.toBinaryString(a);
            for (int j = s.length() - 1; j >= 0; j--) {
                if (s.charAt(j) == '1') {
                    array[s.length() - j - 1]++;
                }
            }
        }
        long answer = 0;
        for (int i = 0; i < array.length; i++) {
            final long l = originalPow(i);
            final long i1 = array[i] * (n - array[i]) % MOD;
            answer += (l * i1) % MOD;
            answer %= MOD;
        }

        System.out.println(answer);
    }

    private static long originalPow(final long a) {
        long returnValue = 1;
        for (long i = 0; i < a; i++) {
            returnValue *= 2;
            returnValue %= MOD;
        }

        return returnValue;
    }
}


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

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// Yes-Noを出力する問題で楽をする
void Ans(bool f){
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

//---------------------------

int main(){
    ll x; cin >> x;
    ll ans=0, cur=100;
    while(cur < x){
        cur += cur/100;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3676
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  cin >> s >> k;
  tmp = -1;
  rep(i, Size(s)) {
    if (s[i] == '1')
      tmp = i;
    else {
      ans = s[i] - '0';
      break;
    }
  }
  tmp++;
  if (tmp >= k)
    Cout(1);
  else
    Cout(ans);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<int(n);++i)
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for copy
// for(int i=0;i<N;++i) {

int main(void) {
  string s;cin>>s;
  int q;cin>>q;
  int mark = 0; // false 0
  string l="";
  string r="";
  REP(i,q) {
    int t;cin>>t;
    if(t==1) {
      mark = (mark+1)%2;
    } else if(t==2){
      int f;cin>>f;
      char c;cin>>c;
      if(mark==1) {
        if(f==1) {
          l.push_back(c);
        } else if(t==2) {
          r.push_back(c);
        }
      } else {
        if(f==1) {
          r.push_back(c);
        } else if(t==2) {
          l.push_back(c);
        }
      }
    }
  }
  // pr(mark);
  // pr(r);
  // pr(s);
  // pr(l);
  if(mark) {
    reverse(l.begin(),l.end());
    reverse(s.begin(),s.end());
    pr(l+s+r);
  } else {
    reverse(r.begin(),r.end());
    pr(r+s+l);
  }
  return 0;
}


Measured memory_bytes: 1348
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <ccomplex>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <numeric>
#include <sstream>
#include <set>
#include <tuple>
#include <iomanip>

using namespace std;
#define MAX 1LL << 60

typedef long long ll;

#define rep(i, s, e) for(ll i = s; i < e; i++)
#define repR(i, s, e) for(ll i = s; i > e; i--)
#define reft0(i, j) setfill('0') << setw(i) << j

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

int main(){
    ll A, B, K;
    cin >> A >> B >> K;

    int cnt = 0;
    repR(i, 100, 0){
        if ((0 == A % i) && (0 == B % i)){
            cnt++;

            if (cnt == K){
                cout << i << endl;
                return 0;
            }
        }
    }

    return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	if(S>="A"&&S<="Z") cout<<"A"<<endl;
	else cout<<"a"<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
	ll N, M;
	cin >> N >> M;
	vector<ll> t(M,0);
	vector<vector<ll> > A(N,t);
	for (ll i=0; i<N; i++) {
		ll K;
		cin >> K;
		for (ll j=0; j<K; ++j) {
			ll v;
			cin >> v;
			A[i][v-1] = 1; // 0 index
		}
	}
	vector<ll> ans;
	for (ll j=0; j<M; j++) {
		ll result = true;
		for (ll i=0; i<N; ++i) {
			if (A[i][j] == 0) {
				result = false;
				break;
			}
		}
		if (result) {
			ans.push_back(j);
		}
	}
	cout << ans.size() << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define ppi pair<int,pair<int,int> >
#define fr first
#define sc second
#define PI acos(-1)
#define mp make_pair

using namespace std;


#define sim template < class c

#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


int a[100010];
int b[100010];
int n;
int main()
{
    ios::sync_with_stdio(0);
    cin .tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        b[i] = a[i] > a[i-1];
        b[i] += b[i-1];
    }
    int ans = 0 ;
    for(int i = 1;i < n;i++){
      int shit = upper_bound(b + i,b + n + 1,b[i])-(b + i) - 1;
        ans = max(ans , shit);
    }
    cout << ans;

    return 0;
}


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

int main(){
    int n; cin >> n;
    //cout <<　fixed << setprecision(15) << (double)2*M_PI*n << endl;
     cout << fixed << setprecision(15) << (double)2*M_PI*n << endl;
    return 0;
}

Measured memory_bytes: 3788
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <fstream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#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 ALL(s) begin(s),end(s)
#define ITE(c) typeof((c).begin())
#define VIEW(dat) for(auto v : dat){cout<<v<<endl;}
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))


using namespace std;

string valOf(int n){ stringstream ss;ss<<n;return ss.str();}
int    valOf(string s){return atoi(s.c_str());}
int    valOf(char s){return (unsigned int)(s - '0');}

int enc(string s){
	int rl=0;
	for(int i=s.size();i>=0;i--){
		if(s[i]=='m'){
			if(i-1>=0){ 
				if(s[i-1]!='m'&&s[i-1]!='c'&&s[i-1]!='x'){ 
					rl+=valOf(s[i-1])*1000;
				}else{
					rl+=1000;
				}
			}else{
				rl+=1000;
			}
		}else if(s[i]=='c'){
			if(i-1>=0){
				if(s[i-1]!='m'&&s[i-1]!='c'&&s[i-1]!='x'){ 
					 rl+=valOf(s[i-1])*100;
				}else{
					rl+=100;
				}
			}else{
				rl+=100;
			}
		}else if(s[i]=='x'){
			if(i-1>=0){
				if(s[i-1]!='m'&&s[i-1]!='c'&&s[i-1]!='x'){ 
					 rl+=valOf(s[i-1])*10;
				}else{
					rl+=10;
				}
			}else{
				rl+=10;
			}
		}else if(s[i]=='i'){
			if(i-1>=0){
				if(s[i-1]!='m'&&s[i-1]!='c'&&s[i-1]!='x'){ 
					 rl+=valOf(s[i-1]);
				}else{
					rl+=1;
				}
			}else{
				rl+=1;
			}
		}
	}
	return rl;
}

string deco(int a){
	string rls="";
	int tmp=0;
	while(a>=1000){	tmp++;	a-=1000;}
	if(tmp){ 
		if(tmp!=1){
			rls+=valOf(tmp)+"m";
		}else{
			rls+="m";
		}
	}
	tmp=0;
	while(a>=100){	tmp++;	a-=100;}
	if(tmp){ 
		if(tmp!=1){
			rls+=valOf(tmp)+"c";
		}else{
			rls+="c";
		}
	}
	tmp=0;
	while(a>=10){	tmp++;	a-=10;}
	if(tmp){ 
		if(tmp!=1){
			rls+=valOf(tmp)+"x";
		}else{
			rls+="x";
		}
	}
	if(a){
		if(a!=1){
			rls+=valOf(a)+"i";
		}else{
			rls+="i";
		}
	}
	return rls;
}

int main(){
	int N;
	
	//ifstream cin("in.txt");
	
	cin>>N;
	while(N--){
		string a, b;
		cin>>a>>b;
		cout<<deco(enc(a)+enc(b))<<endl;;
	}
	
	
}

Measured memory_bytes: 1232
#include <stdio.h>
#include <string.h>

int main(void) {
	char str[201], tmp[201];
	int m, h, len;
	int i;
	
	while (scanf("%s", str), strcmp(str, "-")) {
		scanf("%d", &m);
		
		len = strlen(str);
		
		while (m--) {
			scanf("%d", &h);
			
			strcpy(tmp, &str[h]);
			strncat(tmp, str, h);
			tmp[len] = '\0';
			
			strcpy(str, tmp);
		}
		
		puts(str);
	}
	return 0;
}

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

using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
double const PI = 3.1415926535897932384626433;
using P = pair<int, int>;

int main() {
    int n;
    cin >> n;
    cout << n / 3 << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int n, m;
  cin >> n >> m;
  int sum = 0;
  int t;
  rep(i, m) {
    cin >> t;
    sum += t;
  }

  if (n - sum >= 0) cout << n - sum << endl;
  else cout << -1 << endl;
}


Measured memory_bytes: 3596
S = input()

N = len(S)

ans = "Yes"
for i in range(N // 2 + 1):
    if S[i] != S[- 1 - i]:
        ans = "No"
        break

for i in range(N // 2):
    if S[i] != S[-1 - i - N // 2 - 1]:
        ans = "No"
        break

for i in range(N // 2):
    if S[i + N // 2 + 1] != S[- 1 - i]:
        ans = "No"
        break

print(ans)


Measured memory_bytes: 3060
N, M = map(int,input().split())
H = list(map(int,input().split()))
state = [1 for _ in range(N)]
path_list = []
count = 0
for _ in range(M):
    A,B = map(int,input().split())
    if H[A-1] >= H[B-1]:
        state[B-1] = 0
    if H[B-1] >= H[A-1]:
        state[A-1] = 0
print(sum(state))

Measured memory_bytes: 20144
n,m=map(int,input().split())
flag=[list(input()) for _ in range(n)]
w=[]
b=[]
r=[]
for i in flag:
    w.append(i.count('W'))
    b.append(i.count('B'))
    r.append(i.count('R'))
ans=10**18
for x in range(1,n-1):
    for y in range(x+1,n):
        ans=min(ans,sum(b[:x])+sum(r[:x])+sum(w[x:y])+sum(r[x:y])+sum(w[y:])+sum(b[y:]))
print(ans)


Measured memory_bytes: 5612
// C++ includes
#include <bits/stdc++.h>
// 俳句
using namespace std;

// alias templates
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

// alias declaration
using ll = long long;
using str = string;

using vll = V<ll>;
using vvll = V<vll>;
using vs = V<str>;

// loops
#define FOR(i, a, b)  for (ll i = (a); i <= (ll)(b); i++) // [a,b]
#define rFOR(i, a, b) for (ll i = (b); i >= (ll)(a); i--) // [b,a]
#define REP(i, a) FOR((i), 0, (ll)(a)-1) // [0,a-1]

// for debug
#define dbg(a) cerr << "  " << (#a) << ": " << (a) << "\n";

// procon common constants
const ll MOD_BIG = 1e9 + 7;

int main(void){
    ll a,k,x;
    cin >> k >> x;
    if(500*k >= x){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

int main(){
    ll n;
    cin >> n;
    map<char, vector<string>> s;
    rep(i, n){
        string ss;
        cin >> ss;
        if(ss[0] == 'M' || ss[0] == 'A' || ss[0] == 'R' || ss[0] == 'C' || ss[0] == 'H'){
            s[ss[0]].push_back(ss);
        }
    }
    ll ans = 0;
        rep(i, s.size()){
            for(ll j = i+1; j < s.size(); ++j){
                for(ll k = j+1; k < s.size(); ++k){
                    ans += s[i].size() * s[j].size() * s[k].size();
                }
            }
        }
        cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5748
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]

for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(1,W+1):
        if j >= w:
            DP[i][j] = max(DP[i-1][j],DP[i][j-1],DP[i-1][j-w]+v)
        else:
            DP[i][j] = max(DP[i-1][j],DP[i][j-1])
print(DP[-1][-1])

Measured memory_bytes: 120300
import copy
H, W, K = list(map(int, input().split()))
matrix = [[0 for j in range(W)] for i in range(H)]
matrix2 = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    c_i = input()
    for j in range(W):
        if c_i[j] == '#':
            matrix[i][j] = 1
            matrix2[i][j] = 1
COUNT = 0
for i in range(2**(H+W)):
    x_i = []
    y_i = []
    count = 0
    for j in range(H+W):
        if ((i >> j) & 1):
            if j < H:
                x_i.append(j)
            else:
                y_i.append(j-H)
    for k in x_i:
        for l in range(W):
            matrix[k][l] = -1
    for k in range(H):
        for l in y_i:
            matrix[k][l] = -1
    for k in range(H):
        for l in range(W):
            if matrix[k][l] == 1:
                count += 1
    if count == K:
        COUNT += 1
    matrix = copy.deepcopy(matrix2)
print(COUNT)       

Measured memory_bytes: 9360
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
template<typename T, typename U> inline void chmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> inline void chmin(T &x, U y) { if (x > y) x = y; }


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

    int ans = a*b - a - b + 1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl;
#define printD(a) cout << setprecision(15) << (a) << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<int>& a,int n);

int n;

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int gcd(int u, int v) {
    int r;
    while (0 != v) {
        r = u % v; u = v; v = r;
    }
    return u;
}

signed main(){
    int m;
    cin >> n >> m;
    int t = gcd(n,m);
    int cnt = 1;
    n = sqrt(t);
    for(int i = 1; i <= n;i++){
        if(t%i == 0){
            if(IsPrime(i)){
                cnt++;
            }
            int s = t/i;
            if(IsPrime(s) && s*s != t){
                 cnt++;
                 t /= s;
            }
        }
    }
    print(cnt);
    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<int>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

X = ii()

lim = 10**3
for a in range((-1)*lim, lim+1):
    for b in range((-1)*lim, lim+1):
        if a**5 -b**5 == X:
            print(a, b)
            exit()

Measured memory_bytes: 66184
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 200010
using namespace std;
int n,k,tot=1,cnt,p,a[N];
char s[N];
int main()
{
	scanf("%d%d%s",&n,&k,s+1);
	for (int i=1;i<=n;i++) a[i]=s[i]-'A';
	p=a[1];
	while (k--) { if (!p) p^=1,a[tot]^=1; else p=a[++tot],p^=(++cnt&1); if (tot>n) break; }
	if (tot<=n)	
	{
		for (int i=tot;i<=n;i++) putchar('A'+(a[i]^(cnt&1)));
		int l=tot-1,r=(cnt-1)&1;
		while (l--) putchar('A'+r),r^=1;
	}
	else 
	{
		if ((cnt-1)&1) for (int i=1;i<=n;i++) putchar('A'+(i&1));
		else { putchar('A'+(k&1)); for (int i=1;i<n;i++) putchar('A'+(i&1)); }
	} 
}

Measured memory_bytes: 1408
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#include <vector>

using namespace std;
typedef long long ll;
template <class T = ll>
T in() {
    T x;
    cin >> x;
    return (x);
}
template <class T>
void print(T x) {
    cout << x << "\n";
}
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define reps(x, c) for (auto x : c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair((a), (b))
#define pl pair<ll, ll>
#define INF 2147483600
#define MOD 1000000007
#define fi first
#define se second
#define dbg(x) cerr << #x "=" << (x) << "\n"
#define dbgv(x) \
    cerr << #x << "\n"; \
    reps(y, x) { cerr << y << " "; } \
    cerr << "\n"

int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    vector<ll> b(n + 1);
    vector<ll> w(n + 1);

    FOR(i, 1, n + 1) {
        if (s[i - 1] == '#') {
            b[i]++;
        }
        else {
            w[i]++;
        }
        b[i] += b[i - 1];
        w[i] += w[i - 1];
    }
    ll ans = INF;

    rep(i, n + 1) { ans = min(ans, b[n - i] + w[n] - w[n - i]); }
    cout << ans << endl;
    return 0;
}

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


int main(){
  int N;
  cin >> N;
  vector<int>A(N);
  vector<int>B(N);
  vector<int>C(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
    A.at(i)--;
  }
  for(int i=0;i<N;i++){
    cin >> B.at(i);
  }
  for(int i=0;i<N;i++){
    cin >> C.at(i);
  }
  int ans = 0;
  for(int i=0;i<N;i++){
    ans += B.at(A.at(i));
    if(i>0&&A.at(i)-A.at(i-1)==1){
      ans += C.at(A.at(i-1));
    }
  }
  cout << ans << endl;
}
      


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

const int MAXN = 1000000;
int A[MAXN];

using namespace std; 

int cnt = 0;

void insertionASort(int A[], int n, int g);
void shellSort(int A[], int n);

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &A[i]);
	}
	shellSort(A, n);
	printf("%d\n", cnt);
	for (int i = 0; i < n; i++)
	{
		printf("%d\n", A[i]);
	}
	
	return 0;
}

void insertionASort(int A[], int n, int g)
{
	for (int i = g; i < n; i++)
	{
		int v = A[i];
		int j = i - g;
		for ( ; j >= 0 && A[j] > v; j = j - g)
		{
			A[j + g] = A[j];
			cnt++;
		}
		A[j + g] = v;
	}
}

void shellSort(int A[], int n)
{
	int G[100];
	G[0] = 1;
	int i;
	for (i = 0; i < 110 && G[i] <= n; i++)
	{
		G[i + 1] = G[i] * 3 + 1;
	}
	printf("%d\n", i--);
	for (int j = i; j >= 0; j--)
	{
		printf("%d ", G[j]);
	}
	putchar('\n');
	for (int j = i; j >= 0; j--)
	{
		insertionASort(A, n, G[j]);
	}
}



Measured memory_bytes: 7108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
ll ans;
int main(void){
    cin>>n;
    for(int i=1;i<=n;i++){
        if(i%3!=0&&i%5!=0) ans+=i;
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int H,W,D;
vector<pair<int,int>> A;
vector<ll> ma;
int Q;

void input() {
  cin >>H >>W >>D;
  A.assign(H*W, {0, 0});
  rep(i, H){ rep(j, W){
    int a; cin >>a; a--;
    A[a] = {i, j};
  }}
  ma.assign(H*W, 0);
  // マスの移動は必ずx+Dの数字が書かれているマスへの移動になる
  // ので0～D-1から始まり移動にかかった魔力を累積和的なノリで前計算しておく
  for (int i=0; i<=D-1; i++){
    int t = i;
    while (t + D < H*W){
      ma[t+D] = ma[t] + abs(A[t].first - A[t+D].first) + abs(A[t].second - A[t+D].second);
      t += D;
    }
  }
  cin >>Q;
}

void solve() {
  int L,R; cin >>L >>R; L--; R--;
  ll res = 0;
  if (L == R){
    cout <<res <<endl;
  }else{
    res = ma[R] - ma[L];
    cout <<res <<endl;
  }
}

int main() {
  input();

  rep(q, Q) solve();
}

Measured memory_bytes: 2560
// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll N;
    cin >> N;
    map<ll, ll> A;
    rep (i, N) {
        ll a;
        cin >> a;
        if (a % 4 == 0) {
            A[4] += 1;
        } else if (a % 2 == 0) {
            A[2] += 1;
        } else {
            A[0] += 1;
        }
    }
    if (A[2] == 0) {
        if (A[0] <= A[4] + 1) {
            cout << "Yes" << endl;
            return 0;
        }
    } else {
        if (A[0] <= A[4]) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


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

void solv() {
    int A;
    cin >> A;
    if(A >= 1200){
        cout << "ARC" << endl;
        return;
    }
    cout << "ABC" << endl;
}

int main() {
    solv();
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>

int bonuse(int *a, int *c){
    int tmp = 0;
    do{
        if(*(a + 1) - *a == 1){
            tmp += c[*a - 1];
        }
        *a++;
    }while(*(a + 1));

    return tmp;
}

int sumb(int *b){
    int tmp = 0;
    int i;

    do{
        tmp += *b;
    }while(*b++);

    return tmp;
}

int main(void){
    int n;
    int a[100] = {0};
    int b[100] = {0};
    int c[100] = {0};
    int i;

    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
     for(i = 0; i < n; i++){
        scanf("%d", &b[i]);
    }
     for(i = 0; i < n - 1; i++){
        scanf("%d", &c[i]);
    }

    printf("%d", sumb(b) + bonuse(a, c));

    return 0;
}

Measured memory_bytes: 128
from sys import stdin
from collections import defaultdict
readline = stdin.readline
 
 
def main():
    n = int(readline())
    g = dict()
    for i in range(n):
        nodes = list(map(int, readline().split()))
        g[i] = nodes[1:]
    
    euler, height = euler_tour(g, n)
    index = defaultdict(list)
    for i in range(len(euler)):
        index[euler[i]].append(i)
    rmql = [(height[i], i) for i in euler]
    rmq = segment_tree(rmql,min,(float('inf'),))
 
    q = int(readline())
    for i in range(q):
        u, v = map(int, readline().split())
        l, r = index[u][0], index[v][-1]
        if l > r:
            l, r = index[v][0], index[u][-1]
        print(rmq.find(l, r)[1])
 
 
def euler_tour(g, size):
    height = [None] * size
    euler = []
    root = 0
    dfs_stack = [(root, None, 0)]
    while dfs_stack:
        u, prev, h = dfs_stack.pop()
        height[u] = h
        euler.append(prev)
        if g[u]:
            dfs_stack.extend((v, u, h + 1) for v in g[u])
        else:
            euler.append(u)
    return euler[1:], height
     
import math
class segment_tree:
    def __init__(self, dat, query, default=0):
        self.offset = 2 ** math.ceil(math.log(len(dat), 2))
        self.table = [default] * self.offset + dat + [default] * (self.offset - len(dat))
        self.query = query
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.query(self.table[2 * i], self.table[2 * i + 1])
 
    # [l, r] closed-interval
    def find(self, l, r):
        return self.query(self.__range(l,r))
 
    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
         
    def update(self, i, x):
        i += self.offset
        self.table[i] = x
        while 1 < i:
            i >>= 1
            self.table[i] = self.query(self.table[2 * i], self.table[2 * i + 1])
main()

Measured memory_bytes: 82596
import java.util.Scanner;

public class Main {

    static class Node{
        int parent;
        int left;
        int right;

        public Node() {
            this.parent = -1;
            this.left = -1;
            this.right = -1;
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        T = new Node[n];
        D = new int[n];
        H = new int[n];
        int t,l,r;
        for(int i = 0 ; i < n; i ++){
            T[i] = new Node();
        }
        for(int i = 0 ; i < n; i ++){
            t = sc.nextInt();
            l = sc.nextInt();
            r = sc.nextInt();
            T[t].left = l;
            T[t].right = r;
            if(l != -1){
                T[l].parent = t;
            }
            if(r != -1){
                T[r].parent = t;
            }
        }

        for(int i = 0; i < n; i ++){
            if(T[i].parent == -1){
                R = i;
                break;
            }
        }

        setDepth(R,0);
        setHeight(R);

        print();
    }


    static Node[] T;
    static int[] D,H;
    static int n;
    static int R;

    static void print(){
        for(int i = 0; i < n; i ++){
            System.out.print("node " + i +": parent = " + T[i].parent +", sibling = " + getSibling(i));
            System.out.print(", degree = " + getDegree(i) +", ");
            System.out.print("depth = " + D[i] +", ");
            System.out.print("height = " + H[i] +", ");
            System.out.print(type(i));
            System.out.println();
        }
    }

    static int getSibling(int u){
        if(T[u].parent != -1){
            int p = T[u].parent;
            if(T[p].left != -1 && T[p].left != u){
                return T[p].left;
            }
            else if(T[p].right != -1 && T[p].right != u){
                return T[p].right;
            }
        }
        return -1;
    }


    static int getDegree(int u){
        int d = 0;
        if(T[u].right != -1){
            d++;
        }
        if(T[u].left != -1){
            d++;
        }
        return d;
    }


    static void setDepth(int u,int d){
        if(u == -1) return;
        D[u] = d;
        setDepth(T[u].left,d + 1);
        setDepth(T[u].right,d + 1);
    }

    static int setHeight(int u){
        int h1= 0,h2 = 0;
        if(T[u].left != -1){
            h1 = setHeight(T[u].left) + 1;
        }
        if(T[u].right != -1){
            h2 = setHeight(T[u].right) + 1;
        }
        H[u] = Math.max(h1,h2);
        return Math.max(h1,h2);
    }


    static String type(int u){
        String type;
        if(T[u].parent == -1){
            type = "root";
        }
        else if(T[u].left == -1 && T[u].right == -1){
            type = "leaf";
        }
        else {
            type = "internal node";
        }
        return type;
    }
}



Measured memory_bytes: 26348
N = int(input())
D, X = map(int, input().split())

A = [int(input()) for i in range(N)]

count = 0
for i in A:
    count += 1
    tmp = i
    for n in range(1,100):
        if D >= i*n +1:
            count += 1
        else:
            break
print(count+X)

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

typedef long long ll;

const ll INF = 1ll << 60;

string N;
ll L;
vector<ll> M;
ll Dp[2000000][2];
int main() {
  cin >> N;
  reverse(N.begin(), N.end());
  ll L = N.size();
  M.resize(L);
  for (ll i = 0; i < L; ++i) M[i] = N[i] - '0';
  N.clear();
  Dp[0][0] = 0;
  Dp[0][1] = INF;
  for (ll i = 0; i < L; ++i) {
    Dp[i + 1][0] = min(M[i] + Dp[i][0], M[i] + 1 + Dp[i][1]);
    Dp[i + 1][1] = min(10 - M[i] + Dp[i][0], 9 - M[i] + Dp[i][1]);
  }
  cout << min(Dp[L][0], 1 + Dp[L][1]) << endl;
  return 0;
}


Measured memory_bytes: 25604