akhauriyash/Code-Regression huggingface dataset:
object Main extends App {
  val reader = new StdinReader
  val n, m = reader.nextInt
  val pn = -1 +: Array.fill(n)(reader.nextInt)
  val uf = new UnionFind(n + 1)
  (1 to m).foreach{i =>
    val x, y = reader.nextInt
    uf.union(x, y)
  }
  println(pn.zipWithIndex.tail.count{case (pi, i) =>
    if (i == pi) true
    else uf.find(i)._1 == uf.find(pi)._1
  })

}

// libraries--------------------------------------------------------
class UnionFind(size: Int) {
  val Undefined = -1
  val parents = Array.fill(size)(Undefined)

  // @scala.annotation.tailrec
  /** @retrun (root, rank) */
  def find(x: Int, rank: Int = 0): (Int, Int) = {
    parents(x) match {
      case Undefined => parents(x) = x; (x, rank)
      case p if x == p => (p, rank)
      case p => {
        val (newRoot, newRank) = find(p, rank + 1)
        parents(x) = newRoot
        (newRoot, newRank)
      }
    }
  }

  def union(x: Int, y: Int): Unit = {
    val (xRoot, xRank) = find(x)
    val (yRoot, yRank) = find(y)
    val newRoot = if (xRank > yRank) yRoot else xRoot
    if (xRoot != yRoot) {
      parents(xRoot) = newRoot
      parents(yRoot) = newRoot
    }
    parents(x) = newRoot
    parents(y) = newRoot
  }
}

class StdinReader {
  val is = System.in
  val buffer = new Array[Byte](1024 * 1024)
  var size = 0
  var pos = 0

  private def readByte: Byte = {
    if (pos >= size) {
      pos = 0;
      size = is.read(buffer);
    }
    if (size < 0) -1
    else {
      val ret = buffer(pos)
      pos += 1
      ret
    }
  }

  // support single byte char only
  def next: String = {
    @scala.annotation.tailrec
    def r(sb: StringBuilder, reading: Boolean): String = {
      readByte match {
        case b if ('!' <= b && b <= '~') => r(sb.append(b.asInstanceOf[Char]), true)
        case _ => if (reading) sb.toString else r(sb, false)
      }
    }
    r(new StringBuilder, false)
  }

