akhauriyash/Code-Regression huggingface dataset:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def multi_choose(self, n, r):
        """重複組み合わせ nHr """
        return self.combination(n - 1 + r, r)

    def factorial(self, n):
        return self.fact[n]


def main():
    MOD = 998244353

    N, M, K = map(int, input().split())

    mp = [1]
    t = 1
    for _ in range(N):
        t = t * (M - 1) % MOD
        mp.append(t)

    calc = Calc(max_value=N, mod=MOD)

    ans = mp[N - 1]
    for i in range(1, K + 1):
        ans = (ans + mp[N - 1 - i] * calc.combination(N - 1, i)) % MOD
    ans = ans * M % MOD
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Measured memory_bytes: 83964
#include <iostream>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
int main(void){
double x,h;
while(cin >> x >> h){
    if(x==0 && h==0)
    break;
    double s = x*x+sqrt(h*h+x*x/4)*x/2*4;
    cout << fixed << setprecision(6) << s <<endl;
}
  return 0;
}


Measured memory_bytes: 3288
#include<cstdio>
using ull = unsigned long long;

int main(){
	int N, K;
	scanf("%d %d", &N, &K);
	int p[N];
	for (int i = 0; i < N; ++i){
		scanf("%d", p + i);
	}
	ull sum = 0, max;
	for (int i = 0; i < K; ++i){
		sum += p[i] + 1;
	}
	max = sum;
	for (int i = K; i < N; ++i){
		sum += p[i] - p[i - K];
		if(max < sum) max = sum;
	}
	printf("%lf\n", max/2.0);
	return 0;
}

Measured memory_bytes: 896
n, p = map(int, input().split())
a = list(map(int, input().split()))
zc = 0
oc = 0
for i in range(n):
    a[i] %= 2
    if a[i]:
        oc += 1
    else:
        zc += 1


def comb(x, y):
    if y < 0 or y > x or x < 0:
        return 0
    ret = 1
    for i in range(1, y+1):
        ret *= x+1-i
        ret //= i
    return ret


ans = 0
for i in range(p, oc+1, 2):
    ans += comb(oc, i)
print(ans*2**zc)

