akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

int main() {
    int n;
    cin >> n;
    vector<int> c(n + 1);
    for (int i = 1; i < n; ++i) {
        int x;
        cin >> x;
        c[x]++;
    }
    for (int i = 1; i <= n; ++i) {
        cout << c[i] << '\n';
    }
    return 0;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vv vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define INF 100000000000
#define eps 1e-7
#define mod 1000000007
#define int ll
using namespace std;

int N;
int ans = 0;

signed main(void) {
    cin >> N;

    for (int p=1; p*p<=N; p++) {
        if (N % p == 0) { //約数
            int m_plus_one = N / p;
            int m = m_plus_one - 1;
            if (m==0) continue;
            if (N % m == N / m) ans += m;
        }
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
using namespace std;
typedef string::const_iterator State;

int number(State &begin);
int factor(State &begin);
int term(State &begin);
int expression(State &begin);

int main(void){
  int N;
  cin >> N;
  cin.ignore();
  for(int i = 0; i < N; i++){
    string Expression;
    getline(cin, Expression);

    State begin = Expression.begin();
    int ans = expression(begin);
    cout << ans << endl;
  }
  return 0;
}

int number(State &begin){
  int ret = 0;

  while(isdigit(*begin)){
    ret = ret * 10;
    ret = ret + *begin - '0';
    begin++;
  }
  return ret;
}

int factor(State &begin){
  if(*begin == '('){
    begin++;
    int ret = expression(begin);
    begin++;
    return ret;
  }else{
    return number(begin);
  }
}

int term(State &begin){
  int ret = factor(begin);

  while(true){
    if(*begin == '*'){
      begin++;
      ret = ret * factor(begin);
    }else if(*begin == '/'){
      begin++;
      ret = ret / factor(begin);
    }else{
      break;
    }
  }
  return ret;
}

int expression(State &begin){
  int ret = term(begin);

  while(true){
    if(*begin == '+'){
      begin++;
      ret = ret + term(begin);
    }else if(*begin == '-'){
      begin++;
      ret = ret - term(begin);
    }else{
      break;
    }
  }

  return ret;
}

Measured memory_bytes: 1212
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var K = int.Parse(ReadLine());
        var S = ReadLine();

        var ans = (S.Length <= K) ? S : S.Substring(0, K) + "...";

        WriteLine(ans);
    }
}

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

typedef long long ll;

#define int ll
#define all(v) v.begin(), v.end()
#define reps(__i, a, b) for (int __i = a; i < b; i++)
#define rep(__i, n) reps(__i, 0, n)

const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;

signed main()
{
    int n, d;
    cin >> n >> d;

    cout << (n + (d * 2 + 1) - 1) / (d * 2 + 1) << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    string s;
    cin >> s;
    string ret;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '0')
            ret.push_back('0');
        else if (s[i] == '1')
            ret.push_back('1');
        else if (ret.size() > 0)
            ret.pop_back();
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 256
import fractions
a,b=map(int,input().split())
c=fractions.gcd(a,b)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
if c==1:
  print(1)
else:
  print(len(factorization(c))+1)

Measured memory_bytes: 5048
#include <bits/stdc++.h>
#define lol long long
using namespace std;
int main(){
    string s;
    cin>>s;
    for(int i=0;i<19;i++){
        if(i==5 || i==13) cout<<' ';
        else cout<<s[i];
    }
    cout << "\n";
    return(0);
}

Measured memory_bytes: 3560
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

int main()
{
	unsigned long long x;
	cin >> x;

	auto count = x / 11 * 2;
	if (x % 11 > 0)
	{
		++count;
		if (x % 11 > 6)
		{
			++count;
		}
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define ODR(ch) ((int)(ch - 'a'))

int main(void)
{
  char str[100];
  scanf("%s", str);
  int len = strlen(str), i, cnt[28];
  for(i = 0; i < 28; ++i) { cnt[i] = 0; }
  for(i = 0; i < len; ++i) { ++cnt[ODR(str[i])]; }
  bool flg = true;
  for(i = 0; i < 28; ++i) {
    if(cnt[i] % 2 != 0) { flg = false; break; }
  }
  if(flg) { printf("Yes\n"); } else { printf("No\n"); }
  return 0;
}

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

import numpy as np
N = int(input())
A = list(map(int, input().split()))

A_diff = np.array([a - i for i, a in enumerate(A, 1)])
my_median = np.median(A_diff)

print(int(np.sum(np.abs(A_diff * -1 + my_median))))

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

int main(void) {
 
  // 入力
  int n;
  scanf("%d",&n);
  int list[n];
  for(int i=0;i<n;i++){
    scanf("%d",&list[i]);
  }
  
  int max=0,maxIdx=0,secondMax=0;
  for(int i=0;i<n;i++){
      if(list[i]>max){
          max=list[i];
          maxIdx=i;
      }
  }
  for(int i=0;i<n;i++){
      if(list[i]>secondMax&&i!=maxIdx){
          secondMax=list[i];
      }
  }

  for(int i=0;i<n;i++){
    if(i==maxIdx)printf("%d\n",secondMax);
    else         printf("%d\n",max);
  }

  return 0;
}

Measured memory_bytes: 2304
#define r(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#include <bits/stdc++.h>
#include <cmath>
#include <fstream>
#define f first
#define endl "\n"
#define s second
#define pb push_back
#define ms(a,b) memset(a,b,sizeof(a))
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
typedef long long ll;
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
char _;

int k;
bool ind = false;
void solve(int a,int b, int c, int count){
	if(ind) return;
	if(k==count){
		if(c>b && b>a){
			cout << "Yes" << endl;
			ind = true;
		}
		return;
	}
	
	solve(a*2,b,c,count+1);
	solve(a,b*2,c,count+1);
	solve(a,b,c*2,count+1);
	
	return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int a,b,c;
	cin>>a>>b>>c>>k;

	solve(a*2,b,c,1);
	solve(a,b*2,c,1);
	solve(a,b,c*2,1);

	if(!ind) cout << "No" <<endl;
	return 0;
}


Measured memory_bytes: 3648
#include <stdio.h>

int main(void){

	int sum;
	int lp,mp;
	int lpc,mpc;

	scanf("%d",&sum);
	scanf("%d %d",&lp,&mp);
	scanf("%d %d",&lpc,&mpc);

	if(lp%lpc != 0)
		lp+=lpc-lp%lpc;
	if(mp%mpc != 0)
		mp+=mpc-mp%mpc;

	if( lp/lpc > mp/mpc)
		printf("%d\n",sum-lp/lpc);
	else
		printf("%d\n",sum-mp/mpc);

	return 0;
}

Measured memory_bytes: 596
#include <stdio.h>
#define ROW 100
#define COLUMN 100
int main(void)
{
	int r, c, i, j, s;
	int list[ROW][COLUMN];
	int sum[COLUMN] = {0};
	scanf("%d%d", &r, &c);
	for(i=0; i<r; i++){
		for(j=0; j<c; j++){
			scanf("%d", &list[i][j]);
		}
	}
	for(i=0; i<r; i++){
		s=0;
		for(j=0; j<c; j++){
			printf("%d ", list[i][j]);
			s += list[i][j];
			sum[j] += list[i][j];	
		}
		printf("%d\n", s);
	}
	s=0;
	for(j=0; j<c; j++){
		printf("%d ", sum[j]);
		s += sum[j];
	}
	printf("%d\n", s);
	return 0;
}

Measured memory_bytes: 636
a,b=map(int,input().split())

def gcd(a,b):
  if a<b:
    a,b=b,a
  while a%b:
    a,b=b,a%b
  return b

g=gcd(a,b)

f=set()
for i in range(1,int(g**0.5)+1):
  if g%i==0:
    for j in range(2,int(i**0.5)+1):
      if i%j==0:
        break
    else:
      f.add(i)
    p=g//i
    for j in range(2,int(p**0.5)+1):
      if p%j==0:
        break
    else:
      f.add(p)

print(len(f))

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
        new Main().run();
    }
	int init;
	int year;
	public void run(){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int set = scan.nextInt();
			for(int data = 0;data < set;data++){
				init = scan.nextInt();
				year = scan.nextInt();
				int max = 0;
				int n = scan.nextInt();
				int type;
				double r;
				int f;
				for(int i = 0;i < n;i++){
					type = scan.nextInt();
					r = scan.nextDouble();
					f = scan.nextInt();
					if(type == 1){
						max = Math.max(max,simp(r,f));
					}else if(type == 0){
						max = Math.max(max,comp(r,f));
					}
				}
				System.out.println(max);
			}
		}
	}
	public int simp(double r,int f){
		int a;
		int i;
		for(a = init,i=0;i<year;i++){
			a += ((int)(r*a) - f);
		}
		return a;
	}
	public int comp(double r,int f){
		int a;
		int b;
		int i;
		int total;
		for(a=init,i=0,total=0,b=0;i<year;i++){
			b = (int)(a*r);
			a -= f;
			total += b;
		}
		return a + total;
	}
}

