akhauriyash/Code-Regression huggingface dataset:
/*input
134
4330
34808
98792
0
*/
fn read_line() -> String {
    let mut return_ = format!("");
    std::io::stdin().read_line(&mut return_).ok();
    return_
}

fn main() {
    let mut prime_list: [bool; 1000001] = [true; 1000001];
    let mut multiple;
    prime_list[0] = false;
    for i in 2..1000001 {
        if prime_list[i] {
            multiple = i.pow(2);
            while multiple < 1000001 {
                prime_list[multiple as usize] = false;
                multiple = multiple + i;
            }
        }
    }
    /*
    Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.

    for i = 2, 3, 4, ..., not exceeding √n:
      if A[i] is true:
        for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
          A[j] := false.
    */
    let mut input: u32;
    let mut total: u32;
    loop {
        input = read_line().trim().parse().expect("");
        if input == 0 {
            break;
        }
        /*
        for i in range(num//2 + 1):
        if num % 2 != 0:
            print(num, 'not even'); break
        if i in primes and (num - i) in primes:
            print(i, '+', num - i)
        */
        total = 0;
        //println!("{:?}", input / 2 + 1);
        for i in 2..((input / 2) + 1) {
            if prime_list[i as usize] && prime_list[(input - i) as usize] {
                total = total + 1;
            }
        }
        println!("{}", total);
    }
}



Measured memory_bytes: 6000
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Range(container) container.begin(), container.end()
#define Cin(T, x) T x; cin >> x;
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i];
#define Cout(val) cout << (val) << "\n";
using namespace std;
using ll = long long;

int main(void){
    Cin(int, n);
    Cout(1110 - n);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair < ll, ll > PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll MOD = 1e4+7;
class Union_find {
public: 
    vector<ll> parent;
    Union_find( ll n ){
        // 親のとき： -(その集合のサイズ)
        // 子のとき: 親の番号
        // すべて親(集合1)として初期化
        parent = vector<ll>(n, -1);
    }
    ll root( ll a ){
        if ( parent[a] < 0 ) return a;
        return parent[a] = root(parent[a]);
    }
    ll size( ll a ){
        return -parent[root(a)];
    }
    bool unite( ll a, ll b ){
        a = root(a);
        b = root(b);
        if ( a == b ) return false;
        if ( size(a) < size(b) ) swap(a, b);
        parent[a] += parent[b];
        parent[b] = a;
        return true;
    }
};
int main() {
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> ab(m);
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        --a, --b;
        ab[i] = make_pair(a, b);
    }
    vector<ll> ans(m);
    ans[m-1] = n * ( n - 1 ) / 2;
    Union_find uni(n);
    for ( ll i = m - 1; i > 0; --i ) {
        ans[i-1] = ans[i];
        // 異なる親同士が接続
        if ( uni.root(ab[i].first) != uni.root(ab[i].second ) ) {
            ans[i - 1] -= uni.size(ab[i].first) * uni.size(ab[i].second);
            uni.unite(ab[i].first, ab[i].second);
        }
    }
    rep(i, m) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 4480
#include <stdio.h>

void replace(char *, char *, int ,int);
void reverse(char *, int, int);
void print(char *, int, int);

int main() {
    int i, q, a, b;
    char s[1001], p[1001], command[8];

    scanf("%s", s);
    scanf("%d", &q);

    for (i = 0; i < q; i++) {
        scanf("%s", command);
        scanf("%d%d", &a, &b);

        if (command[0] == 'p') {
            print(s, a, b);
        }
        else if (command[2] == 'p') {
            scanf("%s", p);
            replace(s, p, a, b);
        }
        else if (command[2] == 'v') {
            reverse(s, a, b);
        }
    }

    return 0;
}


void replace(char *s, char *p, int a, int b) {
    int i, n = 0;

    for (i = a; i <= b; i++) {
        s[i] = p[n];
        n++;
    }
}

void reverse(char *s, int a, int b) {
    int i, n = 0;
    char temp[1001];

    for (i = a; i <= b; i++, n++) {
        temp[n] = s[i];
    }

    n = 0;

    for (i = b; i >= a; i--) {
        s[i] = temp[n];
        n++;
    }
}

void print(char *s, int a, int b) {
    int i;

    for (i = a; i <= b; i++) {
        printf("%c", s[i]);
    }
    printf("\n");
}



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

using namespace std;

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

  int n;
  cin >> n;
  vector<int64_t> a(n + 1);
  vector<int64_t> b(n);
  for (int i = 0; i < n + 1; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
  }

  int64_t ans = 0;
  int64_t x = 0, y = 0;
  for (int i = 0; i < n; ++i) {
    x = min(a[i], b[i]);
    b[i] -= x;
    y = min(a[i + 1], b[i]);
    a[i + 1] -= y;
    ans += x;
    ans += y;
  }

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 4780
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1 {
     class Program {
          static void Main(string[] args) {
               string[] s = Console.ReadLine().Split(' ');
               int A = int.Parse(s[0]);
               int B = int.Parse(s[1]);

               if(A == 1) {
                    A = A + 13;
               }
               if(B == 1) {
                    B = B + 13;
               }
               if(A > B) {
                    Console.WriteLine("Alice");
               }
               else if(A == B) {
                    Console.WriteLine("Draw");
               }
               else {
                    Console.WriteLine("Bob");
               }
          }
     }
}



Measured memory_bytes: 13140
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
INF = 10 ** 9


# 先に全ての合成を終えてから延長/縮小をすると考える
# それぞれの竹は、[Aに使う, Bに使う, Cに使う, どれにも使わない]の4通り
# 4 ** 8 = 65536 なので全通り試しても間に合う
def dfs(cur, len_a, len_b, len_c):
    if cur == N:
        if min(len_a, len_b, len_c) > 0:
            # 1本目は合成していないので、10ずつ引いて調整する
            return abs(len_a - A) + abs(len_b - B) + abs(len_c - C) - 30
        else:
            # 竹を1本も使わなかったケースを除外する
            return INF
    # どれにも使わない
    not_use = dfs(cur + 1, len_a, len_b, len_c)
    # Aに使う（Aを使うために合成する）
    use_for_a = dfs(cur + 1, len_a + L[cur], len_b, len_c) + 10
    # Bに使う（Bを使うために合成する）
    use_for_b = dfs(cur + 1, len_a, len_b + L[cur], len_c) + 10
    # Cに使う（Cを使うために合成する）
    use_for_c = dfs(cur + 1, len_a, len_b, len_c + L[cur]) + 10

    return min(not_use, use_for_a, use_for_b, use_for_c)


print(dfs(0, 0, 0, 0))


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

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

using namespace std;

int main(){
	for(int n;scanf("%d",&n),n;){
		int t[16][17];
		rep(i,n) rep(j,n+1) scanf("%d",t[i]+j);

		static int dp[1<<16];
		rep(S,1<<16) dp[S]=1<<29;
		dp[0]=0;
		rep(S,1<<16){
			rep(i,n) if((S&(1<<i))==0) {
				dp[S|(1<<i)]=min(dp[S|(1<<i)],dp[S]+t[i][0]);
				rep(j,n) if(S&(1<<j)) {
					dp[S|(1<<i)]=min(dp[S|(1<<i)],dp[S]+t[i][j+1]);
				}
			}
		}

		printf("%d\n",dp[(1<<n)-1]);
	}

	return 0;
}

Measured memory_bytes: 1016
N = int(input())
S = [input() for _ in range(N)]
a = S.count("AC")
b = S.count("WA")
c = S.count("TLE")
d = S.count("RE")
print("AC x "+str(a))
print("WA x "+str(b))
print("TLE x "+str(c))
print("RE x "+str(d))

Measured memory_bytes: 82564
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
const int MAX = 1000000;
int table[MAX + 1], counter[MAX + 1];
int main() {
    for (int i = 2; i <= 1000; i++) {
        if (table[i] != 0) continue;
        for (int k = i; k <= MAX; k += i) {
            if (table[k] == 0) table[k] = i;
        }
    }
    for (int i = 2; i <= MAX; i++) if (table[i] == 0) {
        table[i] = i;
    }
    int N; cin >> N;
    vector<int> A(N); for (auto &a : A) cin >> a;
    for (int a : A) {
        set<int> S;
        int b = a;
        while (b != 1) {
            S.emplace(table[b]);
            b /= table[b];
        }
        for (auto p : S) {
            counter[p]++;
        }
    }
    int maxval = 0;
    for (int i = 2; i <= MAX; i++) {
        maxval = max(maxval, counter[i]);
    }
    if (maxval <= 1) {
        cout << "pairwise coprime\n";
    } else if (maxval != N) {
        cout << "setwise coprime\n";
    } else {
        cout << "not coprime\n";
    }
    return 0;
}

Measured memory_bytes: 14660
#include <iostream>

using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 4e5 + 5;
const int MOD = 1e9 + 7;

int n, m, k;
int fact[N], invfact[N];

int pow(int a, int b, int m)
{
	int ans = 1;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % m;
		b /= 2;
		a = (a * a) % m;
	}
	return ans;
}