  def nextInt: Int = {
    @scala.annotation.tailrec
    def r(i: Int, reading: Boolean): Int = {
      readByte match {
        case '-' => r(i * -1, true)
        case b if '0' <= b && b <= '9' => r(i * 10 + (b - '0'), true)
        case _ => if (reading) i else r(i, false)
      }
    }
    r(0, false)
  }
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

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

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

template <class T, class U>
void chmax(T &a, U b) {
  if (a < b) a = b;
}

template <class T, class U>
void chmin(T &a, U b) {
  if (b < a) a = b;
}

template <class T>
T Sq(const T &t) {
  return t * t;
}

const int mod = 1e9 + 7;

signed main() {
  int n = read();
  vi a, b;
  REP(i, n) { a.PB(read()); }
  b = a;
  sort(ALL(a), greater<int>());
  int j = 0;
  REP(i, n) {
    if (b[i] == a[j])
      print(a[1]);
    else
      print(a[0]);
  }
}


Measured memory_bytes: 4848
#include <bits/stdc++.h>
using namespace std;
long long n, x;
pair<int, int> y[100005];
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=0;i<n;i++){
	cin >> x;
	y[i] = make_pair(x, i+1);
}
sort (y, y+n);
for (int i=0;i<n;i++) cout << y[i].second << " ";
return 0;
}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {

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

		int n=Integer.parseInt(sc.next());

		int k=Integer.parseInt(sc.next());
		int t,cnt=0;
		double y,ans=0;

		for(int i=1;i<=n;i++){
			t=1;
			cnt=0;
			y=1.0;
			while((i*t)<k){
				t=t*2;
				y=(double)(y/2);
				cnt+=1;
			}
			ans+=(double)(y/n);
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a, b, c;
vector<int> vec(3);
int main() {
    for (int i=0;i<3;i++) cin >> vec[i];
    sort(vec.begin(), vec.end());
    cout << vec[0]+vec[1] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C;
  cin >> A >> B >> C;
  vector<int> D(3);
  D.at(0) = A;
  D.at(1) = B;
  D.at(2) = C;
  sort(D.begin(), D.end());
  int ans = 0;
  int sum = (D.at(2) - D.at(0)) + (D.at(2) - D.at(1));
  if (sum % 2 == 0) ans = sum / 2;
  else ans = sum / 2 + 2;
  cout << ans << endl;
  return 0; 
}

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

int main() {
  int q; cin >> q;
  multimap<string, int> mp;
  for (int i = 0; i < q; i++) {
    int cmd; cin >> cmd;
    if (cmd == 0) {
      string key; int x; cin >> key >> x;
      mp.insert(make_pair(key, x));
    }
    if (cmd == 1) {
      string key; cin >> key;
      auto r = mp.equal_range(key);
      for (auto itr = r.first; itr != r.second; itr++) {
        cout << itr -> second << endl;
      }
    }
    if (cmd == 2) {
      string key; cin >> key;
      mp.erase(key);
    }
    if (cmd == 3) {
      string l, r; cin >> l >> r;
      for (auto itr = mp.lower_bound(l), end = mp.upper_bound(r); itr != end; itr++) {
        cout << itr -> first << " " << itr -> second << endl;
      }
    }
  }
}



Measured memory_bytes: 24840
x,y,a,b,c  = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p = sorted(p,reverse=True)
q = sorted(q,reverse=True)
r = sorted(r,reverse=True)
chk = p[:x]+q[:y]
chk = sorted(chk,reverse=True)
for i in range(c):
  if i < len(chk) and r[i] > chk[-(1+i)]:
    chk[-(1+i)] = r[i]   
print(sum(chk))

Measured memory_bytes: 109676
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

template <typename F>
void forComb(int n, int k, F f)
{
    int comb = (1 << k) - 1;
    while (comb < (1 << n)) {
        f(comb);

        int x = comb & -comb;
        int y = comb + x;
        comb = ((comb & ~y) / x >> 1) | y;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    using E = tuple<int, int>;
    vector<vector<E>> redge(n);
    rep(i, m)
    {
        int s, t, d;
        cin >> s >> t >> d;

        redge[t].push_back(E(s, d));
    }

    const int DMAX = 15 * 1'001;
    vector<vector<int>> dp(1 << n, vector<int>(n));
    int result = DMAX;
    rep(s, n)
    {
        irep(i, n)
        {
            if (i == 0) {
                rep(j, n)
                {
                    dp[i][j] = j == s ? 0 : DMAX;
                }
            } else {
                forComb(n, i, [&](int comb) {
                    rep(j, n)
                    {
                        dp[comb][j] = DMAX;
                        for (const E v : redge[j]) {
                            int k, d;
                            tie(k, d) = v;
                            if ((comb & (1 << k)) != 0) {
                                dp[comb][j] = min(dp[comb][j], dp[comb ^ (1 << k)][k] + d);
                            }
                        }
                    }
                });
            }
        }
        result = min(result, dp[(1 << n) - 1][s]);
    }
    if (result == DMAX) {
        cout << -1 << endl;
    } else {
        cout << result << endl;
    }
    return 0;
}


Measured memory_bytes: 6216
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<"\n"
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define mp make_pair
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
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; 
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
// gcd lcm
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
bool p=false;
set<ll> insuu;
void prime_factor(ll n){
    ll k=n;
  set<ll> s;
	for(ll i=2;i*i<=n;i++){
	    while(k%i==0){
            
          s.insert(i);
	        k/=i;
	    }
	}
	if(k!=1){
      s.insert(k);
    }
  for(auto ss:s){
    if(insuu.count(ss)){
      p=true;
      return ;
    }
    else{
      insuu.insert(ss);
    }
  }
  return ;
}
int main(){
  ll n;
  cin>>n;
  vll a(0);
  bool h=false;
  rep(i,n){
    ll b;
    cin>>b;
    if(b==1){
      h=true;
      continue;
    }
    a.pb(b);
  }
  if(h)a.pb(1);
  ll g=a[0];
  n=sz(a);
  rep(i,n){
    g=gcd(g,a[i]);
  }
  if(g!=1){
    COUT("not coprime");
  }
  else{
    if(n>80000){
      COUT("setwise coprime");
    }
    else{
      rep(i,n){
        prime_factor(a[i]);
      }
      if(p){
        COUT("setwise coprime");
      }
      else{
        COUT("pairwise coprime");
      }
    }
  }
}


Measured memory_bytes: 11584
n = int(input())
a = list(map(int, input().split()))


yesno = True

for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 != 0 and a[i] % 5 != 0:
            yesno = False

if yesno:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3060
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define endl "\n"
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main() {
	ll n,k;
	cin>>n>>k;
	string ss;
	cin>>ss;
	string s = "*";
	s += ss;
	string s1;
	ll ans = 0;
	rep(i,0,s.sz-1){
		if(s[i]!=s[i+1]){
			s1 += s[i+1];
		}
		else{
			ans++;
		}
	}
	ll n1 = s1.sz;
	while(k>0&&n1>2){
		k--;
		n1-=2;
		ans+=2;
	}
	if(n1==2&&k>0)ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
"""
AtCoder :: Beginner Contest 176 :: A - Takoyaki 
https://atcoder.jp/contests/abc176/tasks/abc176_a
"""
import sys
import math


def main():
    """Main program."""
    N, X, T = (int(i) for i in sys.stdin.readline().split())
    ticks = int(math.ceil(N / X))
    print(ticks * T)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

const int INF = 1000000005;

int main(){
    int n, k; 
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    sort(all(h));
    int ans = INF;
    rep(i, n){
        if (i+k-1 == n) break;
        ans = min(ans, h[i+k-1] - h[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3736
x1, y1, x2, y2 = map(int, input().split())
x_diff = x2 - x1
y_diff = y2 - y1

y3, x3 = y2 + x_diff, x2 - y_diff
y4, x4 = y1 + x_diff, x1 - y_diff
print(x3, y3, x4, y4)

Measured memory_bytes: 2940
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<unordered_set>

using namespace std;




vector<int> prime_sieve(int n)
{
    int* arr = new int[n+1];
    
    int i, p;
    for (i = 0; i <= n; ++i) {
        arr[i] = i;
    }
    for (i = 2; i <= n; ++i) {
        if (arr[i] != 0) {
            for (p = arr[i] * arr[i]; p <= n; p += arr[i]) {
                arr[p] = 0;
            }
        }
    }
    vector<int> primes;
    for (i = 2; i <= n; ++i) {
        if (arr[i] != 0) {
            primes.push_back(arr[i]);
        }
    }
    return primes;
}

int min(int a, int b)
{
    return a < b ? a : b;
}



int main()
{
    string str;
    cin >> str;
    int i;
    int a = 0, b = 0;
    for (i = 0; i < str.length();++i)
    {
        if (str[i] == 'A') {
            ++a;
        }
        if (str[i] == 'B') {
            ++b;
        }
    }
    if (a == 0 || b == 0) {
        cout << "No";
    }
    else {
        cout << "Yes";
    }
    
}

    





Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a,b,c;
    scanf("%d %d",&a,&b);
    c = (a * b) % 2;
    if (c == 0) {
        printf("Even\n");
    }
    else{
        printf("Odd\n");
    }
    return 0;
}



Measured memory_bytes: 128
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<limits.h>
#include<utility>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(A) A.begin(),A.end()

const int MAX = 200000;
const int MOD = 998244353;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
	COMinit();
	int n, m, k;
	cin >> n >> m >> k;
	ll ans = 0;
	vector<ll>  a(n, 0);
	a[0] = m;
	rep(i, n-1) {
		a[i + 1] = (a[i] * (m - 1)) % MOD;
	}
	for (int i = 0; i <= k; i++) {
		ll tmp = COM(n - 1, i) * a[n-1-i];
		tmp %= MOD;
		ans = ans + tmp;
		ans %= MOD;
	}
	cout << ans << endl;
}


Measured memory_bytes: 9084
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  //必要な箱を用意
  bool A ; //あるかどうかの判定
  int N; //入力した数字
  
  cin >> N;
  A = false;
  
  for(int i = 1; i < 10 ;i++){
    for(int j = 1; j < 10 ; j++){
      if ( N == i*j)
        A = true;
    }
  }
  if (A == true)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  
}
      
  


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

int main()
{
  ll n, m;
  cin >> n >> m;
  ll l, r;
  l = 0;
  r = 1e9 + 7;
  for (ll i = 0; i < m; i++)
  {
    ll a, b;
    cin >> a >> b;
    l = max(l, a);
    r = min(r, b);
  }
  if (r >= l)
  {
    cout << r - l + 1 << endl;
  }
  else
  {
    cout << 0 << endl;
  }
}


Measured memory_bytes: 3572
import java.io.*;

class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input;
        int n, x, i, j, k, num;

        while (true) {
            input = br.readLine().split(" ");
            n = Integer.parseInt(input[0]);
            x = Integer.parseInt(input[1]);
            if (n == 0 && x == 0) break;
            num = 0;
            for (i = 1; i <= n; i++) {
                for (j = i + 1; j <= n; j++) {
                    for (k = j + 1; k <= n; k++) {
                        if (x - i - j - k == 0) num++;
                    }
                }
            }
            System.out.println(num);
        }
    }
}

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

long long int mod=1e9+7;

int main(){
  int n,x;
  cin>>n>>x;
  if(x==1||x==(2*n-1)){
    cout<<"No"<<endl;
    return 0;
  }
  cout<<"Yes"<<endl;
  vector<int> ans(2*n-1,0);
  if(x==2){
    ans[n-2]=x+1;
    ans[n-1]=x;
    ans[n]=x-1;
    ans[n+1]=x+2;
  }else{
    ans[n-2]=x-1;
    ans[n-1]=x;
    ans[n]=x+1;
    ans[n+1]=x-2;
  }
  int np=1;
  for(int i=0;i<n*2-1;i++){
    if(x==2)while(np>x-2&&np<x+3)np++;
    if(x!=2)while(np>x-3&&np<x+2)np++;
    if(ans[i]==0){
      ans[i]=np;
      np++;
    }
    //while(np>x-2&&np<x+3)np++;
  }

  for(int i=0;i<n*2-1;i++)cout<<ans[i]<<endl;
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	const ULL M = 1000000007;

	ULL dp[101][100000] = {};
	
	void Solve() {
		UL N, K; cin >> N >> K;
		UL n = 1;
		while (n * n <= N) n++; n--;
		UL nn = n;
		vector<UL> Sz(n);
		for (UL i = 0; i < n; i++) { Sz[i] = 1; }
		UL p = n, d = N / (p + 1);
		while (d > 0) {
			Sz.push_back(N / d - p);
			p = N / d;
			nn++;
			d--;
		}
		rep (i, nn) dp[0][i] = 1;
		for (UL k = 1; k <= K; k++) {
			ULL S = 0;
			for (UL np = 0; np < nn; np++) {
				S += Sz[np] * dp[k - 1][nn - np - 1];
				S %= M;
				dp[k][np] = S;
			}
		}
		cout << dp[K][nn - 1] << endl;
	}


	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}


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

int main() {
  int n;
  cin >> n;
  vector<vector<int>> v(n);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < n; j++) {
      if (s[j] == '1') v[i].push_back(j);
    }
  }

  int r = 0;
  for (int start = 0; start < n; start++) {
    bool b = true;
    vector<int> d(n, -1);
    queue<int> q;
    q.push(start);
    d[start] = 0;
    while (b && !q.empty()) {
      int i = q.front();
      q.pop();
      for (auto j : v[i]) {
        if (d[j] == -1) {
          d[j] = d[i] + 1;
          q.push(j);
        } else if (d[j] != d[i] - 1 && d[j] != d[i] + 1) {
          b = false;
          break;
        }
      }
    }
    if (b) r = max(r, *max_element(d.begin(), d.end()) + 1);
  }
  cout << (r ? r : -1) << endl;
}


Measured memory_bytes: 512
A, B = map(int, input().split())

# 0からn以下の数の全てのxorをf(n)とする
# 各桁(2^0,2^1,...の位)ごとに1の個数をカウントしてその偶奇で分ければ良い
# 2^0の位は0,1,0,1,...の周期2
# 2^1の位は0,0,1,1,0,0,1,1,...の周期4
# あとはこれを利用して各桁ごとにカウントすれば良い

def f(n):
    ans = 0
    n += 1
    for i in range(40): # A, Bは最大で10^12なので二進数で2^40の位まであれば大丈夫
        loop = 2**(i+1)
        cnt = (n // loop) * (loop // 2) # (nに完全に収まっているloopの個数) * (1つのloopの中にある1の個数)
        cnt += max(0, (n % loop) - (loop // 2)) # loopが途中で切れている部分の処理
        if cnt % 2 == 1:
            ans += 2**i # 1が奇数個だったら足す
    return(ans)

if A == 0:
    print(f(B))
else:
    print(f(B) ^ f(A-1))


Measured memory_bytes: 3060
fun main(args: Array<String>) {
    while (true) {
        val inStr = readLine()
        val (h, w) = inStr?.split(' ')?.map { s -> s.toInt() } ?: return

        if ((h == 0) && (w == 0)) {
            return
        }
        printChessboard(h, w)
        println()
    }
}

fun printChessboard(height:Int, width:Int) {
    for (y in 1..height) {
        var oddSimbol : Char = if ((y % 2) != 0) '#' else '.'
        var evenSimbol : Char =if ((y % 2) != 0) '.' else '#'

        for (x in 1..width) {
            if ((x % 2) != 0) {
                print(oddSimbol)
            } else {
                print(evenSimbol)
            }
        }
        println()
    }
}



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

typedef long long ll;

int main()
{
    char X, Y;
    cin >> X >> Y;
    if (X==Y) {
        cout <<"=" << endl;
        return 0;
    }
    if (X>Y) {
        cout << ">" << endl;
    }
    else {
        cout << "<" << endl;
    }

}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0); cin.tie(); cout.tie()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define endl '\n'
#define len(a) a.length()
#define TIME cout << endl << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

const long long inf = 1e18;
const double eps = 1e-6;
const long long mod = 1e9 + 7;

int cx[4] = {1, -1, 0, 0};
int cy[4] = {0, 0, 1, -1};

int hx[8] = {2, 2, -2, -2, 1, -1, 1, -1};
int hy[8] = {1, -1, 1, -1, 2, -2, -2, 2};

bool on_board (ll x, ll y, ll n, ll m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

ll binpow (ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1LL)
			res = (res * a) % mod;
		a = (a * a) % mod;
		n >>= 1LL;
	}
	return res;
}

ll string_to_int (string s) {
    reverse(all(s));
    int pw = 1;
    int ans = 0;
    for (int i = 0; i < len(s); i++) {
        ans += (s[i] - '0') * pw;
        pw *= 10;
    }
    return ans;
}

ll div_up (ll x, ll y) {
    if (x == 0)
        return 0;
    return (x - 1) / y + 1;
}

bool is_prime (ll a) {
    for (ll i = 2; i <= sqrt(a); i++)
        if (a % i == 0)
            return false;
    return true;
}

int32_t main()
{
    boost;
    int n; cin >> n;
    map <string, int> mp;
    mp["AC"] = 0;
    mp["WA"] = 0;
    mp["TLE"] = 0;
    mp["RE"] = 0;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        mp[s]++;
    }
    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] << endl;
    return 0;
}



