akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;

template<class _T> static void getint(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}

static void AGC031A();

#if 1
int main()
{
	AGC031A();
	fflush(stdout);
	return 0;
}
#endif

static void AGC031A()
{
	int N;
	getint(N);

	std::string orgs;
	std::cin >> orgs;

	std::map<char, LLONG> chars;
	for (int i = 0; i < N; i++) {
		chars[orgs[i]]++;
	}

	LLONG ans = 1;
	for (auto it = chars.begin(); it != chars.end(); it++) {
		ans = (ans * (it->second + 1)) % MOD_NUM;
	}
	printf("%lld\n", ans - 1);
}



Measured memory_bytes: 512
from collections import deque
import copy


H, W = map(int, input().split())
S = [list(input()) for i in range(H)]


def bfs(maze, start):
    q = deque()
    q.append((start, 0))

    max_depth = 0

    while len(q) > 0:
        p, depth = q.popleft()

        if p[0] < 0 or H <= p[0]:
            continue
        if p[1] < 0 or W <= p[1]:
            continue
        if maze[p[0]][p[1]] == "#":
            continue

        maze[p[0]][p[1]] = "#"
        max_depth = depth

        next_pos = [
            (p[0]-1, p[1]),
            (p[0]+1, p[1]),
            (p[0], p[1]-1),
            (p[0], p[1]+1),
        ]

        for pos in next_pos:
            q.append((pos, depth+1))

    return max_depth


depth = 0
for h in range(H):
    for w in range(W):
        maze = copy.deepcopy(S)
        depth = max(depth, bfs(maze, (h, w)))

print(depth)


Measured memory_bytes: 51932
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ n, a, b ] <- map fromIntegral <$> readInts
	xs :: [Integer] <- map fromIntegral <$> readInts
	let
		ds = zipWith (-) ( tail xs ) xs
	print $ sum $ zipWith min ( repeat b ) $ map ( * a ) ds

Measured memory_bytes: 2940
a, b, k = map(int, input().split())

def make_divisors(n): # 約数列挙
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

a_d = set(make_divisors(a))
b_d = set(make_divisors(b))
d = sorted(list(a_d & b_d), reverse=True)

print(d[k-1])

Measured memory_bytes: 9156
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	b := next()
	m := map[string]string{
		"A": "T", "T": "A", "C": "G", "G": "C",
	}

	fmt.Println(m[b])
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{
   int a ,b, i;

for(int i=1;i<=3000 ;i++){
    cin >> a >> b;
if (a>b)
{
   a = a+b;
   b = a-b;
   a = a-b;
}
   if (a==0 && b==0)
   break ;
   else
  
   cout << a << " " << b<< endl;
}
}


Measured memory_bytes: 2996
using System;
namespace ConsoleTest {
  class Program {
    static void Main(string[] args) {
      string a = Console.ReadLine();
      int b = 0;
      for (int i = 0; i < a.Length; i++) {
        b += int.Parse(a.Substring(i, 1));
      }
      Console.WriteLine((int.Parse(a) % b == 0) ? "Yes" : "No" );
    }
  }
}

Measured memory_bytes: 13140
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c; cin >> a >> b >> c;
    int k; cin >> k;
    while (k-->0) {
        if (a >= b) b <<= 1;
        else if (b >= c) c <<= 1;
    }
    if (a < b && b < c) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}


Measured memory_bytes: 3648
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define divup(a,b) ( ( (a) + ( (b) - 1u) ) / (b) ) // a/b の余り切り上げ
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
const ll mod = 1000000007;
const ll mod9 = 1000000009;


ll fib[50];
signed main(){
    ll n;
    scanf("%lld",&n);
    rep(i,n+1){
        if(i==0 || i==1) fib[i]=1;
        else fib[i]=fib[i-1]+fib[i-2];
    }
    printf("%lld\n",fib[n]);
}



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

using namespace std;

typedef long long ll;
typedef long double ld;

#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(v) v.begin(),v.end()

const int maxn = 1e5 + 100;
const ll inf = 2e18, mod = 1e9 + 7;

int n, a[maxn], cnt[maxn];
ll ans = 1;

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

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

	for (int i = 0; i < n; i++)
	{
		if (a[i] == 0)
			ans = ans * (3 - cnt[0]) % mod;
		else
			ans = ans * (cnt[a[i] - 1] - cnt[a[i]]) % mod;
		cnt[a[i]]++;
	}
	cout << ans << endl;
}



