akhauriyash/Code-Regression huggingface dataset:
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy

def j(q):
    if q==1: print("Heisei")
    else:print("TBD")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())


#n = ip()                              #入力整数1つ
#n,k= (int(i) for i in input().split())      #入力整数横2つ
#n,x,y = (int(i) for i in input().split())    #入力整数横3つ
#n,a,b,c= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
n = ip()                      #入力セット(整数改行あり)(1/2)
a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
b = [[-1,-1]]
for i in range(n):
    b.append([i+1,a[i]])
c = 1
count = 0
while b[c][0] != -1:
    b[c][0] = -1
    count +=1
    c = b[c][1]
    if c == 2:
        print(count)
        exit(0)
print(-1)

Measured memory_bytes: 30448
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>
using namespace std;

int main(){

	bool f[11]={};
	int n,k;
	cin>>n>>k;
	for(int i=0;i<k;i++){
		int y;
		cin>>y;
		f[y]=1;
	}
	long long int x=n;
	while(1){
		long long int r=x;
		bool g=0;
		while(r){//cout<<f[r%10]<<endl;
			if(f[r%10]){//cout<"Y";
				g=1;break;
				
			}
			r/=10;
		}
		
		if(!g)break;
		x++;


	}
	cout<<x<<endl;

	return 0;
}



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

int main(){
    long int n, k;
    cin >> n >> k;

    int number;
    vector<long int> v(n, 0);
    for(int i = 0; i < n; i++){
        cin >> v[i];
        if(v[i] == 1){
            number = i;
        }
    }

    int left = number;
    int right = n - number - 1;

    long int ans_l = left / (k - 1);
    long int ans_r = right / (k - 1);
    long int ans = ans_r + ans_l;

    int tmp = left % (k - 1) + right % (k - 1);

    if(tmp == 0){
        //
    }
    else if(tmp <= k-1){
        ans++;
    }
    else {
        ans+=2;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
using namespace std;
#define ll long long
#define pb push_back

int main() {
  int n;
  cin >> n;
  vector<ll> data(n+1,0);

  data.at(0) = 2;
  data.at(1) = 1;

  if(n == 1){
      cout << 1 << endl;
  } else {
    for(int i=2; i<=n; i++){
        data.at(i) = data.at(i-2) + data.at(i-1);
        // cout << data.at(i) << endl;
    }
    cout << data.at(n) << endl;
  }

}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    char[] c = sc.next().toCharArray();
    int n = c.length;
    int r = 0;
    for(int i=0;i<n/2;i++){
      if(c[i] != c[n-1-i]){
        r++;
      }
    }
    System.out.println(r);
  }
}

Measured memory_bytes: 21844
#include <iostream>

using namespace std;

int dp[100];

int main() {
    int n;
    cin >> n;
    fill(dp, dp + 100, -1);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n] << endl;
}

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

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int total = 0;
  for (int i = 1; i <= N; ++i) {
    int sum = findSumOfDigits(i); // i の各桁の和
    if (sum >= A && sum <= B) { //  i の各桁の和が A 以上 B 以下かどうか
      total += i;
    }
  }
  cout << total << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
using ll = long long;
const ll MOD = 1000000007;

int main() {
  ll N, dp[4]{1};
  cin >> N;
  for (int i = 0; i != N; ++i) {
    dp[3] = (dp[1] + dp[2] + dp[3] * 10) % MOD;
    dp[2] = (dp[0] + dp[2] * 9) % MOD;
    dp[1] = (dp[0] + dp[1] * 9) % MOD;
    dp[0] = dp[0] * 8 % MOD;
  }
  cout << dp[3] << endl;
}


Measured memory_bytes: 3596
#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 main()
{ios_base::sync_with_stdio(false);
int n,d,a[105][105];
cin>>n>>d;
rep(i,0,n-1)
{
	rep(j,0,d-1)cin>>a[i][j];
}
int ans=0;
rep(i,0,n-1)
{
	rep(j,i+1,n-1)
	{
		int kk=0;
		rep(k,0,d-1)kk+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
		int k1=sqrt(kk);
		while(1)
		{
			if(k1*k1>=kk)break;
			k1++;
		}
		if(k1*k1==kk)ans++;
	}
}
ol(ans);
return 0;
}



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

typedef long long ll;
const ll mod = 1000*1000*1000+7;
int N, M;
vector<ll> fact;