int modinv(int k)
{
	return pow(k, MOD - 2, MOD);
}

void precompute()
{
	fact[0] = fact[1] = 1;
	for (int i = 2; i < N; i++)
	{
		fact[i] = fact[i - 1] * i;
		fact[i] %= MOD;
	}
	invfact[N - 1] = modinv(fact[N - 1]);
	for (int i = N - 2; i >= 0; i--)
	{
		invfact[i] = invfact[i + 1] * (i + 1);
		invfact[i] %= MOD;
	}
}

int nCr(int x, int y)
{
	if (y > x)
		return 0;
	int num = fact[x];
	num *= invfact[y];
	num %= MOD;
	num *= invfact[x - y];
	num %= MOD;
	return num;
}


int bulec[2020], redc[2020];
int32_t main()
{
	IOS;
	cin >> n >> k;
	precompute();
	int ans = 0;
	//cout << nCr(1995 + 4 - 1, 4 - 1)%MOD << endl;
	for (int i = 0; i < k; i++) {//箱
		bulec[i] = nCr(k - 1, i)%MOD;
		//cout << bulec[i] << "bule" << i << endl;
		redc[i] = 1;
	}
	int use = n - k; //cout << red << endl;
	for (int i = 0; i < k; i++) {
		
		int red = use - i; 
		if (red < 0) {
			redc[i] = 0;
			continue;
		}
		/*else if (red + i + 2 - 1 < red) {
			continue;
		}*/
		
		redc[i] = nCr(red+i+1, red)%MOD;
		//cout << redc[i] << "red" << i << endl;
	}

	for (int i = 0; i < k; i++) {
		int ans = (bulec[i] * redc[i]) % MOD;
		cout << ans << endl;
	}
	return 0;
}

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

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let sx: i64 = read();
    let sy: i64 = read();
    let tx: i64 = read();
    let ty: i64 = read();
    let mut ans: String = String::new();
    let x: usize = (tx - sx) as usize;
    let y: usize = (ty - sy) as usize;

    for _ in 0..x {
        ans += &"R".to_string();
    }
    for _ in 0..y {
        ans += &"U".to_string();
    }
    for _ in 0..x {
        ans += &"L".to_string();
    }
    for _ in 0..y {
        ans += &"D".to_string();
    }
    ans += "D";
    for _ in 0..x + 1 {
        ans += &"R".to_string();
    }
    for _ in 0..y + 1 {
        ans += &"U".to_string();
    }

    ans += "L";
    ans += "U";

    for _ in 0..x + 1 {
        ans += &"L".to_string();
    }
    for _ in 0..y + 1 {
        ans += &"D".to_string();
    }

    ans += "R";
    println!("{}", ans);
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<ll> Vector;
typedef vector<Vector> DVector;