Measured memory_bytes: 41956
#include<bits/stdc++.h>
#define Min(a,b,c) min((a),min((b),(c)))
#define Max(a,b,c) max((a),max((b),(c)))
#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pb(x) push_back(x)
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-11
#define N 2000005
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
#define pi 3.14159265359
using namespace std;
typedef long long LL;
int main()
{
	LL h,w;
	scanf("%lld %lld",&h,&w);
	if(h%3==0||w%3==0){
		printf("0\n");
		return 0;
	}
	LL ans=1e10;
	for(int i=1;i<w;i++){
		LL a=i*h;
		LL b=w-i;
		LL c=h;
		if(b*c%2==0){
			ans=min(abs(b*c/2-a),ans);
		}else{
			LL bb=b/2*c,cc=(b/2+1)*c;
			ans=min(abs(Max(a,bb,cc)-Min(a,bb,cc)),ans);
			bb=c/2*b,cc=(c/2+1)*b;
			ans=min(abs(Max(a,bb,cc)-Min(a,bb,cc)),ans);
		}
	}
	swap(w,h);
	for(int i=1;i<w;i++){
		LL a=i*h;
		LL b=w-i;
		LL c=h;
		if(b*c%2==0){
			ans=min(abs(b*c/2-a),ans);
		}else{
			LL bb=b/2*c,cc=(b/2+1)*c;
			ans=min(abs(Max(a,bb,cc)-Min(a,bb,cc)),ans);
			bb=c/2*b,cc=(c/2+1)*b;
			ans=min(abs(Max(a,bb,cc)-Min(a,bb,cc)),ans);
		}
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 256
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In,' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var SumA = new int[N];

            SumA[0] = cin.ReadInt;
            for(var i = 1; i < N; i++){
                var A = cin.ReadInt;
                SumA[i] = SumA[i-1] + A;
            }

            var index = 0;
            for(var i = 0; i < N; i++){
                if(SumA[i] > SumA[N-1] - SumA[i]){
                    index = i;
                    break;
                }
            }

            var ans = 0;
            if(2 * SumA[index] - SumA[N-1] > -2 * SumA[index-1] + SumA[N-1]){
                ans = -2 * SumA[index-1] + SumA[N-1];
            }else{
                ans = 2 * SumA[index] - SumA[N-1];
            }

            WriteLine(ans);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream,char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if(inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for(int i = 0;i < tmp.Length;i++)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }

        
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }

}