int main() {
    fact.resize(100002);
    fact[0] = 1;
    for(int i = 1; i < 100002; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
    scanf("%d %d", &N, &M);
    if(N == M) {
        printf("%lld", 2*fact[N]*fact[M]%mod);
        return 0;
    }
    if(abs(N - M) == 1) {
        printf("%lld", fact[N]*fact[M]%mod);
        return 0;
    }
    printf("0");
}


Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {
    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);
        int K = scan.nextInt();
        int A = scan.nextInt();
        int B = scan.nextInt();
        String result = "NG";

        for (int i = A; i <= B; i++) {
            if (i % K == 0) {
                result= "OK";
                break;
            }
        }
        System.out.println(result);
    }
}



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

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

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

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

    string s, t;
    cin >> s >> t;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] != t[i]) {
            cout << "No";
            return 0;
        }
    }

    cout << "Yes";
}

Measured memory_bytes: 3628
lis = list(map(int,input().split()))
cou = 0
lis.sort()
while lis[2] - lis[0] > 1:
    lis[0] +=2
    cou += 1
    lis.sort()
if lis[0] == lis[1] and lis[1] == lis[2]:
    print(cou)
elif lis[1] == lis[2]:
    print(cou + 2)
else:
    print(cou + 1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	ll cnt=0;
	ll now=1;
	while(n!=0){
		n/=2;
		cnt+=now;
		now*=2;
	}
	cout <<cnt;
}

Measured memory_bytes: 3644
nums=[int(n) for n in input()]

n=1
A=[nums[0]]

while n<=3:
    B=[]
    for a in A:
        B+=[a+nums[n],a-nums[n]]
    A=B
    n+=1

ans=str(nums[3])+'=7'
C=B.index(7)

for n in reversed(range(3)):
    if C%2==0:
        ans='+'+ans
    else:
        ans='-'+ans
    ans=str(nums[n])+ans
    C//=2

print(ans)


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

using namespace std;
typedef long long ll;

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

    vector<vector<ll> > adjs(200000);

    for(int i=0;i<N;i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        adjs[x].push_back(y + 100000);
        adjs[y+100000].push_back(x);
    }

    ll ans = 0;

    vector<bool> used(200000, false);
    for(int i = 0; i < 200000; i++){
        if(!used[i] && adjs[i].size() > 0) {
            stack<int> bfs;
            
            bfs.push(i);
            ll nleft = 0;
            ll nright = 0;
            used[i] = true;
            
            while(!bfs.empty()){
                int v = bfs.top();
                bfs.pop();
                if(v < 100000) nleft ++;
                else nright++;

                for(auto w : adjs[v]) {
                    if(!used[w]) {
                        bfs.push(w);
                        used[w] = true;
                    }
                }
            }
            ans += nleft * nright;
        }

    }

    ans -= N;
    cout << ans << endl;
}


Measured memory_bytes: 8576
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353;
constexpr int MAX = 5000000;

int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n; cin >> n;
	vector<vector<int>> vv;
	vector<int> v(n);
	for (int i = 0; i < n; i++) v[i] = i + 1;
	do {
		vv.emplace_back(v);
	} while (next_permutation(v.begin(), v.end()));
	vector<int> p(n); for (int i = 0; i < n; i++) cin >> p[i];
	vector<int> q(n); for (int i = 0; i < n; i++) cin >> q[i];
	int a = lower_bound(vv.begin(), vv.end(), p) - vv.begin();
	int b = lower_bound(vv.begin(), vv.end(), q) - vv.begin();
	cout << abs(a - b) << endl;
	return 0;
}

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

using namespace std;