#define fi          first
#define se          second
#define pb          push_back
#define INF         INT_MAX
#define bcnt        __builtin_popcount
#define all(x)      (x).begin(),(x).end()
#define dbg(x)      cout<<#x"="<<x<<endl
#define uni(x)      x.erase(unique(all(x)),x.end())
#define ub(x,y)     upper_bound(all(x),y)-x.begin()
#define lb(x,y)     lower_bound(all(x),y)-x.begin()
#define rep(i,n)    repl(i,0,n-1)
#define usort(x)    sort(all(x))
#define dsort(x)    sort(all(x),greater<ll>())
#define mkp(x,y)    make_pair(x,y)
#define mmax(x,y)   (x>y?x:y)
#define mmin(x,y)   (x<y?x:y)
#define maxch(x,y)  x=mmax(x,y)
#define minch(x,y)  x=mmin(x,y)
#define exist(x,y)  (find(all(x),y)!=x.end())
#define each(itr,v) for(auto itr:v)
#define repl(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)

//// UnionFind Tree

struct UnionFind{
  vector<int> v;
  UnionFind(int n) : v(n, -1) {}

  // 初期化
  void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }

  // Find
  int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }

  // Union
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }

  // 以下、オプション
  // 根かどうか
  bool is_root(int x) { return v[x] < 0; }

  // xの根
  int root(int x) {
        return v[x] < 0 ? x : v[x] = root(v[x]);
  }
  // 同じ連結成分か
  bool same(int x, int y) { return find(x) == find(y); }

  // 同じ連結成分のサイズ
  int size(int x) { return -v[find(x)]; }
};
int main(){
  cin.sync_with_stdio(false);
  ll n,k,l;
  cin >> n >> k >> l;
  UnionFind uf1(n), uf2(n);
  rep(i,k){
    ll t1,t2;
    cin >> t1 >> t2;
    uf1.unite(t1-1,t2-1);
  }
  rep(i,l){
    ll t1,t2;
    cin >> t1 >> t2;
    uf2.unite(t1-1,t2-1);
  }
  map<P,ll> mp;
  rep(i,n)mp[mkp(uf1.root(i),uf2.root(i))]++;
  rep(i,n)cout << (i == 0 ? "" : " ") << mp[mkp(uf1.root(i),uf2.root(i))];
  cout << endl;
}


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

long long int mod=1e9+7;

int main(){
  string s;
  cin>>s;
  long long int k;
  cin>>k;
  for(int i=0;i<k;i++){
    if(s[i]!='1'){
      cout<<s[i]<<endl;
      return 0;
    }
  }
  cout<<1<<endl;
}


Measured memory_bytes: 256
n,k = map(int, input().split())
if n == 0 or k == 1:
  print(0)
elif n < (k + 1)//2:
  print(n)
elif n < k:
  print(k - n)
elif n == k or n % k == 0:
  print(0)
else:
  print((k * (n//k + 1)) % n)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#include <vector>
#include <numeric>
#include <map>
#include <cmath>
#include <iomanip>
#include <queue>
using ll =long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;

int main() {
    int N, M;
    cin >> N >> M;

    vi a(M), b(M);

    for(int i=0; i<M; i++){
        cin >> a.at(i) >> b.at(i);
    }

    int sum = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(a.at(j) == i+1){
                sum++;
            }
            if(b.at(j)==i+1){
                sum++;
            }
        }
        cout << sum << endl;
        sum = 0;
    }

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

int n, u, k, v, t;
int adjList[101][101];
int adjNum[101];
bool visited[101];

int d[101], f[101];

void dfs(int u) {
    if (visited[u]) return;
    visited[u] = true;

    d[u] = t;
    t++;

    for (int i = 0; i < adjNum[u]; ++i) {
        dfs(adjList[u][i]);
    }

    f[u] = t;
    t++;

}

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

    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &u, &k);
        adjNum[u-1] = k;
        for (int j = 0; j < k; ++j) {
            scanf("%d", &v);
            adjList[u-1][j] = v-1; // all IDs start from 1
        }
    }

    t = 1;
    for (int u = 0; u < n; ++u) {
        dfs(u);
        cout << u+1 << " " << d[u] << " " << f[u] << "\n";
    }

	return 0;
}


Measured memory_bytes: 3232
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int X = sc.nextInt();
        if (X <= 500*K) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

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

int main() {
  int n,x,y,a;
  cin>>n>>x>>y;
  vector<int> num(n,0); 
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      num[min(abs(j-i),abs(y-j)+abs(x-i)+1)-1]++;
    }
  }
  for(int i=0;i<n-1;i++){
    cout<<num[i]<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,s,n) for (int i=s;i<n;++i)