Measured memory_bytes: 13268
from copy import deepcopy
h,w,k=map(int,input().split())
c = [[0 for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    s = input()
    for j in range(w):
        if(s[j]=="#"):
            c[i][j] = 1

for i in range(2**h):
    ca = deepcopy(c)
    for d in range(h):
        if((i>>d) & 1):
            for e in range(w):
                ca[d][e] = 0
    for j in range(2**w):
        cb = deepcopy(ca)
        for d in range(w):
            if((j>>d)&1):
                for e in range(h):
                    cb[e][d] = 0
        summ = 0
        for j in range(h):
            summ += sum(cb[j])
        if(summ == k):
            ans += 1

print(ans)

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

vector<vector<int>> g, e;
int mx = 0;
void dfs(int pre, int crt)
{
  int c = 0;
  for (auto nxt : g[crt])
  {
    if (e[nxt][2] != 0)
      continue;
    c++;
    if (c == pre)
      c++;
    e[nxt][2] = c;
    dfs(c, e[nxt][0] != crt ? e[nxt][0] : e[nxt][1]);
  }
  mx = max(mx, c);
}

int main()
{
  int n;
  cin >> n;
  g.resize(n);
  e.resize(n - 1);

  rep(i, n - 1)
  {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(i);
    g[b].push_back(i);
    e[i].resize(3);
    e[i][0] = a;
    e[i][1] = b;
  }
  dfs(0, 0);
  cout << mx << endl;
  rep(i, n - 1)
    printf("%d\n", e[i][2]);
  return 0;
}

Measured memory_bytes: 11520
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	string o,e;

	cin >> o;
	cin >> e;

	int N = o.size() + e.size();
	int idx_o = 0;
	int idx_e = 0;
	FOR(i,1, N+1){
		if(i%2 == 1){ 
			cout << o[idx_o++];
		}else{
			cout << e[idx_e++];
		}
	}
	cout << endl;


	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const int mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

struct edge{
    int to, id;
    edge() = default;
    edge(int to, int id) : to(to), id(id) {}
};

int n, m;
vector<edge> graph[55];
vector<int> path[25];

bool dfs(int st, const int& goal, const int& id, int parent = -1){
    if(st == goal){
        return true;
    }
    for(int i = 0; i < graph[st].size(); ++i){
        int v = graph[st][i].to;
        if(v == parent) continue;
        if(dfs(v, goal, id, st)){
            path[id].push_back(graph[st][i].id);
            return true;
        }
    }
    return false;
}

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

    cin >> n;
    for(int i = 0; i < n - 1; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        graph[a].push_back(edge(b, i));
        graph[b].push_back(edge(a, i));
    }
    cin >> m;
    vector<ll> eset(m, 0ll);
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        dfs(u, v, i);
        for(int bit : path[i]){
            eset[i] |= 1ll << bit;
        }
    }

    vector<ll> pow2(n+1);
    pow2[0] = 1;
    for(int i = 1; i <= n; ++i) pow2[i] = pow2[i-1] * 2;

    ll res = 0;
    for(int bit = 0; bit < (1 << m); ++bit){
        ll mask = 0;
        for(int i = 0; i < m; ++i){
            if(bit & (1 << i))  mask |= eset[i];
        }
        int cnt = __builtin_popcountll(mask);
        int sign = (__builtin_popcountll(bit) % 2 == 0) ? 1 : -1;
        res += pow2[n - cnt - 1] * sign;
    }

    cout << res << endl;
}

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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

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

    int n;
    cin >> n;
    vi a(n);
    for (auto& x : a) {
        cin >> x;
    }
    vi p(n), s(n);
    p[0] = a[0];
    s[n - 1] = a[n - 1];
    for (int i = 1; i < n; ++i) {
        p[i] = max(a[i], p[i - 1]);
    }
    for (int i = n - 2; i >= 0; --i){
        s[i] = max(a[i], s[i + 1]);
    }

    vi ans(n);
    ans[0] = s[1];
    ans[n - 1] = p[n - 2];
    for (int i = 1; i + 1 < n; ++i) {
        ans[i] = max(p[i - 1], s[i + 1]);
    }

    for (auto& x : ans) {
        cout << x << '\n';
    }
    
    return 0;
}


Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
const long long maxn=205;
const long long inf=1e18;
long long x[maxn],y[maxn],p[maxn],ans[maxn],res[maxn][maxn],n; 
void dfs(long long i,long long num)
{
	if(i==n)
	{
		long long x=0;
		ans[num]=min(ans[num],accumulate(res[n],res[n]+n,x));
		return ;
	}
	for(long long j=0;j<n;j++)
		res[i+1][j]=res[i][j];
	dfs(i+1,num);
	for(long long j=0;j<n;j++)
		res[i+1][j]=min(res[i][j],p[j]*abs(x[j]-x[i]));
	dfs(i+1,num+1);
	for(long long j=0;j<n;j++)
		res[i+1][j]=min(res[i][j],p[j]*abs(y[j]-y[i]));
	dfs(i+1,num+1);
}
int main(){
  	scanf("%lld",&n);
	for(long long i=0;i<n;i++)
      	scanf("%lld%lld%lld",&x[i],&y[i],&p[i]);
	for(long long i=0;i<n;i++)
	{
		res[0][i]=p[i]*min(abs(x[i]),abs(y[i]));
		ans[i]=inf;
	}
	dfs(0,0);
	for(long long i=0;i<=n;i++)
      	printf("%lld\n",ans[i]);
	return 0;
}