template<typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T> p) {
    out << "(" << p.first << "," << p.second << ")";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for (auto a: v)
        out << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename S, typename T>
ostream& operator<<(ostream& out, const map<S, T>& M) {
    for (auto m: M)
        cout << "(" << m.first << "->" << m.second << ") ";
    return out;
}

template<typename S, typename T>
pair<S, T> operator+(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

template<typename S, typename T>
pair<S, T> operator-(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long max_val = -5e18;
    max_val = max(max_val, a * c);
    max_val = max(max_val, a * d);
    max_val = max(max_val, b * c);
    max_val = max(max_val, b * d);
    cout << max_val << endl;
    return 0;
}


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

#define debug(x) cerr<<#x<<'='<<x<<'\n'
#define Int const int &

const int seed1=65599;
const int seed2=131;
const int mod1=666666667;
const int mod2=2333;
int b[233];
struct H {
	int hash1;
	int hash2;
	H(int *a=b) {
		hash1=hash2=0;
		for (int i='a'; i<='z'; i++) {
			hash1=(1ll*hash1*seed1+a[i])%mod1;
			hash2=(1ll*hash2*seed2+a[i])%mod2;
		}
	}
};
int first[mod2+6], nxt[4231];
H ha[4231];
int tot;
inline void add(int *a) {
	ha[++tot]=H(a);
	nxt[tot]=first[ha[tot].hash2+1];
	first[ha[tot].hash2+1]=tot;
}
inline bool find(int *a) {
	H tmp=H(a);
	for (int j=first[tmp.hash2+1]; j; j=nxt[j]) {
		if (ha[j].hash1==tmp.hash1) {
			return true;
		}
	}
	return false;
}
inline void init(void) {
	tot=0;
	memset(first, 0, sizeof first);
}

char s1[4231], s2[4231];

int main(void) {
	scanf("%s%s", s1+1, s2+1);
	int l1=strlen(s1+1);
	int l2=strlen(s2+1);
	for (int len=min(l1, l2); len; len--) {
	//	debug(len);
		init();
		memset(b, 0, sizeof b);
		for (int j=1; j<=len; j++) {
			b[s1[j]]++;
		}
		for (int i=1; i+len-1<=l1; i++) {
			add(b);
			b[s1[i]]--;
			b[s1[i+len]]++;
		}
		
		memset(b, 0, sizeof b);
		for (int j=1; j<=len; j++) {
			b[s2[j]]++;
		}
		for (int i=1; i+len-1<=l2; i++) {
			if (find(b)) {
				cout<<len<<'\n';
				return 0;
			}
			b[s2[i]]--;
			b[s2[i+len]]++;
		}
	}
	puts("0");
	return 0;
}

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

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

          
          
			var inputArray = retreiveLongArray();
			var inputCount = 4;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long A = inputArray[0];
			long B = inputArray[1];
			long C = inputArray[2];
			long D = inputArray[3];

			var takahashiAttackCount = C / B;
			if (C % B > 0) {
				takahashiAttackCount++;
			}

			var aokiAttackCount = A / D;
			if (A % D > 0) {
				aokiAttackCount++;
			}


			//答えの出力
			var ans = takahashiAttackCount <= aokiAttackCount ? "Yes":"No";
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}


Measured memory_bytes: 28104
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

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

	string s;
	getline(cin, s);
	for (int i = 0; (int)i < s.size(); i++){
		if ('a' <= s[i] && s[i] <= 'z'){
			s[i] = s[i] - 'a' + 'A';
		}
		else if ('A' <= s[i] && s[i] <= 'Z'){
			s[i] = s[i] - 'A' + 'a';
		}
	}
	cout << s << '\n';

	return 0;
}


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

int main() {
    long a, b, c;
    cin>>a>>b>>c;

    long tmp1 = c-a-b, tmp2 = 4*a, tmp3=b;
    for(long i=2;i<1000000;++i){
        while(tmp1%i==0 & tmp2%(i*i)==0){
            tmp1 /= i;
            tmp2 /= i*i;
        }
        while(tmp1%i==0 & tmp3%(i*i)==0){
            tmp1 /= i;
            tmp3 /= i*i;
        }
    }
    
       
    if (tmp1<=0)cout<<"No"<<endl;
    else if(tmp1*tmp1 > tmp2*tmp3)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    /**
    if((c-a-b)/(4*a*b)*(c-a-b)>1)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    **/
}


Measured memory_bytes: 256
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    std::string s, t;
    std::cin >> s >> t;
    for (usize i=0; i<s.length()+t.length(); i++) {
        std::cout << (i%2 ? t : s).at(i/2);
    }
    std::cout << '\n';
}


Measured memory_bytes: 256
#ABC127-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()
A=IL()
A.sort()
Q=[IL() for i in range(m)]
Q.sort(key=lambda x:-x[1])
j=0
for i in range(n):
    if Q[j][1]<A[i]:
        break
    else:
        Q[j][0]-=1
        A[i]=Q[j][1]
    if Q[j][0]==0:
        j+=1
    if j==m:
        break
print(sum(A))

Measured memory_bytes: 36144
import java.util.Scanner;
class Main{
    public static void main(String[] av){
	Scanner sc=new Scanner(System.in);
	while(true){
	int H=sc.nextInt();
	int W=sc.nextInt();
	if(H==0&&W==0) break;
	for(int i=0;i<H;i++){
	    for(int j=0;j<W;j++){
		System.out.print("#");
	    }
	    System.out.println();
	}
	 System.out.println();
	}
    
    }
}



Measured memory_bytes: 37916
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

vector<int> g[51];
map<P, bool> mp;
vector<bool> vi(51);