#define drep(i,s,n) for (int i=n;i>=s;--i)
#define all(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define print(x) cout<<(x)<<endl
using namespace std;
typedef long long ll;

int gcd(int a,int b)
{if (a%b == 0) return(b);
 else          return(gcd(b,a%b));}
int lcm(int a,int b)
{return a*b/gcd(a,b);}
void printv(vector<auto> v) {cout<<'[';rep(i,0,v.size()){cout<<v[i]<<',';}cout<<']'<<endl;}
void printvv(vector<vector<auto>> vv)
{
  cout<<'['<<endl;
  rep(q,0,vv.size()){cout<<'[';rep(p,0,vv.at(q).size())cout<<vv.at(q).at(p)<<',';cout <<']'<<endl;}
  cout<<']'<<endl;
}
void solve(); int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}
int step_x[] = {-1,0,0,1};
int step_y[] = {0,-1,1,0};
ll INF=10e12;
//------------------------------------------------------------
ll K,ans=0;
string S;
void solve() {
  cin>>K>>S;

  if(K>=S.size())
  {
    print(S); return;
  }

  rep(i,0,K) cout<<S[i];
  cout << "..." << endl;

  return;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>

struct union_find {
	int N, M;
	std::vector<int> parent, sz;

	union_find(int n) : N(n), M(n) {
		parent.resize(N); sz.resize(N, 1);
		for (int i = 0; i < N; i++) parent[i] = i;
	}

	int root(int i) {
		if (parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}

	bool is_united(int i, int j) {return (root(i) == root(j));}

	int size(int i) {return sz[root(i)];}

	bool unite(int i, int j) {
		if (is_united(i, j)) return false;
		if (size(i) < size(j)) std::swap(i, j);
		i = root(i); j = root(j);
		parent[j] = i; sz[i] += sz[j]; M--;
		return false;
	}
};

int main() {
	int n, m;
	std::cin >> n >> m;
	union_find uf(n);
	while (m--) {
		int a, b;
		std::cin >> a >> b;
		uf.unite(a - 1, b - 1);
	}
 
	int ans = 0;
	for (int i = 0; i < n; i++) ans = std::max(ans, uf.size(i));
	std::cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 4816
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
pre =0
for i in a:
    ans+=b[i-1]
    if pre == i-1 and i!=1:
        ans+=c[i-2]
    pre=i
print(ans)



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

//Potential付きUnionFind木
struct Potentialized_UnionFind
{
    vector<int> par; //par[i]:= iの親の番号
    vector<int> siz; //siz[i]:= iの属する連結成分の大きさ
    vector<int> diff_weight; //diff_weight:= iと根ノードとの距離
    Potentialized_UnionFind(int N) {
        par.resize(N);
        for(int i = 0; i < N; ++i) {
            par[i] = i;
        }
        siz.resize(N,1);
        diff_weight.resize(N,0);
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]]; //走査中に累積和をとることで重みを更新する
            return par[x] = r;
        }
    }

    int weight(int x) {
        root(x);
        return diff_weight[x];
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        return root(x) == root(y);
    }

    bool unite(int x, int y, int w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y), w = -w;
        siz[x] += siz[y];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    int diff(int x, int y) {
        return weight(y) - weight(x);
    }

    int size(int x) { // xの属する木の大きさを得る
        return siz[root(x)];
    }
};

int main()
{
int N, M;
cin >> N >> M;
Potentialized_UnionFind uf(N);
for (int i = 0; i < M; ++i) {
    int l, r, d;
    cin >> l >> r >> d;
    --l, --r;
    if (uf.same(l, r)) {
        int diff = uf.diff(l, r);
        if (diff != d) {
            cout << "No" << endl;
            return 0;
        }
    }
    else {
        uf.unite(l, r, d);
    }
}
cout << "Yes" << endl;
return 0;
}

Measured memory_bytes: 1408
import           Control.Monad
import qualified Data.ByteString     as B
import           Data.Char
import           Data.List
import qualified Data.Set            as S
import qualified Data.Vector.Unboxed as VU

readInt :: IO [Int]
readInt = map read . words <$> getLine

readIntlines :: Int -> IO [[Int]]
readIntlines n = map (map read . words) <$> replicateM n getLine

main :: IO ()
main = do
    [n] <- readInt
    putStrLn . reverse $ solve n

solve :: Int -> String
solve n
  | n > 0 = let m = if (n `mod` 26) > 0 then n `mod` 26 else 26
             in chr (m + 96) : solve ((n - m) `div` 26)
  | otherwise = []


Measured memory_bytes: 3888
#include"bits/stdc++.h"
//#include<bits/stdc++.h>
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
const int mod = 100000003;

int main() {
	ll n, m;
	ll a, b;
	ll count = 0;
	multimap<int, int>mp;
	cin >> n >> m;
	rep(i, 0, n) {
		cin >> a >> b;
		mp.insert(make_pair(a, b));
	}
	for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
		count += itr->second;
		if (count >= m) {
			print(itr->first);
			return 0;
		}
	}
}