Measured memory_bytes: 3820
/* Bismillahirrahmanirrahim */
/* Author : Jehian Norman Saviero (@Reiva5) */
#include <bits/stdc++.h>
 
// MACROS SAMPAH
#define Jehian using
#define Norman namespace
#define Saviero std
 
Jehian Norman Saviero;
 
// MACROS TYPE
typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
 
// MACROS FOR PRINT
#define nl printf("\n")
#define sp printf(" ")
 
// MACROS FOR ATTRIBUTE
#define fi first
#define se second
 
// MACROS FOR FUNCTION AND METHOD
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ALL(x) (x).begin(), (x).end()
#define ALLN(x,n) (x), (x)+(n)
#define CUBE(x) (SQR(x)*(x))
#define SET(x,y) for (int _qwe = sizeof(x)/sizeof(x[0]); _qwe; ) x[--_qwe] = (y)
#define SQR(x) ((x)*(x))
#define SSORT(x,sz) sort(ALLN(x,sz))
#define RESET(x) memset((x), 0, sizeof(x))
#define VSORT(x) sort(ALL(x))
 
// MACROS READ INPUT
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%ld", &x)
#define scll(x) scanf("%lld", &x)
#define scul(x) scl(x)
#define scull(x) scll(x)

const int sz = 1e6+5;
int cnt[sz];

int main() {
	RESET(cnt);
	for (int x = 1; x <= 100; ++x) {
		for (int y = 1; y <= 100; ++y) {
			for (int z = 1; z <= 100; ++z) {
				++cnt[x * x + y * y + z * z + x * y + y * z + x * z];
			}
		}
	}
	int N;
	sci(N);
	for (int i = 1; i <= N; ++i) {
		printf("%d\n", cnt[i]);
	}
	return 0;
}

Measured memory_bytes: 7712
def weight
  master = Array.new(10) { |i| 2**i }
  while gets
    wei = $_.to_i
    spindles = master.select { |i| i <= wei }
    result = []
    while true
      break if wei <= 0
      minus = spindles.max
      if minus > wei
				spindles.delete(minus)
        next
      end
      foo = wei - minus
			wei = foo
      spindles.delete(minus)
      result << minus
    end
    puts result.sort.join(' ')
  end
end

weight

Measured memory_bytes: 8616
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;

int main() {
  int N, T;
  int ans = 0;
  int mint = 10001;
  int minc = 10001;

  cin >> N >> T;

  vector<int> c(N);
  vector<int> t(N);
  for(int i = 0; i < N; i++){
    cin >> c[i] >> t[i];
    if(t[i] <= T && minc > c[i]){
      mint = t[i];
      minc = c[i];
    }
  }
  if(minc == 10001){
  cout << "TLE" << endl;
  }else{
  cout << minc << endl;
  }
}


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

int64 Solve(const int n, const vector<int64>& a, const vector<int64>& b) {
  vector<bool> usable(n, true);
  vector<int64> ia(n), ib(n);
  for (int i = 0; i < n; ++i)
    ia[i] = ib[i] = i;
  sort(ia.begin(), ia.end(), [&a, &b](const int x, const int y) {
      int64 sx = a[x] + b[x];
      int64 sy = a[y] + b[y];
      if (sx != sy)
        return sx > sy;
      return a[x] > a[y];
    });
  sort(ib.begin(), ib.end(), [&a, &b](const int x, const int y) {
      int64 sx = a[x] + b[x];
      int64 sy = a[y] + b[y];
      if (sx != sy)
        return sx > sy;
      return b[x] > b[y];
    });

  int64 ret = 0;
  auto ita = ia.begin();
  auto itb = ib.begin();
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0) {
      while (ita != ia.end() && !usable[*ita])
        ++ita;
      ret += a[*ita];
      usable[*ita] = false;
    } else {
      while (itb != ib.end() && !usable[*itb])
        ++itb;
      ret -= b[*itb];
      usable[*itb] = false;
    }
  }

  return ret;
}

int main() {
  int64 n;
  cin >> n;
  vector<int64> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
  }
  cout << Solve(n, a, b) << "\n";
  return 0;
}


Measured memory_bytes: 3328
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**7)
rs = lambda: sys.stdin.readline().rstrip()
ri = lambda: int(rs())
rf = lambda: float(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]
rf_ = lambda: [float(_) for _ in rs().split()]
INF = float('inf')
MOD = 10 ** 9 + 7
# endregion
print('ABC' + rs())