void dfs(int a) {
	vi[a] = true;
	for (auto& c : g[a]) {
		if (vi[c]) continue;
		if (mp[P(a, c)]) continue;
		dfs(c);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<P> p(m);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		p[i] = make_pair(a, b);
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	int ans = 0;
	rep(i, m) {
		int a = p[i].first, b = p[i].second;
		rep(i, n) vi[i] = false;
		mp[P(a, b)] = true;
		mp[P(b, a)] = true;
		dfs(0);
		bool elf = false;
		rep(i, n) if (!vi[i]) elf = true;
		if (elf) ans++;
		mp[P(a, b)] = false;
		mp[P(b, a)] = false;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef complex<double> xy_t;
const lint mod = 1e9 + 7;

int main(){
    int n;
    string s;
    cin >> n >> s;
    map<pss, lint> mp;
    string t = s.substr(n, n);
    reverse(t.begin(), t.end());
    rep(i, 1<<n){
        string u = "";
        string v = "";
        rep(j, n){
            if((i>>j) & 1) u += t[j];
            else v += t[j];
        }
        ++mp[pss(u, v)];
    }
    lint ans = 0;
    rep(i, 1<<n){
        string u = "";
        string v = "";
        rep(j, n){
            if((i>>j) & 1) u += s[j];
            else v += s[j];
        }
        ans += mp[pss(u, v)];
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 91904
#include <bits/stdc++.h>
#define bug1(x) cout<<#x<<" = "<<x<<endl
#define bug2(x,y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define bug3(x,y,z) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
#define bug4(x,y,z,m) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<" "<<#m<<" = "<<m<<endl

using namespace std;

class Debugger {
public:
	template<typename T>
	void printVector(vector<T> const &vec, bool printSize=true){
		if(printSize){
			cout << vec.size() << endl;
		}
		for(auto &elem : vec){
			cout << elem << " ";
		}
		cout << endl;
	}

	template<typename T>
	void printMatrix(vector<vector<T>> const &matrix){
		cout << matrix.size()<< " ";
		if(!matrix.empty()){
			cout << matrix[0].size();
		}
		cout << endl; 
		for(auto &vec : matrix){
			printVector(vec, false);
		}
		cout << endl;
	}
};

#define ll long long
const int maxN = 100005;
const ll INF = 1000000000000000000LL;

class TaskB {
private:
	Debugger debugger;

public:
	void solveOne(int it){
		int n;
		cin >> n;
		int ans = 0;
		for(int i = 1; i <= n; i++){
			int x;
			cin >> x;
			if(i % 2 == 1 and x % 2 == 1){
				ans++;
			}
		}
		cout << ans << endl;

	}

	void solve(){
		int tc = 1;
		for(int it = 1; it <= tc; it++){
			solveOne(it);
		}
	}
};


int main(){
	ios_base::sync_with_stdio(false);
	TaskB solver;
	solver.solve();
	return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MOD = (int)1e9 + 7;

int n,m,h[101],hnum[101],dh[101];
long long dp[101][101];

int pow_(long long x,int y) {///快速幂求 x的y次方
    long long ans = 1;
    if(y > 0) {
        while(y) {
            if(y % 2)ans = ans * x % MOD;
            x = x * x % MOD;
            y /= 2;
        }
    }
    return ans;
}

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) {
        scanf("%d",&h[i]);
        dh[++ m] = h[i];
    }
    sort(dh + 1,dh + m + 1);///高度排序
    m = unique(dh + 1,dh + m + 1) - dh - 1;///离散化 m是离散化后的长度
    for(int i = 1;i <= n;i ++) {
        hnum[i] = lower_bound(dh + 1,dh + m + 1,h[i]) - dh;
    }
    dp[0][0]=1;
    for(int i = 1;i <= n;i ++) {
        for(int j = hnum[i] + 1;j <= hnum[i - 1];j ++)
            (dp[i][0] += dp[i - 1][j] * 2 % MOD) %= MOD;

        (dp[i][0] += dp[i - 1][0] * 2 % MOD) %= MOD;///交叉或者不交叉

        int d = pow_(2,h[i] - h[i - 1]);
        for(int j = 1;j <= min(hnum[i - 1],hnum[i]);j ++) {
            dp[i][j] = dp[i - 1][j] * d % MOD;
        }
        for(int j = hnum[i - 1] + 1;j <= hnum[i];j ++) {///比前一列高出的部分
            if(j > 1)(dp[i][j] += dp[i - 1][0] * (pow_(2,dh[j] - dh[j - 1]) - 1) % MOD * 2 % MOD * pow_(2,h[i] - dh[j]) % MOD) %= MOD;
            else (dp[i][1] += dp[i - 1][0] * (pow_(2,dh[1]) - 2) % MOD * pow_(2,h[i] - dh[1]) % MOD) %= MOD;///上一列中无重复相同的乘上化不超过上一列高度中有重复的
        }
    }
    long long ans = 0;
    for(int i = 0;i <= hnum[n];i++)
        (ans += dp[n][i]) %= MOD;
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

int main(){

    int s;

    cin >> s;

    int x,y;

    x = (s - s%100)/100;
    y = s%100;

    int YYMM = 0;
    int MMYY = 0;

    if(x >= 0 && y <=12 && y >= 1){
        YYMM++;
    }
    if(y >= 0 && x <=12 && x >= 1){
        MMYY++;
    }

    if(YYMM == 1 && MMYY == 1){
        cout << "AMBIGUOUS" << endl;
    } else if(YYMM == 0 && MMYY == 1){
        cout << "MMYY" << endl;
    } else if(YYMM == 1 && MMYY == 0){
        cout << "YYMM" << endl;
    } else {
        cout << "NA"<< endl;
    }

}

Measured memory_bytes: 3560
#include <stdio.h>

int main(void)
{
  int s1;
  int s2;
  int s3;
  
  scanf("%d", &s1, &s2, &s3);
  
  printf("%d\n", s1%10 + (s1/10)%10 + (s1/100)%10);
  
  return (0);
}

Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
//#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M  1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000
#define N 200005
#define vi vector<int>
#define all(v) v.begin(),v.end()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int dp[N][13];
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   string s;
   cin>>s;
   dp[0][0]=1;
   int n=s.length();
   for(int i=0;i<n;i++)
   {   int c;
       if(s[i]=='?')c=-1;
       else
        c=s[i]-'0';
       for(int j=0;j<10;j++)
       {
           if(c!=-1 && c!=j)continue;
           for(int k=0;k<13;k++)
           {
               dp[i+1][(k*10 + j)%13]+=dp[i][k];

           }
       }
       for(int j=0;j<13;j++)dp[i+1][j]%=M;
   }
   cout<<(dp[n][5] + M)%M<<endl;
}



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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    Int(n);
    int2(a, b);

    if (b < a) {
        cout << 0 << endl;
        return 0;
    }

    if (n == 1 && a == b) {
        cout << 1 << endl;
        return 0;
    } else if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    cout << (b - a) * (n - 2) + 1<< endl;


    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
string S, T; 
cin >> S >> T; 
string ans = "No"; 
string U; 
for (int k = 0; k < S.size(); k++){
U += 'x'; 
}
for (int k = 1; k <= S.size(); k++){
 U.at(0) = S.at(1); 
for (int i = 1; i < S.size()-1; i++){
 U.at(i) = S.at(i+1); 
}
 U.at(S.size()-1) = S.at(0); 
 S = U; 
 if(S == T){ans = "Yes"; 
break; 
}
}
 cout << ans << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define lP pair<ll, ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;

int N, K, sushi[100001], P;
iP p[100000];
ll s, res, cnt;

int main() {
	cin >> N >> K;
	for (int i = 0; i != N; ++i)
		cin >> p[i].second >> p[i].first;
	sort(p, p + N, greater<>());
	for (int i = 0; i != K; ++i) {
		s += p[i].first;
		++sushi[p[i].second];
		if (sushi[p[i].second] == 1)
			++cnt;
	}
	res = s + cnt*cnt;
	P = K - 1;
	for (int i = K; i != N; ++i) {
		if (!sushi[p[i].second]) {
			for (; P >= 0; --P) {
				if (sushi[p[P].second] > 1) {
					--sushi[p[P].second];
					++sushi[p[i].second];
					s -= p[P].first;
					s += p[i].first;
					++cnt;
					res = max(res, s + cnt*cnt);
					--P;
					break;
				}
			}
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    int n;
    cin >> n;

    vector <int> A(n);
    int mx = 0, snd_mx = 0;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        if (A[i] > mx) {
            snd_mx = mx;
            mx = A[i];
        } else if (A[i] > snd_mx) {
            snd_mx = A[i];
        }
    }

    for (int i = 0; i < n; i++) {
        if (A[i] == mx) {
            cout << snd_mx << "\n";
        } else {
            cout << mx << '\n';
        }
    }

    return 0;
}

Measured memory_bytes: 2432
import java.util.*;
import java.io.*;

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };

	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		String s = fs.next();
		int len = s.length();
		String ans = "";
		String fir = "First", sec = "Second";
		if(s.charAt(0)==s.charAt(len-1)) {
			//終わる時は、奇数個
			if(len%2==0) {
				ans = fir;
			}
			else {
				ans = sec;
			}
		}
		else {
			if(len%2==0) {
				ans = sec;
			}
			else {
				ans = fir;
			}
		}
		System.out.println(ans);
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

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

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

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

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

	public double nextDouble() {
		return Double.parseDouble(next());
	}

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

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

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 100005;

int N, M;
vector<int> Edge[MAX_N];

int D[MAX_N];

bool flag = false;
void solve(int pos, int d = 1) {
  if(D[pos] != 0) {
    if(D[pos] != d) {
      flag = true;
    }
    return;
  }

  D[pos] = d;
  int nextD = (d == 1 ? 2 : 1);
  for(int next : Edge[pos]) {
    solve(next, nextD);
  }
}

signed main()
{
  cin >> N >> M;
  REP(i,M) {
    int a,b; cin>>a>>b; a--; b--;
    Edge[a].push_back(b);
    Edge[b].push_back(a);
  }

  solve(0);

  if(flag) {
    cout << N*(N-1)/2 - M << endl;
    return 0;
  }

  int a = 0, b = 0;
  REP(i,N) {
    if(D[i] == 1) {
      a++;
    } else{
      b++;
    }
  }

  int ans = 0;
  int A = 0;
  REP(i,N) {
    for(int next : Edge[i]) {
      if(D[i] != D[next]) {
        ans++;
      }
    }
  }

  // cerr << a << " " << b << " " << ans << endl;
  cout << a*b - ans/2 << endl;

  return 0;
}

Measured memory_bytes: 7552
#include <iostream>
#include <vector>
using namespace std;
int main(void){
        int N;
        cin >> N;
        vector<int> A(N);
        int count=0;
        for (int i = 0; i < N; i++) cin >> A.at(i);
        int flag = 1;
        while(flag){
                for (int i = 0; i < N; i++){
                        if(A.at(i)%2) flag = 0;
                        A.at(i) = A.at(i)/2;
                }
        if(flag) ++count;

        }
        cout << count << endl;
        return 0;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int, input().split()))
h = h[::-1]
f = True
for i in range(n-1):
    if h[i] < h[i+1]:
        h[i+1] -= 1
    if h[i] < h[i+1]:
        f = False
        break
if f: print('Yes')
else: print('No')

Measured memory_bytes: 15020
#include<iostream>
#include<stdio.h>
#include<fstream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<map>
#include<iomanip>
#include<cassert>
#include<complex>
#include<functional>
#include<list>
#include<cmath>
#include<stack>
#include<assert.h>
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define F first
#define S second
using namespace std;
LL n,a,b;
int main(){
  cin>>n>>a>>b;
  LL x=max(a,b);
  LL y=min(a,b);
  if((x-y)%2==0){
  	cout<<(x-y)/2<<"\n";
  }
  else{
  	cout<<min((x-1+y)/2,(n-x+n-y+1)/2)<<"\n";
  }
  return 0;
}

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

const int N = 101;
int n, W, arr[N], v[N];
unordered_map < long long , int > dp[N];

int call(int i, long long w)
{
    if(i == n)
        return 0;
    if(dp[i].find(w) != dp[i].end())
        return dp[i][w];
    int ret = call(i + 1, w);
    if(w + arr[i] <= W)
        ret = max(ret, v[i] + call(i + 1, w + arr[i]));
    return dp[i][w] = ret;
}

int main()
{
    cin>>n>>W;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        cin>>v[i];
        dp[i].clear();
    }
    printf("%d\n", call(0, 0));

    return 0;
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=998244353;
const LL LINF=1LL<<62;
const int INF=1<<20;


int main(){
    LL n;
    while(cin >> n,n){
        string c;cin >> c;
        P a = P(0LL,0LL);
        a.fs = 1LL<<52;
        for (int i = 0; i < c.length(); i++) {
            if(c[i]=='1') a.sc += (1LL<<(c.length()-i-1));
        }
        P s = a;
        s.sc += (1LL<<52);
        a.sc += (1LL<<52);
        while(n>0){
            LL num = ((1LL<<53)-s.sc)/a.sc;
            if(((1LL<<53)-s.sc)%a.sc) num++;
            if(num>n){
                s.sc += a.sc*n;
                break;
            }
            else{
                n-=num;
                s.sc += a.sc*num;
                a.sc >>= 1;
                s.sc >>= 1;
                s.fs++;
            }
            if(a.sc == 0) break;
        }
        bitset<12> x(s.fs);
        bitset<52> y(s.sc-(1LL<<52));
        cout << x << y << endl;
    }
    return 0;
}



Measured memory_bytes: 3152
#include <iostream>
    #include <algorithm>
    using namespace std;
    int n, s, i, a[105];
    int main() {
    	cin>>n;
    	for(i=0; i<n; i++) cin>>a[i];
    	sort(a, a+n, greater<int>());
    	for(i=0; i<n; i++) i%2 ? s-=a[i] : s+=a[i];
    	cout<<s;
    	return 0;
    }

Measured memory_bytes: 256
import sys
input=sys.stdin.buffer.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
from collections import deque
N = int(input())
xy = [[0,0]]*N
A = [0]*N
for i in range(N):
    a = int(input())
    A[i] = a
    xy[i] = [list(map(int,input().split())) for _ in range(a)]
Max = 0
for i in range(2**N):
    bitlist = deque()
    for j in range(N):
        if ((i >> j) & 1): #2進数表示のj桁目(0桁目から数える)が1かどうか
            bitlist.appendleft(1)
        else:
          	bitlist.appendleft(0)
    bitlist = list(bitlist)
    cc = 0
    for i in range(N):
        c = 0
        if bitlist[i] == 1:
            for k in range(A[i]):
                if xy[i][k][1] == 1:
                    if bitlist[xy[i][k][0]-1] == 0:
                        c = 1
                        break
                else:
                    if bitlist[xy[i][k][0]-1] == 1:
                        c = 1
                        break
        if c == 1:
            cc = 1
            break
    if cc == 0:
        ss = 0
        for jj in bitlist:
            ss += jj
        Max = max(Max,ss)
print(Max)


    



Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <utility>

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

  std::unordered_map<int, std::vector<int>> v_dict;
  for(int i = 0; i < M; i++){
    int u,v;
    std::cin >> u >> v;
    v_dict[u].push_back(v+N);
    v_dict[u+N].push_back(v+2*N);
    v_dict[u+2*N].push_back(v);
  }
  int S,T;
  std::cin >> S >> T;

  if(S == T){
    std::cout << "0" << std::endl;
    return 0;
  }

  int nsteps = 1;
  std::unordered_set<int> found;
  std::vector<int> current_nodes, next_nodes;
  found.insert(S);
  current_nodes.push_back(S);
  while(true){
    if(current_nodes.size() == 0){
      std::cout << "-1" << std::endl;
      return 0;
    }
    for(const auto& n: current_nodes){
      if(v_dict.find(n) == v_dict.end()) continue;
      for(const auto& neigh: v_dict[n]){
        if(neigh == T){
          std::cout << nsteps/3 << std::endl;
          return 0;
        }
        if(found.find(neigh) != found.end()) continue;
        next_nodes.push_back(neigh);
        found.insert(neigh);
      }
    }
    nsteps++;
    std::swap(current_nodes, next_nodes);
    next_nodes.clear();
  }

  return 0;
}



Measured memory_bytes: 41844
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)
	cnta := 0
	for i :=0 ;i<len(s); i++ {
		if string(s[i]) == "1" {
			cnta++
		}
	}
	cntb := len(s)-cnta
	if  cntb >= cnta {
		fmt.Println(2*cnta)
	} else if cntb < cnta {
		fmt.Println(2*cntb)
	}
}

