akhauriyash/Code-Regression huggingface dataset:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *p = map(int, read().split())
ans = 0
l = list(range(n))
r = list(range(n))
memo = [-1] * (n + 1)
for i, pp in enumerate(p):
    memo[pp] = i
for i, idx in enumerate(memo[1:], 1):
    l1 = idx - 1
    r1 = idx + 1
    while l1 >= 0 and l1 != l[l1]:
        l1 = l[l1]
    while r1 < n and r1 != r[r1]:
        r1 = r[r1]
    l[idx] = l1
    r[idx] = r1
    if l1 != -1:
        l2 = l1 - 1
        while l2 >= 0 and l2 != l[l2]:
            l2 = l[l2]
        ans += (l1 - l2) * (r1 - idx) * i
    if r1 != n:
        r2 = r1 + 1
        while r2 < n and r2 != r[r2]:
            r2 = r[r2]
        ans += (r2 - r1) * (idx - l1) * i
print(ans)


Measured memory_bytes: 73764
#16D8101012J 伊藤惇　dj Python3

def Insertion_Sort(N,A,flag=0):
    for i in range(0,N):
        v=A[i]
        j=i-1
        while j>=0 and A[j]>v:
            A[j+1]=A[j]
            j=j-1
        A[j+1]=v
        if flag==1:
            print(A[0],end="")
            for i in range(1,N):
                print(" {}".format(A[i]),end="")
            print('\n',end="")
    return A    


if __name__ == "__main__":
    N=int(input())
    A=list(map(int,input().split()))
    Insertion_Sort(N,A,1)


"""
(py361) [16D8101012J@ise72c ~]$ python ALDS1_1_A.py
10
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
9 10 8 7 6 5 4 3 2 1
8 9 10 7 6 5 4 3 2 1
7 8 9 10 6 5 4 3 2 1
6 7 8 9 10 5 4 3 2 1
5 6 7 8 9 10 4 3 2 1
4 5 6 7 8 9 10 3 2 1
3 4 5 6 7 8 9 10 2 1
2 3 4 5 6 7 8 9 10 1
1 2 3 4 5 6 7 8 9 10
"""



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

#define LOCAL 0

#define lli long long int
#define llu unsigned long long int
#define ld long double
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define si(n) scanf("%d",&n)
#define slli(n) scanf("%lld",&n);
#define ss(n) scanf("%s",n);

const long double EPS = 1e-10;
const lli MOD = 1000000007ll;
const lli mod1 = 1000000009ll;
const lli mod2 = 1100000009ll;
int INF = (int)1e9;
lli INFINF = 5e18;
int debug = 0;
long double PI = acos(-1.0);

using namespace std;

lli bit_count(lli _x){lli _ret=0;while(_x){if(_x%2==1)_ret++;_x/=2;}return _ret;}
lli bit(lli _mask,lli _i){return (_mask&(1<<_i))==0?0:1;}
lli powermod(lli _a,lli _b,lli _m=MOD){lli _r=1;while(_b){if(_b%2==1)_r=(_r*_a)%_m;_b/=2;_a=(_a*_a)%_m;}return _r;}
lli add(lli a,lli b,lli m=MOD){lli x=a+b;while(x>=m)x-=m;while(x<0)x+=m;return x;}
lli sub(lli a,lli b,lli m=MOD){lli x=a-b;while(x<0)x+=m;while(x>=m)x-=m;return x;}
lli mul(lli a,lli b,lli m=MOD){lli x=a*1ll*b;x%=m;if(x<0)x+=m;return x;}

lli Xs,Ys,Xt,Yt;
lli N;
lli X[1010],Y[1010],R[1010];
ld dist[1010][1010];
ld dp[1010];

ld solve(int i,int j){
    return sqrt((Y[i]-Y[j])*(Y[i]-Y[j]) + (X[i]-X[j])*(X[i]-X[j]));
}

ld shpth(int source,int sink){
    for(int i=1;i<=N+2;i++)
        dp[i] = INFINF;
    dp[source] = 0;
    set<pair<ld,int> > Q;
    Q.insert({0,source});
    while(!Q.empty()){
        pair<ld,int> it = *Q.begin();
        Q.erase(it);
        int u = it.S;
        for(int i=1;i<=N+2;i++){
            if(dp[i] > dp[u] + dist[u][i]){
                dp[i] = dp[u] + dist[u][i];
                Q.insert({dp[i],i});
            }
        }
    }
    return dp[sink];
}

int main()
{
if(LOCAL){
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    debug = 1;
}
    srand (time(NULL));

    cout<<fixed<<setprecision(15);
    cin>>Xs>>Ys>>Xt>>Yt;
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>X[i]>>Y[i]>>R[i];
    }
    X[N+1] = Xs;
    Y[N+1] = Ys;
    X[N+2] = Xt;
    Y[N+2] = Yt;
    for(int i=1;i<=N+2;i++)
        for(int j=1;j<=N+2;j++)
            dist[i][j] = max((ld)0,solve(i,j)-R[i]-R[j]);

    cout<<shpth(N+1,N+2);

    return 0;
}


Measured memory_bytes: 35712
using System;
using System.Linq;

