akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int main(){
    char a[20],b[20],c[20];
    char ch;
    int i=0;
    while((ch=getchar())!=' ') {
        a[i]=ch;
        i++;
    }
    int j=0;
    while((ch=getchar())!=' '){
        b[j]=ch;
        j++;
    }
    int k=0;
    while((ch=getchar())!='\n'){
        c[k]=ch;
        k++;
    }
    if(a[i-1]==b[0]&&b[j-1]==c[0]) printf("YES\n");
    else  printf("NO\n");
    return 0;
}

Measured memory_bytes: 128
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: i64,
        b: i64,
        t: i64,
    }
    println!("{}", (t / a) * b);
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define N	250000
#define MD	0x7fffffff

int rand_(int n) {
	return (rand() * 76543LL + rand()) % n;
}

int inv(int a) {
	return a == 1 ? 1 : (long long) inv(a - MD % a) * (MD / a + 1) % MD; 
}

int X, Y, IX, IY;

void srand_() {
	struct timeval tv;

	gettimeofday(&tv, NULL);
	srand(tv.tv_sec ^ tv.tv_usec);
	X = rand_(MD - N * 2) + N * 2, IX = inv(X);
	Y = rand_(MD - N * 2) + N * 2, IY = inv(Y);
}

long long xy[N + 1];

int compare(const void *a, const void *b) {
	int i = *(int *) a;
	int j = *(int *) b;

	return xy[i] == xy[j] ? 0 : (xy[i] < xy[j] ? -1 : 1);
}

int find(long long *aa, int n, long long a) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2;

		if (aa[i] <= a)
			lower = i;
		else
			upper = i;
	}
	return lower == -1 || aa[lower] != a ? -1 : lower;
}