Measured memory_bytes: 1024
#include<stdio.h>
#include<map>
#include<string>
#include<string.h>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<math.h>
#include<stack>
#include<set>
#define INF 2147483647
#define n 300000
#define loop(i, a, b) for(int i=a; i<=b; i++)
#define mem(arr) memset(arr, 0, sizeof(arr));
using namespace std;
typedef long long lli;
typedef double llf;
typedef pair<int, int> P;
struct edge{
	int to, weight;
};
void solve();
int main()
{
	int times = 1;
//	cin >> times;
	loop(i, 1, times)
	{
		solve();
		cout << '\n';
	}
	return 0;
}
vector<edge> V[n + 50];
int a, b, c, d, e, f;
int arr[n + 50], arr1[n + 50], arr2[n + 50];
string str, str1, str2;

void solve()
{
	cin >> str1 >> str2;
	str2 += str1;
	cout << str2;		
}

Measured memory_bytes: 8704
#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,x[1001],sum;
    double sd,v,m;
    while(1)
    {
        scanf("%d",&n);
        if(n==0)
            break;
        sd=0;
        sum=0;
        v=0;
        for(i=0; i<n; i++)
        {
            scanf("%d",&x[i]);
            sum+=x[i];
        }
        m=(double)sum/n;
        for(i=0; i<n; i++)
        {
            v+=((x[i]-m)*(x[i]-m));
        }
        sd=sqrt(v/n);
        printf("%.8lf\n",sd);
    }
    return 0;
}



Measured memory_bytes: 2052
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ll long long

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

  ll d[5010];
  for(int i=0;i<k;i++){
    scanf("%lld",&d[i]);}

  for(int i=0;i<q;i++){
    ll n,x,m;
    scanf("%lld %lld %lld",&n,&x,&m);
    ll an=x%m,tmp;
    ll zeros=0;
    ll amari = (n-1)%k;
    for(int j=0;j<k;j++){
      tmp = d[j]%m;
      if(amari>j){
	if(tmp==0) zeros+=(n-1)/k+1;
	an += ((n-1)/k+1)*tmp;}
      else{
	if(tmp==0) zeros+=(n-1)/k;
	an+=((n-1)/k)*tmp;}}
    //printf("%lld %lld %lld\n",zeros,an,n-1);
    ll ans = n-1-zeros-an/m;
    printf("%lld\n",ans);}
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;

int main() {
  string s;
  cin >> s;
  vi was(4);
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == 'N') was[0] = 1;
    if (s[i] == 'S') was[1] = 1;
    if (s[i] == 'W') was[2] = 1;
    if (s[i] == 'E') was[3] = 1;
  }
  if (was[0] + was[1] == 1 || was[2] + was[3] == 1) cout << "No\n";
  else cout << "Yes\n";
  return 0;
}

Measured memory_bytes: 764
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().solve();
		return;
	}

	private void solve() {
		// 入力
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int roads[] = new int[N + 1];
		for (int i = 0; i < M; i++) {
			roads[sc.nextInt()]++;
			roads[sc.nextInt()]++;
		}
		sc.close();

		// 出力
		for (int i = 1; i < roads.length; i++) {
			System.out.println(roads[i]);
		}

		return;
	}
}


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

using namespace std;

typedef long long ll;
typedef vector<long long> vll;

// Prefix Sum + Binary Search
int solve(vll A, vll B, int k) {
    int res = 0;
    for (size_t i = 1; i < A.size(); ++i) {
        A[i] += A[i - 1];
        if (A[i] <= k) {
            res = max(res, static_cast<int>(i + 1));
        }
    }
    for (size_t i = 1; i < B.size(); ++i) {
        B[i] += B[i - 1];
        if (B[i] <= k) {
            res = max(res, static_cast<int>(i + 1));
        }        
    }
    
    for (size_t i = 0; i < A.size(); ++i) {
        if (A[i] > k) {
            break;
        }
        ll target = k - A[i];
        auto it_B = lower_bound(B.begin(), B.end(), k - A[i]);
        if (it_B - B.begin() >= static_cast<int>(B.size())) {
            continue;
        }
        int j = (*it_B == target) ? it_B - B.begin() : it_B - B.begin() - 1;
        if (j < static_cast<int>(B.size())) {
            res = max(res, static_cast<int>(i + j + 2));
        }
    }

    return res;
}

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

	int n, m, k; cin >> n >> m >> k;
    int a;
    vll A, B;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        A.push_back(a);
    }
    for (int i = 0; i < m; ++i) {
        cin >> a;
        B.push_back(a);
    }

    cout << solve(A, B, k) << endl;
}


Measured memory_bytes: 9520
#include <stdio.h>

int main() {
	int n, i, m, x, v[20], c[20];
	scanf("%d", &n);
	m = 0;
	for (i = 0; i < n; i++) scanf("%d", &v[i]);
	for (i = 0; i < n; i++) scanf("%d", &c[i]);
	for (i = 0; i < n; i++) {
		x = v[i] - c[i];
		if (x > 0) m += x;
	}
	printf("%d", m);
}