Measured memory_bytes: 1280
#include <iostream>
#include<bits/stdc++.h>
#define ll long long int
#define lld long double
#define F first
#define S second
#define f(i,a,b) for(int i=a;i<=b;i++)
#define g(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mh make_heap
#define ph push_heap
#define pq priority_queue
#define bits(x) __builtin_popcountll(x)
#define op(x) cout<<"Case #"<<x<<": "
#define op1(x) cout<<"Scenario #"<<x<<": "
#define endl "\n"
using namespace std;
const ll mod = 998244353;
const ll INF = LLONG_MAX;
const ll NEGINF = LLONG_MIN;
const int N = 18;
const ll MAXN = 1000001;

ll n, k;
ll l[11], r[11];


void solve(int t)
{
	cin >> n >> k;

	for (int i = 0; i < k; i++)
	{
		cin >> l[i] >> r[i];

	}

	ll dp[n + 1] = {0};
	ll pr[n + 1] = {0};
	dp[1] = 1;
	pr[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < k; j++)
		{
			dp[i] = (dp[i] % mod + (pr[max(i - l[j], (ll)0)] - pr[max(i - r[j] - 1, (ll)0)] + mod) % mod) % mod;
		}
		pr[i] = (pr[i - 1] % mod + dp[i] % mod) % mod;
	}

	cout << dp[n] % mod << endl;





}



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



	int t = 1;
	//cin >> t;



	for (int i = 1; i <= t; i++)
	{
		solve(i);

	}
}