Measured memory_bytes: 62956
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ll_s long
#define mod 1000000007
#define forn(i,start,lim) for(ll i=start;i<lim;i++)
#define forn_d(i,start,lim) for(ll i=start;i>=lim;i--)
#define f first
#define s second
#define pb push_back
#define pf push_front
#define mp make_pair
#define debug1(a) cout<<"------\n"<<#a<<" = "<<a<<endl<<"------"<<endl
#define debug2(a,b) cout<<"--------------\n"<<#a<<" = "<<a<<" ; "<<#b<<" = "<<b<<endl<<"--------------"<<endl
#define debug3(a,b,c) cout<<"----------------------\n"<<#a<<" = "<<a<<" ; "<<#b<<" = "<<b<<" ; "<<#c<<" = "<<c<<endl<<"----------------------"<<endl
#define sz(a) (ll)(a.size())
#define debug4(a) cout<<"chu "<<a<<endl
#define endl "\n"

int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  string s,t;
  cin>>s>>t;
  s=" "+s;
  t=" "+t;
  ll n=sz(s),m=sz(t);
  vector <vector<ll>> dp(n+5,vector<ll>(m+5,0LL));
  for(ll i=1;i<n;i++){
    for(ll j=1;j<m;j++){
      if(s[i]==t[j])
        dp[i][j]=1+dp[i-1][j-1];
      else
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
  }
  /*for(ll i=1;i<n;i++){
    for(ll j=1;j<m;j++)
      cout<<dp[i][j]<<" ";
    cout<<endl;
  }*/
  string ans;
  ll i=n-1,j=m-1;
  while(i!=0 && j!=0){
    if(s[i]==t[j]){
      ans.pb(s[i]);
      i--;
      j--;
    }else{
      if(dp[i-1][j]>dp[i][j-1]){
        i--;
      }else{
        j--;
      }
    }
  }
  reverse(ans.begin(),ans.end());
  cout<<ans<<endl;
  return 0;
}


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

int main() {
	int n,l,r,hantei,count;
	string s;
	while(1){
		l = r = hantei = count = 0;
		cin >> n;
		if(n == 0)break;
		for(int i = 0;i < n;i++){
			cin >> s;
			if(s == "lu"){
				l = 1;
			}
			else if(s == "ru"){
				r = 1;
			}
			else if(s == "ld"){
				l = 0;
			}
			else if(s == "rd"){
				r = 0;
			}
			if(l == 1 && r == 1 && hantei == 0){
				count++;
				hantei = 1;
			}
			else if(l == 0 && r == 0 && hantei == 1){
				count++;
				hantei = 0;
			}
		}
		cout << count << endl;
	}
	return 0;
}

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

int main (void) {
    unsigned long long n;
    cin >> n;

    unsigned long long ans = 0;
    for (unsigned long long i = 1; i * i < n; i++) {
        if (n % i) continue;
        if (i + 1 == n / i) continue;
        ans += n / i - 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>

const int Mod = 1000000007;
const int MN = 20, MM = 20;

inline void Add(int &x, int y) { x -= Mod - y; x += x >> 31 & Mod; }

int N, M, K, t[MM][MN];
int f[2][1 << MN];

int main() {
	scanf("%d%d%d", &N, &M, &K), --N;
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N; ++j)
			t[i][j] = -1;
	for (int i = 1; i <= K; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		t[--a][--b] = c;
	}
	int o = 0;
	f[o][0] = 1;
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			o ^= 1;
			for (int S = 0; S < 1 << N; ++S) f[o][S] = 0;
			for (int S = 0; S < 1 << N; ++S) if (f[o ^ 1][S]) {
				int v = f[o ^ 1][S];
				if (t[i][j] != 1) {
					if (~S >> j & 1) Add(f[o][S], v);
				}
				if (t[i][j] != 0) {
					if (S >> j & 1) Add(f[o][S], v);
					else {
						int T = S >> j;
						if (T) T &= T - 1;
						T = (T + 1) << j | (S & ((1 << j) - 1));
						Add(f[o][T], v);
					}
				}
			}
		}
	}
	int Ans = 0;
	for (int S = 0; S < 1 << N; ++S) Add(Ans, f[o][S]);
	printf("%d\n", Ans);
	return 0;
}

Measured memory_bytes: 5836
use whiteread::parse_line;

fn main() {
    let s: String = parse_line().unwrap();
    let chars: Vec<char> = s.chars().collect();

    let mut ret = 0;
    for i in 0..(chars.len() - 1) {
        if chars[i] != chars[i + 1] {
            ret += 1;
        }
    }
    println!("{}", ret);
}


Measured memory_bytes: 2804
#include <iostream>
#include <cmath>
#include <cstring>
#include <limits>
#include <vector>

const int nax = 100;
long long W[nax];
long long V[nax];
std::vector<long long>dp((int)1e5+5, 1e9+7);

int main() {

	int n, w;
	std::cin >> n >> w;

	for (int i=0; i<n; i++) {
		std::cin >> W[i];
		std::cin >> V[i];
	}
	//for (int i=0; i<n; i++) std::cin >> V[i];

	long long sval = 0;
	for (int i=0; i<n; i++) sval += V[i];

	dp[0] = 0;

	for (int i=0; i<n; i++) {
		for (int j=sval-V[i]; ~j; j--) {
			dp[j+V[i]] = std::min(dp[j+V[i]], dp[j]+W[i]);
		}
	}

	int ans = 0;
	for (int i=0; i<=sval; i++) {
		if (dp[i] <= w) ans = std::max(ans, i);
	}

	//std::cout << sval << "\n";

	//for (int i=0; i<=sval; i++) std::cout << dp[i] << " ";
	//std::cout << "\n";

	std::cout << ans << "\n";

	return 0;
}


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

using namespace std;
using ll = long long;
using edge = struct {int to; ll cost;};