Measured memory_bytes: 3628
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let n: usize = read().unwrap();
    let mut vec: Vec<usize> = Vec::new();
    for _ in 0..n {
        vec.push(read().unwrap());
    }
    let mut min: usize = vec[0];
    let mut count: usize = 1;
    for &v_i in vec[1..].iter() {
        if v_i <= min {
            count += 1;
            min = v_i;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 6396
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <cmath>
#include <cstring>
#include <assert.h>
#include <utility>
#include <tuple>
#include <array>
#include <bitset>
#include <cstdlib>

using int64 = long long;

#define repeat(i, x) for (int i = 0; i < (int)(x); i++)

constexpr int MAX_N = 200000;

int size[MAX_N], cs[MAX_N];
int64 table[MAX_N], answer[MAX_N];
std::vector<int> G[MAX_N];

void DFS(int root, int parent, int color) {
    size[root] = 1;
    int64 temp = table[color];

    for (int child : G[root]) {
        if (child == parent) continue;

        // child を根とする、色が color である頂点を含まない部分木のなかで
        // 最大の木の頂点数(num)を計算したい。
        int64 before = table[color];
        DFS(child, root, cs[child]);
        int64 after = table[color],
              num = size[child] - (after - before);

        answer[color] -= num * (num - 1) / 2 + num;
        size[root] += size[child];
    }
    // 色が color の頂点で最も浅い位置にいるのは root なので
    table[color] = temp + size[root];
}

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

    int64 N;
    std::cin >> N;

    repeat (i, N) {
        std::cin >> cs[i];
        cs[i]--;
    }

    repeat (i, N - 1) {
        int a, b;
        std::cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    repeat (i, N) {
        answer[i] = N * (N - 1) / 2 + N;
    }

    DFS(0, -1, cs[0]);

    // 色が i である頂点を含まず、かつ根を含む部分木について計算。
    repeat (i, N) {
        int64 num = N - table[i];
        answer[i] -= num * (num - 1) / 2 + num;
        std::cout << answer[i] << std::endl;
    }

    return 0;
}



Measured memory_bytes: 34408
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
using namespace std;
long long mod = 1e9+7;

vector<int> divisor(int n) {
  vector<int> ret;
  for(int i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main(void) {

  int n; cin >> n;
  vector<int> a(n+1, -1);
  for(int i=1; i<=n; i++ ) {
    cin >> a[i];
  }
  vector<int> x(n+1, 0);
  vector<int> ans;
  for(int i=n; i>=1; i--) {
    if(a[i] != x[i]) {
      vector<int> d = divisor(i);
      for(int j=0; j<d.size(); j++) {
        x[d[j]]++;
        x[d[j]]%=2;
      }
      ans.push_back(i);
    }
  }

  bool f = true;
  for(int i=1; i<=n; i++) {
    if(a[i] != x[i]) f = false;
  }
  if(!f) {
    cout << -1 << endl;
    return 0;
  }

  cout << ans.size() << endl;
  if(ans.size() == 0) return 0;
  for(int i=0; i<ans.size(); i++) cout << ans[i] << " ";
  cout << endl;

 
  return 0;
}

// EOF


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 998244353;

long long modpow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = (ret * x) % MOD;  
        x = (x * x) % MOD;
        n >>= 1;  
    }
    return ret;
}

long long inverse(long long x){
    return modpow(x,MOD-2);
}

int main(){
    ll n,s;
    cin >> n >> s;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<vector<ll>> dp(n+1,vector<ll>(s+1,0));
    ll two = inverse(2);
    dp[0][0] = modpow(2,n);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=s;j++){
            if(j- a[i-1]>=0) dp[i][j] = (dp[i-1][j] + (dp[i-1][j-a[i-1]]*two)%MOD)%MOD;
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][s] << endl;
    return 0;
}

Measured memory_bytes: 73704
#include<iostream>
using namespace std;
int main(){
	int n,maxv=-100000;
	cin>>n;
	string b[n+1];	
	for(int i=1;i<=n;i++)
		cin>>b[i];
		
	int m;
	cin>>m;
	string r[m+1];
	for(int i=1;i<=m;i++)
		cin>>r[i];
	
	int s=0;
	string bz;
	for(int i=1;i<=n;i++)
	{
		s=0;
		bz=b[i];
		for(int j=1;j<=n;j++)
		{
			if(bz==b[j])
			s++;
		}
		for(int k=1;k<=m;k++)
		{
			if(bz==r[k])
			s--;
		}
		if(s>maxv)
		maxv=s;
	}
	
	if(maxv<0)
	{
		cout<<"0"<<endl;
		return 0;
	}
	
	cout<<maxv<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define rrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)

#define fi first
#define se second

using namespace std;

using ll = long long;
using v_int = vector<int>;
using v2_int = vector<v_int>;
using v_ll = vector<ll>;
using v2_ll = vector<v_ll>;
using v_string = vector<string>;
using v_bool = vector<bool>;
using v2_bool = vector<v_bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const double PI = 3.1415926535897932;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const ll MOD = 1000000007;
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p) {
    return o << "{" << p.first << "," << p.second << "}";
}
template<typename T> inline
istream& operator>>(istream &is, vector<T> &vec) {
    for(auto &v : vec) { is >> v; }
    return is;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &vec) {
    for(auto &v : vec) { os << v << ",";}
    return os;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<vector<T> > &mat) {
    for(auto &row : mat) { os << row << endl; }
    return os;
}