Measured memory_bytes: 6768
#include<stdio.h>

int main()
{
	int spread[101][101];
	int r,c;
	int i,j;
	for(i=0;i<101;i++)
	{
		for(j=0;j<101;j++)
		{
			spread[i][j]=0;
		}
	}
	scanf("%d %d",&r,&c);
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
		{
			scanf("%d",&spread[i][j]);
			spread[r][c]+=spread[i][j];
			spread[i][c]+=spread[i][j];
			spread[r][j]+=spread[i][j];
		}
	}
	for(i=0;i<=r;i++)
	{
		for(j=0;j<=c;j++)
		{
			printf("%d",spread[i][j]);
                        if(j!=c)printf(" ");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 644
readArray::IO String -> IO[Int]
readArray = fmap $ map read . words
res a b c d
    |abs (c-a) <= d = "Yes"
    |abs (b-a) <= d && abs (c-b) <= d = "Yes"
    |otherwise = "No"
main = do
    [a,b,c,d] <- readArray getLine
    putStrLn $ res a b c d

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

long long n, dsize;
vector<long long> x,y,d;
string dir = "LUDR";

string solve(int now);

int main(){
    cin >> n;
    x.resize(n);
    y.resize(n);
    for(int i = 0;i < n;++i)cin >> x[i] >> y[i];
    for(int i = 1;i < n;++i)
        if(abs(x[i-1] + y[i-1]) % 2 != abs(x[i] + y[i]) % 2){
            cout << -1 << endl;
            return 0;
        }
    for(int i = 0;i < 31;++i)d.push_back((1LL << (30 - i)));
    if(!(abs(x[0] + y[0]) % 2))d.push_back(1);
    dsize = d.size();
    cout << dsize << endl;
    for(int i = 0;i < dsize;++i){
        if(i != 0)cout << " ";
        cout << d[i];
    }
    cout << endl;
    for(int i = 0;i < n;++i)cout << solve(i) << endl;
    return 0;
}

string solve(int now){
    string ans;
    long long uv[2] = {x[now]+y[now]+(1LL<<31) - 1,x[now]-y[now]+(1LL<<31) - 1};
    if(abs(x[now]+y[now])%2 == 0)++uv[0],++uv[1];
    for(int i = 0;i < dsize;++i){
        int flag = 0;
        for(int j = 0;j < 2;++j){
            if(uv[j] >= 2 * d[i]){
                flag += 1 <<j;
                uv[j] -= 2 * d[i];
            }
        }
        ans += dir[flag];
    }
    assert(uv[0] == 0 && uv[1] == 0);
    return ans;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        String S = sc.next();

        if (S.charAt(1) == 'B') {
            System.out.println("ARC");
        } else if (S.charAt(1) == 'R') {
            System.out.println("ABC");
        } else {

        }
    }
}

Measured memory_bytes: 35732
n = int(input())
l = sorted([[int(i) for i in input().split()] for _ in range(n)],key = lambda x : (x[1],x[0]))

time = 0
flg = True
for i in l:
    time += i[0]
    if time > i[1]:
        flg = False
        break
    
print('Yes' if flg else 'No')

Measured memory_bytes: 55384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a;
  cin >> a;
  vector<int> t(a);
for (int i = 0; i < a; i++) {
  cin >> t.at(i);
}
  vector<int> v(a);
  for (int i = 0; i < a; i++) {
  v.at(i) = t.at(i);
}
  sort(t.begin(), t.end());
  int r;
  r = a / 2;
  int k;
  int l;
  k = t.at(r-1);
  l = t.at(r);
  for(int i = 0; i < a; i++){
    if(v.at(i) <= k){
      cout << l << endl;}
    else{cout << k << endl;}
  }
  }

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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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;
}

