akhauriyash/Code-Regression huggingface dataset:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    minus = []
    plus = []
    M = I()
    A = LI()
    zero = []
    ans = []
    for a in A:
        if a < 0:
            minus.append(a)
        elif a > 0:
            plus.append(a)
        else:
            zero.append(0)
    minus.sort()
    plus.sort(reverse = True)
    if not minus:
        #print(minus,plus,zero)
        if zero and plus:
            a = zero.pop()
            b = plus.pop()
            minus.append(a-b)
            ans.append("{} {}".format(a, b))
        elif len(plus) >= 2:
            a = plus.pop()
            b = plus.pop()
            minus.append(a-b)
            ans.append("{} {}".format(a, b))
        
    if not plus:
        if zero and minus:
            a = zero.pop()
            b = minus.pop()
            plus.append(a-b)
            ans.append("{} {}".format(a, b))
        elif len(minus):
            a = minus.pop()
            b = minus.pop()
            plus.append(a-b)
            ans.append("{} {}".format(a, b))
        


    while minus and plus:
        if len(minus) == len(plus) == 1:
            a = plus.pop()
            b = minus.pop()
            ans.append("{} {}".format(a,b))
            plus.append(a - b)
            break
        a = minus.pop()
        b = plus.pop()
        if len(minus) > len(plus):
            ans.append("{} {}".format(b,a))
            plus.append(b-a)
        else:
            ans.append("{} {}".format(a,b))
            minus.append(a - b)

    while zero:
        if minus:
            a = zero.pop()
            b = minus.pop()
            #print(a, b)
        elif plus:
            a = plus.pop()
            b = zero.pop()
            #print(a, b)
        elif len(zero) >= 2:
            a = zero.pop()
            b = zero.pop()
            #print(a,b)
        else:
            break
        plus.append(a - b)
        ans.append("{} {}".format(a,b))

    if zero:
        print(*zero)
    elif minus:
        print(*minus)
    else:
        print(*plus)
    print(*ans,sep="\n")

if __name__ == '__main__':
    main()


Measured memory_bytes: 76768
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>
#include <cstring>
#include <iomanip>
#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1000000000
typedef long long  ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