template<typename T> inline
void chmin(T &a, T b) { a = min(a, b); }
template<typename T> inline
void chmax(T &a, T b) { a = max(a, b); }

int main(void)
{
    int n;
    cin >> n;
    
    vector<pii> p;
    rep(i,n) {
        int a;
        cin >> a;
        p.push_back({a,i+1});
    }
    sort(p.begin(),p.end());

    rep(i,n) {
        cout << p[i].se << endl;
    }
    return 0;
} /*atcoder*/



Measured memory_bytes: 4236
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	int N, T; cin >> N >> T;
	vector<ll>t(N + 1, INF);
	rep(i, N)cin >> t[i];
	ll ans = 0;
	rep(i, N) {
		if (t[i + 1] - t[i] <= T) {
			ans += t[i + 1] - t[i];
		}
		else {
			ans += T;
		}
	}
	cout << ans << "\n";

	return 0;
}


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

typedef long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
const double EPS = 1e-9, PI = 3.141592653589793;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define fi first
#define se second
#define m_p make_pair

template<class T> inline void chmax(T &a, T b) {if(a < b) a = b;}
template<class T> inline void chmin(T &a, T b) {if(a > b) a = b;}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll n,k;
  cin >> n >> k;
  vector<ll> h(n),dp(n,INF);
  rep(i,n) cin >> h[i];
  dp[0] = 0;
  rep(i,n){
    REP(j,1,k+1){
      //i番目から飛べるとこまで飛ぶ
      chmin(dp[i+j], dp[i]+(abs(h[i]-h[i+j])));
    }
  }
  cout << dp[n-1] << "\n";
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
 