template<class T>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

inline void out() {
	cout<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

bool isout(int h, int w, int H, int W) {
	return ( h<0 || h>=H || w<0 || w>=W );
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


int H,W,M;
set<intpair> mine;
intvec h,w;

void input() {
	cin>>H>>W>>M;
	h.resize(H,0), w.resize(W,0);
	for(int i=0; i<M; i++) {
		int x,y; cin>>x>>y; x--,y--;
		mine.insert(intpair(x,y));
		h[x]++, w[y]++;
	}
}

void solve() {
	int mxh=-1;
	intvec hm,wm;
	for(int i=0; i<H; i++) {
		if(mxh<h[i]) {
			mxh=h[i];
			hm.clear();
		}
		if(mxh==h[i]) hm.pushb(i);
	}
	int mxw=-1;
	for(int i=0; i<W; i++) {
		if(mxw<w[i]) {
			mxw=w[i];
			wm.clear();
		}
		if(mxw==w[i]) wm.pushb(i);
	}

	int ans=-1;
	for(int i=0; i<hm.size(); i++) for(int j=0; j<wm.size(); j++) {
		if(mine.find(intpair(hm[i],wm[j]))==mine.end()) {
			ans=mxh+mxw;
			cout<<ans<<endl;
			return;
		}
		ans=mxh+mxw-1;
	}

	cout<<ans<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


Measured memory_bytes: 23772
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
  int n,i,j,t,ans1=0,ans2=0,ans3=0,list[100][100]={2};
  while(1){
  cin >> n;
  if(n==0){
    break;
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      cin >> list[i][j];
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      ans1=ans1+list[i][j];
      ans2=ans2+list[j][i];
    }
    list[i][j]=ans1;
    ans3=ans3+ans1;
    ans1=0;
    list[j][i]=ans2;
    ans2=0;
  }
  list[i][j]=ans3;
  ans3=0;
  for(i=0;i<n+1;i++){
    for(j=0;j<n+1;j++){
      printf("%5d",list[i][j]);
    }
    cout << endl;
  }
  }
  return (0);
}

Measured memory_bytes: 1232