int main() {
	static char cc[N + 1];
	static long long xy_[N + 1];
	static int ii[N + 1], hh[N + 1], kk[N + 1];
	int n, n_, i;
	long long x, y, px, py, ans;

	srand_();
	scanf("%d%s", &n, cc);
	x = y = 0, px = py = 1;
	for (i = 0; i < n; i++) {
		if (cc[i] == '+')
			x = (x + px) % MD, y = (y + py) % MD;
		else if (cc[i] == '-')
			x = (x - px) % MD, y = (y - py) % MD;
		else if (cc[i] == '>')
			px = px * X % MD, py = py * Y % MD;
		else
			px = px * IX % MD, py = py * IY % MD;
		if (x < 0)
			x += MD;
		if (y < 0)
			y += MD;
		xy[i + 1] = x * MD + y;
	}
	for (i = 0; i <= n; i++)
		ii[i] = i;
	qsort(ii, n + 1, sizeof *ii, compare);
	n_ = 0;
	for (i = 0; i <= n; i++) {
		int i_ = ii[i];

		if (n_ == 0 || xy_[n_ - 1] != xy[i_])
			xy_[n_++] = xy[i_];
		hh[i_] = n_ - 1;
	}
	ans = 0;
	for (i = n; i >= 0; i--) {
		int h;

		if (cc[i] == '>')
			px = px * IX % MD, py = py * IY % MD;
		else if (cc[i] == '<')
			px = px * X % MD, py = py * Y % MD;
		x = (xy[n] / MD * px + xy[i] / MD) % MD;
		y = (xy[n] % MD * py + xy[i] % MD) % MD;
		if (x < 0)
			x += MD;
		if (y < 0)
			y += MD;
		h = find(xy_, n_, x * MD + y);
		if (h != -1)
			ans += kk[h];
		kk[hh[i]]++;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 8752
/*------------------------- Bism Allah Alruhmin Alrahim -------------------------------*/
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i > -1; i--)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define vc vector
#define f first
#define s second
#define pb(i) push_back(i)
#define mx(ar, n) (*max_element(ar, ar + n))
#define mn(ar, n) (*min_element(ar, ar + n))

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;


int main()
{
    int n ,m ;
    cin >> n >> m ;
    string s ; 
    cin >> s; 
    s[m-1] =  s[m-1] -'A' + 'a' ;
    cout << s << endl ;
    return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ; 
#define ll              long long int
// #define cini(x)	        scanf("%lld",&x)
// #define cins(s)	        scanf("%s",s)
#define deb(x)          cout << (x) << "  " ;
#define out(x)          cout << (x) << endl ;
#define endl            '\n'
#define pb              push_back
#define mk              make_pair
#define fastio          ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define loop(x,n,v)     for(ll v=x; v<n; v++)
#define loopr(n,x,v)     for(ll v=n-1; v>=x; v--)
#define mod             1000000007
#define all(x)          x.begin(), x.end()
#define clr(x)          memset(x, 0, sizeof(x))
#define sortall(x)      sort(all(x))
#define tr(it, a)       for(auto it = a.begin(); it != a.end(); it++)
#define PI              3.1415926535897932384626
#define setbits(x)      __builtin_popcount(x)
#define zrobits(x)      __builtin_ctz(x)
#define ps(x,y)         fixed << setprecision(y) << (x)
#define w(t)            int t; cin>>t; while(t--) 
#define     vi          vector<ll>
#define     vtt         vector<pair<ll,ll>> 
#define     pii         pair<ll,ll> 
#define  mapp           map<ll,ll> 
#define  sett           set<ll>
int dp[1000][1000] ;
ll mpow(ll base, ll exp); 
// =================================
// =================================





int main(){
    fastio ;
    // w(t)
    // {
        ll a=0, b=0, c=0, d=0, e=0, p=0, q=0, r=0 ;
        ll ans=0, res=0, cnt=0, sum=0, diff=0, mul=1, val=0, k=0 ;
        // loop(0,n,i) brr[i]=0;
        // char s[100005];
        string s ;
        ll n,m ;
        cin >> n ;
        cin >> m ;
        // cin >> s ;
        ll arr[n+1], brr[n+1]; 
        loop(0,n,i) cin >> arr[i] ;

        brr[0]=0;
        brr[1]=abs(arr[1]-arr[0]);
        loop(2,m+1,i){
            if(i>=n) break;
            a=INT_MAX;
            loop(1,i+1,j){
                a = min(brr[i-j]+abs(arr[i]-arr[i-j]),a);
            }
            brr[i]=a;
            // cout << brr[i] << " " << i << endl;
        }

        loop(m+1,n,i){
            a=INT_MAX;
            loop(1,m+1,j){
                a = min(brr[i-j]+abs(arr[i]-arr[i-j]),a);
                // cout << j << " -- " ;
            }
            brr[i]=a;
        }
        out(brr[n-1]);

    // }
    return 0 ;
}

// g++ x.cpp -o as && ./as

Measured memory_bytes: 5192
var GET = (function () {function f(s) {return new g(s);}function g(s) {this._s = s.trim().split("\n");}g.prototype.getValue = function (n) {return this._s[n];};g.prototype.getArray = function (n) {return this.stoa(this._s[n]);};g.prototype.slice = function (s, limit) {return this._s.slice(s, +limit + s || undefined).map(v => this.stox(v));};g.prototype.sliceArray = function (s, limit) {return this._s.slice(s, +limit + s || undefined).map(v => this.stoa(v));};g.prototype.stoa = function (s) {return s.split(" ").map(v => this.stox(v));};g.prototype.stox = function (v) {var i = +v;return (i === i) ? i : v;};return f;})();
var o = GET(require("fs").readFileSync("/dev/stdin", "utf8"));

console.log(main());
function main(){
    var N = o.getValue(0);
    var Bs = o.getArray(1);

    var As = [Bs[0]];
    for(var i = 0; N - 2 > i; i++) {
        As.push(Math.min(Bs[i], Bs[i + 1]))
    }

    As.push(Bs[N - 2]);
    return As.reduce((a, c) => {
        return a + c;
    }, 0)
}


Measured memory_bytes: 11468
import collections

n = int(input())
v = list(map(int, input().split()))

# 全要素が同じとき
if len(set(v)) == 1:
    print(len(v)//2)
    exit()

v_even = v[::2]
v_odd = v[1::2]

c_even = collections.Counter(v_even)
n_v_even_majority = c_even.most_common()[0][1]
c_odd = collections.Counter(v_odd)
n_v_odd_majority = c_odd.most_common()[0][1]

# 最頻要素が同じとき
if c_even.most_common()[0][0] == c_odd.most_common()[0][0]:
    if len(set(v_even)) == 1 & len(set(v_odd)) == 1:
        print(0)
    elif len(set(v_even)) > 1:
        tmp = n - c_even.most_common()[1][1] - n_v_odd_majority
        if len(set(v_odd)) > 1:
            tmp = min(tmp, n - n_v_even_majority - c_odd.most_common()[1][1])
        print(tmp)
else:
    print(n - n_v_even_majority - n_v_odd_majority)

Measured memory_bytes: 20572
#include <bits/stdc++.h>
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
using namespace std;

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+9;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int a,b,c;
	cin >> a >> b >> c;
	if(a == b) cout << c << endl;
	else if(b == c) cout << a << endl;
	else cout << b << endl;
	return 0;
}

Measured memory_bytes: 764
using System;

class Program
{
    static void Main()
    {

		int n = int.Parse(Console.ReadLine());

		for(int i=0;i<n;i++)
		{
		string[] input = Console.ReadLine().Split(' ');

		decimal x1 = decimal.Parse(input[0]);
		decimal y1 = decimal.Parse(input[1]);
		decimal x2 = decimal.Parse(input[2]);
		decimal y2 = decimal.Parse(input[3]);
		decimal x3 = decimal.Parse(input[4]);
		decimal y3 = decimal.Parse(input[5]);
		decimal x4 = decimal.Parse(input[6]);
		decimal y4 = decimal.Parse(input[7]);


		decimal diff1 = x2 - x1;
		decimal diff2 = y2 - y1;
		decimal diff3 = x4 - x3;
		decimal diff4 = y4 - y3;

		if(diff1==0 && diff3==0)
		{
			Console.WriteLine("YES");
		}
		
		else if(diff1==0 && diff3!=0)
		{
			Console.WriteLine("NO");
		}
		
		else if(diff1!=0 && diff3==0)
		{
			Console.WriteLine("NO");
		}
		else if(diff2/diff1 == diff4/diff3)
		{
			Console.WriteLine("YES");
		} else
		{
			Console.WriteLine("NO");
		}
	}

    }
}



Measured memory_bytes: 9232
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from operator import itemgetter

    class BinaryIndexTree:
        def __init__(self, n):
            self.size = n
            self._container = [0] * (n + 1)
            self.depth = n.bit_length()

        def sum(self, i):
            if i == 0:
                return 0
            s = 0
            while i > 0:
                s += self._container[i]
                i -= i & (-i)
            return s

        def add(self, i, x):
            if i == 0:
                return
            while i <= self.size:
                self._container[i] += x
                i += i & (-i)

        def lower_bound(self, x):
            if x == 0:
                return 0

            s = 0
            idx = 0
            for i in range(self.depth, -1, -1):
                k = idx + (1 << i)
                if k <= self.size and s + self._container[k] < x:
                    s += self._container[k]
                    idx += 1 << i
            return idx + 1

        def __repr__(self):
            return str(self._container)

    n, q = map(int, readline().split())
    c = [0] + list(map(int, readline().split()))
    query = []
    for i in range(q):
        l, r = map(int, readline().split())
        query.append((l, r, i))

    query.sort(key=itemgetter(1))
    idx = dict()
    cur = 0
    bit = BinaryIndexTree(n)
    res = [0] * q
    s = 0
    for i in range(q):
        l, r, j = query[i]
        while cur < r:
            cur += 1
            color = c[cur]
            if idx.get(color):
                bit.add(idx[color], -1)
            else:
                s += 1
            bit.add(cur, 1)
            idx[color] = cur
        res[j] = s - bit.sum(l - 1)

    for i in range(q):
        print(res[i])


if __name__ == '__main__':
    main()


Measured memory_bytes: 233128
<?php
fscanf(STDIN, "%d", $n);
fscanf(STDIN, "%d", $k);
fscanf(STDIN, "%d", $x);
fscanf(STDIN, "%d", $y);
$a = 0;
$b = 0;
if ($n > $k) {
    $b = $n - $k;
}
$a = $n - $b;
echo $a * $x + $b * $y . "\n";
?>

Measured memory_bytes: 3576
#include <stdio.h>

int main(void) {
int a,b,c;
scanf("%5d",&a);
scanf("%5d",&b);
scanf("%5d",&c);
 if(a<b&&b<c){
   printf("%d %d %d\n",a,b,c);
 }
 if(a<c&&c<b){
   printf("%d %d %d\n",a,c,b);
 }
 if(b<a&&a<c){
   printf("%d %d %d\n",b,a,c);
 }
 if(b<c&&c<a){
   printf("%d %d %d\n",b,c,a);
 }
 if(c<a&&a<b){
   printf("%d %d %d\n",c,a,b);
 }
 if(c<b&&b<a){
   printf("%d %d %d\n",c,b,a);
 }
 if(a==b&&b==c){
   printf("%d %d %d\n",a,b,c);
 }
 if(a==b&&b<c){
   printf("%d %d %d\n",a,b,c);
 }
if(a<b&&b==c){
 printf("%d %d %d\n",a,b,c);
}
if(a==c&&c<b){
  printf("%d %d %d\n",a,c,b);
}
if(c<a&&a==b){
  printf("%d %d %d\n",c,a,b);
}
if(b==c&&c<a){
  printf("%d %d %d\n",b,c,a);
}
if(b<a&&a==c){
  printf("%d %d %d\n",b,a,c);
}
}


Measured memory_bytes: 2712
#include <bits/stdc++.h>
using namespace std;
int main() {
    int A,B;
    cin >> A >>  B;
    int sum = 0;
    if (A > B){
        sum += A; A--;
    }else{
        sum += B; B--;
    }
    if (A > B){
        sum += A; A--;
    }else{
        sum += B; B--;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;

ll a[200010];
ll g[200010];

ll cnt = 1;
vector<ll> route;
bool seen[200010];

ll last;

void dfs(int v){
    int nv = g[v];
    if (seen[nv]) {
        route.push_back(nv);
        last = nv;
        return;
    }
    seen[nv] = true;
    route.push_back(nv);
    cnt++;
    dfs(nv);
}

int main(){
    ll n, k;
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    rep(i, n){
        g[i] = a[i] - 1;
    }
    seen[0] = true;
    route.push_back(0);
    
    dfs(0);
//    cout << cnt << endl;

    // rep(i, route.size()) cout << route[i] << " ";
    // cout << endl;
    int ind;

    ll m = route.size();
    rep(i, m){
        if (route[i] == last){
            ind = i;
            break;
        }
    }
    ll roop = m - ind - 1;
    // cout << ind << " " << roop << endl;
    
    if (k <= m - 1){
        cout << route[k] + 1 << endl;
        return 0;
    }

    k += 1;
    k -= ind;
    k %= roop;
    if (k == 0) k = roop;
    // cout << k << endl;
    cout << route[ind + k - 1] + 1 << endl;

    return 0;
}

Measured memory_bytes: 17352
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////




int main() {

	ll N;
	cin >> N;

	vector<ll> a(N + 1);
	repn(i, N) cin >> a[i];

	sort(++a.begin(), a.end(),greater<ll>());

	ll ans = 0;

	repn(i, N) {
		if (i % 2 == 1) { ans += a[i]; }
		else { ans -= a[i]; }
	}

	cout << ans;


	system("PAUSE");

	

}


Measured memory_bytes: 504
#include<stdio.h>
int main()
{
	int a,b,temp;
	while(scanf("%d%d",&a,&b)!=EOF&&(a||b))
	{
		temp=0;
		if(a>b)
		{
			temp=a;a=b;b=temp;
		}
		printf("%d %d\n",a,b);
	}
	return 0; 
}

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

typedef long long ll;

ll a[5001];

int main() {
  int num;
  while( cin >> num, num ) {
    ll maxn = -1000000000;
    for ( int i = 0; i < num; i++ ) cin >> a[i];
    for ( int i = 0; i < num; i++ ) {
      ll sum = 0;
      for ( int j = i; j < num; j++ ) {
	sum += a[j];
	maxn = max(maxn,sum);
      }
    }
    cout << maxn << endl;
  }
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<ll> a(N);
  ll bit = 0;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    bit = bit^a[i];
  }
  for (int i = 0; i < N; i++) cout << (a[i]^bit) << " ";
  cout << endl;
}


Measured memory_bytes: 4844
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			for(int k = 1; k <= n; k++) {
				ans += __gcd(i, __gcd(j, k));
			}
		}
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7;

int main() {
    int N, X, Y, k;
    cin >> N >> X >> Y;

    //距離と数
    map<int,int> m;
    
    for(int i = 1; i <= N; ++i){
        for(int j = i+1; j <= N; ++j){
            k = min(min(j-i, abs(j-Y)+abs(X-i)+1), abs(j-X)+abs(Y-i)+1);

            //key add
            if(m.count(k) == 0) m.insert(make_pair(k,1));
            //value++
            else m[k] = ++m[k];
        }
    }
    
    for(int i = 1; i < N; ++i) cout << m[i] << endl;
}


Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  set<long> primes;
  primes.insert(2);
  for (long i = 3; i <= 100000; i+= 2) {
    bool flag = true;
    for (auto it: primes) {
      if (it * it > i) break;
      if (i % it == 0) {
        flag = false;
        break;
      }
    }
    if (flag) primes.insert(i);
  }

  vector<long> accum(100010, 0);
  long count = 0;
  for (long i = 1; i <= 100000; i+= 2) {
    if (primes.count(i) and primes.count((i + 1) / 2)) count++;
    accum[i] = count;
  }

  long Q;
  cin >> Q;

  rep (i, Q) {
    long l, r;
    cin >> l >> r;
    if (l == 1) cout << accum[r] << endl;
    else cout << accum[r] - accum[l-2] << endl;
  }

  return 0;
}


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

int calc(int a, int b) {
  string s = to_string(a);
  string t = to_string(b);
  int ret = 0;
  for(int i=0; i<s.size(); i++){
    ret += s[i]-'0';
  }
  for(int i=0; i<t.size(); i++){
    ret += t[i]-'0';
  }
  return ret;
}

int main() {
  int n;
  int ans = 1e9;
  cin >> n;
  for(int a=1; a<=n/2; a++){
    int b = n - a;
    int tmp = calc(a, b);
    ans = min(ans, tmp);
  }
  cout << ans << endl;

  return 0;
}




//


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

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

    if(A<B){
        if((A==1)&&(B!=1)){
            cout << "Alice" << endl;
        }
        else{
            cout << "Bob" << endl;
        }
    }
    else if(A>B){
        if((B==1)&&(A!=1)){
            cout << "Bob" << endl;
        }
        else{
            cout << "Alice" << endl;
        }
    }
    else if(A == B){
        cout << "Draw" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main(){
    let input = read_vec::<i32>();
    let n = input[0];
    let x = input[1];
    let mut mn = Vec::new();
    for _ in 0..n {
        mn.push(read::<i32>());
    }
    let mini = mn.iter().min().unwrap();
    let sum :i32 = mn.iter().sum();
    let mut ans :i32 = if x - sum > 0{
        (x - sum ) / mini
    } else {
        0
    };
    ans +=n;
    println!("{}",ans);
}

Measured memory_bytes: 4352
def halfsplitsearch(list,start,end,minmax):
    if minmax=='min':
        while end-start>1:
            test=(end+start)//2
            if condition(list[test][0]):
                end=test
            else:
                start=test
        if condition(list[start][0]):
            return start
        else:
            return end
    else:
        while end-start>1:
            test=(end+start)//2
            if condition(list[test][0]):
                start=test
            else:
                end=test
        if condition(list[end][0]):
            return end
        else:
            return start

import sys

input=sys.stdin.readline

A,B,Q=map(int,input().split())
s=[[] for i in range(0,A)]
for i in range(0,A):
    y=int(input())
    s[i]=[y,'s',i]
t=[[] for i in range(0,B)]
for i in range(0,B):
    y=int(input())
    t[i]=[y,'t',i]
x=[0 for i in range(0,Q)]
for i in range(0,Q):
    x[i]=int(input())

list=s+t
list.sort()
s.sort()
t.sort()

sans=[0 for i in range(0,A)]
for i in range(0,A):
    ans=0
    def condition(num):
        return num<s[i][0]
    ans=halfsplitsearch(t,0,len(t)-1,'max')
    if ans!=B-1:
        sans[i]=min(abs(s[i][0]-t[ans][0]),abs(s[i][0]-t[ans+1][0]))
    else:
        sans[i]=abs(s[i][0]-t[ans][0])

tans=[0 for i in range(0,B)]
for i in range(0,B):
    ans=0
    def condition(num):
        return num<t[i][0]
    ans=halfsplitsearch(s,0,len(s)-1,'max')
    if ans!=A-1:
        tans[i]=min(abs(t[i][0]-s[ans][0]),abs(t[i][0]-s[ans+1][0]))
    else:
        tans[i]=abs(t[i][0]-s[ans][0])


for i in range(0,Q):
    a=0
    b=0
    test1=10**100
    test2=10**100
    def condition(num):
        return num<x[i]
    a=halfsplitsearch(list,0,len(list)-1,'max')
    if list[a][1]=='s':
        test1=abs(x[i]-list[a][0])+sans[list[a][2]]
    else:
        test1=abs(x[i]-list[a][0])+tans[list[a][2]]
    if a!=len(list)-1:
        if list[a+1][1]=='s':
            test2=abs(x[i]-list[a+1][0])+sans[list[a+1][2]]
        else:
            test2=abs(x[i]-list[a+1][0])+tans[list[a+1][2]]
    print(min(test1,test2))

Measured memory_bytes: 125116
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

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

    ll N;
    cin >> N;

    ll M = N * (N-1) / 2 - N / 2;
    cout << M << "\n";
    ll p;
    if (N % 2 == 0) {
        p = N + 1;
    } else {
        p = N;
    }

    for (ll i = 1; i <= N; i++) {
        for (ll j = i+1; j <= N; j++) {
            if (i + j == p) continue;
            cout << i << " " << j << "\n";
        }
    }
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 62;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n+1, vector<int>(n+1, INF));
  vector<vector<bool>> flag(n+1, vector<bool>(n+1, false));
  rep(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    g[a][b] = c;
    g[b][a] = c;
    flag[a][b] = true;
    flag[b][a] = true;
  }
  for(int k = 1; k <= n; ++k) {
    for(int i = 1; i <= n; ++i) {
      for(int j = 1; j <= n; ++j) {
        if(g[i][j] > g[i][k] + g[k][j]) {
          flag[i][j] = false;
          g[i][j] = g[i][k]+g[k][j];
        }
      }
    }
  }

  int use = 0;
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) if(flag[i][j]) ++use;
  }
  cout << m-use/2 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <numeric>