#define REP(i, n) for(int i = 0; i < (n); i++)
#define SREP(i, s) for(int i = 0; i < (s.size()); i++)
#define SORT(v, n) sort(v, v+n);
#define GSORT(v, n) sort(v, v+n, greater<int>());
#define VSORT(v) sort(v.begin(),v.end());
#define VGSORT(v) sort(v.begin(),v.end(),greater<int>());
#define REV(a) reverse(begin(a),end(a));
 
ll gcd(ll x, ll y){
	if(x<y) swap(x,y);
	if(y==0) return x;
	return gcd(y,x%y);
}
 
ll lcm(ll x, ll y){
	return (x*y/gcd(x,y));
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
////////////////////////////////////////////
	int n;
	cin >> n;
	int ans=(n-1)/111;
  	cout << (ans+1)*111 << endl;
/////////////////////////////////////////////
}

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


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

    if(S=="Sunny")
        {cout<<"Cloudy"<<'\n';}

    if(S=="Cloudy")
        {cout<<"Rainy"<<'\n';}

    if(S=="Rainy")
        {cout<<"Sunny"<<'\n';}




return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 
int Q;

int prime[101010];
bool is_prime[101010];

//Range Sum Query(RSQ)を処理するセグ木
struct SegmentTree
{
private:
    int n;
    vector<int> node;
 
public:
    //元配列v(vector)をセグメント木で表現する
    SegmentTree(vector<int> v)
    {
        //最下段のノード数は元配列のサイズ以上になる最小の２冪→これをnとおく
        //セグメント木全体で必要なノード数は2n-1である
        int sz = v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2 * n - 1, 0);
 