Measured memory_bytes: 3064
package main
import "fmt"
func main() {
  var k,a,b,m int64
  fmt.Scan(&k,&a,&b)
  m = 0
  if a >= k {
    m = 1
  } else if a <= b {
    m = -1
  } else {
    m = 1 + 2*((k-b-1)/(a-b))
  }
  fmt.Println(m)
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define reprev(i, n) for(ll i = (n-1LL); i >= 0; --i)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll,ll> P;
typedef long double ld;

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, r, s, p, k, inf=INT32_MIN;
    string t;
    cin >> n >> k >> r >> s >> p >> t;
    map<char, int> m;
    m['r'] = p; m['s'] = r; m['p'] = s;
    ll dp[200000][2] = {}; // lose:win
    rep (i, n) {
        if (i < k) dp[i][1] = m[t[i]];
        else {
            dp[i][0] = max(dp[i - k][0], dp[i - k][1]);
            dp[i][1] = max(dp[i - k][1] + (t[i - k] == t[i] ? 0 : m[t[i]]), dp[i - k][0] + m[t[i]]);
        }
    }
    rep (i, n) {
        rep (j, 2) eprintf("%lld ", dp[i][j]);
        eprintf("\n"); 
    }
    ll ans = 0;
    rep (i, k) {
        if (n - k + i >= 0) ans += max(dp[n - k + i][0], dp[n - k + i][1]);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3664
n = int(input())
s = input()
nin = s[1:n].count("E")
ans = nin
for i in range(n - 1):
    if s[i] == "E" and s[i + 1] == "E":
        nin -= 1
    elif s[i] == "W" and s[i + 1] == "W":
        nin += 1
    if nin < ans:
        ans = nin
print(ans)

Measured memory_bytes: 3700
import math
K = int(input())
b = []
ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        b.append(math.gcd(i, j))
n = len(b)
for i in range(n):
    for k in range(1, K+1):
        ans += math.gcd(b[i], k)
print(ans)

Measured memory_bytes: 9432
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    n=int(input())
    A=np.array(list(map(int,input().split())))
    mod=10**9+7
    ans=0
    for i in range(60):
        c=np.count_nonzero(A&1)
        A>>=1
        ans+=(c*(n-c))<<i%mod
    print(ans%mod)

if __name__=='__main__':
    main()

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

int main(){
    int a, b;
    char op;
    while(1){
        cin >> a >> op >> b;
        if(op == '+'){
            cout << a + b;
        }
        else if(op == '-'){
            cout << a - b;
        }
        else if(op == '*'){
            cout << a * b;
        }
        else if(op == '/'){
            cout << a / b;
        }
        else{
            break;
        }
        cout << endl;
        
    }
}


Measured memory_bytes: 3088
def card_encoder(a):
  result = []
  for i in a:
    s = list(map(str,i))
    c_attr = s[0]
    s.pop(0)
    c_num = int(''.join(s))
    result.append([c_attr,c_num])
  return result

def card_encoder2(a):
  result = []
  for i in a:
    s = list(map(str,i))
    s.pop(0)
    c_num = int(''.join(s))
    result.append(c_num)
  return result

def card_decoder(a):
  result = []
  for t in a:
    result.append(t[0] + str(t[1]))
  return result

def bubble_sort(a,n):
  a = card_encoder(a)
  flag = 1
  while flag:
    flag = 0
    for i in range(1,n)[::-1]:
      if a[i][1] < a[i-1][1]:
        temp = a[i]
        a[i] = a[i-1]
        a[i-1] = temp
        flag = 1
  a = card_decoder(a)
  return a
  
def selection_sort(a,n):
  a = card_encoder(a)
  for i in range(0,n):
    minv = i
    for j in range(i,n):
      if a[j][1] < a[minv][1]:
        minv = j
    if a[i][1] != a[minv][1]:
      temp = a[i]
      a[i] = a[minv]
      a[minv] = temp
  a = card_decoder(a)
  return a

def main():
  num = int(input())
  s = list(input().split())
  bubble1 = bubble_sort(s,num)
  select1 = selection_sort(s,num)
  print(' '.join(bubble1))
  print(is_stable(s,bubble1))
  print(' '.join(select1))
  print(is_stable(s,select1))

def is_stable(a_in, a_out):
  v_in = card_encoder2(a_in)
  n = len(a_in)
  for i in range(0,n):
    for j in range(i + 1,n):
      for a in range(0,n):
        for b in range(a + 1,n):
          if v_in[i] == v_in[j] and a_in[i] == a_out[b] and a_in[j] == a_out[a]:
            return 'Not stable'
  return 'Stable'

main()


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

using namespace std;

#define FOR(i,n) for(int i=0; i<n; ++i)
#define FORR(i,a,n) for(int i=a; i<n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

const int INF = 0x3f3f3f3f;

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
 
//int in() { int x; scanf("%d", &x); return x; }
//ll lin() { ll x; scanf("%lld", &x); return x; }
//void printfv(VI a){ int n = a.size(); FOR(i, n) cout << a[i] << " "; }

bool isPrime(int n) 
{ 
    // Corner case 
    if (n <= 1) 
        return false; 
  
    // Check from 2 to n-1 
    for (int i = 2; i < n; i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
}

int main(void){

    int x;
    cin >> x;

    do {
        if(isPrime(x)){
            cout << x;
            break;
        } else {
            x++;
        }

    } while(true);

    return 0;
}


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

#define SIZE 1024

int main(void){
  int n, i;
  double vecx[SIZE] = {0}, vecy[SIZE] = {0};
  double D[4] = {0};

  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%lf", &vecx[i]);
  for (i = 0; i < n; i++)
    scanf("%lf", &vecy[i]);

  // calculate D1
  D[0] = 0;
  for (i = 0; i < n; i++) {
    if (0 < vecx[i] - vecy[i])
      D[0] += vecx[i] - vecy[i];
    else
      D[0] += vecy[i] - vecx[i];
  }

  // calculate D2
  D[1] = 0;
  for (i = 0; i < n; i++)
    D[1] += pow(vecx[i] - vecy[i], 2);
  D[1] = sqrt(D[1]);

  // calculate D3
  D[2] = 0;
  for (i = 0; i < n; i++) {
    if (0 < vecx[i] - vecy[i])
      D[2] += pow(vecx[i] - vecy[i], 3);
    else
      D[2] += pow(vecy[i] - vecx[i], 3);
  }
  D[2] = cbrt(D[2]);

  // calculate D_infinity
  D[3] = 0;
  for (i = 0; i < n; i++) {
    if (D[3] < vecx[i] - vecy[i])
      D[3] = vecx[i] - vecy[i];
    else if (D[3] < vecy[i] - vecx[i])
      D[3] = vecy[i] - vecx[i];
  }

  for (i = 0; i < 4; i++)
    printf("%lf\n", D[i]);
  return 0;
}

Measured memory_bytes: 744
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define mod 1000003
#define ll long long

int n, m, x, y;
int a[100005];

int main(){
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>x>>y;
        a[x]++;
        a[y]++;
    }
    for(int i=1; i<=n; i++){
        if(a[i]%2){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}


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

int main() {
    ll n,c=0,d=0,m;//q;
    cin>>n;
   // m=n;
       while(n>0)
       {
           if(n>=500)
            {
            c+=n/500;
            n=n%500;
            }
            if(n>=5)
            {
              d+=n/5;
              break;
            }
            break;
            
         
       }
    cout<<c*1000+d*5<<endl;
	// your code goes here
	return 0;
}


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

int main(){
  string s1,s2,s3;
  cin >> s1 >> s2 >> s3;
  if(s1.at(s1.size()-1)==s2.at(0) && s2.at(s2.size()-1)==s3.at(0))cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//define
typedef pair<int,int>pi;
#define elif else if
#define int long long
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define Rep(x,y) for(int k=x;k<y;k++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define vint vector<int>
#define vvint vector<vector<int>>
#define vtr vector<string>
#define vvtr vector<vector<string>>
#define vhar vector<char>
#define mod 100000007
#define elif else if
#define str string

signed main(){
  int N,M,O,P=0,count=0,count2=0,crash=0,nowtab=1;
  double d;
  char C,c;
  str S,T;
  vint v(0);
  cin>>N;
  while(true){
    rep(1,N+1)if(N%i==0)count++;
    if(count==2)break;
    N++;
    count=0;
  }
  cout<<N<<endl;
}


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

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

    if(a > b){
        tmp = a;
        a = b;
        b = tmp;
    }
    if(b > c){
        tmp = b;
        b = c;
        c = tmp;
    }
    if(a > b){
        tmp = a;
        a = b;
        b = tmp;
    }

    cout << a << " " << b << " " << c << endl;

    return 0;
}


Measured memory_bytes: 3088
#include<iostream>
using namespace std;
static const int N = 100;

int main() {
	int M[N][N];
	int n, u, k, v;

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) M[i][j] = 0;
	}
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++) {
			cin >> v;
			v--;
			M[u][v] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if ( j ) cout << " ";
			cout << M[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3084
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
using namespace std;
vector<vector<int>> Graph;
int DP[100010];
bool CAN=true;

int main(){
  ll N,cnt=0LL;
  cin>>N;
  ll A[N];
  REP(i,N){
    cin>>A[i];
    if(A[i]%2==1) cnt++;
  }
  if(cnt%2==0) COYE;
  else CONO;
  return 0;
}

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

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

Measured memory_bytes: 3588
import math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

N = int(input())
P = list(map(int, input().split()))
m = int(1e9)
ans = 0
for e in P:
    if e < m:
        ans += 1
        m = e
print(ans)



Measured memory_bytes: 24744
import itertools


def m():
    N, M, X = map(int, input().split())
    CA = [list(map(int, input().split())) for _ in range(N)]
    ans = float('inf')
    for i in itertools.product([True, False], repeat=N):
        tmp = [0] * (M + 1)
        for j, v in enumerate(i):
            if v:
                for k in range(M + 1):
                    tmp[k] += CA[j][k]
        f = 1
        for p in range(1, M + 1):
            if tmp[p] < X: f = 0
        if f: ans = min(ans, tmp[0])
    return ans if ans != float('inf') else "-1"


print(m())


Measured memory_bytes: 9124
#include <stdio.h>
#define ll long long
#define NUM 5

int main(void){
    ll N;
    ll a[NUM];
    scanf("%lld", &N);
    for(int i = 0; i < 5; i++){
        scanf("%lld", &a[i]);
    }

    ll min_;
    min_ = a[0];
    for(int i = 1; i < 5; i++){
        min_  = a[i] < min_ ? a[i] : min_;
    }

    ll ans = 4 + N / min_;
    if (N % min_ != 0){
        ans += 1;
    }
    
    printf("%lld\n", ans);
    return 0;
}


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

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

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

pub trait LexicalPermutation {
  /// Return `true` if the slice was permuted, `false` if it is already
  /// at the last ordered permutation.
  fn next_permutation(&mut self) -> bool;
}
impl<T> LexicalPermutation for [T] where T: Ord {
  /// Original author in Rust: Thomas Backman <serenity@exscape.org>
  fn next_permutation(&mut self) -> bool {
    // These cases only have 1 permutation each, so we can't do anything.
    if self.len() < 2 { return false; }

    // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
    let mut i = self.len() - 1;
    while i > 0 && self[i-1] >= self[i] {
      i -= 1;
    }

    // If that is the entire vector, this is the last-ordered permutation.
    if i == 0 {
      return false;
    }

    // Step 2: Find the rightmost element larger than the pivot (i-1)
    let mut j = self.len() - 1;
    while j >= i && self[j] <= self[i-1]  {
      j -= 1;
    }

    // Step 3: Swap that element with the pivot
    self.swap(j, i-1);

    // Step 4: Reverse the (previously) weakly decreasing part
    self[i..].reverse();

    true
  }
}
fn main() {
  let (n, r) = {
    let tmp: Vec<usize> = read_vec();
    (tmp[0], tmp[1])
  };

  let ans = if (n >= 10) {
    0
  } else {
    100 * (10 - n)
  };

  println!("{}", r + ans);
}

Measured memory_bytes: 4352
#include "bits/stdc++.h"
using namespace std;
int main(){
  int N, K, X, Y;
  cin >> N;
  cin >> K;
  cin >> X;
  cin >> Y;
  if(N < K)
    cout << N * X << endl;
  else
    cout << K * X + (N - K) * Y << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define MAX 1000

using namespace std;

int N, ans, cnt, sum;
bool flg;

int main() {
	int L;
	string S[101];
	cin >> N >> L;
	rep(i,N) cin >> S[i];

	sort(S, S + N);

	rep(i, N) cout << S[i];
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int w = sc.nextInt();
		int[] value = new int[w];
		for (int i = 0; i < w; i++) value[i] = i + 1;
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			String str = sc.next();
			String[] ab = str.split(",");
			int a = Integer.parseInt(ab[0]) - 1;
			int b = Integer.parseInt(ab[1]) - 1;
			int c = value[a];
			value[a] = value[b];
			value[b] = c;
		}
		for (int i = 0; i < w; i++) System.out.println(value[i]);
	}
}



Measured memory_bytes: 26088
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

A,B = inputIL()

G = gcd(A,B)

if G == 1:
  print(1)
  exit()

print(len(factorization(G))+1)

Measured memory_bytes: 64492
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int 
#define pb push_back 
#define mp make_pair 
#define pii pair <int , int > 
#define pll pair < ll , ll >
int main(){
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
	ll n ;
	cin >> n ;
	ll arr[n] , x = 0 ;
	for(int i = 0 ; i < n ; i++){
		cin >> arr[i] ;
		x ^= arr[i] ;
	}
	for(int i = 0 ; i < n ; i++){
		cout << (arr[i]^x) << " " ;
	}
}

Measured memory_bytes: 5092
#include<stdio.h>
#include<bitset>
int main()
{
	const int N=50001;
	int i,j,n,c;
	std::bitset<N>p(3);
	p.flip();
	for(i=2;i*i<N;++i)if(p[i])for(j=i*2;j<N;j+=i)p[j]=0;
	while(scanf("%d",&n),n)
	{
		for(c=i=0,j=n;i<=j;++i,--j)if(p[i]&&p[j])++c;
		printf("%d\n",c);
	}
	return 0;
}

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

int main() {
  int n, i;
  cin >> n;
  
  vector<int> a(n), b(n), c(n);
  for(i = 0; i < n; i++){
    cin >> a.at(i);
  }
  for(i = 0; i < n; i++){
    cin >> b.at(i);
  }
  for(i = 0; i < n; i++){
    cin >> c.at(i);
  }
  
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());
  
  long long ans = 0, aa, cc;
  for(i = 0; i < n; i++){
    auto pos_a = lower_bound(a.begin(), a.end(), b.at(i));
    aa = distance(a.begin(), pos_a);
    auto pos_c = upper_bound(c.begin(), c.end(), b.at(i));
    cc = distance(c.begin(), pos_c);
    ans += aa * (n - cc);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 1536
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;

int main() {
  vector<int> A(3); cin >> A[0] >> A[1] >> A[2];
  int K; cin >> K;
  sort(A.begin(),A.end());
  for (int i = 0; i < K; ++i) A[2] *= 2;
  int sum = A[0] + A[1] + A[2];
  cout << sum << endl;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define int long long
using P = pair<int, int>;
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};
constexpr int INF = 1234567890;
constexpr int MOD = 1000000000 + 7;
// constexpr int MOD = 998244353;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int fact(int n) { return n > 1 ? n * fact(n - 1) % MOD : 1; }
int modinv(int a)
{
    int b = MOD, u = 1, v = 0;
    while (b)
    {
        int t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= MOD;
    if (u < 0)
        u += MOD;
    return u;
}
constexpr int modpow(int a, int n)
{
    int rtn = 1;
    while (n > 0)
    {
        if (n & 1)
            rtn = rtn * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return rtn;
}

// to node, color(void: 0), index
vector<vector<array<int, 3>>> to;
int colorval = 0;

void dfs(int node, int past_color)
{
    int color = 1;
    for (auto &&toi : to[node])
    {
        if (color == past_color)
            color++;

        toi[1] = color;
        dfs(toi[0], color);

        colorval = max(color, colorval);
        color++;
    }
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(10);

    int n;
    cin >> n;
    to.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        to[a - 1].push_back({b - 1, 0, i});
    }
    dfs(0, 0);
    vector<int> ans(n - 1);
    for (auto &&toi : to)
    {
        for (auto &&toj : toi)
        {
            ans[toj[2]] = toj[1];
        }
    }

    cout << colorval << endl;
    for (auto &&x : ans)
    {
        cout << x << endl;
    }
}


Measured memory_bytes: 6784
//
// Created by kuroneko on 2019-08-04.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <sstream>

using namespace std;

typedef long long ll;

#define INF 1000000000000009LL
#define MOD 1000000007LL

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight):src(src), dst(dst), weight(weight) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

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

    int cnt = 0, i = 1, j = 1;
    bool flag = true;

    while (1) {
        i *= 10;
        if (i <= N) {
            if (flag) cnt += i - j;
        } else {
            if (flag) {
                cnt += N - j + 1;
            }
            break;
        }
        j = i;
        flag = !flag;
    }

    cout << cnt << endl;
}


Measured memory_bytes: 888
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
k,a,b=IL()
ans=1
if a>=b:
    ans=1+k
else:
    if b-a<=2:
        ans=1+k
    else:
        if a-1+2>k:
            ans=1+k
        else:
            k=k-(a+1)
            ans=b
            ans+=(k//2)*(b-a)+k%2
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			double a = sc.nextDouble();
			double b = sc.nextDouble();
			double c = sc.nextDouble();
			double d = sc.nextDouble();
			double e = sc.nextDouble();
			double f = sc.nextDouble();
			double x;
			double y;
			/*
			ax + by = c
			dx + ey = f
			*/
			y = (c*d - f*a) / (b*d - e*a);
			x = (c - b*y)/a;
			System.out.printf("%.3f %.3f\n",x,y);
		}
	}
}

Measured memory_bytes: 28424
s = list(input())

k, m, n, h = 0, 0, 0, 0

if 'N' in s:
    k = 1
if 'S' in s:
    m = 1
if 'W' in s:
    n = 1
if 'E' in s:
    h = 1

if (abs(k-m))%2 == 0 and (abs(n-h))%2 == 0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
import heapq 

def main():
    Q = int(input())
    ans = 0
    l = []
    r = []
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            ans += query[2]
            heapq.heappush(l, -query[1])
            heapq.heappush(r, query[1])
            if -l[0] > r[0]:
                l_max = -1 * heapq.heappop(l)
                r_min = heapq.heappop(r)
                ans += abs(l_max-r_min)
                heapq.heappush(l, -r_min)
                heapq.heappush(r, l_max)

        else:
            print(-l[0],ans)






if __name__ == "__main__":
    main()

Measured memory_bytes: 93528
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner (System.in)){
			double a = sc.nextDouble();
			double b = sc.nextDouble();
			double C = sc.nextDouble();
			
			C = Math.toRadians(C);

			double S,L,h;

			S = 0.5*a*b*Math.sin(C);
			L = a + b + Math.sqrt(Math.pow(a,2)+Math.pow(b,2)-(2*a*b*Math.cos(C)));
			h = b*Math.sin(C);

			System.out.printf("%.8f\n",S);
			System.out.printf("%.8f\n",L);
			System.out.printf("%.8f\n",h);
		}
	}
}