#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vec vector<int>
#define vecll vector<ll>

using namespace std;
///////////////////////////////////////////////////////////



int main() {
    int n, k;
    cin >> n >> k;
    vec h;
    int x;
    rep(i, n) {
        cin >> x;
        h.push_back(x);
    }
    sort(h.begin(), h.end());
    ll sum = 0;
    rep(i, n-k)
        sum += h[i];
    cout << sum << endl;


    return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

int main() {
  int N, L, min = 100,taste;
  cin >> N >> L;
  for(int i = 0; i < N; i++) {
    if(i == 0) {
        taste = L + i;
    } else {
        taste += L + i;          
    }
     if(abs(L + i) < min) {
      min = abs(L + i);
    }
  }
  if(taste < 0) {
      cout << taste + min << endl;
  } else {
      cout << taste - min << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args)
	{
		//変数
		int count=0;
		boolean sw=false;
		String answer="";
		int e=0;
		int f=0;
		int g=0;
		int h=0;
		//List<Integer> hb=new ArrayList<Integer>();
		//long a=0;
		//int af=Integer.MAX_VALUE;
		//入力
		Scanner sc = new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		int d=sc.nextInt();
		//int [][] cost =new int[N-1][2];
		//処理
		if(a==1 || b==1 || c==1 || d==1)
		{
			e=1;
		}
		if(a==9 || b==9 || c==9 || d==9)
		{
			f=1;
		}
		if(a==7 || b==7 || c==7 || d==7)
		{
			g=1;
		}
		if(a==4 || b==4 || c==4 || d==4)
		{
			h=1;
		}
		//
		if(e==1 && f==1 && g==1 && h==1)
		{
			answer="YES";
		}else
		{
			answer="NO";
		}
		// 出力
		System.out.println(answer);
	}
}

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

int main(){
	int n, m, i, j, t, k;
	while(~scanf("%d %d", &n, &m)){
		k = n + m;
		if(k >= 10) printf("error\n");
		else printf("%d\n", k);
	}
	return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

G=[[0]*4 for i in range(4)]
for i in range(3):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
visited=[0]*4
def dfs(node):
    visited[node]=1
    for gi in G[node]:
        if not visited[gi]:
            dfs(gi)
            return
dfs(0)
if all(visited):
    print("YES")
else:
    print("NO")
        


Measured memory_bytes: 38256
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    R = [[0] * w for _ in range(h)]
    L = [[0] * w for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if i == 0:
                U[i][j] = 1 if s[i][j] == "." else 0
                D[-i-1][j] = 1 if s[-i-1][j] == "." else 0
            else:
                U[i][j] = U[i-1][j] + 1 if s[i][j] == "." else 0
                D[-i-1][j] = D[-i][j] + 1 if s[-i-1][j] == "." else 0
            if j == 0:
                L[i][j] = 1 if s[i][j] == "." else 0
                R[i][-j-1] = 1 if s[i][-j-1] == "." else 0
            else:
                L[i][j] = L[i][j-1] + 1 if s[i][j] == "." else 0
                R[i][-j-1] = R[i][-j] + 1 if s[i][-j-1] == "." else 0
    m_l = 0
    for i in range(h):
        for j in range(w):
            m_l = max(m_l, R[i][j] + L[i][j] + U[i][j] + D[i][j] - 3)
    print(m_l)


if __name__ == '__main__':
    slove()


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

int main() {
  int N;
  cin >> N;
  if(N%10 == 3)
    cout<<"bon"<<endl;
  else if(N%10 ==0|N%10==1|N%10==6|N%10==8)
    cout<<"pon"<<endl;
  else
    cout<<"hon"<<endl;
}



Measured memory_bytes: 3620
n,k,q = map(int,input().split()) 
a = []
for i in range(q):
  a.append(int(input()))
def subPoints(n):
  return  n - len(a)
points = [k]*n
points = list(map(subPoints,points))
for cleared in a:
  points[cleared-1] += 1
for p in points:
  if p <= 0:
    print('No')
  else:
    print('Yes')

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


int main(){

int a,b,c,d;

cin>>a>>b>>c>>d;

bool s = false ;
int i = 1;
while(s==false){
    if(i%2 != 0) c = c-b;
    else a = a -d;

    i++;

    if(c<= 0){
        cout<<"Yes"<<endl;
        s = true;
    }
    else if(a<=0){
        cout<<"No"<<endl;
        s = true ;
    }
}


}


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

using namespace std;

using ll = long long;

template <typename T> struct UnionFind {
  vector<T> data;
  UnionFind(T n) : data(n, -1) {}
  bool unite(T x, T y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x])
        swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  T root(T x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  bool same(T x, T y) { return root(x) == root(y); }
  T size(T x) { return -data[root(x)]; }
  void minus(T x) { data[root(x)]++; }
};

bool f[200001] = {};

int main() {
  int n;
  cin >> n;
  int k, l;
  cin >> k >> l;
  UnionFind<int> uf(n);
  for (int i = 0; i < k; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    uf.unite(a, b);
  }
  UnionFind<int> uf1(n);
  for (int i = 0; i < l; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    uf1.unite(a, b);
  }
  map<pair<int, int>, int> mp;
  for (int i = 0; i < n; ++i) {
    mp[{uf.root(i), uf1.root(i)}]++;
  }
  for (int i = 0; i < n; ++i) {
    cout << mp[{uf.root(i), uf1.root(i)}] << " ";
  }
}

Measured memory_bytes: 13568
#!/usr/bin/env python3
from itertools import accumulate

n, k = map(int, input().split())
p = list(map(int, input().split()))
cs = [0] + list(accumulate(p))
pvt = 0
for i in range(n - k + 1):
    m = cs[pvt + k] - cs[pvt]
    s = cs[i + k] - cs[i]
    if s > m:
        pvt = i
print((cs[pvt + k] - cs[pvt] + k) / 2)


Measured memory_bytes: 25152
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define pb push_back
#define pf push_front
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define f first
#define s second
#define sz(x) (int)x.size()
#define endl "\n"
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout<<(x)<<endl
#define watch2(x,y) cout<<(x)<<" "<<(y)<<endl
#define watch3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

const int INF = 9e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int i, n, a[N], b[N], ans[N];

void solve()
{
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    reverse(b + 1, b + n + 1);
    int l = -1, r = -1, val;
    for (i = 1; i <= n; i++)
    {
        if (a[i] == b[i])
        {
            if (l == -1)
                l = i;
            r = i;
            val = b[i];
        }
    }
    if (l != -1)
    {
        set<int> pos;
        for (i = 1; i <= n; i++)
        {
            if (b[i] != val && a[i] != val)
                pos.insert(i);
        }
        if (sz(pos) < r - l + 1)
        {
            cout << "No";
            return;
        }
        for (i = l; i <= r; i++)
        {
            int idx = *pos.begin();
            swap(b[idx], b[i]);
            pos.erase(pos.begin());
        }
    }
    cout << "Yes" << endl;
    for (i = 1; i <= n; i++)
    {
        cout << b[i] << " ";
    }
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fastio;
    int t;
    //cin >> t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 16124
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
typedef long long LL;
constexpr int kMod = 1000000007;

LL dp[10000][101][2] = {};  // idx, sum%D, less/tight

int main() {
  std::string S; std::cin >> S;
  int D; std::cin >> D;

  dp[0][0][0] = 1;
  for (size_t idx = 0; idx < S.length(); ++idx) {
    int c = S[idx] - '0';
    for (int sum = 0; sum < D; ++sum) {
      for (int less : {0, 1}) {
        for (int n = 0; n < 10; ++n) {
          if (n<c)         dp[idx+1][(sum + n) % D][1] += dp[idx][sum][less];
          else if (n == c) dp[idx+1][(sum + n) % D][less] += dp[idx][sum][less];
          else if (less)   dp[idx+1][(sum + n) % D][less] += dp[idx][sum][less];

          dp[idx+1][(sum + n) % D][0] %= kMod;
          dp[idx+1][(sum + n) % D][1] %= kMod;
        }
      }
    }
  }

  std::cout
    << (dp[S.length()][0][0] + dp[S.length()][0][1] + kMod - 1) % kMod << std::endl;
}


Measured memory_bytes: 16000
#include <iostream>
#include<sstream>
#include<string>
#include<vector>
#include <cmath>
#include <limits>
#include <queue>
#include<algorithm>
#include<cstring>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <iomanip>
#include <map>
#include <stack>
#include <memory>
#include <numeric>
#include <type_traits>

using namespace std;

#define rep(i,n) for (int (i)=0;(i)<(n);i++)
typedef long long ll;
const int MAXV = 1e6;


int main(){
  int n; cin >> n;
  priority_queue<ll> q;
  ll a;
  rep(i,n){
    cin >> a;
    q.push(a);
  }
  ll ans = 0;
  if (n%2 == 0){
    ans -= q.top();
    rep(i,n/2){
      ans += q.top()*2;
      q.pop();
    }
  }
  else{
    ans -= q.top();
    rep(i,(n-1)/2){
      ans += q.top()*2;
      q.pop();
    }
    ans += q.top();
  }
  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 5352
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

double distanceAB(double xa, double ya, double xb, double yb);
//void trace(int A[], int N);

/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/


static const int MAX = 100;
static const int INFTY = (1 << 21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

void dijkstra()
{
	int minv;
	int d[MAX], color[MAX];
	
	REP(n)
	{
		d[i] = INFTY;
		color[i] = WHITE;
	}
	
	d[0] = 0;
	color[0] = GRAY;
	while (1)
	{
		minv = INFTY;
		int u = -1;
		REP(n)
		{
			if (minv > d[i] && color[i] != BLACK)
			{
				u = i;
				minv = d[i];
			}
		}
		if (u == -1) break;
		color[u] = BLACK;
		for (int v=0; v<n; v++)
		{
			if (color[v] != BLACK && M[u][v] != INFTY)
			{
				if (d[v] > d[u] + M[u][v])
				{
					d[v] = d[u] + M[u][v];
					color[v] = GRAY;
				}
			}
		}
	}
	
	REP(n)
	{
		cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;
	}
}


int main()
{
	cin >> n;
	
	rep(i, n) rep(j, n) M[i][j] = INFTY;
	
	int k, c, u, v;
	rep(i, n)
	{
		cin >> u >> k;
		rep(j, k)
		{
			cin >> v >> c;
			M[u][v] = c;
		}
	}
	
	dijkstra();
	
	return 0;
}


/*
void trace(int A[], int N)
{
	REP(N)
	{
		if (i > 0) cout << " ";
		cout << A[i];
	}
	cout << endl;
}
*/


double distanceAB(double xa, double ya, double xb, double yb)
{
	return sqrt((xb-xa)*(xb-xa) + (yb-ya)*(yb-ya));
}

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

int n;
ll a[100100], s1, s2;

inline int f(int i) {
	return (i < (n+1)/2-1) ? -2 : (i > (n+1)/2) ? 2 : -1;
}
inline int g(int i) {
	return (i < (n+1)/2) ? -2 : (i > (n+1)/2+1) ? 2 : 1;
}
inline int h(int i) {
	return (i < n/2) ? -2 : (i == n/2) ? -1 : (i == n/2+1) ? 1 : 2;
}

int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lld",a+i);
	sort(a+1,a+n+1);
	if (n & 1) {
		for (int i=1;i<=n;i++) {
			s1 += a[i] * f(i);
			s2 += a[i] * g(i);
		}
		printf("%lld\n",max(s1,s2));
	} else {
		for (int i=1;i<=n;i++) {
			s1 += a[i] * h(i);
		}
		printf("%lld\n",s1);
	}
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  unsigned long long int a,b,c,res=1,no=0;
  cin>>a;
  while(a--){
	cin>>c;
	if(no==0){
		b=log10(res)+log10(c);
		if(b>18){no=1;}
		res*=c;
		if(res>1000000000000000000){no=1;}
	}
	if(c==0){cout<<"0";return 0;}
  }
  if(no==0){cout<<res;}else{cout<<"-1";}
}

Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
int gride[2][1000000];
int n;
int maxi=0;
void parcourie(int i,int j,int total){
    if(i==1&&j==n-1){
        maxi=max(maxi,total+gride[i][j]);
        return;
    }
    if(i+1==1)
        parcourie(i+1,j,total+gride[i][j]);

    if(j+1<n)
        parcourie(i,j+1,total+gride[i][j]);
}
 int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=0;i<2;i++){
        for(int j=0;j<n;j++)
        cin>>gride[i][j];
    }
    parcourie(0,0,0);
    cout<<maxi;

}


Measured memory_bytes: 2304
using System;
using System.Linq;
using System.Collections.Generic;

namespace ConsoleApp1 {
    public class Class {
        static void Main(string[] args) {
            var a = Console.ReadLine();

            if (a == a.ToUpper()) {
                Console.Write("A");
            } else {
                Console.Write("a");
            }
        }
    }
}

Measured memory_bytes: 26212
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
s=sum(a)

candidates=set()
for i in range(1,int(s**0.5)+1):
  if s%i==0:
    candidates.add(i)
    candidates.add(s//i)

ans=0
for cdd in candidates:
  f=sorted([x%cdd for x in a])
  # calc need
  ans=max(ans,cdd) if sum(f[:-sum(f)//cdd])<=k else ans   
    
print(ans)

Measured memory_bytes: 9364
n=int(input())
x=list(map(int,input().split()))

newx=sorted(x)

lower_med=newx[n//2-1]
higher_med=newx[n//2]

for i in range(n):
    if x[i]<=lower_med:
        print(higher_med)
    else:
        print(lower_med)

Measured memory_bytes: 30840
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();

   int[] a = new int[N];
   for(int i=0;i<N;i++) a[i] =sc.nextInt();

   Arrays.sort(a);
   int count =1;
   int tmp =a[0];
   for(int i=1;i<N;i++)
   {
     if(tmp<a[i])
     {
       tmp = a[i];
       count++;
     }
   }
   System.out.println(count);
 }
}

Measured memory_bytes: 21716
#include<iostream>
#include<string>
using namespace std;
int main(){
  string str,str1;
  while(1){
    int HIT=0,BLOW=0;
    cin>>str>>str1;
    if(str.size()!=4)break;
    for(int i=0;i<4;i++)
      for(int j=0;j<4;j++)
	if(str[i]==str1[j])
	  if(i==j)HIT++;
	  else BLOW++;
    cout<<HIT<<' '<<BLOW<<endl;
  } 
 return 0;
}

Measured memory_bytes: 1180
n, m = map(int,input().split())
A = ['']*n
B = ['']*m
for i in range(n):
    A[i] = input()
for i in range(m):
    B[i] = input()

w_dif = len(A[0])-len(B[0])
w_w = len(B[0])
ans = 'No'
for h in range(n-m+1):
    for w in range(w_dif+1):
        window = [wh[w:w+w_w] for wh in A[h:h+m]]
        if window==B:
            ans = 'Yes'
            break
print(ans)

Measured memory_bytes: 9092
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int n, h, m = 0, ans = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &h);
        if (m <= h) ++ans, m = h;
    }
    printf("%d\n", ans);
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    
    bool can = false;
    for(int i = 0; 4 * i <= n; ++i) {
        if((n - 4 * i) % 7 == 0) can = true;
    }
    
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uu unsigned
#define io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
#define pl pair<ll,ll>
#define mkp make_pair
#define ss second
#define ff first
#define mit(a,b) map<a,b>::iterator
#define sit(a) set<a>::iterator
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define printcas cout<<"Case "<<cas<<": "
#define _ continue;
#define endl '\n'
#define __ cout<<endl;continue;
const ll oo=(1ll<<60);
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
vector<vector<vector<double>>> dp(305,vector<vector<double>>(305,vector<double>(305,-1.0)));
double n;
double e(double t1,double t2,double t3)
{
    if(dp[(int)t1][(int)t2][(int)t3]!=-1) return dp[(int)t1][(int)t2][(int)t3];
    return dp[(int)t1][(int)t2][(int)t3]=(1.0/(t1+t2+t3))*(n+((!t1)?0:(t1*e(t1-1.0,t2,t3)))+((!t2)?0:(t2*e(t1+1.0,t2-1.0,t3)))+((!t3)?0:(t3*e(t1,t2+1.0,t3-1.0))));
}
int main()
{
     //io;
    //string hudai(1000000,'a');
    int T=1;
    //T=gi();
     for(int cas=1;cas<=T;cas++)
    {
        double t1=0.0,t2=0.0,t3=0.0,x;
       cin>>n;
       for(int i=1;i<=n;i++)
       {
           cin>>x;
           if(x==1)t1+=1.0;
           else if(x==2) t2+=1.0;
           else t3+=1.0;
       }
//       int mx=max(t1,max(t2,t3));
//       for(int i=0;i<=n+2;i++)for(int j=0;j<=n+2;j++)for(int k=0;k<=n+2;k++)dp[i][j][k]=-1;
       dp[0][0][0]=0;
       printf("%.15lf",e(t1,t2,t3));

    }
    return 0;
}


Measured memory_bytes: 228740