#define mod 1000000007
#define REP(i, n) for (int i = 0; i < n; i++)
#define INF (1 << 29)


//long C(long n, long r);
//long long gcd(long long a, long long b);
//long long lcm(long long a, long long b);

void solve()
{
    string s;
    cin >> s;
    int n = s.length();
    int ts = n;
    for(int i = 1; i < n; i++){
        if(s[i-1] != s[i]) ts = min(ts, max(i, n-i));
    }
    cout << ts << "\n";
}

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


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

int main(){

    int dist[8] = {0, 0, 6, 13, 18, 23, 43, 58};
    int fee[8][8] = {};
    fee[1][2] = 300;    fee[2][3] = 350;    fee[3][4] = 250;    fee[4][5] = 250;    fee[5][6] = 600;    fee[6][7] = 500;
    fee[1][3] = 500;    fee[2][4] = 450;    fee[3][5] = 400;    fee[4][6] = 850;    fee[5][7] = 1150;
    fee[1][4] = 600;    fee[2][5] = 600;    fee[3][6] = 1000;   fee[4][7] = 1300;   
    fee[1][5] = 700;    fee[2][6] = 1150;   fee[3][7] = 1350;   
    fee[1][6] = 1350;   fee[2][7] = 1500;   
    fee[1][7] = 1650;   
    int d, hd, md, a, ha, ma;
    while(1){
        cin >> d;
        if(d == 0)  break;
        cin >> hd >> md >> a >> ha >> ma;
        hd = hd*100 + md;
        ha = ha*100 + ma;
        
        int distance = dist[a] - dist[d];
        int ans = fee[d][a];
        if(distance <= 40){
            if((1730 <= hd && hd <= 1930) || (1730 <= ha && ha <= 1930)){
                ans /= 2;
                ans = (ans % 50 == 0) ? ans : (ans/50+1)*50; 
            }
        }

        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
long MOD=1e9+7,n,c,p=-1,dp[1<<18],N;
vector<long>v;
map<long,long>m;
int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>c;
    if(c!=p){
      v.push_back(c);
      p=c;
    }
  }
  if(n==1){
    cout<<1<<endl;
    return 0;
  }
  dp[0]=1;
  m[v[0]]=1;
  N=v.size();
  for(int i=1;i<N;i++)m[v[i]]=dp[i]=(m[v[i]]+dp[i-1])%MOD;
  cout<<dp[N-1]<<endl;
}


Measured memory_bytes: 18676
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using Tup = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<(v)<<"\n";
#define fl cout<<flush;
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl '\n'
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld pi=3.141592653589793238;

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll A;
    cin >> A;
    ll B;
    cin >> B;
    prt((A)*(B))

    return 0;
}


Measured memory_bytes: 3544
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <map>

using namespace std;
using ll = long long;



int main() {
	string target = "keyence";
	string str;
	cin >> str;
	for (size_t i = 0; i < str.length() + 1; i++)
	{
		if (target.substr(0, i) == str.substr(0, i) && target.substr(i) == str.substr(str.size() - target.size() + i)) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}

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

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    HashSet<Integer> set = new HashSet<>();
    for (int i = 0; i < N; i++) {
      int a = scanner.nextInt();
      if (set.contains(a)) {
        set.remove(a);
      } else {
        set.add(a);
      }
    }
    System.out.println(set.size());
  }
}


Measured memory_bytes: 61304
moji = input()

cnt = 0
li = [0]

last = 1000

for i in range(len(moji)):
    if moji[i] == "A" or moji[i] == "G" or moji[i] == "C" or moji[i] == "T":
        cnt += 1
        last = i
        if i == len(moji)-1:
            li.append(cnt)
    elif last == i-1:
        li.append(cnt)
        cnt = 0

print(max(li))

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

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    vector<int> kinds_of_fruits(n);

    for(int& kof: kinds_of_fruits)
        cin >> kof;

    sort(kinds_of_fruits.begin(), kinds_of_fruits.end());

    int ans = 0;

    for(int i = 0; i < k; ++i)
        ans += kinds_of_fruits[i];

    cout << ans;

    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cmath>

int n;
int dp[100001];
int h[100001];

int main() {
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		dp[i] = 2000000000;
		std::cin >> h[i];
	}
	dp[0] = 0;
	for (int i = 0; i < n - 1; i++) {
		if (dp[i] + abs(h[i + 1] - h[i]) < dp[i + 1]) {
			dp[i + 1] = dp[i] + abs(h[i + 1] - h[i]);
		}
		if (dp[i] + abs(h[i + 2] - h[i]) < dp[i + 2]) {
			dp[i + 2] = dp[i] + abs(h[i + 2] - h[i]);
		}
	}
	std::cout << dp[n - 1] << std::endl;
}


Measured memory_bytes: 4284
"""
二分探索木を構成する
"""
import copy

class Node:
    def __init__(self, node_id, parent=None, left=None, right=None):
        self.node_id = node_id
        self.parent = parent
        self.left = left
        self.right = right

class Tree:
    def insert_root_node(self, new_id):
        global root_node #途中でインスタンス化すると水の泡なんですよ
        root_node = Node(new_id)

    def insert_node(self, root_id, new_id): #new_idは追加するノード
        compare_node = root_node #はじめはrootから比較スタート
        new_node = Node(new_id) #インスタンス化
        while compare_node is not None: #compare_nodeが存在するとき
            #この下の一行は最重要アイディア
            #親の可能性がある時，とりあえず代入して情報を記録しておく
            new_node.parent = compare_node 
            #右か左か
            if compare_node.node_id < new_id:
                compare_node = compare_node.right
            else:
                compare_node = compare_node.left

        #compare_node == Noneの時，上の２つの分岐のどっちからきたかわからない
        #そのため，親と比較し直す必要がある
        if new_node.parent.node_id < new_id:
            new_node.parent.right = Node(new_id)
        else:
            new_node.parent.left = Node(new_id)