Measured memory_bytes: 28280
n=int(input())
ls=list(map(int,input().split()))

right_odd=0
right_even=0
left_odd=0
left_even=0
for i in range(len(ls)):
    if (i+1)%2==0:
        right_even+=ls[i]
    else:
        right_odd+=ls[i]
total=right_odd+right_even
right_odd-=ls[0]
ans=[]
for i in range(n):
    if (i+1)%2==1:
        k=i
        ans.append(total-(right_even+left_odd)*2)
        if k>=n-1:
            k%=n
        if k!=n-1:
            right_even-=ls[k+1]
        left_odd+=ls[k]
    else:
        k=i
        ans.append(total-(right_odd+left_even)*2)
        if k>n:
            k%=n
        right_odd-=ls[k+1]
        left_even+=ls[k]

print(" ".join(list(map(str,ans))))

Measured memory_bytes: 19504
#include<stdio.h>
int main(){
  int A[2][101]={},i,j,n,t=0;
  scanf("%d",&n);
  for(i=0;i<2;i++)for(j=1;j<=n;j++){scanf("%d",&A[i][j]);A[i][j]+=A[i][j-1];}
  for(i=1;i<=n;i++){j=A[0][i]+A[1][n]-A[1][i-1];t=j<t?t:j;}
  printf("%d",t);
}


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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{int x,y,t;};
struct Edge{int to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  Graph(int n):E(n){E.resize(n);V=n;}
  void add_edge(int from,int to,int cost){E[from-1].pb({to-1,cost});}
};
int main(){
  ll w,h;cin>>w>>h;
  vector<ll>width(w),height(h);
  for(int i=0;i<w;i++)
    cin>>width[i];
  for(int j=0;j<h;j++)
    cin>>height[j];
  sort(ALL(width));
  sort(ALL(height));
  ll wcnt=0,hcnt=0;
  ll ans=0;
  ll sum=0;
  while(sum<(h+1)*(w+1)-1){
    if((wcnt==w)||(hcnt!=h&&height[hcnt]<width[wcnt])){
      ans+=height[hcnt]*(min(w+1-wcnt,((h+1)*(w+1)-1)-sum));
      sum+=min(w+1-wcnt,((h+1)*(w+1)-1)-sum);
      hcnt++;
    }else{
      ans+=width[wcnt]*(min(h+1-hcnt,((h+1)*(w+1)-1)-sum));
      sum+=min(h+1-hcnt,((h+1)*(w+1)-1)-sum);
      wcnt++;
    }
    // cout<<sum<<" "<<ans<<" "<<hcnt<<" "<<wcnt<<endl;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1920
//
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MOD 1000000007
#define PI 3.14159265
#define EPS 1e-9
#define Pi acos(-1.0)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define forr(i,a,b) for(int i=(a); i<(b); i++)
#define clean(arr,val) memset(arr,val,sizeof(arr))
#define forn(i,n) forr(i,0,n)
#define PB push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vpll;

/*CODE START HERE*/

int n, m, sum;
int arr[55];

int main(){
    ios::sync_with_stdio(0);
    cin >> n >> m;
    forn(i,n) cin >> arr[i];
    sort(arr,arr+n,greater<int>());
    sum = 0;
    forn(i,m) sum+=arr[i];
    cout << sum << "\n";
    return 0;
}

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

int GetDigit(int num){
	int digit=0;
	while(num!=0){
		num/=10;
		digit++;
	}
	return digit;
}

int main(){
	long N;
	cin>>N;
	int keta=GetDigit(N);
	stack<vector<int> >S;
	vector<int>status;
	for(int i=0;i<keta;++i){
		status.push_back(0);
	}
	S.push(status);
	int ans=0;
	while(!S.empty()){
		vector<int>now=S.top();
		status=S.top();
		S.pop();
		/*
		for(int i=0;i<status.size();++i){
			cout<<status[i]<<" ";
		}
		cout<<endl;
		*/
		for(int i=0;i<keta;++i){
			if(status[i]==0){
				status[i]=3;
				S.push(status);
				status[i]=5;
				S.push(status);
				status[i]=7;
				S.push(status);
				break;
			}
		}
		while(now[now.size()-1]==0 && now.size()>0)now.pop_back();
		/*
		for(int i=0;i<now.size();++i){
			cout<<now[i]<<" ";
		}
		cout<<endl;
		*/
		int tmp=0;
		int judge3=0;
		int judge5=0;
		int judge7=0;
		for(int i=0;i<now.size();++i){
			if(now[i]==3)judge3=1;
			if(now[i]==5)judge5=1;
			if(now[i]==7)judge7=1;
			//cout<<pow(10,now.size()-i-1)<<endl;
			tmp+=now[i]*pow(10,now.size()-i-1);
		}
		if(judge3==1 && judge5==1 && judge7==1 && tmp<=N)ans++;
	}
	cout<<ans<<endl;
}


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

#define PI 3.14159265358979323846264338327950L
#define ll long long
#define lli long long int
#define lld long double

using namespace std;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    char s;
    cin >> s;
    if (s >= 'a' && s <= 'z') {
        cout << 'a' << "\n";
    } else {
        cout << 'A' << "\n";
    }
    return 0;
}


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


int main() {
  string s;
  cin >> s;
  if (s=="hi" || s=="hihi" || s=="hihihi" || s=="hihihihi" || s=="hihihihihi" || s=="hihihihihihi" || s=="hihihihihihihi" || s=="hihihihihihihihi" || s=="hihihihihihihihihi" || s=="hihihihihihihihihihi") cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iomanip>
#include<string>
#include <numeric>
using namespace std;
int a[810];
#define rep(i,n) for(int i=0;i<n;i++)
int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << a - (b + c - d) << endl;
}



Measured memory_bytes: 3092
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

#define FOR(i,l,r) for(size_t i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define INF 100000000000ULL



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

	size_t s, w;
	cin >> s >> w;

	if (s <= w) {
		cout << "unsafe" << endl;
	}
	else {
		cout << "safe" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3648
while True:
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        break
    for tate in range(a):
        for yoko in range(b):
            if tate % 2 == 0:
                if yoko % 2 == 0:
                    print("#" ,end="")
                else:
                    print("." ,end="")
            else:
                if yoko % 2 == 0:
                    print("." ,end="")
                else:
                    print("#" ,end="")
        print()
    print()


Measured memory_bytes: 7000
#include <iostream>
#include <unordered_map>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;

#define Nmax 100001

int Q[Nmax];
char W[Nmax];
vector<int> G[Nmax];

void bfs(int node) {
    int st, dr;
    Q[st = dr = 0] = node;
    while (st <= dr) {
        node = Q[st];
        for (auto it : G[node]) {
            if (!W[it]) {
                Q[++dr] = it;
                W[it] = 1;
            }
        }
        ++st;
    }
}

int main() {
    int N, M, A, B;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    int nr = 0;
    for (int i = 1; i <= N; ++i) {
        if (!W[i]) {
            ++nr;
            bfs(i);
        }
    }
    cout << nr - 1;
    return 0;
}


Measured memory_bytes: 9152
#ifdef MY_LOCAL
#define MY_NAMESPACE(ns) namespace ns {
#define MY_NAMESPACE_    }
#define MY_DEBUG(s)      s
#else
#define MY_NAMESPACE(ns) 
#define MY_NAMESPACE_    
#define MY_DEBUG(s)      
#endif

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define EPS (1e-7)
#define IINF ((int)1e9)


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

	int n;
	cin >> n;

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

	ll target = 0;  // (new a[0])^(new a[1]) must equal a[2]^...^a[n-1] for Takahashi to win the Nim game
	for (int i = 2; i < n; i++)
	{
		target ^= a[i];
	}

	// square-division
	// record all the results which satisfies (new a[0])^(new a[1])=target at the lower 20 bits (as 10^12 = 2^39.9)
	vector<ll> result_candidates;
	ll ceil_num_to_move_low20 = min((ll)(1 << 20), a[0]);
	for (ll num_to_move_low20 = 0; num_to_move_low20 < ceil_num_to_move_low20; num_to_move_low20++)
	{
		ll post_move_check = (a[0] - num_to_move_low20) ^ (a[1] + num_to_move_low20) ^ target;
		if ((post_move_check & (1 << 20) - 1) == 0)
			result_candidates.push_back(num_to_move_low20);
	}

	// higher 20 bits
	ll res = (ll)1 << 50;
	for (auto this_num_to_move_low20 : result_candidates)
	{
		for (ll num_to_move = this_num_to_move_low20; num_to_move < min(res, a[0]); num_to_move += (1 << 20))
		{
			ll post_move_check = (a[0] - num_to_move) ^ (a[1] + num_to_move) ^ target;
			if (post_move_check == 0)
				res = min(res, num_to_move);
		}
	}

	if (res == (ll)1 << 50)
		res = -1;
	cout << res << "\n";
	return 0;
}
MY_NAMESPACE_

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

ll cnt[100010];
int main() {
	ll n,k;
	cin>>n>>k;
	priority_queue<ll>q;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		q.push(now);
	}
	while(k!=0){
		k--;
		ll now=q.top();
		q.pop();
		now/=2;
		q.push(now);
	}
	ll ans=0;
	while(q.size()!=0){
		ll now=q.top();
		ans+=now;
		q.pop();
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 4256
#include <cstdio>
#include <string>
#include <vector>

using namespace std;
int r, c;

string ConvertDecToBinString(int dec_num) {
    if (dec_num == 0) { return string("0"); }
    string bin_num_str;
    while (dec_num) {
        if ((dec_num & 1) == 0) { bin_num_str.insert(bin_num_str.begin(), '0'); }
        else { bin_num_str.insert(bin_num_str.begin(), '1'); }
        dec_num >>= 1;
    }

    return bin_num_str;
}

int GetTurnOverMaxGoodNum(vector<vector<int> >& senbeis, int raw) {
    string bin_raw_string = ConvertDecToBinString(raw);
    for (size_t i = 0; i < r; i++) {
        if (bin_raw_string[i] == '1') {
            for (size_t j = 0; j < c; j++) {
                senbeis[i][j] = 1 - senbeis[i][j];
            }
        }
    }

    int max_good_senbei_num = 0;
    for (size_t j = 0; j < c; j++) {
        int zero_num = 0;
        for (size_t i = 0; i < r; i++) {
            if (senbeis[i][j] == 0) { zero_num++; }
        }
        max_good_senbei_num += max(zero_num, r - zero_num);
    }

    for (size_t i = 0; i < r; i++) {
        if (bin_raw_string[i] == '1') {
            for (size_t j = 0; j < c; j++) {
                senbeis[i][j] = 1 - senbeis[i][j];
            }
        }
    }

    return max_good_senbei_num;
}

int main() {
    scanf("%d %d", &r, &c);
    while (r * c != 0) {
        auto senbeis = vector<vector<int> >(r, vector<int>(c));
        int max_good_senbei_num = 0;
        for (size_t i = 0; i < r; i++) {
            for (size_t j = 0; j < c; j++) {
                scanf("%d", &senbeis[i][j]);
            }
        }
        for (size_t i = 0; i < 2 << (r - 2) + 1; i++) {
            int good_num = GetTurnOverMaxGoodNum(senbeis, i);
            if (max_good_senbei_num < good_num) { max_good_senbei_num = good_num; }
        }
        printf("%d\n", max_good_senbei_num);
        scanf("%d %d", &r, &c);
    }

    return 0;
}

Measured memory_bytes: 3080
import sys

board=[[0]*10 for i in xrange(10)]

large=[[0,0,1,0,0],
       [0,1,1,1,0],
       [1,1,1,1,1],
       [0,1,1,1,0],
       [0,0,1,0,0],]
middle=[[0,0,0,0,0],
        [0,1,1,1,0],
        [0,1,1,1,0],
        [0,1,1,1,0],
        [0,0,0,0,0],]
small=[[0,0,0,0,0],
       [0,0,1,0,0],
       [0,1,1,1,0],
       [0,0,1,0,0],
       [0,0,0,0,0],]

size=[0,small,middle,large]

def isOnBoard(y,x):
    return 0<=y<10 and 0<=x<10

for line in sys.stdin.readlines():
    x,y,s=map(int,line.strip().split(","))
    for i in xrange(-2,3):
        for j in xrange(-2,3):
            if isOnBoard(y+i,x+j):
                board[y+i][x+j]+=size[s][i+2][j+2]

print len([j for i in board for j in i if j==0])
print max([i for j in board for i in j])

Measured memory_bytes: 4280
# -*- coding: utf-8 -*-

import sys
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def lcm(x, y): return (x * y) // gcd(x, y)

A,B,C,D=MAP()

cntC=B//C-(A-1)//C
cntD=B//D-(A-1)//D
CD=lcm(C, D)
cntCD=B//CD-(A-1)//CD
AB=B-A+1
print(AB-cntC-cntD+cntCD)


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

int N;
vector<int> L;

void solve() {
		cin >> N;
		int v;
		for (int i = 0; i < 2*N; i++) {
			cin >> v;
			L.push_back(v);
		}
		sort(L.begin(),L.end());
		int ans = 0;
		for (int i = 0; i < 2*N; i += 2) ans += min(L[i],L[i+1]);
		cout << ans << endl;
		
}

int main() {
	solve();
}

Measured memory_bytes: 256
while True:
    a=int(input())
    if a==0:
        break
    b=1
    for i in range(1,a+1):
       b=b*i
    j=0
    while True:
        if b%10 != 0:
            break
        b=b//10
        j=j+1
    print(j)    


Measured memory_bytes: 5624
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=100005;
int n,a[MAX];
int winner,current;
int gcd(int x,int y)
{
	if(x%y==0) return y;
	else return gcd(y,x%y);
}
void change(int pistol)
{
	int temp;
	a[pistol]--;
	temp=a[1];
	for(int i=2;i<=n;++i){
		temp=gcd(temp,a[i]);
	}
	for(int i=1;i<=n;++i){
		a[i]/=temp;
	}
}
bool check()
{
	int even=0,odd=0,pistol=0;
	for(int i=1;i<=n;++i){
		if(a[i]%2==0) even++;
		else{
			odd++;
			if(a[i]!=1) pistol=i;	
		} 
	}
	if(even%2==1){
		winner=current;
		return true;
	}
	if(odd>=2){
		winner=1-current;
		return true;
	}
	if(odd==1&&pistol==0){
		winner=1-current;
		return true;
	}
	change(pistol);
	return false;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	current=1;
	while(!check()) current=1-current;
	if(winner==1) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(long long i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;



int main() {
    int l;
    cin >> l;
    long double ans;
    ans = l*l*l/27.0;
    cout << fixed << setprecision(15) << ans << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
x = list(map(int, input().split()))


l = []
# 連続するK本の選び方について、左端は0,1,2,...,N-K
for i in range(N - K + 1):
    left = i
    right = i + K - 1
    # leftが先、rightが後の場合
    ans1 = abs(x[left]) + abs(x[right] - x[left])
    # rightが先、leftが後の場合
    ans2 = abs(x[right]) + abs(x[right] - x[left])
    tmp_ans = min(ans1, ans2)
    l.append(tmp_ans)

ans = min(l)
print(ans)


Measured memory_bytes: 20064
#include <iostream>
#include <math.h>

using namespace std;
int L = (int)pow(10., 9.) + 7;

int fib(long *p, int n)
{
  if (n < 0) return 0;
  if (p[n] != 0) return p[n];
  else return p[n] = (fib(p, n-1) + fib(p, n-2)) % L;
}

int main()
{
  int n, m;
  cin >> n >> m;
  long f[n+1] = {1, 1};
  
  if (m == 0) cout << fib(f, n) % L << endl;
  else{
    int a[m+2];
    a[0] = -1;
    for (int i = 1; i < m + 1; i++) cin >> a[i];
    a[m+1] = n+1;

    long sum = 1;
    for (int i = 1; i <= m + 1; i++) sum = sum * fib(f, a[i] - a[i-1] - 2 ) % L;

    cout << sum << endl;
  }
  return 0;
}
  
    

Measured memory_bytes: 5760
#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=1e9+7;
const LL LINF=1LL<<62;



int main(){
    int N;
    cin >> N;
    int ans=0;
    for(int i=1;i<=N;i++){
        int c=0;
        for(int j=1;j<=N;j++){
            if((i%j==0)&&j%2) c++; 
        }
        if(c==8) ans++;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main() {
  int K;
  cin >> K;
  
  int ans = 0;
  for (int a = 1; a <= K; ++a) {
    for (int b = 1; b <= K; ++b) {
      for (int c = 1; c <= K; ++c) {
        ans += gcd(a, gcd(b, c));
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3176
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a, b) ((a < b) ? a : b)
#define _max(a, b) ((a < b) ? b : a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a) ? 1 : -1)
#define SORT(v) sort(v.begin(), v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

int main() {
    cout << fixed << setprecision(10);
    int N;
    cin >> N;
    vector<int> v(N);
    REP(i, N) cin >> v[i];
    vector<int> c;
    for(int i = N - 1; 0 <= i; i--) {
        auto d = upper_bound(c.begin(), c.end(), v[i]);
        if(c.end() == d) {
            c.push_back(v[i]);
        } else {
            *d = v[i];
        }
    }
    cout << c.size();
    return 0;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e13;
const int mod = 1e9+7;
#define ll long long
signed main() {
    int n,p;
    cin>> n>>p;
    bool odd = false;
    rep(i,n) {
        int x;
        cin >> x;
        if(x%2==1) odd = true;
    }
    if(!odd) cout << (int)pow(2,n)*((p+1)%2) << endl;
    else cout << (int)pow(2,n-1) << endl;
    return 0;
}



Measured memory_bytes: 4064
import sys
input = sys.stdin.readline

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)


Measured memory_bytes: 159636