Measured memory_bytes: 128
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    String s;
    char[] c;
    int i, n;

    for(;sc.hasNext();){
      s = sc.next(); c = new char[s.length()];
      for(i = 0;i < s.length();i++)c[i] = s.charAt(i);
      for(i = 0;i < s.length();i++){
        if(c[i] != '@')out.print(c[i]);
        else{
          n = (int)(c[++i] - '0');
          for(i++;n-- > 0;)out.print(c[i]);
        }
      }
      out.println();
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 17132
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;
// #define int long long
mt19937 rnd(time(0));
typedef long long ll;
typedef long double ld;

// #define _GLIBCXX_DEBUG
#define f first
#define s second
#define pb push_back
#define pii pair<int, int> 
#define vi vector<int>
#define int ll

void solve(){
	ld a, b, c;
	cin >> a >> b >> c;
	if (a + b + 2 * sqrtl(a * b) < c) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t = 1;
	while(t--){
		solve();
	}
	
	return 0;
}


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

using namespace std;
using ll = long long;

int main() {
    ll a, b, c;cin >> a >> b >> c;
    if (((c - a - b) > 0) && (((c - a - b) * (c - a - b) - 4 * a * b) > 0)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

using namespace std;

#define all(v) (v).begin(), (v).end()

using li = long long;
using ld = long double;

void solve(bool);

int main() {
#ifdef YA
    auto s = clock();
    assert(freopen("input.txt", "r", stdin));
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif

    cout << fixed << setprecision(20);

    solve(true);

#ifdef YA1
    while (true) solve(false);
#endif

#ifdef YA
    cout << endl << endl << "time = " << (clock() - s) / (double)CLOCKS_PER_SEC << endl;
#endif

    return 0;
}

void solve(bool __attribute__((unused)) read) {
	li n, k;
    cin >> n >> k;
    if (2 * k - 1 <= n)
        cout << "YES\n";
    else
        cout << "NO\n";
}

// IDI OBRATNO KOD SMOTRET, RANO POKA SUBMITIT


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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const ll MOD = 1000000007;
const int MN = 5010;

inline void add(int &x, int y) { x += y; if (x >= MOD) x -= MOD; }

int N;
ll dv[MN];
vi g[MN];
int dp[2][MN][2][MN];
int sz[MN];
int u[MN];

void dfs(int v, int p) {
	sz[v] = 1;
	dp[0][v][0][1] = 1;
	int c = 0, f = 1;

	for (int to : g[v]) if (to != p) {
		dfs(to, v);
		for (int j = 0; j <= sz[v] + sz[to]; ++j) {
			dp[f][v][0][j] = dp[f][v][1][j] = 0;
		}

		for (int j = 0; j <= sz[v]; ++j) {
			for (int k = 0; k <= sz[to]; ++k) {
				rep(p, 2) if (dp[c][v][p][j] != 0) {
					rep(q, 2) if (dp[u[to]][to][q][k] != 0) {
						ll t = dp[u[to]][to][q][k];
						//connect
						add(dp[f][v][(p+q)&1][j+k], (ll)dp[c][v][p][j] * dp[u[to]][to][q][k] % MOD);
						//cut
						add(dp[f][v][(p+q+1)&1][j], (ll)dp[c][v][p][j] * dp[u[to]][to][q][k] % MOD * dv[k] % MOD);
					}
				}
			}
		}

		swap(c, f);
		sz[v] += sz[to];
	}

	u[v] = c;
}

int main() {
	cin >> N;
	rep(i, N-1) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].pb(b); g[b].pb(a);
	}

	dv[0] = 1;
	for (int i = 2; i < MN; i += 2) {
		dv[i] = dv[i-2] * (i - 1) % MOD;
	}

	dfs(0, -1);
	ll ret = 0;
	rep(i, 2) {
		rep(j, MN) {
			ll t = dp[u[0]][0][i][j] * dv[j] % MOD;
			if (i == 1) t = MOD - t;
			ret = (ret + t) % MOD;
		}
	}

	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 391040
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC
{
    class ProgramA
    {
        static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(" ");
            var n = long.Parse(inputs[0]);
            var m = long.Parse(inputs[1]);
            var k = long.Parse(inputs[2]);
            var result = false;

            if (n + m == k) result = true;
            if (n + k == m) result = true;
            if (k + m == n) result = true;

            Console.WriteLine(result ? "Yes" : "No");
        }
    }
}


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

int main(){
  int x,y;
  for(int i=1;i<=3000;i++){
    cin >> x >> y;
    if((x != 0)||(y != 0)){
      if(x > y){
	cout << y << " " << x << endl;
      }else{
	cout << x << " " << y << endl;
      }
    }else{
      break;
    }
  }
  return 0;
}



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

int main() {
    int x, y;
    cin >> x >> y;

    bool exist = false;
    for (auto cranes = 0; cranes <= x; cranes++) {
        int turtles = x - cranes;
        int legs = 2 * cranes + 4 * turtles;

        if (legs == y) exist = true;
    }

    string answer = exist ? "Yes" : "No";
    cout << answer;
}

Measured memory_bytes: 3576
import java.util.*;

public class Main{
	public static void main(String [] args){
		/*int n,k;
		int arrA[];
		Scanner t = new Scanner(System.in);

		n = t.nextInt();
		k = t.nextInt();
		arrA = new int[n];

		for(int i = 0; i < n; i++){
			int numb = t.nextInt();
			arrA[i] = numb;
		}

		int valor = arrA[k];

		if (valor == 0){
			System.out.println(valor);
		}else{
			int nv = valor - 1;
			System.out.println(nv);
		}*/

		int n, k;
		Scanner t = new Scanner(System.in);
		n = t.nextInt();
		k = t.nextInt();
		
		int resp = n * k;

		System.out.println(resp);
		
	}
	
}

Measured memory_bytes: 35772
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll n,m,i,j,a1,a2,ans,t,a,b,c,x,y;
    while(cin>>a>>b>>c>>x>>y)
    {
        if(a+b>c+c)
        {
            int p=min(x,y);
            int q=max(x,y);
            a1=p*2*c;
            a1+=(x-p)*min(2*c,a);
            a1+=(y-p)*min(b,2*c);
             a2=q*2*c;
            ans=min(a1,a2);
        }
        else
            ans=x*a+y*b;
        cout<<ans<<endl;

    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define rep(i, n) FOR(i, 0, n)
#define repi(i, n) FOR(i, 1, n + 1)
#define pp(v) cout << #v "=" << (v) << endl;
#define ppa(v) cout << "----\n"; rep(i,v.size()) cout << #v << "[" << i << "] = " << v[i] << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)

int center_height(int x, int y, int cx, int cy, int h) {
  return abs(x-cx) + abs(y-cy) + h;
}

// ABC112C Pyramid 方針
// cx,cyで全探索
// 全座標が1万以上、観測地点100以下より、高度が0でない観測地点が一つ以上ある
// 高度が0でない観測地点を一つ選び、頂上の高さHを算出
// 観測地点の頂上からのマンハッタン距離をLとする
// 観測地点の高度が0の時、L < Hなら矛盾
// 観測地点の高度altが0以外の時、L + alt <> Hなら矛盾

int main() {
  int n; cin >> n;
  vector<int> x(n),y(n),h(n);
  rep(i,n) cin >> x[i] >> y[i] >> h[i];

  rep(cx,101) rep(cy,101) {
    bool valid = true;
    int H, L;
    rep(i,n) {
      if (h[i] == 0) continue;
      H = center_height(x[i],y[i],cx,cy,h[i]);
      break;
    }

    rep(i,n) {
      L = center_height(x[i],y[i],cx,cy,h[i]);
      if (h[i] == 0 && L < H) valid = false;
      if (h[i] != 0 && L != H) valid = false;
      if (!valid) break;
    }

    if (valid) {
      cout << cx << " " << cy << " " << H << endl;
      exit(0);
    }
  }
}

Measured memory_bytes: 256
from itertools import product

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

AB = sorted([a + b for a, b in product(A, B)], reverse=True)
ABC = sorted([ab + c for ab, c in product(AB[:max(K, Z)],
                                          sorted(C, reverse=True))],
             reverse=True)
for s in ABC[:K]:
    print(s)

Measured memory_bytes: 141852
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int now = 1;
    rep(i, 0, n){
        now = min(now * 2, now + k);
    }
    cout << now << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
const ll mod=1e+9;
typedef pair<ll,ll> P;
#define fi first
#define se second

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int a,b;
cin>>a>>b;
cout<<max(a+b,max(a-b,a*b))<<endl;
}


Measured memory_bytes: 256
N = int(input())
x = list(map(str, input().split()))
res=[0,0,0,0]

def check(a):
    if a==[1,1,1,1]:
        print('Four')
        quit()


for i in range(0,N):
    if x[i]=='G':
        res[0]=1
    if x[i]=='Y':
        res[1]=1
    if x[i]=='W':
        res[2]=1
    if x[i]=='P':
        res[3]=1
    check(res)

print('Three')

quit()

Measured memory_bytes: 3064
from bisect import bisect_left

N, M = map(int, input().split())
ab = [0]*M
for i in range(M):
    ab[i] = tuple(map(int, input().split()))
ab.sort(key=lambda x: x[1])

cutted = [-1]
for i in range(M):
    a, b = ab[i]
    if a <= cutted[-1]:
        continue
    cutted.append(b-1)
print(len(cutted)-1)


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

const int MAX_N=205;
const int MAX_M=10000;
const int MAX_R=1005;
const int INF=0x3f3f3f3f;

int land[MAX_N][MAX_N];
int water[MAX_N][MAX_N];
int N, M, R;
int dp[MAX_R][MAX_N];
int dest[MAX_R];

int main(){
    while((cin>>N>>M) && N>0){
        memset(land, 0x3f, sizeof(land));
        memset(water, 0x3f, sizeof(water));
        memset(dp, 0x3f, sizeof(dp));
        int x, y, t; char sl;
        for(int i=0; i<M; i++){
            scanf("%d %d %d %c ", &x, &y, &t, &sl);
            --x; --y;
            if(sl=='L'){
				land[x][y]=min(land[x][y],t);
				land[y][x]=land[x][y];
			}
            else {
				water[x][y]=min(water[x][y], t);
				water[y][x]=water[x][y];
			}
        }
        for(int i=0; i<N; i++) water[i][i]=land[i][i]=0;
        for(int i=0; i<N; i++){
        	for(int j=0; j<N; j++){
            	for(int k=0; k<N; k++){
                	land[j][k]=min(land[j][k], land[j][i]+land[i][k]);
                	water[j][k]=min(water[j][k], water[j][i]+water[i][k]);
            	}
        	}
   	    }
        cin>>R;
        for(int i=0; i<R; i++) {
			cin>>dest[i]; --dest[i];
		}
        for(int i=0; i<N; i++) dp[0][i]=water[dest[0]][i]+land[dest[0]][i];
        int pre=dest[0], z;
        for(int i=1; i<R; i++){
            z=dest[i]; 
            for(int j=0; j<N; j++){
                int mincost=INF;
                for(int k=0; k<N; k++){
                    if(dp[i-1][k]!=INF && water[j][k]!=INF 
                    && land[pre][k]!=INF && land[z][j]!=INF){
                        if(j==k) t=dp[i-1][k]+land[pre][z];
                        else t=dp[i-1][k]+water[k][j]+land[pre][k]+land[j][z];
                        mincost=min(mincost, t);
                    }
                }
                dp[i][j]=mincost;
            }
            pre=z;
        }
        int mincost=INF;
        for(int i=0; i<N; i++) mincost=min(mincost, dp[R-1][i]);
        cout<<mincost<<endl;
    }
}


Measured memory_bytes: 4288
using System;

public class hello
{
	public static void Main()
	{
		while (true)
		{
			var n = int.Parse(Console.ReadLine().Trim());
			if (n == 0) break;
			var h = new int[26];
			var t = new int[26];
			var a = new bool[26, 26];
			var used = new bool[26];
			for (int i = 0; i < n; i++)
			{
				var s = Console.ReadLine().Trim();
				var hc = s[0] - 'a';
				var tc = s[s.Length - 1] - 'a';
				h[hc]++;
				t[tc]++;
				used[hc] = true;
				used[tc] = true;
				a[hc, tc] = true;
			}
			var ans1 = check1(h, t);
			if (ans1)
			{
				var ans2 = check2(a,used);
				Console.WriteLine(ans2? "OK":"NG");
			}
			else Console.WriteLine("NG");

		}
	}
	static bool check2(bool[,] a, bool[] used)
	{
		for (int i = 0; i < 26; i++)
			for (int j = 0; j < 26; j++)
				for (int k = 0; k < 26; k++)
					if (a[j, i] && a[i, k]) a[j, k] = true;
		for (int i = 0; i < 26; i++)
			if (used[i])
				for (int j = 0; j < 26; j++)
					if (used[j])
						if ( !a[i,j]) return false;
		return true;
	}
	static bool check1(int[] h, int[] t)
	{
		for (int i = 0; i < 26; i++)
			if (h[i] != t[i]) return false;
		return true;
	}
}



Measured memory_bytes: 17952
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		if (N==3 | N==5 | N==7) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 21204
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		//問題入力
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[][] array = new int[n][2];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 2; j++) {
				array[i][j] = sc.nextInt();
			}
		}
		long space = 1L << 62;
		; //暫定的な面積(あとで表示するのでこれはforのブロックの外で宣言)
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k1 = 0; k1 < n; k1++) {
					for (int l = 0; l < n; l++) {
						int counter = 0; //長方形に含まれる点の数をカウント
						for (int c = 0; c < n; c++) {
							if (array[c][0] >= array[i][0] && array[c][0] <= array[j][0] && array[c][1] >= array[k1][1]
									&& array[c][1] <= array[l][1]) {
								counter++;
							}
						}
						if (counter >= k) {
							space = Math.min(space,
									1L*(array[j][0] - array[i][0]) * (array[l][1] - array[k1][1]));
						}
					}
				}
			}
		}
		System.out.println(space);
		sc.close();
	}
}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
# define ll int64_t
#define rep(i,n) for(ll i=0;i<n;i++)
#define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool compare_by_a(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first != b.first) return a.first<b.first;
    else return a.second<b.second;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}