        //最下段に値を入れたあとに、下の段から埋めていく
        //値を埋めるときは自分の２つの子を見ればいい
        REP(i,sz) node[i+(n-1)] = v[i];
        for (int i=n-2; i>=0; i--) {
            //★セグ木の処理を書き換えるときはここを書き換える
            node[i] = node[2*i+1] + node[2*i+2];
        }
    }
 
    void update(int x, int val)
    {
        //最下段のノードにアクセスする
        x += n - 1;
 
        //最下段のノードを更新したら、あとは親に登って更新していく
        node[x] = val;
        while (x > 0) {
            //x=0でないなら親がある
            x = (x - 1) / 2;
            node[x] = node[2*x+1] + node[2*x+2];
        }
    }
 
    //★追加
    void add(int k, int val)
    {
        k += n - 1;
        node[k] += val;
 
        while (k > 0) {
            k = (k - 1) / 2;
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
 
    //要求区間[a,b)の要素の最小値を答える
    //k:=自分がいるノードのインデックス
    //対象区間は[l,r)にあたる
    int getsum(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        //最初に呼び出されたときの対象区間は[0,n)
        if (r < 0) r = n;
 
        //要求区間と対象区間が交わらない→答えに影響を与えない値を返す
        //★セグ木の機能によって変える
        if (r <= a || b <= l) return 0;
 
        //要求区間が対象区間を完全に被覆→対象区間を答えの計算に使う
        if (a <= l && r <= b) return node[k];
 
        //要求区間が対象区間の一部を被覆→子について探索を行う
        //左の子をvl、右の子をvrとしている
        //新しい対象区間は現在の対象区間を半分にしたもの
        int vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }
};

// n以下の素数の数を返す
int sieve(int n)
{
  int p = 0;
  for (int i=0; i<=n; i++) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int i=2; i<=n; i++) {
    if (is_prime[i]) {
      prime[p++] = i;
      for (int j=2*i; j<=n; j+=i) is_prime[j] = false;
    }
  }
  return p;
}
 
signed main()
{
  cin >> Q;
  sieve(101000);

  vector<int> a(101010, 0);
  SegmentTree st(a);

  for (int i=1; i<=100000; i++) {
    if (i % 2 == 1 && is_prime[i] && is_prime[(i + 1) / 2]) {
      st.update(i, 1);
    }
  }

  REP(i,Q) {
    int l, r;
    cin >> l >> r;
    cout << st.getsum(l, r + 1) << endl;
  }
}

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