Measured memory_bytes: 4992
from itertools import permutations
BASE = 12*3600
def convert(v):
    return "%02d:%02d:%02d" % (v // 3600, (v // 60) % 60, v % 60)
while 1:
    N = int(input())
    if N == 0:
        break
    R = set()
    L = []
    for i in range(N):
        ts = set()
        *E, = map(int, input().split())
        for a, b, c in permutations(E, r=3):
            for i in range(60):
                h = (a+i) % 60; m = (b+i)%60; s = (c+i) % 60
                if m // 12 == h % 5:
                    v = 3600*(h//5) + 60*m + s
                    ts.add(v)
                    R.add(v)
        L.append(sorted(ts))
    R = sorted(R)
    res = 13*3600; mi = ma = 0
    C = [0]*N
    for r in R:
        s = r
        for i in range(N):
            c = C[i]; ts = L[i]; l = len(ts)
            while c < l and ts[c] < r:
                c += 1
            C[i] = c
            if c == l:
                s = max(s, BASE + ts[0])
            else:
                s = max(s, ts[c])
        if s - r < res:
            res = s - r
            mi = r % BASE; ma = s % BASE
    print("%s %s" % (convert(mi), convert(ma)))


Measured memory_bytes: 5720
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int ans,a[N],x,y,v,n,cc[17],c[N],q,mx[N],dp[N],ff[N];
int i,j,k;
int main(){
	cin>>n;
	for(i=1;i<n;++i){
		cin>>x>>y>>v;
		a[x]^=v;
		a[y]^=v;
	}
	for(i=0;i<n;++i)++cc[a[i]];
	for(i=1;i<=15;++i){
		ans+=cc[i]/2;
		q+=((cc[i]&1)<<i-1);
	}
	for(i=1;i<(1<<15);++i){
		dp[i]=dp[i>>1]+(i&1);
	}
	for(i=1;i<(1<<15);++i)--dp[i];
	for(i=1;i<(1<<15);++i){
		for(j=0;j<15;++j){
			if(((1<<j)&i))ff[i]^=(j+1);
		}
	}
	for(i=1;i<=n;++i){
		if(ff[i])continue;
		for(k=(i-1);k;k=(k-1)&i){
			if(ff[k]==0)dp[i]=min(dp[i],dp[k]+dp[i^k]);
		}
	}cout<<dp[q]+ans;
}

Measured memory_bytes: 8576
#!/usr/bin/env python
# coding: utf-8

# In[40]:


N = int(input())
data = []
for i in range(N):
    tmp = list(map(int, input().split()))
    data.append(tmp)
# print(data)


# In[44]:


import numpy as np


# In[45]:


data = np.array(data)
diff = data[1:] - data[:-1]
diff = diff.tolist()
diff.insert(0, data[0].tolist())
# print(diff)


# In[46]:


flag = True
for idx,item in enumerate(diff):
#     print(idx, item)
    dist = abs(item[1]) + abs(item[2])
    if dist > item[0]:
        flag = False # "No"
    else:
        if (item[0] - dist)%2 != 0:
            flag = False 

if flag:
    print("Yes")
else:
    print("No")


# In[ ]:






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

using namespace std;

int main(){
 int n;
 cin >> n;
 int count = 0;
 for(int i = 0;i < n;i++){
  int l, r;
  cin >> l >> r;
  count += (r - l) + 1;
 }
 cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 999999999

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long int ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

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

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

ll a[2016];
ll b[2016][2016]; // b[i][j] := i回魔法を使い、スライム番号jを得ることができる秒数の最小値

int main() {
    ll N, x; cin >> N >> x;
    rep(i,0,N) cin >> a[i];

    rep(i,0,N) {
        rep(j,0,N) {
            if(i == 0) b[i][j] = a[j];
            else b[i][j] = min(b[i-1][j], a[(j-i+N) % N]);
        }
    }

    ll ans = LONG_MAX;
    rep(i,0,N) {
        ll temp = i * x;
        rep(j,0,N) temp += b[i][j];
        ans = min(ans, temp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 31744
def read():
    N, M = list(map(int, input().strip().split()))
    L = []
    R = []
    for m in range(M):
        l, r = list(map(int, input().strip().split()))
        L.append(l)
        R.append(r)
    return N, M, L, R


def solve(N, M, L, R):
    l_max = max(L)
    r_min = min(R)
    n_cards = r_min - l_max + 1
    return n_cards if n_cards > 0 else 0


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


Measured memory_bytes: 11072
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int len,flag=1;
    cin>>s;
    len=s.size();
    for(int i=0;i<len;i++)
    {
        if(s[i]!=s[len-i-1])
        {
            flag=0;
        }
    }
    int half2=(len-1)/2;
    int half3=(len+3)/2;
    for(int i=0;i<half2;i++)
    {
        if(s[i]!=s[half2-i-1])
        {
            flag=0;
        }
    }
     for(int i=half3-1;i<len;i++)
    {
        if(s[i]!=s[len-i-1])
        {
            flag=0;
        }
    }
    if(flag)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
from collections import Counter as c
n = int(input())
a = list(map(int,input().split()))
a.sort()

count, a_max = 0, a[-1]
li = [True] * (a_max+1)

for i in a:
  if li[i] == "x":
    count -= 1
    li[i] = "y"

  if li[i] == True:
    count += 1
    li[i] = "x"

  j = 2
  while i * j <= a_max:
    li[i*j] = False
    j += 1

print(count)

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

int main(){
    string A;
    cin >> A;
    vector<string> AL;
    AL = {"a","b","c","d","e","f","g","h","i","j"
    ,"k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
    for(int i = 0;i < AL.size();i++){
        if(A == AL.at(i)){
            cout << AL.at(i+1) <<endl;
            break;
        }

    }


}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

unsigned long long int frac(unsigned long long int a){
    if(a > 1) return a * frac(a-1) % 1000000007;
    return 1;
}

int main(){
    unsigned long long int n,m;
    scanf("%llu %llu",&n,&m);
    if(abs((int)n-(int)m) > 1){
        printf("0\n");
        return 0;
    }
    unsigned long long int N = frac(n);
    unsigned long long int M = frac(m);
    unsigned long long int k = (abs((int)n-(int)m) == 0)? 2 : 1;
    int c = (int)((N * M * k) % 1000000007);
    printf("%d\n",c);
}

Measured memory_bytes: 1664
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {

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

        // 入力
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] p = new int[m];
        int[] key = new int[m];
        for(int i = 0; i < m; i++){
            p[i] = sc.nextInt();
            int b = sc.nextInt();
            for(int j = 0; j < b; j++){
                key[i] |= 1<<(sc.nextInt() - 1);
            }
        }
        // 計算
        int result = -1;
        int[] dp = new int[1<<n];
        int INF = (int)1e8;
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for(int i = 0; i < 1<<n; i++){
            for(int j = 0; j < m; j++){
                dp[i | key[j]] = min(dp[i | key[j]],  dp[i] + p[j]);
            }
        }
        if(dp[(1<<n) - 1] != INF){
            result = dp[(1<<n) - 1];
        }

        // 出力
        System.out.println(result);

    }
}


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

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string n;
  cin >> n;
  string s = "0";
  string t = "0" + string(n.size(), '9');
  long long pow10 = 1;
  for (int i = 1; i < n.size(); ++i) {
    pow10 *= 10;
  }
  auto ds = [&](auto n) {
    int sum = 0;
    while (n) {
      sum += n % 10;
      n /= 10;
    }
    return sum;
  };
  int ans = ds(stoll(n));
  for (int i = 0; i < n.size(); ++i) {
    s += n[i];
    t.pop_back();
    ans = max(ans, ds((stoll(s) - 1) * pow10 + stoll(t)));
    pow10 /= 10;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        final int DIV = 1000000007;
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();
        sc.close();

        if(w == 1){
            System.out.println(1);
            return;
        }else if(w == 2){
            System.out.println((int)Math.pow(2, h-1));
            return;
        }

        long[] row = new long[w-1];
        long num = 0;
        out: for(int i=0; i<(int)Math.pow(2, w-1); i++){
            char[] set = String.format("%" + (w-1) + "s", Integer.toString(i, 2)).replace(' ', '0').toCharArray();
            for(int j=0; j<w-2; j++){
                if(set[j] == '1' && set[j+1] == '1') continue out;
            }
            num++;
            for(int j=0; j<w-1; j++){
                if(set[j] == '1') row[j]++;
            }
        }

        long[][] dp = new long[h+1][w];
        // Arrays.fill(dp[0], 1);
        dp[0][0] = 1;

        for(int i=0; i<h; i++){
            dp[i+1][0] = dp[i][0] * (num - row[0]) + dp[i][1] * row[0];
            dp[i+1][w-1] = dp[i][w-1] * (num - row[w-2]) + dp[i][w-2] * row[w-2];
            for(int j=1; j<w-1; j++){
                dp[i+1][j] = dp[i][j] * (num - row[j-1] - row[j])
                            + dp[i][j-1] * row[j-1] + dp[i][j+1] * row[j];
            }
            for(int j=0; j<w; j++){
                dp[i+1][j] %= DIV;
            }
        }

        System.out.println(dp[h][k-1]);
    }
}

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

int main(){
	int n;
  	string s;
  	cin >> n >> s;
  
  	rep(i, s.size()){
      	if(s[i] + n > 90) s[i] = 'A'+(s[i]+n-91);
    	else s[i] = s[i] + n;
    }
  
  	cout << s << endl;
}

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

ll INF = 1e9 + 5;

int main()
{
	ll n; 
	cin>>n;
	
	vector<ll> minimumPointsToJump(n+1, INF);
	vector<ll> heights(n+1, 0);
	minimumPointsToJump[0]=0;
	
	for(int i=0;i<n;i++){
		cin>>heights[i];
		for(int j=i-1;(j>=(i-2)) && (j>=0);j--)
			{
				//cout<<j<<"j ";
				minimumPointsToJump[i] = min(minimumPointsToJump[i], minimumPointsToJump[j] + abs(heights[i]-heights[j]));
			}
	}

	cout<<minimumPointsToJump[n-1]<<"\n";
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var num = ToInt32(ReadLine());
        var arr = Array.ConvertAll(ReadLine().Split(' '), int.Parse);
        var set = new HashSet<int>();
        var dic = new Dictionary<int, int>();
        for (var i = 0; i < num; i++)
            if (dic.ContainsKey(arr[i])) dic[arr[i]]++;
            else dic[arr[i]] = 1;
        var result = 0;
        for (var i = 0; i < num; i++)
        {
            if (!set.Contains(arr[i]))
            {
                var cou = dic[arr[i]];
                if (cou < arr[i]) result += cou;
                else if (cou > arr[i]) result += cou - arr[i];
                set.Add(arr[i]);
            }
        }
        WriteLine(result);
    }
}


Measured memory_bytes: 33700
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _094A
{
    class Program
    {
        static void Main(string[] args)
        {
            int A, B, X;

            string[] str = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
            A = int.Parse(str[0]);  //数値で受け取りたい場合は変換する
            B = int.Parse(str[1]);
            X = int.Parse(str[2]);


            if (X >= A && X <= A + B)
            { Console.Write("YES"); }
            else { Console.Write("NO"); }
        }
    }
}


Measured memory_bytes: 13140
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    a, b, c, d = getList()
    print(max(a* c, a*d, b *c, b*d))

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Measured memory_bytes: 10396
//CODE FESTIVAL 2017 qual C
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main(ll argc, char* argv[]) {
	ll n;
	cin >> n;
	string s;
	cin >> s;
	ll changeStoneNumber = 0;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i]=='.')
		{
			changeStoneNumber++;
		}
	}
	ll answer = changeStoneNumber;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i]=='.')
		{
			changeStoneNumber--;
		}
		else
		{
			changeStoneNumber++;
		}
		answer = min(answer,changeStoneNumber);
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 644
import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int t=1;
//        String T=br.readLine();
//        if(T!=null) t=Integer.parseInt(T);
        while(t-- > 0) {
            int x = Integer.parseInt(br.readLine());
            if(x >= 30) System.out.print("Yes\n");
            else System.out.print("No\n");
        }
    }
}