def inParse(tmp_node):
    if not tmp_node:
        return
    inParse(tmp_node.left)
    print(' '+str(tmp_node.node_id), end='')
    inParse(tmp_node.right)
        
def preParse(tmp_node):
    if not tmp_node:
        return
    print(' '+str(tmp_node.node_id), end='')
    preParse(tmp_node.left)
    preParse(tmp_node.right)

def find(search_id):
    tmp_node = root_node
    while tmp_node:
        if tmp_node.node_id == search_id:
            print('yes')
            return
        elif tmp_node.node_id < search_id:
            tmp_node = tmp_node.right
        else:
            tmp_node = tmp_node.left
    print('no')



tree = Tree()

n = int(input())
root_id = 0
root_node = None
for i in range(n):
    order = input().split()
    if not root_node: #何も入ってない時
        root_id = int(order[1])
        tree.insert_root_node(int(order[1]))
    elif order[0][0] == 'i':
        new_id = int(order[1])
        tree.insert_node(root_id, new_id)
    elif order[0][0] == 'p':
        node = copy.copy(root_node)
        inParse(node)
        print()
        node = copy.copy(root_node)
        preParse(node)
        print()
    elif order[0][0] == 'f':
        find(int(order[1]))





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

int main(void) {
    int A,B,C,K;cin>>A>>B>>C>>K;
    int result = 0;
    if (K <= A) cout << K << endl;
    else if (A < K && K  <= A + B) cout <<  A << endl;
    else cout << A + (K - A - B) * (-1) << endl;
    return 0;
}

Measured memory_bytes: 3192
n = int(input())
h = list(map(int,input().split()))
sh = []
max_h = 0
for i in range(0,n):
    max_h = max(h[i],max_h)
    sh.append(max_h)

count = 0
for i in range(0,n):
    if h[i] >= sh[i]:
        count += 1
print(count)

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


int main(){
	int N;
	cin >> N;
	int now = 1;
	int rem = 0;
	long long ans = 1;
	for(int i = 0 ; i < N ; i++){
		int a;
		cin >> a;
		rem++;
		if( a < now ){
			ans *= rem;
			ans %= (int)1e9 + 7;
			rem--;
		}else{
			now += 2;
		}
	}
	for(int i = 1 ; i <= rem ; i++){
		ans *= i;
		ans %= (int)1e9 + 7;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
# D - Grid Components

A, B = map(int, input().split())
print(100, 100)

grid = []
for _ in range(50):
    grid.append(["#"] * 100)
for _ in range(50):
    grid.append(["."] * 100)

white_count = 1
row = 0
col = 0
while white_count < A:
    grid[row][col] = "."
    col += 2
    if col == 100:
        col = 0
        row += 2
    white_count += 1

black_count = 1
row = 99
col = 0
while black_count < B:
    grid[row][col] = "#"
    col += 2
    if col == 100:
        col = 0
        row -= 2
    black_count += 1

for i in range(100):
    print("".join(grid[i]))

Measured memory_bytes: 3188
def resolve():
    a = []
    for i in range(3):
        a.append([int(x) for x in input().split(" ")])
    
    n = int(input())
    lst = []
    for i in range(n):
        lst += [int(input())]

    flag = False
    for i in range(3):
        if row(i,lst,a):
            print("Yes")
            return
        if col(i,lst,a):
            print("Yes")
            return
    if diag1(lst,a) or diag2(lst,a):
        print("Yes")
        return
    print("No")
        
        

def row(i,lst,a):
    '''print("aは", file=sys.stderr)
    print(a, file=sys.stderr)
    print("lstは", file=sys.stderr)
    print(lst, file=sys.stderr)'''
    for j in range(3):
        if not a[i][j] in lst:
            return False
    return True

def col(j,lst,a):
    for i in range(3):
        if not a[i][j] in lst:
            return False
    return True

def diag1(lst,a):
    for i in range(3):
        if not a[i][i] in lst:
            return False
    return True

def diag2(lst,a):
    for i in range(3):
        if not a[2-i][i] in lst:
            return False
    return True

resolve()

Measured memory_bytes: 3064
#include <stdio.h>

int main()
{
  int N, M;
  int A[100];
  int B[100][100];
  int ans[100] = {0};
  int i, j;

  scanf("%d", &N);
  scanf("%d", &M);

  for(i=0; i<M; i++)
    scanf("%d", &A[i]);

  for(i=0; i<M; i++){
    for(j=0; j<N; j++){
      scanf("%d", &B[i][j]);
    }
  }

  for(i=0; i<M; i++){
    for(j=0; j<N; j++){
      if(B[i][j] == A[i])
        ans[j]++;
      else
        ans[A[i]-1]++;
    }
  }

  for(i=0; i<N; i++)
    printf("%d\n", ans[i]);

  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    vi X(N);
    cin >> X;
    int L;
    cin >> L;
    
    vvi doubling(60, vi(N, -1));
    rep(i, 0, N) {
        if (X[N - 1] - X[i] < L) {
            doubling[0][i] = N - 1;
        } else {
            int ok = i + 1;
            int ng = N - 1;
            while (abs(ok - ng) > 1) {
                int m = (ok + ng) / 2;
                if (X[m] - X[i] <= L) {
                    ok = m;
                } else {
                    ng = m;
                }
            }
            doubling[0][i] = ok;
        }
    }
    rep(k, 0, 59) {
        rep(i, 0, N) {
            doubling[k + 1][i] = doubling[k][doubling[k][i]];
        }
    }

    auto query = [&](int a, int b) -> int {
        if (a > b) swap(a, b);
        int x = a;
        int ans = 0;
        while (1) {
            if (x >= b) {
                return ans;
            }
            rep(k, 0, 60) {
                if (doubling[k + 1][x] >= b) {
                    x = doubling[k][x];
                    ans += 1 << k;
                    break;
                }
            }
        }
        return -1;
    };

    int Q;
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        cout << query(a, b) << endl;
    }
    return (0^_^0);
}



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

using namespace std;

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)