void solve(std::istream &in, std::ostream &out);

int main() {
#ifdef LOCAL
  freopen("../IO/e.in", "right", stdin);
//  freopen("../IO/e.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  solve(std::cin, std::cout);
  return 0;
}

constexpr int md = (int)1e9 + 7;
int pw(int64_t a, int64_t b) {
  int64_t res = 1;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % md;
    a = a * a % md;
  }
  return res;
}

int a[100000 + 1515];

void solve(std::istream &in, std::ostream &out) {
  int n, k;
  in >> n >> k;
  int sm = 0;
  for (int i = k; i >= 1; --i) {
    a[i] = pw(k/i, n);
    for (int j = 2 * i; j <= k; j += i) {
      a[i] = (a[i] + md - a[j]) % md;
    }
    sm = (sm + (int64_t)a[i]*i) % md;
  }
  out << sm << '\n';
}



Measured memory_bytes: 3976
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
using ull = unsigned long long;
using P = pair<int, int>;

static constexpr ull MOD = 1000000007;
static constexpr double pi = 3.14159265359;

int main() {
    string n;
    cin >> n;
    for (char c : n) {
        if (c == '1') cout << 9;
        else if (c == '9') cout << 1;
        else cout << c;
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define NIL -1
typedef long long ll;
const ll INF = 1LL<<60;
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; }

double dp[10][10];
int N;

int main(){
    cin >> N;
    vector<pair<double, double>> points(N);
    vector<int> v;
    rep(i, N){
        double x, y;
        cin >> x >> y;
        points[i] = make_pair(x, y);
        v.push_back(i);
    }

    rep(i, N){
        rep(j, N){
            if(i==j) dp[i][j] = 0;
            else dp[i][j] = sqrt(pow((points[i].first - points[j].first),2) + pow((points[i].second - points[j].second), 2));
        }
    }

    double sum = 0;
    int np = 0;
    do {
        double s = 0;
        rep(i, N-1) s += dp[v[i]][v[i+1]];
        ++np;
        sum += s;
    } while (std::next_permutation(v.begin(), v.end()));

    double average = 0;
    average = sum / np;

    printf("%.10f", average);

}

Measured memory_bytes: 256
H, W = map(int, input().split())
As =[input() for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if As[i][j] == '#':
            cnt += 1
if cnt == H+W-1:
    print('Possible')
else:
    print('Impossible')

Measured memory_bytes: 3060
N = int(input())
T,A= map(int,input().split())
H = list(map(int,input().split()))
ans = 9999
tmp = 9999
for i in range(N):
    temp = T-H[i]*0.006
    x = abs(temp-A)
    if x <= ans:
        ans = x
        tmp = i+1
print(tmp)

Measured memory_bytes: 38384
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 20:52:46 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""

A, B, Q = map(int, input().split())
INF = 10**18

s = [-INF] +[int(input()) for i in range(A)] + [INF]
t = [-INF] +[int(input()) for i in range(B)] + [INF]

x = [0]*Q
for i in range(Q):
    x[i] = int(input())
    se, te = bisect.bisect_right(s, x[i]), bisect.bisect_right(t, x[i])
    res = INF
    for S in [s[se-1], s[se]]:
        for T in [t[te-1], t[te]]:
            d1, d2 = abs(S-x[i]) + abs(T-S), abs(T-x[i]) + abs(T-S)
            res = min(res, d1, d2)
    print(res)



Measured memory_bytes: 26104
n = gets.chomp
pn = gets.split.map(&:to_i)
p1 = pn.shift
p2 = pn.shift
puts pn.inject([p1>p2,p2,0]){|sum,p|[(sum[1]>p),p,((sum[0]==(sum[1]>p)) ? sum[2]+1 : sum[2])]}[2]

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long int
#define ff first
#define ss second
#define S size()
#define mod (ll)(1e9+7)
#define mset(a,k) memset(a,k,sizeof(a));
#define fr(i, x, y) for ( ll i = x; i < y;i++)
#define dr(i, x, y) for ( ll i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define pqueue priority_queue<ll>
#define piqueue priority_queue<ll,vll ,greater<ll>>
#define mapcl map<char,ll>
#define mapll map<ll,ll>
#define mapsl map<string,ll>
#define vi vector<ll>
#define vs vector<string>
#define vb vector<bool>
#define psi pair<string,ll>
#define pii pair<ll,ll>
#define piii pair<ll,pii>
#define vii vector<pii>
#define vvi vector<vi>
#define vvii vector<vii>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
//----------------------------------------FUNCTIONS-------------------------------------
ll gcd(ll x, ll y )						{if (y == 0) return x; return gcd(y, x % y);}
ll lcm(ll a, ll b)						{return (a * b) / gcd(a, b);}
ll logx(ll base, ll num)				{int cnt = 0; while (num != 1) {num /= base; ++cnt;} return cnt;}
vi vin(ll n)							{vi a(n); fr(i, 0, n) cin >> a[i]; return a;}
void out(vi a)							{for (int i = 0; i < (ll)a.S; i++) { cout << a[i] << " "; } cout << endl;}
void in(ll *a, ll n)        			{for (ll i = 0; i < n; i++)cin >> a[i];}
void out(ll *a, ll n)					{fr(i, 1, n + 1) {cout << a[i] << " ";} cout << '\n';}
void out1(vi v)							{fr(i, 0, (ll)v.S) {cout << v[i] << " ";} cout << endl;}
//----------------------------------------START-------------------------------------------
const ll maxN = (ll)(1 * 1e6 + 5 );

void solve()
{

	string s;
	cin >> s;
	if (s[0] != 'R' && s[1] != 'R' && s[2] != 'R')cout << 0 << '\n';
	else if (s[0] == 'R' && s[1] == 'R' && s[2] == 'R')cout << 3 << '\n';
	else if (s[0] == 'R' && s[1] == 'R' || s[1] == 'R' && s[2] == 'R')cout << 2 << '\n';
	else cout << 1 << '\n';
}
int main()
{
	fast();
#ifndef ONLINE_JUDGE
	freopen ("inp1.txt", "r", stdin);

	freopen ("out1.txt", "w", stdout);
#endif
	ll t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}



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

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

ans = 0
score = 0
for i in range(1, N + 1):
    score = i
    count = 0
    while score < K:
        count += 1
        score *= 2
    ans += 1 / N * ((1 / 2) ** count)

print(ans)


Measured memory_bytes: 2940
/*
これを入れて実行
g++ code.cpp
./a.out
*/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = { -1, 0, +1, 0 };
int dx4[4] = { 0, +1, 0, -1 };
int dy8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dx8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
	return f.second > s.second;
}

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

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

ll nCr(ll n, ll r){
	if (r == 0 || r == n){
		return 1;
	}
	else if (r == 1){
		return n;
	}
	return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}

ll nPr(ll n, ll r){
	r = n - r;
	ll ret = 1;
	for (ll i = n; i >= r + 1; i--) ret *= i;
	return ret;
}

//-----------------------ここから-----------
int n;
vector<int> l;
bool check(ll a, ll b, ll c){
	if (a < b + c && b < c + a && c < a + b){
		return true;
	}
	return false;
}

int main(void){
	
	cin >> n;
	l.resize(n);

	for (int i = 0; i < n; i++) cin >> l[i];

	sort(l.begin(), l.end());
	ll ans = 0;
	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			int ok = j;
			int ng = n;
			while (abs(ok - ng) > 1){
				ll mid = (ok + ng) / 2;
				if (check(l[i], l[j], l[mid])){
					ok = mid;
				}
				else {
					ng = mid;
				}
			}
			ans += max(0, ok - j);
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
n = int(input())
k = n // 4
r = n % 4
if r == 0:
  print("Yes")
elif r == 1:
  if k >= 5:
    print("Yes")
  else:
    print("No")
elif r == 2:
  if k >= 3:
    print("Yes")
  else:
    print("No")
else:
  if k >= 1:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int a[10];

void solve() {
    int min1 = INT_MIN, min2 = INT_MIN;
    for(int i = 0;i < 10; i++) {
        if(a[i] > min1 && a[i] > min2) {
            if(min1 > min2) {
                min1 = a[i];
            } else {
                min2 = a[i];
            }
        } else if(a[i] > min1) {
            min1 = a[i];
        } else if(a[i] > min2) {
            min2 = a[i];
        } else {
            printf("NO\n");
            return ;
        }
    }
    printf("YES\n");
    return ;
}

int main() {
    int num;
    scanf("%d", &num);
    while(num--) {
        for(int i = 0;i < 10; i++) {
            scanf("%d", &a[i]);
        }
        solve();
    }
}


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

import sys
import os
import math


n = int(input())
A = list(map(int, input().split()))
cnt = 0

def merge(A, left, mid, right):
    global cnt

    S = A[left:mid]
    T = A[mid:right]
    S.append(float('inf'))
    T.append(float('inf'))

    s_i = 0
    t_i = 0
    for i in range(right - left):
        cnt += 1
        if S[s_i] < T[t_i]:
            A[left + i] = S[s_i]
            s_i += 1
        else:
            A[left + i] = T[t_i]
            t_i += 1


def merge_sort(A, left, right):
    if left + 1 == right:
        # ???????????????
        return
    else:
        # ??????????????????
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

merge_sort(A, 0, len(A))
print(*A)
print(cnt)

Measured memory_bytes: 63740
#include <iostream>
#include <iomanip>
#define rep(i, n) for(unsigned int i = 0; i < (unsigned int)(n); i++)
using namespace std;

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

int main(){
  int K;
  unsigned int ans=0;
  cin >> K;
  rep(a,K){
    rep(b,K){
      rep(c,K){
       ans += gcd(a+1,gcd(b+1,c+1));
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
fun main(args: Array<String>) {
    val (a, b, c, x, y) = readLine()!!.split(' ').map { it.toInt() }

    val mutableList = mutableListOf<Int>()

    mutableList.add(a * x + b * y)
    mutableList.add(c * x * 2 + if (x >= y) 0 else b * (y - x))
    mutableList.add(c * y * 2 + if (y >= x) 0 else a * (x - y))

    println(mutableList.min())
}


Measured memory_bytes: 38296