Measured memory_bytes: 32464
#include<stdio.h>
int main(){
  int n,m,i;
  scanf("%d%d",&n,&m);
  int num[n+1];
  for(i=1;i<=n;i++)
    num[i]=0;
  for(i=0;i<m;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    num[a]++;
    num[b]++;
  }
  for(i=1;i<=n;i++)
    printf("%d\n",num[i]);
  return 0;
}

Measured memory_bytes: 1672
sx, sy, tx, ty = map(int, input().split())
w = tx - sx 
h = ty - sy 
ans = ""
for _ in range(h):
  ans += "U"
for _ in range(w):
  ans += "R"
for _ in range(h):
  ans += "D"
for _ in range(w):
  ans += "L"

ans += "L"
for _ in range(h+1):
  ans += "U"
for _ in range(w+1):
  ans += "R"
ans += "D"
ans += "R"
for _ in range(h+1):
  ans += "D"
for _ in range(w+1):
  ans += "L"
ans += "U"
print(ans)

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

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

ll dp[440][440];

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

  int N;
  cin >> N;
  vector<ll> a(N);

  rep(i, N) cin >> a[i];

  rep(i, N){
    rep(j, N){
      dp[i][j] = INF;
    }
  }

  vector<ll> suma(N+1);
  rep(i, N+1){
    suma[i] = 0;
  }

  rep(i, N){
    suma[i+1] = suma[i] + a[i];
  }

  rep(i, N){
    dp[i][i] = 0;
  }

  for(int dist = 1; dist < N; dist++){
    for(int i = 0; i + dist < N; i++){
      for(int k = i+1; k <= i+dist; k++){
        ll part_sum = suma[i+dist+1] - suma[i];
        chmin(dp[i][i+dist], dp[i][k-1] + dp[k][i+dist] + part_sum);
      }
    }
  }

  cout << dp[0][N-1] << endl;



  return 0;
}