typedef long long ll;
typedef vector<int> vi;

ll mod = 1e9+7;

int solve() {
    int n, k; cin >> n >> k;

    // auto get_length = [&] () {
    //     string s = "";
    //     while (n) {
    //         s = to_string(n % k) + s;
    //         n /= k;
    //     }

    //     return static_cast<int>(s.size());
    // };    

    auto get_length = [&] () {
        int cnt = 0;
        while (n) {
            cnt++;
            n /= k;
        }

        return cnt;
    };

    return get_length();
}

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

	cout << solve() << endl;
}


Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF 1000000000
#define MOD 1000000007

int main(){
    int A, B, C; cin >> A >> B >> C;
    cout << B + min(A+B+1, C) << endl;
    return 0;
}


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

#define pb         push_back

const int INF = 100000000;

int main(void) {
	while(1){
		int n, m, a;
		cin >> n >> m >> a;
		if(n == 0 && m == 0 && a == 0) break;

		vector<int> amida[102];
		for(int i=0; i<=100; i++){
			amida[i] = vector<int>(1002, -1);
		}

		for(int i=0; i<m; i++){
			int h, p, q;
			cin >> h >> p >> q;

			amida[p-1][h-1] = q-1;
			amida[q-1][h-1] = p-1;
		}

		int now = a-1;
		for(int i=1000; i>=0; i--){
			if(amida[now][i] != -1){
				now = amida[now][i];
				//cout << now << endl;
			}
		}

		cout << now+1 << endl;

	}
	
	return 0;
}

Measured memory_bytes: 1584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define ip pair<ll,ll>
#define ff first
#define ss second
#define MAX 200005
const ll MOD = 1000000007;

vector<int> adj[MAX];
int parent[MAX];

void dfs(int u, int p){
	parent[u] = p;
	for(int v: adj[u]){
		if(v == p)
			continue;
		dfs(v, u);
	}
}

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

	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	dfs(1,0);

	ll ans = 0;
	for(ll i=1;i<=n;i++){
		ll idx = parent[i];
		// cout<<i<<" "<<idx<<endl;
		if(i<idx)
			ans += i*(idx-i);
		else
			ans += (i-idx)*(n+1-i);
	}

	cout<<ans<<"\n";
}

Measured memory_bytes: 24616
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
map<int,int> mp;
for(int i=0;i<N;i++){
int a;
cin>>a;
mp[a]++;
}
int ans = 0;
for(auto it:mp){
if(it.second%2==1) ans++;
}
cout<<ans<<endl;
}

Measured memory_bytes: 4864
/*
 * test.cpp
 *
 *
 *      Author: Fireworks
 */

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<cmath>
#include<bitset>
#include<set>
#include<iomanip>
#include<fstream>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<list>
#include<sstream>

using namespace std;

typedef pair<int,int> ii;
typedef pair<int,long long> il;
typedef pair<long long,long long> ll;
typedef pair<ll,int> lli;
typedef pair<long long,int> li;
typedef pair<double,double> dd;
typedef pair<ii,int> iii;
typedef pair<double,int> di;
typedef pair<ii,ii> iiii;
long long mod = 1000000007LL;
long long base = 37;
long long large = 1000000000000000000LL;



int main(){
	int n;
	cin>>n;
	vector<int> a(n,0);
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a.begin(),a.end());
	int s = 0;
	int mini = 1000000;
	for(int i=0;i<n;i++){
		s+=a[i];
		if(a[i]%10){
			mini=min(a[i],mini);
		}
	}
	if(s%10==0) s-=mini;
	s=max(s,0);
	cout<<s<<endl;

	/*int totalcase;
	int testcase=0;
	cin>>totalcase;
	ofstream out;
	out.open("result.txt");

	while(totalcase--){
		testcase++;
		out<<"Case #"<<testcase<<": ";
		cout<<testcase<<": "<<endl;

		//GOGOGO


		//END
	}
	out.close();*/

	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define all(a) (a).begin(), (a).end()


int main(){
    int N, D;
    cin >> N >> D;
    vector<vector<int>> X(N,vector<int>(D));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < D; j++) cin >> X[i][j];
    }
    int ans = 0;
    for(int i = 0; i < N; i++){
        for(int j = i; j < N; j++){
            if(i == j) continue;
            ll dist = 0;
            for(int k = 0; k < D; k++){
                dist += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            }
            bool flag = false;
            for(int k = 1; k <= dist; k++){
                if(k * k == dist) flag = true;
            }
            if(flag) ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3616