namespace _5_A
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
                if (x[0] == 0 && x[1] == 0)
                {
                    break;
                }
                int a = x[0];
                int b = x[1];
                for(int a1=1;a1<=a; a1++)
                {
                    for(int b1 = 1; b1 <= b; b1++)
                    {
                        Console.Write("#");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
        }
    }
}

Measured memory_bytes: 9236
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;


static vector<int> IntArray(int l)
{
    vector<int> result(l);
    for (int i(0); i < l; i++)
    {
        cin >> result[i];
    }
    return std::move(result);
}

static vector<vector<int>> IntMatrix(int h, int w)
{
    vector<vector<int>> result(h);
    for (int i(0); i < h; i++)
    {
        result[i] = vector<int>(w);
        for (int j(0); j < w; j++)
        {
            cin >> result[i][j];
        }
    }
    return std::move(result);
}

int main()
{
    auto tmp = IntArray(2);
    int a, b;
    a = tmp[0];
    b = tmp[1];
    int x = a + b;
    int y = a - b;
    int z = a * b;
    int ans;
    if (max(x, y) > max(y, z))
    {
        ans = max(x, y);
    }
    else
    {
        ans = max(y, z);
    }
    cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)

using namespace std;

inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int main(){
	
	int n=read();
	int now=0; int Max=0;
	FOR(i,1,n){
		char c; cin>>c;
		if(c=='I') now++;
		else	   now--;
		Max=max(Max,now);
	}
	
	cout<<Max;

	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int main(){
	int N;
	long long x,y;
	unsigned long long X=0;
	scanf("%d",&N);
	while(N--){
		scanf("%lld%lld",&x,&y);
		for(int i=0;i<63;i++)if(y<=1ll<<i&&((1ull<<i)-y&x)==(1ull<<i)-y)X^=1ull<<i;
	}
	if(X>>62&1)X^=1ull<<63;
	printf("%lld\n",(long long)X);
}

Measured memory_bytes: 128
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <sstream>
#include <stdio.h>
#include<cstdio>

#include<string>
#include<cmath>
#include<map>
//#include<cstdlib>
#include<deque>
#include<queue>
#include<climits>
#include<cstring>
using namespace std;

const int N_MAX = 1000000;

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

  // table
  int** table = new int*[N];
  for(int i=0; i<N; i++){
    table[i] = new int[N];
    memset(&table[i][0], 0, N*sizeof(table[i][0]));
    // &table[i][0] can be table[i] because it only needs head address.
    
    //[..., [int, int,int], ...]
    // memset(start_addr, 0, delta_arr) fills
    // start_addr to (start_addr + delta_arr) by 0.
    // table[i] refers to the first addr of table[i],
    // for each integer to be filled by 0, size of the element
    // (not table[i]) should be given.
  }
  
  for(int i=0; i<N; i++){
    int row_num, k;
    cin >> row_num >> k;

    row_num--;
    
    for(int j=0; j<k; j++){
      int col_num;
      cin >> col_num;
      col_num--;
      table[row_num][col_num] = 1;
    }
  }

  //print table
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      cout << table[i][j];
      if(j!=N-1) cout << " ";
      else cout << endl;
    }
  }
  
  for(int i=0; i<N; i++){
    delete[] table[i];
  }
  delete[] table;
  
  return 0;
}



Measured memory_bytes: 3144
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <string>
#include <cmath>
#include <iomanip>
#include <cstdio>
using namespace std;

typedef long long ll;

string s;
char sta[100005];

int main(){
	cin>>s;
	//int len = strlen(s);
	int top = 0;
	sta[top] = '2';
	
	int ans = 0;
	for(int i=0;i<s.size();i++){
		if(s[i]!=sta[top]&&top!=0){
			ans+=2;
			top--;
			continue;
		}
		sta[++top] = s[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        int N;
        long[] A;
        long sum = 0, ans = 0;
        Map<Long, Long> sumMap = new HashMap<>();

        void solve(InputReader in, PrintWriter out) {
            N = in.nextInt();
            A = in.nextLongArray(N);

            for (int i = 0; i < N; ++i) {
                sum += A[i];
                sumMap.put(sum, sumMap.containsKey(sum) ? sumMap.get(sum) + 1 : 1);
            }

            for (Map.Entry<Long, Long> m : sumMap.entrySet()) {
                long k = m.getKey(), v = m.getValue();
                if (k == 0) {
                    ans += (v + 1)*v/2;
                } else {
                    ans += v*(v - 1)/2;
                }
            }

            out.println(ans);
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        int[] nextIntArray(int n) {
        	int[] arr = new int[n];
        	for (int i = 0; i < n; ++i) {
        		arr[i] = nextInt();
        	}
        	return arr;
        }

        long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = nextLong();
            }
            return arr;
        }
    }
}