template<typename T>
T gcd(T a,T b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

template<typename T>
T lcm(T a,T b){
	T g = gcd(a, b);
	return a /g* b ;
}

void clear( std::queue<pair<int,int> > &q )
{
   std::queue<pair<int,int> > empty;
   std::swap( q, empty );
}
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
template<typename T>
int  GetDigit(T num){
    int digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

template<typename T>
std::vector<T> enum_div(T n)//nの約数を列挙
{
	std::vector<T> ret;
	for(T i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			ret.push_back(i);
			if(i!=1 && i*i!=n)
			{
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}


class DisjointSet{
    public:
        vector<int> rank, p;

        DisjointSet(){
        }

        DisjointSet(int size){
            rank.resize(size, 0);
            p.resize(size, 0);
            for (int i = 0; i < size;i++){
                makeSet(i);
            }
        }
        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }

        bool same(int x,int y){
            return findSet(x) == findSet(y);
        }
        void unite(int x,int y){
            link(findSet(x), findSet(y));
        }
        void link(int x,int y){
            if(rank[x]>rank[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank[x]==rank[y]){
                    rank[y]++;
                }
            }
        }
        int findSet(int x){
            if(x!=p[x]){
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};


int main()
{
    string X;
    cin >> X;
    int N = X.size();
    int snum=0;
    int pai = 0;

    REP(i,0,N){
        if(X[i]=='S'){
            snum++;
        }else{
            if(snum>0){
                snum--;
                pai++;
            }
        }

    }
    cout << N - pai * 2 << endl;
}

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

int main(){
  int A,B,C,D;
  cin >> A;
  cin >> B;
  cin >> C;
  cin >> D;
  
  while(A>0 && C>0){
    C -= B;
    if(C<=0) break;
    A -= D;
  }
  //cout << A << endl;
  //cout << C << endl;
  if(A>0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3596
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

use rand::prelude::*;

#[allow(unused_macros)]
macro_rules! echo {
    ($($e:expr),+) => ( { $(println!("{}", $e))+ } );
}

#[allow(unused)]
fn calc(i: usize, day: usize, s: &Vec<Vec<isize>>, c: &Vec<isize>, last: &mut Vec<usize>) -> isize {
    last[i] = day;
    let up = s[day - 1][i];
    let mut down = 0;

    for j in 0..26 {
        down += (day - last[j]) as isize * c[j];
    }

    up - down
}

fn update(i: usize, j: usize, day: usize, s: &Vec<Vec<isize>>, c: &Vec<isize>) -> isize {
    let mut ans = s[day - 1][j] - s[day - 1][i];
    let c_diff = c[j] - c[i];
    let i = i as isize;
    let j = j as isize;
    ans += c_diff * (j * j - 25 * j - i * i + 25 * i);
    ans
}

fn main() {
    input! {
        d: usize,
        c: [isize; 26],
        s: [[isize; 26]; d],
    }

    // let mut score = 0;
    // let mut last = vec![0; 26];

    let mut tmp_dec_max = (0, 0);
    for e in c.iter().enumerate() {
        if tmp_dec_max.1 < *e.1 {
            tmp_dec_max = (e.0, *e.1);
        }
    }

    let mut contests = vec![];

    for day in 1..=d {
        let mut tmp_inc_max = (0, 0);
        for i in 0..26 {
            if tmp_inc_max.1 < s[day - 1][i] {
                tmp_inc_max = (i, s[day - 1][i]);
            }
        }

        let target: usize;

        if tmp_inc_max.0 == tmp_dec_max.0 {
            target = tmp_inc_max.0;
        } else if tmp_inc_max.1 > tmp_dec_max.1 {
            target = tmp_inc_max.0;
        } else {
            target = tmp_dec_max.0;
        };
        contests.push(target);
        // score += calc(tmp_inc_max.0, day, &s, &c, &mut last);
    }

    let mut rng = rand::thread_rng();
    let ch_contest: Vec<_> = (0..26).collect();
    let ch_day: Vec<_> = (1..=d).collect();

    for _ in 0..500_000 {
        if let Some(contest) = ch_contest.choose(&mut rng) {
            if let Some(day) = ch_day.choose(&mut rng) {
                let before = contests[*day - 1];
                if update(before, *contest, *day, &s, &c) > 0 {
                    contests[*day - 1] = *contest;
                }
            };
        };
    }

    for e in contests {
        echo!(e + 1);
    }

    // score += 10_isize.pow(6);
    // score = std::cmp::max(0, score);

    // dbg!(score);
}


Measured memory_bytes: 2728
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	for(int i = 0; i < (1 << 3); i++){
		int val = s[0] - '0';
		string res = "";
		res += s[0];
		for(int j = 0; j < 3; j++){
			if(i & (1 << j)){
				val += s[j + 1] - '0';
				res += '+';
				res += s[j + 1];
			}else{
				val -= s[j + 1] - '0';
				res += '-';
				res += s[j + 1];
			}
		}
		if(val == 7){
			res += "=7";
			cout << res << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n; cin >> n;
    string s; cin >> s;
    string ans = "Yes";

    int h = n / 2;
    if (n % 2 || s.substr(0, h) != s.substr(h, n)) ans = "No";

    cout << ans << endl;

    return 0;
}


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

typedef long long ll;

int main(){
    ll n, x; cin>>n>>x;
    vector<ll> cntP(60, 0), l(60, 0);
    cntP[0]=1, l[0]=1;
    for(int i=1; i<=n; i++){
        cntP[i]=cntP[i-1]*2+1;
        l[i]=l[i-1]*2+3;
    }

    ll lb=1, ub=l[n];
    ll ans=0;
    while(n--){ // [lb, ub]
        ll mid=(lb+ub)/2;

        if(x==lb){
            break;
        }
        else if(lb<x && x<mid){
            ub=mid-1;
            lb++;
            if(n==0) ans++;
        }
        else if(x==mid){
            ans+=cntP[n]+1;
            break;
        }
        else if(mid<x && x<ub){
            lb=mid+1;
            ub--;
            ans+=cntP[n]+1;
            if(n==0) ans++;
        }
        else if(x==ub){
            ans+=cntP[n+1];
            break;
        }
    }
    cout << ans << endl;
}

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

int main(void)
{
	int n,A[10000];
	int i, j, k, tmp, minj = 0;
	int count = 0;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}

	
	for (i = 0;i <= n - 1;i++) {
		minj = i;
		for (j = i;j <= n - 1;j++) {
			if (A[j] < A[minj]) {
				minj = j;
			}
		}
		if (minj != i) {
			tmp = A[i];
			A[i] = A[minj];
			A[minj] = tmp;
			count++;
		}
	}

	for (k = 0; k < n; k++) {
		printf("%d", A[k]);
		if (k != n - 1) {
			printf(" ");
		}
		else
		{
			printf("\n%d\n",count);
		}
	}
	
	return 0;
}


Measured memory_bytes: 2120
#include <stdio.h>
int main(void)
{
int m, f, r, p;
char h;

while(1){

scanf("%d %d %d",&m,&f,&r);

if(m == f && f == r && r == -1)
break;

if(m != -1 && f != -1)
p = m + f;
else
p = 0;

if(p >= 80)
h = 'A';
else if(80 > p && p >= 65)
h = 'B';
else if(65 > p && p >= 50)
h = 'C';
else if(50 > p && p >= 30){
h = 'D';
if(r >= 50)
h = 'C';
}
else if(p < 30)
h = 'F';

printf("%c\n",h);

}
return 0;
}

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

const int INF = 1e9 + 5;

int main(){
	
	int n,k;
    scanf("%d%d", &n,&k);
    vector<int> fill(n);
    for(int& x : fill) {
        scanf("%d", &x);
    }
    vector<int> dp(n, INF);
    dp[0] = 0;
	dp[1] = abs(fill[1]-fill[0]);
	
	for(int i=2;i<n;i++){
		int index = 1;
		for(int j=i-1;j>=0&&index<=k;j--){
			dp[i] = min(dp[i],dp[j]+abs(fill[j]-fill[i]));
			index++;
		}
		
	}
	
    printf("%d\n", dp[n-1]);
	
	return 0;
}


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

int main() {
  int A,B;
  cin >> A >> B;
  int V = 0;
  for(int i = A; i <= B; i++){
    int a,b,c,d;
    a = i/10000;
    b = i%10000%1000%100%10;
    c = i%10000/1000;
    d = i%10000%1000%100/10;
    if(a == b && c == d){
      V = V + 1;
    }
  }
  cout << V << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long
const int INF = 1LL << 60;

signed main(){

  int n; cin >> n;
  vector<int> x(n);
  int sum = 0;
  for(int i = 0; i < n; i++){
    cin >> x[i];
    sum += x[i];
  }
  sort(x.begin(),x.end());

  //int k = (x[n-1] + x[0]) / 2;
  int k = sum / n;
  int ans = INF;
  for(int i = -10000; i < k + 10000; i++){
    int res = 0;
    for(int j = 0; j < n; j++){
      res += (i - x[j]) * (i - x[j]);
    }
    ans = min(ans, res);
  }
  cout << ans << endl;

  return 0;
}


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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> map(H,vector<char>(W,'-'));
  for(int i = 0;i < H; i++){
  	for(int j = 0; j< W; j++){
    	cin >> map.at(i).at(j);
    }
  }
  for(int i = 0;i < H; i++){
    int flag = 1;
  	for(int j = 0; j< W; j++){
    	if(map.at(i).at(j) == '#'){
        	flag = 0;
          	break;
        }
    }
    if(flag){
    	map.erase(map.begin() + i);
      	i--;
      	H--;
    }
  }
  for(int j = 0; j< W; j++){
    int flag = 1;
  	for(int i = 0;i < H; i++){
    	if(map.at(i).at(j) == '#'){
        	flag = 0;
          	break;
        }
    }
    if(flag){
     	for(int i = 0;i < H; i++){
      		map.at(i).erase(map.at(i).begin() + j);
      	}
   	  	j--;
      	W--;
    }
  }
  for(int i = 0; i< H; i++){
  	for(int j = 0; j < W; j++){
    	cout << map.at(i).at(j);
    }
    cout << endl;
  }
}


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

using namespace std;

const int N = 10;
int field[N][N];
int ansx[20], ansy[20], anssz[20];
int dx[] = { 0, 1, 0 };
int dy[] = { 1, 1, 2 };

bool drop(int val, int x, int y, int size){
	for (int s = 0; s < 3; ++s){
		if (s != size) continue;
		if (x - dy[s] < 0 || x + dy[s] >= N || y - dy[s] < 0 || y + dy[s] >= N) return false;

		for (int k = 0; k < 2; ++k)
		for (int i = y - dy[s]; i <= y + dy[s]; ++i){
			for (int j = x - dy[s]; j <= x + dy[s]; ++j){
				if (size == 1 || abs(x - j) + abs(y - i) <= dy[s]){
					if (k) field[i][j] += val;
					else if (field[i][j] + val < 0) return false;
				}
			}
		}
	}
	return true;
}

bool dfs(int x, int y, int n){
	if (x == N) return dfs(0, y+1, n);
	if (y == N) return n == 0;

	if (!field[y][x]) return dfs(x+1, y, n);
	for (int i = 2; i >= 0; --i){
		bool b = drop(-1, x+dx[i], y+dy[i], i);
		if (b && dfs(x, y, n-1)){
			ansx[n] = x+dx[i];
			ansy[n] = y+dy[i];
			anssz[n] = i+1;
			return true;
		}
		if(b) drop(1, x+dx[i], y+dy[i], i);
	}
	return false;
}

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
		cin >> field[i][j];

	dfs(0, 0, n);
	for (int i = 1; i <= n; ++i){
		cout << ansx[i] << ' ' << ansy[i] << ' ' << anssz[i] << '\n';
	}

	return 0;
}

Measured memory_bytes: 1160
package main

import(
	"fmt"
)

func main() {
	nums := []int{1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1}
	var x, y int
	fmt.Scan(&x, &y)
	if nums[x-1] == nums[y-1] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		
		
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		
		if(a==b&&a==c){
			System.out.println("1");
		}else if(a==b && a!=c){
			System.out.println("2");
		}else if(a==c&&a!=b){
			System.out.println("2");
		}else if(a!=b&&b==c){
			System.out.println("2");
		}else if(a!=b&&a!=c){
			System.out.println("3");
		}
		
}
}

Measured memory_bytes: 9812
#include <stdio.h>
int main (void)
{
	int a, b;

	scanf("%d %d", &a, &b);

	if (a < b)
		printf("a < b\n");
	else if (a > b)
		printf("a > b\n");
	else
		printf("a == b\n");

	return 0;
}

Measured memory_bytes: 580
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,flag,ans;
    vector<int> pf;
    cin >> N;
    for(int i=2; ; i++){
        flag=1;
        for(int j=0; j<pf.size(); j++){
            if(i%pf.at(j)==0){
                flag=0;
                break;
            }
        }
        if(flag){
            if(i>=N){
                ans=i;
                break;
            }else{
                pf.push_back(i);
            }
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 384
import sys
H, W = map(int, input().split())

grid = []
dot_h = []
sharp_h = []
dot_w = []
sharp_w = []

for h in range(H):
    line = input()
    line = line[:W]
    grid.append(line)
    if line.count('.') == W:
        dot_h.append(h)
    # if line.count('#') == W:
    #     sharp_h.append(h)
for w in range(W):
    dot_c = 0
    sharp_c = 0
    for h in range(H):
        if grid[h][w] == '.':
            dot_c += 1
        # if grid[h][w] == '#':
        #     sharp_c += 1
    if dot_c == H:
        dot_w.append(w)
    if sharp_c == H:
        sharp_w.append(w)
    
for h in range(H):
    if h in dot_h or h in sharp_h:
        continue
    for w in range(W):
        if w in dot_w or w in sharp_w:
            continue
        # print(grid[h][w], end="")
        sys.stdout.write(grid[h][w])
    print('')

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

using namespace std;

typedef long long ll;

#define MOD (int)1e9+7
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>b;--i)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()

ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }

return ans;
}

ll c(ll a,ll b)
{
  if(a==0)return b==0?1:0;

if(b>a)return 0;

  ll val=1;
ll fac=1;
for(int i=1;i<=b;i++)fac*=i;
for(int i=a;i>=a-b+1;i--)val*=i;

  return val/fac;

}

ll f(ll n)
{
  ll ans=1LL;
  while(ans<=n)ans<<=1;

return ans;
}

int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
ll n;cin>>n;

ll fin=(n+1)/2;

cout<<fin<<"\n";





return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define mod (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
int gcd(int A,int B) {if(!B)return A;return gcd(B,A%B);}
int a[200005];
vector<int>b(200005,0);
int cnt = 0;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int i=n;i>=1;i--)
	{
		int balls = 0;
		for(int j=i;j<=n;j+=i)balls+=b[j];
			
		if(balls%2 != a[i]%2){b[i] = 1;cnt++;}
	}
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++)if(b[i])cout<<i<<" ";
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int H,W,N;
int X[3030],Y[3030];
pair<int,int> P[3030];

ll dp[3030][2];
ll dpD[3030][3030];

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(i,N+2) {
		if(i==1) Y[i]=H-1,X[i]=W-1;
		else if(i>0) {
			cin>>Y[i]>>X[i];
			Y[i]--;
			X[i]--;
		}
		P[i]={X[i]+Y[i],X[i]};
	}
	N+=2;
	sort(P,P+N);
	FOR(i,N) {
		X[i]=P[i].second;
		Y[i]=P[i].first-P[i].second;
	}
	
	dp[0][0]=1;
	FOR(x,N) {
		for(y=x+1;y<N;y++) if(X[x]<=X[y] && Y[x]<=Y[y]) {
			ll pat=comb(X[y]+Y[y]-X[x]-Y[x],X[y]-X[x]);
			(dp[y][0]+=dp[x][1]*pat)%=mo;
			(dp[y][1]+=dp[x][0]*pat)%=mo;
		}
	}
	
	cout<<(dp[N-1][1]+mo-dp[N-1][0])%mo<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 9856
function Main(input) {
    var s = input;
    var k = input.length - 1;
    var oCount = 0;
    var res;
    for(var i = 0; i < k; i++){
        if(s[i] == "o"){
            oCount++;
        }
    }
    if(oCount >= 8){
        res = "YES";
    }else{
        if(8 <= 15 - k + oCount){
            res = "YES";
        }else{
            res = "NO";
        }
    }
    console.log(res);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
a, b = map(int, input().split())
A = str(bin(a))[2:]
B = str(bin(b))[2:]
if A[-1] == '0':
    if (b-a+1)%2 == 0:
        mae = '0'
    else:
        if a <= 1:
            c = '0'
        else:
            c = A[:-1]
        mae = str(bin(int(c, 2)+int((b-a)/2)))[2:]
    if (b-a+1)%4 == 0 or (b-a+1)%4 == 1:
        print(int(mae+'0', 2))
    else:
        print(int(mae+'1', 2))
else:
    if (b-a+1)%2 == 0:
        if a <= 1:
            c = '0'
        else:
            c = A[:-1]
        if b <= 1:
            d = '0'
        else:
            d = B[:-1]

        mae = str(bin(int(c, 2)^int(d, 2)))[2:]
    else:
        mae = A[:-1]
    if (b-a+1)%4 == 0 or (b-a+1)%4 == 3:
        print(int(mae+'0', 2))
    else:
        print(int(mae+'1', 2))


Measured memory_bytes: 3064
#include <stdio.h>
     
    int main(){
       int n,k,i;
       long s,x;
     
       scanf("%d %d %ld",&n,&k,&s);
       if (s<1000000000) x=s+1;
       else              x=s-1;
       if (k>0) printf("%ld",s);
       else     printf("%ld",x);
       for (i=1;i<k;i++) printf(" %ld",s);
       if (k==0) i=1;
       else      i=0;
       for (;i<n-k;i++) printf(" %ld",x);
       puts("");
       return 0;
    }

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;

int main(){
    ll n; cin >> n;
    vector<pair<ll,ll>> ab(n);
    rep(i,n) cin >> ab.at(i).first;
    rep(i,n) cin >> ab.at(i).second;

    std::sort(ab.begin(), ab.end(), [](const pair<ll,ll> x, const pair<ll,ll> y) {
        return x.first - x.second > y.first - y.second;
    });

    ll dif = 0;
    ll ans = 0;

    for(int i=n-1;i>=0;i--){
        if(ab.at(i).first >= ab.at(i).second) break;
        dif += (ab.at(i).second - ab.at(i).first);
        ans++;                
    }

    ll x = 0;

    while(dif>0){
        if(ab.at(x).first <= ab.at(x).second) break;
        dif -= ab.at(x).first - ab.at(x).second;
        ans++, x++;
        if(dif<=0) break;
    }

    if(dif>0){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
    //rep(i,n) cout << ab.at(i).first << " " << ab.at(i).second << endl;   
}

Measured memory_bytes: 1792
$s = gets.chomp
t = gets.chomp
def f(s, t, i = 0, j = 0, k = 0)
    return true if i >= $s.size
    begin
        j += 1 until s[j]*1 == $s[i]
    rescue
        return false
    end
    f(t, s, i + 1, k, j + 1)
end
puts f($s, t) || f(t, $s) ? 'Yes' : 'No'


Measured memory_bytes: 8868
#include<iostream>

using namespace std;

int main() {
  int D;

  cin >> D;

  if (D == 25) {
    cout << "Christmas" << endl;
  }
  else if (D == 24) {
    cout << "Christmas Eve" << endl;
  }
  else if (D == 23) {
    cout << "Christmas Eve Eve" << endl;
  }
  else if (D == 22) {
    cout << "Christmas Eve Eve Eve" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
#define db double
signed main(){
    int l,r,d,res=0;
    cin>>l>>r>>d;
    for (int i = l; i <=r ; ++i) {
        if(i%d==0)res++;
    }
    cout<<res;
    return 0;
}

Measured memory_bytes: 3592
n = int(input())

adj = [[100001 for j in range(n)] for i in range(n)]

for u in range(n):
    x = list(map(int, input().split()))
    for v, c in zip(x[2::2], x[3::2]):
        adj[u][v] = c

unvisited = {v for v in range(n)}

distance = [9900001] * n


def dijkstra(s):
    distance[s] = 0

    while True:
        mincost = 9900001
        for i in unvisited:
            if distance[i] < mincost:
                mincost = distance[i]
                u = i

        if mincost == 9900001:
            break

        unvisited.discard(u)

        for v in unvisited:
            weight_uv = adj[u][v]
            if weight_uv != 100001:
                t_d = distance[u] + weight_uv
                if t_d < distance[v]:
                    distance[v] = t_d



dijkstra(0)

for v, d in enumerate(distance):
    print(v, d)

Measured memory_bytes: 7844
n, k = gets.split.map(&:to_i)
ps = gets.split.map(&:to_i)

max = sum = ps[0...k].inject(:+)

(n - k).times do |i|
  sum -= ps[i]
  sum += ps[i + k]
  max = sum if max < sum
end

puts (max + k) / 2.0

Measured memory_bytes: 14980
import java.util.*;
public class Main {
    void run() {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String s = sc.next();
            if (s.equals("0")) break;
            System.out.println(dfs(convert(s)));
        }
    }
    
    String dfs(String str) {
        Set<String> visited = new HashSet<String>();
        visited.add(str);
        
        LinkedList<String> q = new LinkedList<String>();
        LinkedList<Integer> qi = new LinkedList<Integer>();
        q.add(str); qi.add(0);
        
        while (!q.isEmpty()) {
            String s = q.removeFirst();
            int c = qi.removeFirst();  
            if (ok(s)) return "" + c;
            for (int i = 0; i < s.length() - 1; i++) if (s.charAt(i) != s.charAt(i + 1)) {
                int n = s.charAt(i) - '0' + s.charAt(i + 1) - '0';
                n = (3 - n % 3) % 3;
                String next = s.substring(0, i) + n + n + s.substring(i + 2, s.length());
                if (!visited.contains(next)) {
                    q.addLast(next);
                    qi.addLast(c+1);
                    visited.add(next);
                }
            }
        }
        return "NA";
    }
    
    String convert(String str) {
        String ret = "";
        for (int i = 0; i < str.length(); i++) {
            switch (str.charAt(i)) {
            case 'r': ret += "" + 0; break;
            case 'g': ret += "" + 1; break;
            case 'b': ret += "" + 2; break;
            }
        }
        return ret;
    }
    
    boolean ok(String s) {
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) != s.charAt(i + 1)) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        new Main().run();
    }
}

Measured memory_bytes: 97956
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int N, M;
	cin >> N >> M;
	vector<vector<int>> E(N); 
	for (int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	vector<vector<int>> dp(11, vector<int>(N, -1));
	int Q;
	cin >> Q;
	vector<int> c(Q);
	for (int i = 0; i < Q; i++){
		int v, d;
		cin >> v >> d >> c[i];
		v--;
		dp[d][v] = i;
	}
	for (int i = 10; i >= 1; i--){
		for (int j = 0; j < N; j++){
			dp[i - 1][j] = max(dp[i - 1][j], dp[i][j]);
			for (int k : E[j]){
				dp[i - 1][k] = max(dp[i - 1][k], dp[i][j]);
			}
		}
	}
	for (int i = 0; i < N; i++){
		if (dp[0][i] == -1){
			cout << 0 << endl;
		} else {
			cout << c[dp[0][i]] << endl;
		}
	}
}

Measured memory_bytes: 13712
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<std::unordered_map<int,std::vector<int>>> a(n+1);
    for(int i=0;i<m;i++){
        int p,q,c;
        std::cin>>p>>q>>c;
        a[p][c].push_back(q);
        a[q][c].push_back(p);
    }
    std::deque<std::tuple<int,int,int>> d;
    for(auto e:a[1])
        d.emplace_back(1,1,e.first);
    std::vector<int> b(n+1,n+1);
    std::vector<std::unordered_set<int>> s(n+1);
    while(!d.empty()){
        int v=std::get<0>(d.front());
        int p=std::get<1>(d.front());
        int c=std::get<2>(d.front());
        d.pop_front();
        if(p==n){
            std::cout<<v<<std::endl;
            return 0;
        }
        if(v<b[p]){
            for(auto e:a[p]){
                if(e.first==c)
                    continue;
                for(int q:e.second){
                    if(v+1<=b[q]&&!s[q].count(e.first))
                        d.emplace_back(v+1,q,e.first);
                }
            }
        }
        if(v<=b[p]&&s[p].insert(c).second){
            b[p]=v;
            for(int q:a[p][c]){
                if(v<=b[q]&&!s[q].count(c))
                    d.emplace_front(v,q,c);
            }
        }
    }
    std::cout<<-1<<std::endl;
    return 0;
}

Measured memory_bytes: 55680
n, m, c = [int(i) for i in input().split()]
Bs = [int(i) for i in input().split()]
ans = 0
for i in range(n):
    As = [int(i) for i in input().split()]
    mul = sum(a * b for a, b in zip(As, Bs))
    ans += 1 if mul + c > 0 else 0
print(ans)

Measured memory_bytes: 38384
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
// numeric_limits<ll>::max()
// cout << setprecision(20) << double << endl;

bool string_order(std::pair<ll, ll> first_entry,
                  std::pair<ll, ll> second_entry)
{
    return (first_entry.second > second_entry.second);
}

int main(void)
{
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    for (ll i = 0; (i < N); ++i) {
        cin >> A[i];
    }
    vector<pair<ll, ll>> data(M);
    for (ll i = 0; (i < M); ++i) {
        cin >> data[i].first >> data[i].second;
    }
    sort(A.begin(), A.end());
    std::sort(data.begin(), data.end(), string_order);
    ll index = 0;
    for (ll i = 0; (i < M); ++i) {
        for (ll j = 0; (j < data[i].first); ++j) {
            if (A[index] < data[i].second) {
                A[index] = data[i].second;
                ++index;
            } else {
                goto ABORT;
            }
        }
    }
ABORT:
    ll res = 0;
    for (ll i = 0; (i < N); ++i) {
        res += A[i];
    }
    cout << res << endl;
    return 0;
}


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

int main(){
    int N;  cin >> N;
    vector<int> h(N);
    for(int i=0; i<N; i++)  cin >> h[i];
    
    int ans = 0;
    while(true){
        int s = -1;
        for(int i=0; i<N; i++){
            if(h[i] != 0){
                s = i;
                break;
            }
        }
        if(s==-1) break;

        int g = -1;
        for(int i=s; i<N; i++){
            if(h[i]==0){
                g = i-1;
                break;
            }
            if(i==N-1) g = N-1;
        }

        int hmin = 101;
        for(int i=s; i<=g; i++){
            hmin = min(hmin, h[i]);
        }
        for(int i=s; i<=g; i++){
            h[i]-=hmin;
        }
        ans += hmin;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>
#include <sstream>

#define ll long long
#define Int ll
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

#define MAX_M 1000001
#define MOD 1000000007

Int X_, Y_;
Int fac[MAX_M];

void input() {
  cin >> X_ >> Y_;
}

void buildFact() {
    fac[0] = fac[1] = 1;
    for (int i = 2; i < MAX_M; i++){
        fac[i] = fac[i - 1] * i % MOD;
    }
}

Int modinv(Int a, Int p) {
  Int b = p, u = 1, v = 0;
  while (b) {
    Int t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= p;
  if (u < 0) u += p;
  return u;
}

Int nCk(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * modinv((fac[k] * fac[n - k] % MOD), MOD) % MOD;
}

void solve() {
  buildFact();
  if ((X_ + Y_) % 3 != 0) {
    cout << 0 << endl;
    return;
  }

  Int m = (2 * X_ - Y_) / 3;
  Int n = (Y_ - m)/2;
  if (m < 0 || n < 0) {
    cout << 0 << endl;
    return;
  }

  cout << nCk(m + n, n) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}


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

#define H 2
#define W 3

char c[H][W];

int main()
{
	string ans = "YES";

	for( int i = 0; i < H; i++ ) {
		for( int j = 0; j < W; j++ ) {
			cin >> c[i][j];
		}
	}

	for( int i = 0; i < H; i++ ) {
		for( int j = 0; j < W; j++ ) {
			if( c[i][j] != c[H-1-i][W-1-j] ) {
				ans = "NO";
				break;
			}
		}
		if( ans == "NO" ) {
			break;
		}
	}


	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
         
    int main() {
      cin.tie(0);
      ios::sync_with_stdio(false);
          
      string s;
      cin >> s;
      int len = s.length();
      bool judge = true;
          
      for(int i = 0; i < len; i++) {
        if(i % 2 != 0) {
          if(s[i] == 'R') {
            judge = false;
            break;
          }
        }else {
          if(s[i] == 'L') {
            judge = false;
            break;
          }
        }
      }
      if(judge == true) {
        cout << "Yes" << endl;
      }else {
        cout << "No" << endl;
      }
    }

Measured memory_bytes: 256
#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()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
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(){
  
  string s;
  cin>>s;
  string t="CODEFESTIVAL2016";
  int ans = 0;
  REP(i,16){
    if(s[i] != t[i]){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

vector<int> g[100100];
bool used[100100];

void dfs(int v,int p){
	for(int t:g[v]){
		if(p==t)continue;
		dfs(t,v);
	}
	if(used[v])return;
	if(p!=-1&&!used[p]){
		used[p]=1;
		used[v]=1;
		return;
	}
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i=0;i<n-1;i++){
		int x,y; cin >> x >> y;
		x--; y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0,-1);
	for(int i=0;i<n;i++){
		if(!used[i]){
			cout << "First" << endl;
			return 0;
		}
	}
	cout << "Second" << endl;
}

Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
mt19937 rnd;



int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    vector<int> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << a[k - 1] << "\n";

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 256
# Aizu Problem 0049: Blood Group
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

counts = {'A': 0, 'B': 0, 'AB': 0, 'O': 0}
for line in sys.stdin:
    no, group = line.strip().split(',')
    counts[group] += 1

for group in ['A', 'B', 'AB', 'O']:
    print(counts[group])

Measured memory_bytes: 7444
import queue

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

group = [0] * N
group_id = 1
que = queue.Queue()

for i in range(N):
    if group[i] != 0:
        continue
    group[i] = group_id
    que.put(G[i])
    while not que.empty():
        q = que.get()
        for j in q:
            if group[j] == 0:
                que.put(G[j])
                group[j] = group_id
    group_id += 1

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if group[s] == group[t]:
        print('yes')
    else:
        print('no')



Measured memory_bytes: 24648
#include <iostream>
#include <string>

using namespace std;

string itoa(int in)
{
	string str,zero;
	if (in == 0) {
		str = '0';
		return str;
	}
	while (in) {
		str = zero + (char)((in % 10) + '0') + str;
		in /= 10;
	}
	return str;
}

int main()
{
	int temp,n,i;
	string d,ch;
	cin >> n;
	for (i = 0;i < n;i++) {
		cin >> temp;
		d += (char)temp + '0';
	}
	for (i = 0;d.find(itoa(i)) != -1;i++) {	}
	cout << i << endl;
	return 0;
}

Measured memory_bytes: 1212
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
typedef long long int ll;
typedef long double ld;
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; }
const long long INF = 1LL << 60;
 
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll n,ans=1;
    cin >> n;
    ll x=n;
    for (ll i=1;i*i<=n;i++){
        if (n%i==0){
            x=i;
        }
    }
    x=n/x;
    while(x>=10){
        ans++;
        x/=10;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n,k = (int(i) for i in input().split()) 
kakuritu=0

for i in range(n):
    if i+1 >= k :
        kakuritu += 1/n
    elif i+1 < k:
        a=1
        while float(k) - (i+1)*pow(2,a) > 0:
            a += 1
        kakuritu += (1/n) * pow(1/2,a)
print(kakuritu)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define pb push_back
#define pll pair <ll, ll>
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#define plll pair <pair <ll, ll>, ll>
#define pllll pair <pair <ll, ll>, pair <ll, ll> >
#define psl pair <string, ll>
#define all(a) a.begin(), a.end()

typedef long long ll;

typedef long double ld;

using namespace std;

const ll maxn = 3e2;
const ll inf = 1e9;

ll n, m, k, t;

vector <ll> V[maxn];

ll C[maxn];

ll D[maxn];

ll P[maxn];

void dfs1(ll v) {
    for (auto v1 : V[v]) {
        if (C[v1] == 0) {
            C[v1] = 3 - C[v];
            dfs1(v1);
        }
        else {
            if (C[v1] == C[v]) {
                cout << -1;
                exit(0);
            }
        }
    }
}

ll bfs(ll v) {
    ll q, w, e;
    for (q = 0; q < n; q++) {
        D[q] = inf;
    }
    queue <ll> Q;
    for (auto v1 : V[v]) {
        D[v1] = 1;
        P[v1] = v1;
        Q.push(v1);
    }
    while (!Q.empty()) {
        ll v1 = Q.front();
        Q.pop();
        for (auto v2 : V[v1]) {
            if (v2 == v) {
                continue;
            }
            if (D[v2] != inf) {
                continue;
            }
            D[v2] = D[v1] + 1;
            P[v2] = P[v1];
            Q.push(v2);
        }
    }
    ll ans1 = 0, p1 = 0;
    for (q = 0; q < n; q++) {
        if (q == v) {
            continue;
        }
        if (ans1 < D[q]) {
            ans1 = D[q];
            p1 = P[q];
        }
    }
    ll ans2 = 0;
    for (q = 0; q < n; q++) {
        if (q == v) {
            continue;
        }
        if (P[q] == p1) {
            continue;
        }
        ans2 = max(ans2, D[q]);
    }
    // cout << ans1 << " " << ans2 << endl;
    return ans1;
}

int main() {
    pyshnapyshnakaa;
    ll q, w, e, a, b, c;
    string s;
    cin >> n;
    for (q = 0; q < n; q++) {
        cin >> s;
        for (w = 0; w < n; w++) {
            if (s[w] == '1') {
                V[q].pb(w);
            }
        }
    }
    ll ans = 0;
    C[0] = 1;
    dfs1(0);
    for (q = 0; q < n; q++) {
        ll dans = bfs(q) + 1;
        ans = max(ans, dans);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<deque>
#include<algorithm>
#define x first
#define y second
using namespace std;

const int N = 300005, M = 1000005;
const long long INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> PII;
int n, m, k, ans, ccnt[N];
vector<int> v[N];
PII p[N];
bool st[N];
string s;


int main()
{
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < k; ++i)
		scanf("%d%d", &p[i].x, &p[i].y);
	for(int i = 0; i < k; ++i)
	{
//		printf("%d, %d \n", p[i].x, p[i].y);
		v[p[i].x].push_back(p[i].y);
		++ccnt[p[i].y];
	}
	int M = 0, Mcnt = 1;
	for(int i = 1; i <= m; ++i)
		if(ccnt[i] > M)
		{
			M = ccnt[i];
			Mcnt = 1;
		}
		else if(ccnt[i] == M)
			++Mcnt;
	for(int i = 1; i <= n; ++i) if(v[i].size())
	{
		int cnt = 0;
		for(auto j: v[i])
			if(ccnt[j] == M) ++cnt;
//		printf("row %d: %d, sz = %d\n", i, cnt, int(v[i].size()));

		if(cnt < Mcnt) ans = max(ans, M + int(v[i].size()));
		else ans = max(ans, M - 1 + int(v[i].size()));
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 23656
#include <cstdio>
int a;
int main(void){
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++){
        int b=-1,c=-1;
        bool flag=0;
        for(int j=1;j<=10;j++){
            scanf("%d",&a);
            if(b<a&&c<a&&!flag){
                if(b<c){
                    c=a;
                }
                else{
                    b=a;
                }
            }
            else if(b<a&&c>a&&!flag){
                b=a;
            }
            else if(b>a&&c<a&&!flag){
                c=a;
            }
            else{
                    flag=1;
                continue;
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

Measured memory_bytes: 2556
use std::vec::Vec;
use std::cmp::max;

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

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

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 2);
  (v[0], v[1])
}

fn main() {
    let l: f64 = read();
    let ans = (l/3.) * (l/3.) * (l/3.);
    println!("{}", ans);
}

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
  int n, r;
  cin >> n >> r;
  for (int i = 1; i < n; i++) {
    int a;
    cin >> a;
    r = gcd(r, a);
  }
  cout << r << endl;
}


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

using namespace std; 
struct seg{
    int size=1;
    vector < int > tizzi;
    int  neu=0;
    seg(int n){
        while(size<n)size*=2;
        tizzi.assign(size*2,neu);
    }
    int comb (int &a,int &b){
        return a+b;
    }
    void set (int i,int v){
        set(i,v,0,0,size);
    }
    void set( int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
                tizzi[x]=v;
            return;
        }
        int m=(lx+rx)/2;
        if(i<m)
        set(i,v,2*x+1,lx,m);
        else
        set(i,v,2*x+2,m,rx);
        tizzi[x]=comb(tizzi[2*x+1],tizzi[2*x+2]);
    }
    int query(int l,int r,int x,int lx,int rx){
        if(lx>=r ||l>=rx) return neu;
        if(l<=lx&&r>=rx) return tizzi[x];
        int m=(lx+rx)/2;
       int  li = query(l,r,2*x+1,lx,m);
       int ri = query(l,r,2*x+2,m,rx);
        return comb(li,ri);
    }
    int query(int l,int r){
        return query(l,r,0,0,size);
    }
};
signed main (){ 
      ios_base::sync_with_stdio(false);
    cin.tie(NULL);
int N,M;
cin>>N>>M;
vector < int > in ( N+1);
for(int i=1;i<=N;i++)
    cin>>in[i];
vector  < int > lastind(*max_element(in.begin(),in.end())+1,0);
deque < pair <int,int> > righth [N+1];
int ans [M];
seg f(N+1);
for(int i=0;i<M;i++){
    int l,r;
    cin>>l>>r;
    righth[r].push_back({l,i});
}
for(int i=1;i<=N;i++){
    if(lastind[in[i]]>0) f.set(lastind[in[i]],0);
    lastind[in[i]]=i;
    f.set(i,1);
    for(int q=0;q<righth[i].size();q++){
        ans[righth[i][q].second]=f.query(righth[i][q].first,i+1);
    }

}
for(int i=0;i<M;i++)
    cout<<ans[i]<<'\n';
}


Measured memory_bytes: 350596