int main(){
    ll n=0;
    string s;
    cin>>s;
    if(s.size()==1){
        cout<<0<<endl;
        return 0;
    }if(s.size()==2){
        if(s[0]==s[1]) cout<<0<<endl;
        else cout<<1<<endl;
        return 0;
    }
    rrep(i,s.size()-1){
        if(s[i-1]!=s[i] && s[i]!=s[i+1]) continue;
        else{
            n++;
            if(s[i]==s[i+1] && s[i-1]!=s[i]) s[i+1]=s[i-1];
            if(s[i]==s[i-1] && s[i]!=s[i+1]) s[i]=s[i+1];
            if(s[i]==s[i+1] && s[i]==s[i-1]){
                if(s[i]=='1') s[i]='0';
                else s[i]='1';
            }
        }
    }
    cout<<n<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P, ll> T;
 
long long int INF = 1e18;
const ll fact_table = 800008;
double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
ll dx[8]={1,0,-1,0,1,1,-1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
// #define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
#define pc(x) cout << x << ",";
 
 
// ll mod = 998244353;
 ll mod = 1000000007;
  
ll mypow(ll number1,ll number2, ll mod){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = mypow(number1,number2 / 2, mod);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5];
 
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = rui(fact[fact_table],mod - 2);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/
bool multicase = false;

ll n,m,num,sum,a,b,c,d,e,h,q;
ll w, ans;
ll k;
char s[500005], t[500005];
double x[500005], y[500005], z[500005];

void init(){
    struct timeval _time;
    gettimeofday(&_time, NULL);
    ll usec = _time.tv_usec * 1000000;
    srand(usec);
    return;
}

void solve(){
    cin >> n;
    p((n + 1) / 2);
    return;
}

int main(){
    // init();
    ll q;
    if(multicase){
        cin >> q;
    }else{
        q = 1;
    }
    while(q--){
        solve();
    }
    return 0;

}


















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

typedef struct node{
  int key;
  struct node *p;
  struct node *l;
  struct node *r;
} Node;

typedef Node *NodePointer;
NodePointer root = NULL;

NodePointer createNode(){
  NodePointer z = malloc(sizeof(Node));
  z->l = NULL;
  z->r = NULL;
  z->p = NULL;
  z->key = 0;
  return z;
}

int insert(int key){
  
  NodePointer z = createNode();
  NodePointer y = NULL;
  NodePointer x = root;
  z->key = key;
  
  while(x != NULL){
    y = x;
    if(z->key < x->key) x = x->l;
    else x = x->r;
  }
  z->p = y;
  if(y == NULL) root = z;
  else if(z->key < y->key) y->l = z;
  else y->r = z;
}
  
void inorder(NodePointer p){
    
  if(p != NULL){
    inorder(p->l);
    printf(" %d",p->key);
    inorder(p->r);
  }
}

void preorder(NodePointer p){
  if(p != NULL){
    printf(" %d",p->key);
    preorder(p->l);
    preorder(p->r);
  }
}

int main(void){

  int i,key,n;
  char str[20];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",str);

    if(str[0] == 'i'){
      scanf("%d",&key);
      insert(key);
    }
    else if(str[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 24040
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    ll n,d; cin>>n>>d;
    vector<P> a(n);
    rep(i,n) cin>>a[i].first>>a[i].second;

    ll cnt = 0;
    rep(i,n) {
        if (a[i].first*a[i].first + a[i].second*a[i].second <= d*d) {
            cnt++;
        }
    }

    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 6424
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define PI 3.14159265359
#define sz(c) (int)c.size()
#define len(c) (int)c.length()
#define hcf(a, b) __gcd(a, b)
#define all(c) c.begin(), c.end()
#define vint vector<int>
#define vll vector<ll>
#define vpint vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define fr(it, a, b) \
    for (int it = (a); it < (b); it++)
#define tr(c, it) \
    for (auto it = c.begin(); it != c.end(); it++)
#define cpresent(c, e) (find(all(c), e) != c.end())
#define present(c, e) (c.find(e) != c.end())
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef unsigned long long lu;
const ll mod = 1e9 + 7;
int32_t main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll k, p = 1, ans = 0;
    cin >> k;
    set<ll> s;
    ll nw = 0;
    while (true)
    {
        nw = (nw + p * 7) % k;
        p = (p * 10) % k;
        ans++;
        if (present(s, nw) || nw == 0)
        {
            if (present(s, nw))
            {
                ans = -1;
            }
            break;
        }
        s.insert(nw);
    }
    cout << ans << "\n";
    return 0;
}

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

int main()
{

int n,k=0;
cin>>n;
int a[n];

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


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

    if(a[i]%2==1)
        k++;


   }


cout<<k<<endl;

}




Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

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

    cout << max(a*b,c*d) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int h, w;
    cin >> h >> w;
    char s[h][w];
    rep(i, 0, h) {
        rep(j, 0, w) {
            cin >> s[i][j];
        }
    }

    rep(i, 0, h) {
        rep(j, 0, w) {
            if (s[i][j] == '.') {
                int cnt = 0;
                for (int di = - 1; di <= 1; di++) {
                    for (int dj = - 1; dj <= 1; dj++) {
                        if (0 <= i + di && i + di < h && 0 <= j + dj && j + dj < w) {
                            if (s[i + di][j + dj] == '#') {
                                cnt++;
                            }
                        }
                    }
                }
                s[i][j] = '0' + cnt;
            }
        }
    }

    rep(i, 0, h) {
        rep(j, 0, w) {
            cout << s[i][j];
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pl = pair<ll,ll>;
using pi = pair<int,int>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
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; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;

template<int MOD> struct Fp {  
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = Fp<MOD>;

signed main(){
	//cout << fixed << setprecision(10);
	string s; cin >> s;
    int n = s.size();
    vector<vector<mint>> dp(n + 1,vector<mint>(13,0));
    dp[0][0] = 1;
    rep(i,0,n){
        rep(j,0,13){
            if(s[i] == '?'){
                rep(k,0,10){
                    dp[i + 1][(10 * j + k) % 13] += dp[i][j];
                }
            }
            else{
                int k = s[i] - '0';
                dp[i + 1][(10 * j + k) % 13] += dp[i][j];
            }
        }
    }
    cout << dp[n][5] << endl;
}



Measured memory_bytes: 16704
#include <iostream>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

const int M = 13;

string s;
ll t = 1, ans;
ll dp[2][13];
int ind[13][13];
int ho = 0, ge = 1;

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

    rep(i,M) {
        rep(j,M) ind[i][j] = i*j%M;
    }

    cin >> s;
    dp[ho][0] = 1;
    for (int i = (int)s.size()-1; i >= 0; i--) {
        if (s[i] != '?') {
            int x = t*(s[i]-'0')%M;
            rep(j,M) {
                if (x == M) x -= M;
                dp[ge][x++] = dp[ho][j];
            }
        } else {
            ll sum = 0;
            rep(j,9) sum += dp[ho][ind[t][j]];
            for (int j = 9; j < M; j++) {
                sum += dp[ho][ind[t][j]];
                dp[ge][ind[t][j]] = sum;
                sum = sum+100*MOD-dp[ho][ind[t][j-9]];
            }
            for (int j = 0; j < 9; j++) {
                sum += dp[ho][ind[t][j]];
                dp[ge][ind[t][j]] = sum;
                sum = sum+100*MOD-dp[ho][ind[t][j+4]];
            }
        }
        if (i%3) rep(j,M) dp[ge][j] %= MOD;
        t = t * 10 % M;
        swap(ho,ge);
    }
    cout << dp[ho][5]%MOD << endl;
}


Measured memory_bytes: 512
n= int(input())
l= list(map(int,input().split()))
s= 0
for i in range(n):
	if(l[i]<l[0]):
		l[0],l[i]= l[i],l[0]
for j in range(n):
	if(l[n-1]<l[j]):
		l[n-1],l[j]= l[j],l[n-1]
for k in range(n):
	s+= l[k]
print(l[0],l[n-1],s)

Measured memory_bytes: 8656
#include<bits/stdc++.h>
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define pii pair<int,int>
#define REP(i,a) for(int (i)=0; (i)<(a); (i)++)
#define RREP(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define REP2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
#define EPS (1e-7)
#define pi (3.14159265358979)
typedef long long ll;

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int a,b,x;
  cin>>a>>b>>x;
  double ans;
  double height = x/(a*a);
  double room =a*a*b - x; 
  if((x*2)>=(a*a*b)){
    double h = 2.0*room/(a*a);
    ans = (double)atan(h/a)*(double)180/pi; 
  }else{
    double h = a-((double)2.0*x)/(a*b);
    ans = (double)atan(b/(a-h))*(double)180/pi;
  }
  cout<<setprecision(7)<<ans;
  return 0;
}

Measured memory_bytes: 256
<?php
error_reporting(0);
//$N = explode(" ",trim(fgets(STDIN)));
list($A,$B,$X) = explode(" ",trim(fgets(STDIN)));
//$Q=trim(fgets(STDIN));
if ($A+$B>=$X && $A<=$X) {
  printf("YES\n");
}
else {
  printf("NO\n");
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, c) for(long long i=0; i<(long long)c; i++)
const ll INF=1000000000000001;
int main() {
	int n;
	int ans=0;
	cin >> n;
	int accnt=0;
	int wacnt=0;
	int tlecnt=0;
	int recnt=0;
	rep(i,n){
		string s;
		cin >> s;
		if (s=="AC")accnt++;
		if (s=="WA")wacnt++;
		if (s=="TLE")tlecnt++;
		if (s=="RE")recnt++;
	}
	cout <<"AC x "<<accnt<<endl;
	cout <<"WA x "<<wacnt<<endl;
	cout <<"TLE x "<<tlecnt<<endl;
	cout <<"RE x "<<recnt<<endl;
	return 0;
}


Measured memory_bytes: 3624
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>

using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 999999
#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<k;i++)
typedef long long ll;
typedef unsigned long long ull;
int main(){
    char stage[4][4]={{0}};
    while(scanf("%s",stage[0]), stage[0][0] != '0'){
        reps(i,1,3)scanf("%s",stage[i]);
        /*Check*/
        bool f = false;
        rep(i,3){
            if(stage[i][0] == 'b' && stage[i][1] == 'b' && stage[i][2] == 'b'){
                puts("b");
                f = true;
                break;
            }
            if(stage[i][0] == 'w' && stage[i][1] == 'w' && stage[i][2] == 'w'){
                puts("w");
                f = true;
                break;
            }
            if(stage[0][i] == 'b' && stage[1][i] == 'b' && stage[2][i] =='b'){
                puts("b");
                f = true;
                break;
            }
            if(stage[0][i] == 'w' && stage[1][i] =='w' && stage[2][i] == 'w'){
                puts("w");
                f = true;
                break;
            }
        }
        if(f)continue;
        if(stage[0][0] == stage[1][1] && stage[1][1] ==stage[2][2] &&stage[0][0] == 'b'){
            puts("b");
            f = true;
            continue;
        }
        if(stage[0][0] == stage[1][1] && stage[1][1] ==stage[2][2] &&stage[0][0] == 'w'){
            puts("w");
            f = true;
            continue;
        }
        if(stage[0][2] == stage[1][1] && stage[1][1] ==stage[2][0] &&stage[0][2] == 'b'){
            puts("b");
            f = true;
            continue;
        }
        if(stage[0][2] == stage[1][1] && stage[1][1] ==stage[2][0] &&stage[0][2] == 'w'){
            puts("w");
            f = true;
            continue;
        }
        if(!f)puts("NA");
    }
    return 0;
}

Measured memory_bytes: 1112
#include <iostream>

using namespace std;

#define N 10000
#define Q 10500
#define NF 0

int s[N], t[Q];

int linearSearch(int n, int q)
{
  int i;
  int count = 0;
  int k = n;

  for(int j = 0; j < q; j++) {
    i = 0;
    s[k] = t[j];   
    while(s[i] != t[j]) i++;
    if(i >= n) count += NF;
    else count += 1;
    k++;
  }

  return count;
}

int main(void)
{
  int n;
  cin >> n;
  for(int i = 0; i < n; i++) cin >> s[i];

  int q;
  cin >> q;
  for(int i = 0; i < q; i++) cin >> t[i];

  cout << linearSearch(n, q) << endl;

  return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORe(i, k, n) for(int i = (k); i <= (n); i++)
#define FORr(i, k, n) for(int i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(int i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;

int main(void){
  char b;
  cin >> b;
  char ans;
  if(b == 'A') ans = 'T';
  if(b == 'C') ans = 'G';
  if(b == 'G') ans = 'C';
  if(b == 'T') ans = 'A';
  cout << ans << endl;
  return 0;
}

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

int main() {
	// your code goes here
	int N;
	cin >> N;

	vector<int> a(N);
	for(int i=0;i<N;i++) cin >> a[i];
	
	// i ... number of sorted elements
	// j ... location of bubble (right end)
	
	int swapped = 0;
	for(int i=0;i<N;i++){
		for(int j=N-1; j>i; j--){
			if(a[j] < a[j-1]){
				int temp = a[j];
				a[j] = a[j-1];
				a[j-1] = temp;
				swapped++;
			}
		}
	}
	
	for(int i=0;i<N;i++){
		cout << a[i];
		if(i<N-1) cout << ' ';
		else cout << endl;
	}
	cout << swapped << endl;
	
	return 0;
}


Measured memory_bytes: 3140
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
#define mp make_pair
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
    vl x(5);
    rep(i,5){
        cin >> x[i];
        if(x[i]==0){
            cout << i+1 << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3628