Measured memory_bytes: 51472
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) v.begin(), v.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main() 
{
  int a; cin >> a;
  if(a < 1200)cout << "ABC" << endl;
  else cout << "ARC" << endl;
  system("pause");
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define PB push_back
#define MP make_pair
#define MOD (int)1e8
#define maxn (int)2e5+1
#define inf (int) 1e17
#define int long long
#define ll long long
#define vi vector<int> 
#define pii pair<int, int>
#define mii map<int, int> 
#define print(stuff) cout << stuff << endl
#define len(stuff) stuff.size()

signed main() {	
	start_routine;
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	if (abs(a - c) <= d) {
		print("Yes");
	}
	else if (abs(a - b) <= d && abs(b - c) <= d) {
		print("Yes");
	}
	else {
		print("No");
	}
	end_routine;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unistd.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
double Pi = 3.1415926535897932384626;
 
vector<ll> G[550010];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
ll mod = 998244353;
 
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 

ll fact[800005],rfact[800005];
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=800000; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[800000] = rui(fact[800000],mod - 2);
    for(ll i=800000; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}

 
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k,ans;
ll x[500005],y[500005],z[500005];

char s[500005];

int main(){
    cin >> n;
    ans = INF;
    for(ll i=1;i*i<=n;i++){
        if(n % i == 0){
            a = i;
            b = n / i;
            ans = min(ans, a + b - 2);
        }
    }
    p(ans);
    return 0;
}











Measured memory_bytes: 15360
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define lin puts("");
ll n,x,y,a[300000],b[300000],c=0,t=0,sum=0,z=0,i=0,j,f=0;
char ch[101],cr,ss[101];
string s;
int gcd(int,int);
int main()
{
    cin>>n>>x;
    rep(i,0,x-1){
    cin>>a[i];
    sum+=a[i];
    }
    if(sum>n)
        cout<<-1<<endl;

    else
        cout<<n-sum<<endl;
    return 0;
}


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

int main(){
    int N, M;
    cin >> N >> M;
    long H[N+1];
    H[0] = 0;
    rep(i, N) cin >> H[i+1];
    int A[M], B[M];
    rep(i, M) cin >> A[i] >> B[i];

    vector<int> G(N+1, 1);
    G[0] = 0;

    rep(i, M){
        if (H[A[i]] >= H[B[i]]){
            G[B[i]] = 0;
        }
        if (H[A[i]] <= H[B[i]]){
            G[A[i]] = 0;
        }
    }

    int ans = 0;

    rep(i, N+1){
        ans += G[i];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5192
import numpy as np
N = int(input())
H = np.array([int(i) for i in input().split(' ')])
length = 0
max_length=0
for i in range(N-1):
    if H[i+1] - H[i] <= 0:
        length +=1
    else:
        length = 0
        if max_length < length:
            max_length = length
    if max_length < length:
        max_length = length
print(max_length)

Measured memory_bytes: 23416
import sys
input = sys.stdin.readline
from math import gcd

MOD = 10**9+7

n,k = map(int,input().split())
res = 0

c = [0]*(k+1)

for i in range(k,1,-1):
    tmp = pow(k//i,n,MOD)
    for j in range(i*2,k+1,i):###
        tmp -= c[j]
    c[i] = tmp%MOD
    res = (res+c[i]*i)%MOD

res = (res+pow(k,n,MOD)-sum(c))%MOD

print(res)







Measured memory_bytes: 11172
from sys import stdin

class Node:
    def __init__(self):
        self.parent = -1
        self.children = [-1, -1]

class Tree:
    def __init__(self, nodes):
        self.nodes = nodes

    def size(self):
        return len(self.nodes)

    def preorder(self, i):
        if i != -1:
            c = self.nodes[i].children
            print(" ", i, sep="", end="")
            self.preorder(c[0])
            self.preorder(c[1])

    def inorder(self, i):
        if i != -1:
            c = self.nodes[i].children
            self.inorder(c[0])
            print(" ", i, sep="", end="")
            self.inorder(c[1])

    def postorder(self, i):
        if i != -1:
            c = self.nodes[i].children
            self.postorder(c[0])
            self.postorder(c[1])
            print(" ", i, sep="", end="")

n = int(stdin.readline().rstrip())
nodes = [Node() for _ in range(n)]
for i in range(n):
    l = [int(x) for x in stdin.readline().rstrip().split()]
    nodes[l[0]].children = l[1:3]
    if l[1] != -1:
        nodes[l[1]].parent = l[0]
    if l[2] != -1:
        nodes[l[2]].parent = l[0]

t = Tree(nodes)

root = [node.parent for node in t.nodes].index(-1)
print("Preorder")
t.preorder(root)
print("\nInorder")
t.inorder(root)
print("\nPostorder")
t.postorder(root)
print()



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

int main()
{
   int n;
   vector<int> r;
   while (scanf("%d",&n) != EOF)
   {
      int count=0;
      for (int a=0; (a<=n && a<10); a++)
      {
	 for (int b=0; (b<=n-a && b<10); b++)
	 {
	    for (int c=0; (c<=n-a-b && c<10); c++)
	    {
	       if (n-a-b-c<10)count++;
	    }
	 }
      }
      r.push_back(count);
   }
   for (int i=0; i<r.size(); i++)
   {
      cout << r[i] << endl;
   }
   return 0;
}

Measured memory_bytes: 0
#define _USE_MATH_DEFINES
//#include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <complex>
#include <deque>
#include <iomanip>
#include <ios>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using ll=long long;
const ll MOD = 1000000007;

vector<ll> pos;
vector<ll> neg;
int zero=0;

void solve(ll N, ll K, std::vector<ll> A){
  REP(i,N){
    if(A[i]>0)pos.push_back(A[i]);
    else if(A[i]<0)neg.push_back(A[i]);
    else zero++;
  }
  if((N-zero>K&&pos.size()>0)||
     (N-zero>K&&pos.size()==0&&K%2==0)||
     (N-zero==K&&neg.size()%2==0)){
    ll result=1;
    ll must_pos=max(K-K/2*2,K-(ll)neg.size()/2*2);
    sort(pos.begin(),pos.end(),greater<ll>());
    sort(neg.begin(),neg.end());
    int pos_index=0,neg_index=0;
    for(;pos_index<must_pos;pos_index++){
      result*=pos[pos_index];
      result%=MOD;
    }
    for(int i=(int)must_pos;i<K;i+=2){
      if((int)pos.size()>=pos_index+2&&(int)neg.size()>=neg_index+2){
	ll pp=pos[pos_index]*pos[pos_index+1];
	ll nn=neg[neg_index]*neg[neg_index+1];
	if(pp>nn){
	  pp%=MOD;
	  result*=pp;
	  result%=MOD;
	  pos_index+=2;
	}else{
	  nn%=MOD;
	  result*=nn;
	  result%=MOD;
	  neg_index+=2;
	}
      }else if((int)pos.size()>=pos_index+2){
	result*=pos[pos_index];
	result%=MOD;
	result*=pos[pos_index+1];
	result%=MOD;
	pos_index+=2;
      }else{
	result*=neg[neg_index];
	result%=MOD;
	result*=neg[neg_index+1];
	result%=MOD;
	neg_index+=2;
      }
    }
    cout<<result<<endl;
  }else if(zero){
    cout<<0<<endl;
  }else{
    ll result=1;
    sort(pos.begin(),pos.end());
    sort(neg.begin(),neg.end(),greater<ll>());
    auto p=pos.begin();
    auto n=neg.begin();
    REP(i,K){
      if((p==pos.end())||
	 (n!=neg.end()&&*p>-(*n))){
	result*=-(*n);
	n++;
	result%=MOD;
      }else{
	result*=*p;
	p++;
	result%=MOD;
      }
    }
    cout<<MOD-result<<endl;
  }
}

int main(){
  ll N;
  (void)scanf("%lld",&N);
  ll K;
  (void)scanf("%lld",&K);
  std::vector<ll> A(N);
  for(int i = 0 ; i < N ; i++){
    (void)scanf("%lld",&A[i]);
  }
  solve(N, K, std::move(A));
  return 0;
}


Measured memory_bytes: 6960
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MX      54
typedef long long int LL;
int a[MX];
int n,p;
LL C[MX][MX];
void getC()
{
int i,j;
	C[1][0] = C[1][1] = 1LL;
	C[0][0] = C[0][1] = 1LL;
	for( i = 1;i <= MX;i++)
	{
		C[i][0] = C[i][i] = 1LL;
	}
	for( i = 2;i <= MX;i++)
	{
		for(j = 1;j < i;j++)
		C[i][j] = C[i - 1][j] + C[i - 1][j - 1] ;
	}
}
int main()
{
    getC();
    cin>>n>>p;
    LL cnt1 = 0,cnt2 = 0;
    for(int i = 1; i <= n;i++){
        scanf("%d",&a[i]);
        if(a[i]%2==0)
            cnt1+= 1;
        else
            cnt2+= 1;
    }
    LL cnt = 1LL<<cnt1;
    LL ans = 0;
            for(int i = p;i<= cnt2;i+=2)
                    ans += C[cnt2][i];
        LL res = ans*cnt;
        printf("%lld\n",cnt*ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2000000;
int n,a[N+1],k,b[N+1];
int main()
{
	cin>>k>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	b[1]=k-a[n]+a[1];
	for(int i=2;i<=n;i++)b[i]=b[i-1]+a[i]-a[i-1];
	//for(int i=1;i<=n;i++)cout<<b[i]<<" ";
	//cout<<endl;
	int sum=0,sum2=0x7fffffff;
	for(int i=1;i<=n;i++)
	{
		//cout<<sum2<<' ';
		sum2=min(b[i]+b[n]-b[i+1],sum2);
	}
//	cout<<endl;
//	cout<<b[n]-b[1]<<endl<<sum2<<endl;
	cout<<min(b[n]-b[1],sum2);
}


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

 int main() {
 int n;
 cin >> n;
 vector<int> d(n);

 for(int i = 0; i < n; i++)

    cin >> d[i];

 int ans = 0;
 for(int i = 0; i < n; i++) {for(int j = i + 1; j < n; j++) {ans += d[i] * d[j];}


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

 }


Measured memory_bytes: 3620
fun main(args : Array<String>) {
    var (X,A,B)= ReadInts()

    if(A>=B){
        println("delicious")
    }else if (A+X>=B){
        println("safe")
    }else{
        println("dangerous")
    }

    

}



fun ReadInts():MutableList<Int>{
    return readLine()!!.split(" ").map{it.toInt()}.toMutableList()
}

fun ReadLongs():MutableList<Long>{
    return readLine()!!.split(" ").map{it.toLong()}.toMutableList()
}
fun ReadDoubles():MutableList<Double>{
    return readLine()!!.split(" ").map{it.toDouble()}.toMutableList()
}
  

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

int main() {
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<int> p(a);
    vector<int> q(b);
    vector<int> r(c);
    for (int m = 0; m < a; ++m) cin >> p[m];
    for (int n = 0; n < b; ++n) cin >> q[n];
    for (int i1 = 0; i1 < c; ++i1) cin >> r[i1];
    sort(p.rbegin(), p.rend());
    sort(q.rbegin(), q.rend());
    sort(r.rbegin(), r.rend());
    vector<int> eat;
    for (int i = 0; i < x; ++i) eat.emplace_back(p[i]);
    for (int j = 0; j < y; ++j) eat.emplace_back(q[j]);
    for (int k = 0; k < c; ++k) eat.emplace_back(r[k]);
    sort(eat.rbegin(), eat.rend());
    ll ans = 0;
    for (int l = 0; l < x + y; ++l) {
        ans += eat[l];
    }
    cout << ans << endl;
}


Measured memory_bytes: 3572
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
ans = False
for i in range(X+1, Y+1):
    if i > max(x) and i <= min(y):
        ans = True
        break

print("War" if ans == False else "No War")

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

int main(){

    int x1, x2, x3, x4;
    int y1, y2, y3, y4;

    cin >> x1 >> y1 >> x2 >> y2;

    int dx, dy;
    dx = x2 - x1;
    dy = y2 - y1;

    x3 = x2 - dy;
    y3 = y2 + dx;
    x4 = x1 - dy;
    y4 = y1 + dx;

    cout << x3 << " " <<  y3 << " " << x4 << " " << y4 << endl;

    return 0;
}


Measured memory_bytes: 256
s = input()
mx=0
cnt=0
for i in range(len(s)):
    if s[i]=='A'or s[i]=='C'or s[i]=='G'or s[i]=='T':
        cnt+=1
    else:
        mx=max(mx,cnt)
        cnt=0
mx=max(mx,cnt)
print(mx)


Measured memory_bytes: 9064
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll          long long
#define pb          push_back
#define eb 			emplace_back
#define mp 			make_pair
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define all(a)      (a).begin(),(a).end()
#define fi          first
#define si          second
#define sz(x)       (ll)x.size()
#define endl        '\n'
#define checkbit(n, b) ((n >> b) & 1)
#define mod        998244353
#define inf        1000000000000000000
#define puts(n)		cout<<n;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define setbits(x) __builtin_popcount(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
ll bpow(ll a,ll b){
	ll res=1;
	while(b!=0){
		if(b%2) res = (res*a)%mod;
		a = (a*a)%mod;
		b/=2;
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,s;
	cin>>n>>s;
	ll a[n];
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	ll dp[n+1][s+1]={};
	ll val = bpow(2,mod-2);
	dp[0][0] = bpow(2,n);
	for(ll i=0;i<n;i++){
		for(ll j=0;j<=s;j++){
			dp[i+1][j] = (dp[i+1][j]+ dp[i][j])%mod;
			if(j+a[i]<=s) dp[i+1][j+a[i]] = (dp[i+1][j+a[i]] + dp[i][j]*val)%mod;
		}
	}
	cout<<dp[n][s];
	
	
	return 0;
}

Measured memory_bytes: 73936
import numpy as np


def solve():
    N, K = map(int, input().split())
    h = np.array(list(map(int, input().split())))
    dp = np.full(N, 10**9, dtype=np.int)
    dp[0] = 0

    for i in range(1, N):
        dp[i:i + K] = np.fmin(
            dp[i:i + K],
            dp[i - 1] + np.abs(h[i:i + K] - h[i - 1])
        )
    return dp[-1]


if __name__ == "__main__":
    print(solve())

Measured memory_bytes: 22924
#!/usr/bin/env python3
# ITP2_9_B: Set Operation - Set Intersection


def intersect(n, m, a, b):
    i, j = 0, 0
    while i < n and j < m:
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            yield a[i]
            i += 1
            j += 1


def run():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = int(input())
    b = [int(j) for j in input().split()]

    for v in intersect(n, m, a, b):
        print(v)


if __name__ == '__main__':
    run()



Measured memory_bytes: 35908
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(60):
  keta=1<<i
  cnt=0
  for j in a:
    if keta & j:
      cnt+=1
  ans+=keta*cnt*(n-cnt)%mod


print(ans%mod)


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

int N, K;

void solve() {
	int a = 1;
	for (int i = 0; i < N; i++) {
		if (a * 2 < a + K) a *= 2;
		else a += K;
	}
	cout << a << endl;
}
int main() {
	cin >> N >> K;
	solve();
	return 0;
}

Measured memory_bytes: 256
using System;

namespace ConsoleApp_ITP1_8_B
{
    class Program
    {
        static void Main(string[] args)
        {

            for(; ; )
            {
                double output = 0;
                string input = Console.ReadLine();

                if (input == "0")
                    break;
                else
                {
                    foreach(var s in input)
                    {
                        output += Int32.Parse(s.ToString());
                    }
                    Console.WriteLine(output);
                }
            }
        }
    }
}



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

#define ll long long int 
#define ull unsigned long long int
#define db double
#define ld long double
#define MOD 1000000007
#define inf (1LL << 62)
#define pi acos(-1.0)
#define si(a) scanf("%lld",&a)
#define sd(n) scanf("%lf", &n)
#define for1(i, stop) for(ll i = 1; i <= stop; i++)
#define for0(i, stop) for(ll i = 0; i < stop; i++)
#define rep1(i, start) for(ll i = start; i >= 1; i--)
#define rep0(i, start) for(ll i = (start-1); i >= 0; i--)
#define loop(i, start, stop, inc) for(ll i = start; i <= stop; i += inc)
#define pb(v,a) v.push_back(a)
#define pll pair <ll, ll>
#define mp make_pair
#define pbp(v,a,i) v.push_back(make_pair(a,i)) 
#define srt(v) sort(v.begin(),v.end())
#define rv(v) reverse(v.begin(),v.end())
#define ms(n, i) memset(n, i, sizeof(n))
#define debug printf("Debug\n");
#define en '\n'



#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);


int main()
{
	_fastio
	ll x,y;
	bool fl=false;
	cin>>x>>y;
	for1(i,x)
	{
		ll lg=(i*2)+((x-i)*4);
		if(lg==y)
			fl=true;
		lg=(i*4)+((x-i)*2);
		if(lg==y)
			fl=true;
	}
	if(fl)
		cout<<"Yes"<<en;
	else
		cout<<"No"<<en;
}

Measured memory_bytes: 3640
import java.util.Scanner;

public class Main{
    public static void main(String[]argc){
        Scanner sc = new Scanner(System.in);
        for(int k=0;;k++){
            int m = sc.nextInt();
            int f = sc.nextInt();
            int r = sc.nextInt();
            if(m==-1&&f==-1&&r==-1) break;
            if(m==-1||f==-1){
                System.out.println("F");
            }else if(m+f>=80){
                System.out.println("A");
            }else if(m+f>=65&&m+f<80){
                System.out.println("B");
            }else if(m+f>=50&&m+f<65){
                System.out.println("C");
            }else if(m+f>=30&&m+f<50&&r>=50){
                System.out.println("C");
            }else if(m+f>=30&&m+f<50&&r<50){
                System.out.println("D");
            }else{
                System.out.println("F");
            }
        }
     }
}



Measured memory_bytes: 26332
#include <bits/stdc++.h>
using namespace std;
int main(){
   int N,ans = 0;
   cin >> N;
   vector<int> vec(N);
for (int i = 0; i < N; i++) {
  cin >> vec.at(i);
}
for (int i = 0; i < N; i++){
    if (vec[i] % 2 == 1 && (i + 1) % 2 == 1){
       ++ans;
    }
}
cout << ans << endl;
return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

int main(){
  
  int n;
  cin>>n;
  vector<string> a(n);
  REP(i,n){
    cin>>a[i];
  }
  bool flag = false;
  REP(i,n){
    REP(j,n){
      if(a[i][j]=='.')continue;
      flag = true;
      break;
    }
    if(flag)break;
  }
  
  if(!flag){
    cout<<-1<<endl;
    return 0;
  }
  
  int col_with_white = 0;
  REP(j,n){
    bool white = false;
    REP(i,n){
      if(a[i][j]=='.'){
        white = true;
        break;
      }
    }
    if(white){
      col_with_white++;
    }
  }
  
  int ans = n+1;
  REP(i,n){//真っ黒にしたい行の選択
    int num = 0;//その行のなかで白いマスの数
    REP(j,n){
      if(a[i][j]=='.'){
        num++;
      }
    }
    REP(k,n){
      if(a[k][i]=='#'){
        break;
      }
      if(k==n-1){
        num++;
      }
    }
    
    ans = min(ans, num);
  }
  
  ans += col_with_white;
  cout<<ans<<endl;
      
  return 0;
}

Measured memory_bytes: 512
function Main(input) {
    var N = parseInt(input[0], 10);
    var SP = input.slice(1);

    var S = [];
    var P = [];

    SP.forEach((value, index) => {
        if (index % 2 === 0) {
            S.push(value);
        } else {
            P.push(parseInt(value, 10));
        }
    });

    var objectList = [];

    for (var i = 0; i < N; i++) {
        objectList.push({
            name: S[i],
            value: P[i],
            index: i + 1
        });
    }

    objectList = objectList.sort((a, b) => {
        if (a.name !== b.name) {
            return a.name > b.name ? 1 : -1;
        } else {
            return b.value - a.value;
        }
    });

    for (v of objectList) {
        console.log(v.index);
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

Measured memory_bytes: 21956
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
  while(true){
    int n,m=0;
    int a,b,e;
    string s1,s2;
    char c,d;
    int i,j,k;
    cin>>n;
    if(!n)break;
    int graph[200][200];
    for(i=0;i<200;i++)
      for(j=0;j<200;j++)
	graph[i][j] = 10000000;
    vector<string> names(200);
    for(i=0;i<n;i++){
      cin>>a>>s1>>c>>b>>d>>e>>s2;
      j=0,k=0;
      for(;j<m;j++)if(names[j]==s1)break;
      if(j==m){
	names[j] = s1;
	m++;
      }
      for(;k<m;k++)if(names[k]==s2)break;
      if(k==m){
	names[k] = s2;
	m++;
      }
      graph[k][j] = e;
      graph[j][k] = -e;
    }
    for(k=0;k<m;k++){
      for(i=0;i<m;i++){
	for(j=0;j<m;j++){
	  if(graph[i][k]+graph[k][j]<graph[i][j])graph[i][j]=graph[i][k]+graph[k][j];
	}
      }
    }
    bool bb = true;
    for(i=0;i<m;i++)
      if(graph[i][i]<0)bb=false;
    if(bb)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
import math

N = int(input())
A = list(map(int, input().split()))

for i in range(N):
	A[i] -= i + 1
	
A.sort()

if N % 2 == 0:
	center = (A[N // 2] + A[N // 2 - 1]) // 2
else:
	center = A[(N - 1) // 2]

ans = 0
	
for i in range(N):
	ans += abs(A[i] - center)
	
print(ans)

Measured memory_bytes: 86612
n, m = map(int, input().split())

a = []
b = []

for i in range(n):
	a.append(list(map(int, input().split())))

for i in range(m):
	b.append(int(input()))

for i in range(n):
	ans = 0
	for j in range(m):
		ans += a[i][j] * b[j]
	print(ans)


Measured memory_bytes: 6016
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int main(void) {
    int a,p;
    cin>>a>>p;

    cout<<(3*a+p)/2<<endl;

    return 0;
}




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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* na, Arg1&& arg1, Args&&... args) {
  const char* c = strchr(na + 1, ',');
  cerr.write(na, c - na) << " : " << arg1 << " , ";
  __f(c + 1, args...);
}
#define SZ(v) (int)v.size()
#define endl "\n"
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) sort(ALL(v)),v.erase(unique(ALL(v)),v.end())
typedef long long LL;
typedef pair <int,int> pii;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 1e9;
const LL INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;

void solve() {
  int n;
  cin >> n;
  int d = n%10;
  if (d == 2 || d == 4 || d == 5 || d == 7 || d == 9)
    cout << "hon" << endl;
  if (d == 0 || d == 1 || d == 6 || d == 8)
    cout << "pon" << endl;
  if (d == 3)
    cout << "bon" << endl;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  int t = 1;
//  cin >> t;
  for (int tc = 1; tc <= t; tc++) solve();
  return 0;
}



Measured memory_bytes: 3608
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
using namespace std;
int a[110],b[110],c[110];
char x[110],y[110];
void ff(char z[110])
{
    int d=strlen(z);
    for(int i=0;i<d/2;i++)
    {
        swap(z[i],z[d-1-i]);
    }

}
int main()
{
   int n;
   scanf("%d",&n);
   while(n--)
   {
       memset(a,0,sizeof(a));
       memset(b,0,sizeof(b));
       memset(c,0,sizeof(c));
       scanf("%s",x);
       scanf("%s",y);
      ff(x),ff(y);
        if(strlen(x)>80||strlen(y)>80)
        {
            printf("overflow\n");
            continue;
        }

     for(int i=0;i<strlen(x);i++)
     {
         a[i]=x[i]-'0';
     }
     for(int i=0;i<strlen(y);i++)
     {
         b[i]=y[i]-'0';
     }
     int d=0,s;
      for(int i=0;i<110;i++)
      {
          s=a[i]+b[i]+d;
         c[i]=s%10;
         d=s/10;
      }
      int p=0;
      for(int i=109;i>=0;i--)
      {
          if(c[i])
          {
              p=i;
              break;
          }
      }
      if(p>=80)
      {
          printf("overflow\n");
          continue;
      }
      
          for(int i=p;i>=0;i--)
          {
              printf("%d",c[i]);
          }
          printf("\n");
      
   }
}

Measured memory_bytes: 3132
from collections import deque, defaultdict
n = int(input())
l = [[] for i in range(n + 1)]
ab = [list(map(int, input().split())) for i in range(n - 1)]
for a, b in ab:
    l[a].append(b)
    l[b].append(a)
que = deque([1])
p = [-1] * (n + 1)
p[1] = -2
ma = max([len(i) for i in l])
d = defaultdict(int)
print(ma)
while que:
    u = que.popleft()
    x = d[(u, p[u])]
    c = 1
    for v in l[u]:
        if p[v] != -1:
            continue
        p[v] = u
        if c == x:
            c += 1
        d[(u, v)] = d[(v, u)] = c
        c += 1
        que.append(v)
for a, b in ab:
    print(d[(a, b)])

Measured memory_bytes: 65764
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    int n, k;
    string s;
    cin >> n >> s >> k;
    --k;
    char x = s[k];
    REP(i,n) {
        if (s[i] != x) {
            s[i] = '*';
        }
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import Counter
N = int(input())
a_list = list(map(int,input().split()))

l = len(set(a_list))

def check():
    counter = Counter(a_list)
    if l == 1:
        if a_list[0] == 0:
            return True
        return False
    if l == 2:
        if counter[0] == N/3:
            return True
        return False
    if l == 3:
        x,y,z = set(a_list)
        if int(bin(x^y^z), 0) == 0 and set(list(counter.values()))==set([N/3]):
            return True
        return False
    return False

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

Measured memory_bytes: 60784
import sys
 
n=int(sys.stdin.readline())
dic={}
#辞書作成
for i in range(n):
    a=int(sys.stdin.readline())
    dic[i+1]={}
    for _ in range(a):
        b=list(map(int,sys.stdin.readline().split()))
        dic[i+1][b[0]]=b[1]
 
#最大人数求める。
max=0
for i in range(2**n):
    out=[0]*n
    a=2**(n-1)
    num=0
    #2進数に変換
    for j in range(n):
        if i>=a:
            out[j]=1
            i-=a
            num+=1
        a=a//2
    #判定
    if num>max:
        ju=1
        for j in range(n):
            if out[j]==1:
                for k in dic[j+1].keys():
                    if dic[j+1][k]==out[k-1]:
                        continue
                    else:
                        ju=0
                        break
                if ju==0:
                    break
        if ju==1:
            max=num
print(max)

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

int main()
{
	int a, b;
	cin >> a >> b;
	float x = stoi(to_string(a) + to_string(b));
	for (int i = 1; i < 317; ++i)
	{
		if (x / i == i)
		{
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

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

ll MOD =1e9+7;

int main(){
    ll n;
    cin>>n;
    
    ll ans,a10=1,a9=1,a8=1;

    if(n==1)ans=0;
    else{
        rep(i,n){
            a10=a10*10%MOD;
            a9=a9*9%MOD;
            a8=a8*8%MOD;
        }
        ans=(a10-a9*2+a8)%MOD;
        if(ans<0)ans+=MOD;
    }
    cout<<ans<<endl;
}

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

#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)

bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された

    if(n%2 == 0) return false;
    if(n%3 == 0) return false;
    // 2と3の倍数でないので6の倍数ではないことが保証された

    if(n%6 != 1 && n%6 != 5) return false;
    // 6の倍数前後の数(素数かもしれない数)であることが保証された

    // 6の倍数前後の数を使って試し割りをする
    for(unsigned i=5;i*i<=n;i+=6){
        if(n%i     == 0) return false; // 6n-1
        if(n%(i+2) == 0) return false; // 6n+1
    }

    return true;
}

int main(){
  int q,a[100010]={},l,r;
  cin >> q;
  
  for(int i=3; i<=100005; i+=2){
    if(is_prime(i) && is_prime((i+1)/2)){
      a[i] = a[i-1]+1;
    }else{
      a[i] = a[i-1];
    }
    a[i+1] = a[i];
  }
  
  /*rep(i,20){
    cout << a[i] << " ";
  }
  cout << endl;*/
  
  rep(i,q){
    cin >> l >> r;
    cout << a[r]-a[l-1] << endl;
  }
}



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

const int MAX_N = 2e5 + 5;
int A, B, C;

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> A >> B >> C;
	cout << min({A + B, A + C, B + C});

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main () {
 int a,b;
 scanf("%d %d", &a, &b);

 if (a %3 == 0) printf("Possible");
 else if (b % 3 == 0)  printf("Possible");
 else if ( (a+b)%3==0)  printf("Possible");
 else printf("Impossible"); 
 return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }
constexpr int INF = 1001001001;
constexpr long long INFL = (1LL<<60);
constexpr double eps = (1e-9);

vector<ll> enum_divisor(ll m) {
  vector<ll> divisors;
  for (ll i = 1; i*i <= m; ++i) {
    if (m % i != 0) continue;
    divisors.push_back(i);
    if (i * i != m) divisors.push_back(m / i);
  }
  return divisors;
}

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

  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> v(1000001, 0);
  rep(i, n) {
    cin >> a[i];
    v[a[i]]++;
  }

  ll ans = 0;
  for (auto& x : a) {
    auto divisors = enum_divisor(x);
    bool flag = true;
    for (auto& y : divisors) {
      if ((y == x && v[y] > 1) || (y != x && v[y] != 0)) {
        flag = false;
        break;
      }
    }
    if (flag) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 7948
#include<iostream>
using namespace std;
int main(){
    int H,W;
    while(1){
        cin>>H>>W;
        if(H==0&&W==0)break;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                cout<<"#";
            }cout<<"\n";
        }cout<<endl;
    }return 0;
}

Measured memory_bytes: 3096
a,b,k = map(int,input().split())
while True:
  if k == 0:
    print(a,b)
    break
  else:
    a,b = a//2,b+a//2
    k -= 1
  if k == 0:
    print(a,b)
    break
  else:
    a,b = a+b//2,b//2
    k -= 1

Measured memory_bytes: 3060
import java.util.Scanner
import scala.collection.Searching._

import scala.annotation.tailrec

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    println(-(sc.nextInt - sc.nextInt * 2))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)

    solve(sc)
  }
}


Measured memory_bytes: 27312
using System;

class Program {
  static void Main() {
    int x = int.Parse(Console.ReadLine());
    int ans = 1;
    for (int b = 2; b * b <= x; b++) {
      for (int p = 2; ; p++) {
        int t = (int)Math.Pow(b, p);
        if (t <= x) ans = Math.Max(ans, t);
        else break;
      }
    }
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 11092
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<unordered_map>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define PI 3.141592653589793

using namespace std;
using ll = unsigned long long;


int main() {

	int x, y;

	cin >> x >> y;

	for (int i = 0; i <= x; i++) {
		 int j=x-i;
		 if (y == i * 2 + j * 4) {
			 cout << "Yes" << endl;
			 return 0;
		 }
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3636