Measured memory_bytes: 1664
from math import ceil


def solve(s):
    n, h, *ab = map(int, s.split())
    max_a = max(ab[::2])
    *b, = filter(lambda x: x > max_a, ab[1::2])
    if sum(b) >= h:
        b = sorted(b)
        ans = 0
        while h > 0:
            h -= b.pop()
            ans += 1
        return ans
    else:
        return len(b) + ceil((h - sum(b)) / max_a)


n, m = map(int, input().split())
print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 27308
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vvin=vector<vin>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vst=vector<string>;
using P = pair<ll,ll>;
const int inf=1e9+7;
const ll INF=9e18;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int n,m;
bool check( vin &a){
 bool ans=true;
  int q=-1;
  rep(i,0,n){
   int x=a[i];
    int cnt=0;
    while(x%2==0){
     cnt++;
      x/=2;
    }
    if(q==-1)q=cnt;
    else{
     if(q!=cnt)ans=0; 
    }
  }
  return ans;
}

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

int main(){cout<<fixed<<setprecision(20);
           /*
           b[i]=a[i]/2;
           X=2*b[i](p+1/2)
           X=b[i]*(2p+1)
           (2p+1)==1以上の奇数
           Xはb[i]の公倍数かつ　2の素因数の数は全てのb[i]に等しい
           b[i]の2の素因数が全て等しいことが必要
           */
           cin>>n>>m;
           vin a(n);
           rep(i,0,n){
            cin>>a[i];
             a[i]/=2;
           }
           if(!check(a)){
             cout<<0<<endl;
             return 0;
           }
           ll l=1;
           rep(i,0,n){
             l=lcm(l,a[i]);
             if(l>m){
              cout<<0<<endl;
               return 0;
             }
           }
           ll ans=0;
           ans++;
           ans+=(m-l)/(2*l);
           cout<<ans<<endl;
}

Measured memory_bytes: 3756
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]



Q = int(input())

slis = primes(10 ** 5)
sdic = {}

for i in slis:
    sdic[i] = 1

#print (len(sdic))

"""
for i in range(10 ** 5 - 2):

    i += 3

    flag = True

    for j in sdic:
        if i % j == 0:
            flag = False

    if flag:
        sdic[i] = 1


#print (sdic)
"""

adic = {}
adic[-1] = 0
for j in range(10 ** 5 // 2):

    now = 1 + j * 2

    if now in sdic and (now + 1) // 2 in sdic:
        adic[now] = adic[now-2] + 1

    else:
        adic[now] = adic[now-2]

for i in range(Q):

    l,r = map(int,input().split())

    print (adic[r] - adic[l-2])

    


Measured memory_bytes: 11344
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

int ans[500005];

int main()
{ios_base::sync_with_stdio(false);
string s;
cin>>s;
int n=s.length();

int ptr=0;

while(1)
{
	if(ptr>=n)break;
	int st=ptr,c[2]={0};
	while(s[ptr]=='R')c[ptr%2]++,ptr++;
	int mid=ptr;
	while(s[ptr]=='L')c[ptr%2]++,ptr++;
	ans[mid]=c[mid%2];
	ans[mid-1]=c[1-mid%2];
}

rep(i,0,n-1)
{
	ol(ans[i]);os;
}
return 0;
}



Measured memory_bytes: 1104
#include<bits/stdc++.h>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#define endl  "\n"
#define ll long long
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cin.exceptions(cin.failbit);cout.tie(NULL);
using namespace std;
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i += 6)
    {
        if ((n % i == 0) || (n % (i + 2) == 0))
            return false;
    }
    return true;
}
int32_t main()
{
	int x;
	cin >> x;
	int temp=100;
	int cnt=0;
	while(temp<x)
	{
		temp+=temp/100;
		cnt++;
	}
	cout << cnt;
}


Measured memory_bytes: 3632
#include<stdio.h>
#include<math.h>

int Prime_check(int x){
 int i;

 if(x==2)return 1;

 for(i=2;i<=sqrt(x);i++)
  if(x%i == 0)return 0;

return 1;
}

int main(){
 int n,i;
 int x;
 int cnt=0;

 scanf("%d",&n);
 for(i=0;i<n;i++){
  scanf("%d",&x);
  if(Prime_check(x))cnt++;
 }

 printf("%d\n",cnt);

return 0;
}


Measured memory_bytes: 2040
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define pd(a,n) for(int i=0;i<n;i++)cout<<a[i]<<((i==n-1)?"\n":" ")
#define pdd(a,n,m)for(int i=0;i<m;i++)pd(a,m)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>

int n;
int x[10],y[10];
vector<int>p;

int main(){
  cin>>n;
  rep(i,n)cin>>x[i]>>y[i];
  rep(i,n)p.pb(i);
  int cnt=0;
  double sum=0.0;

  do{
    rep(i,n-1){
      int a=p[i],b=p[i+1];
      sum+=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
    }
    cnt++;
  }while(next_permutation(p.begin(),p.end()));
  printf("%.10lf\n",sum/cnt);
  return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

const int MX_N = 2e4+5;
const int MX_NA = 4e6+5;

int N, A[MX_N];
bitset<MX_NA> dp;

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

    cin >> N;
    int S = 0;
    FOR(i,1,N) { cin >> A[i]; S += A[i]; }

    S = (S+1)/2;
    dp.reset(); dp[0] = 1;
    FOR(i,1,N) {
        dp |= dp << A[i];
    }
    FOR(i,S,MX_NA-1) if (dp[i]) { cout << i; return 0; }
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main() {
     vector<int> D(5);
     for(int i = 0;i < 5;i++){
          cin >> D[i];
     }
     int ans = 0;
     int x = 10;
     for(int i = 0;i < 5;i++){
          if(D[i] % 10 == 0){
               ans += D[i];
          }else{
               x = min(x,D[i] % 10);
               ans += ((D[i] / 10) + 1)*10;
          }
     }

     cout << ans + x - 10 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
#define MOD 1000000007
using ll = long long;
using namespace std;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin>>n;
map<string,int> ban;
string ans="Yes";
string w_now,w_old;
rep(i,n){
    cin>>w_now;
    int tail=w_old.size()-1;
    if(i>0){
        if(w_old[tail]!=w_now[0]||ban.count(w_now)){
            ans="No";
            break;
        }
    }
    ban[w_now]++;
    w_old=w_now;
}
cout<<ans<<endl;
//system("pause");
return 0;
}

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

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

    int count_odd[100000] = {};
    int count_even[100000] = {};
    for (int i = 0; i < n; i++){
        int v;
        cin >> v;
        if (i % 2 == 0){
            count_odd[v]++;
        }else{
            count_even[v]++;
        }
    }

    int max_odd = 0;
    int max_odd_index = 0;
    int max_odd_second = 0;
    int max_odd_index_second = 0;

    int max_even = 0;
    int max_even_index = 0;
    int max_even_second = 0;
    int max_even_index_second = 0;

    for (int i = 0; i < 100000; i++){
        if (count_odd[i] > max_odd_second){
            if (count_odd[i] > max_odd){
                max_odd_second = max_odd;
                max_odd_index_second = max_odd_index;

                max_odd = count_odd[i];
                max_odd_index = i;
            }else{
                max_odd_second = count_odd[i];
                max_odd_index_second = i;
            }
        }

        if (count_even[i] > max_even_second){
            if (count_even[i] > max_even){
                max_even_second = max_even;
                max_even_index_second = max_even_index;

                max_even = count_even[i];
                max_even_index = i;
            }else{
                max_even_second = count_even[i];
                max_even_index_second = i;
            }
        }
    }

    int ans;

    if (max_odd_index != max_even_index){
        ans = n - max_odd - max_even;
    }else if(n - max_odd - max_even == 0){
        ans = n / 2;
    }else{
        if ((n - max_odd - max_even_second) > (n - max_odd_second - max_even)){
            ans = n - max_odd_second - max_even;
        }else{
            ans = n - max_odd - max_even_second;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1152