akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;
import java.util.regex.*;

class Main{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String w = br.readLine();	//キーボードで入力された１行目の文字を読み取る
        String t;
        String upper;
        String lower;
        int count = 0;
        int i = 0;
        int j = 0;
        
        while((t=br.readLine())!=null){
            if("END_OF_TEXT".equals(t) || w.length()>10 || t.length()>1000){
                break;                       //END_OF_TEXTが入力されたらwhileを抜ける
            }
            String[] str = t.split(" ");
            for(int k=0; k<str.length; k++){
            	if(str[k].equalsIgnoreCase(w)){
            		count++;
            	}
            }
        }
        System.out.println(count);
     }
}

Measured memory_bytes: 16908
import java.util.*;

public class Main {
    public static void main(String[] args) {
	Scanner s = new Scanner(System.in);
	int N = s.nextInt();
	for(int tc = 0; tc < N; ++tc) {
	    int[] len = new int[3];
	    for(int i = 0; i < 3; ++i) {
		len[i] = s.nextInt();
	    }
	    Arrays.sort(len);
	    if(Math.pow(len[0], 2) + Math.pow(len[1], 2)
	       == Math.pow(len[2], 2)) {
		System.out.println("YES");
	    } else {
		System.out.println("NO");
	    }
	}
    }
}

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

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


Measured memory_bytes: 256
// ~/BAU/ACM-ICPC/Teams/Rampage/Corvus
// ~/sudo apt-get verdict Accpeted

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <limits.h>
#include <math.h>
#include <string.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 200002;
const ll MOD = 1e9 + 7;

int n, a[N], x[N];
ll s[N];

int main() {
scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		s[i] = s[i - 1] + a[i];
		x[i] = x[i - 1] ^ a[i];
	}

	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		int l = i, r = n, m, j = -1;
		while (l <= r) {
			m = (l + r) / 2;

			if (s[m] - s[i - 1] == (x[m] ^ x[i - 1])) {
				j = m;
				l = m + 1;
			}
			else r = m - 1;
		}
		ans += 1ll * (j - i + 1);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll int mod=1e9+7;
int num[4],n;
double p[330][330][330];
double dp(int x,int y,int z){
    if(p[x][y][z]>=0)return p[x][y][z];
    double sum=(double)n/(x+y+z);
    if(x)sum+=dp(x-1,y,z)*x/(x+y+z);
    if(y)sum+=dp(x+1,y-1,z)*y/(x+y+z);
    if(z)sum+=dp(x,y+1,z-1)*z/(x+y+z);
    return p[x][y][z]=sum;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                p[i][j][k]=-1;
    p[0][0][0]=0;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        num[x]++;
    }
    printf("%.10lf\n",dp(num[1],num[2],num[3]));
    return 0;
}


Measured memory_bytes: 258176
from heapq import heappop, heappush
n = int(input())
p = [int(x) for x in input().split()]


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:]

    def update(self, k, x):
        k += self.N-1
        self.tree[k] = x
        while k+1:
            k = (k-1)//2
            self.tree[k] = self.opr(self.tree[k*2+1], self.tree[k*2+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 1:
            if p & 1 == 0:
                res = self.opr(res, self.tree[p])
            if q & 1 == 1:
                res = self.opr(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.opr(res, self.tree[p])
        else:
            res = self.opr(self.opr(res, self.tree[p]), self.tree[q])
        return res


ind = [0]*(n+1)
Odd = SegmentTree([10**30]*n)
Even = SegmentTree([10**30]*n)

for i in range(n):
    ind[p[i]] = i
    if i % 2 == 0:
        Even.update(i, p[i])
    else:
        Odd.update(i, p[i])

cand = []
heappush(cand, (Even.query(0, n), 0, n, True))

q = []
for _ in range(n//2):
    first, l, r, is_even = heappop(cand)
    if is_even:
        second = Odd.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Even.query(l, ind[first]), l, ind[first], True))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Odd.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], False))
        if ind[second]+1 < r:
            heappush(
                cand, (Even.query(ind[second], r), ind[second]+1, r, True))
    else:
        second = Even.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Odd.query(l, ind[first]), l, ind[first], False))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Even.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], True))
        if ind[second]+1 < r:
            heappush(
                cand, (Odd.query(ind[second], r), ind[second]+1, r, False))

print(*q)


Measured memory_bytes: 152432
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int n, a[200005], t, rt, ln, rn;
bool used[200005], s;
vector<int> ch[200005];
int dfs(int t){
	int ret = 0;
	bool ap[20] = {};
	for(int u: ch[t]) if(u != rt) ap[dfs(u)] = true;
	if(t == a[rt] && s) ap[ln] = true;
	for(; ap[ret]; ret++);
	if(t == a[rt]) ln = ret;
	return ret;
}
int main(){
	scanf("%d", &n);
	rep(i,n){
		scanf("%d", a+i);
		ch[--a[i]].push_back(i);
	}
	for(; !used[t]; t = a[t]) used[t] = true;
	rt = t;
	rn = dfs(rt);
	if(rn == ln){
		s = true;
		if(rn != dfs(rt)) printf("IM");
	}
	puts("POSSIBLE");
}

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

int main() {
	int n;

	while (cin >> n,n	)
	{

		vector<string> w;
		for (int i = 0;i < n;++i) {
			string tmp;
			cin >> tmp;
			w.push_back(tmp);
		}

		int flag = 0;
		int len = 0;
		int output = 100000000;
		for (int i = 0;i < n;++i) {
			flag = 0;
			len = 0;
			for (int j = i; j< n;++j) {
				len += w[j].size();
				if (flag == 0 || flag == 2) {
					if (len == 5) {
						len = 0;
						flag++;
					}
					else if (len > 5) {
						break;
					}
				}
				else {
					if (len == 7) {
						len = 0;
						flag++;
					}
					else if (len > 7) {
						break;
					}
				}
			}

			if (flag >= 5) {
				output = i + 1;
				break;
			}
		}

		cout << output << endl;
	}


}

Measured memory_bytes: 3156
#include <cstdio>
#include <algorithm>
using namespace std;


int n,m;
static int h[200], r[200];
static int dp[200];

int calc(int i) {
  if(dp[i] == -1) {
    dp[i] = 1;
    for(int j = 0; j < n+m; j++) {
      if(h[j] < h[i] && r[j] < r[i]) {
        dp[i] = max(dp[i], calc(j)+1);
      }
    }
  }
  return dp[i];
}


int main() {
  for(int tci = 0; ; tci++) {
    scanf("%d", &n); if(n==0) break;
    for(int i = 0; i < n; i++) {
      scanf("%d%d", h+i, r+i);
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
      scanf("%d%d", h+n+i, r+n+i);
    }
    fill(dp, dp+n+m, -1);
    int mv = 0;
    for(int i = 0; i < n+m; i++) {
      mv = max(mv, calc(i));
      // fprintf(stderr, "%d / %d+%d : %d\n", i, n, m, calc(i));
    }
    printf("%d\n", mv);
  }
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef long long unsigned int llui;
typedef long long int lli;
typedef long double float64;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;

#define INF 1000000000
#define MOD 1000000007
#define EPS 1e-9
#define DEBUG(x) cout<< '>' << #x << ':' << x << "\n";
#define all(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define UNIQUE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define tr(container, it) \
    for(typeof(container.begin()) it = container.begin(); it != container.end(); it++) 


// #define sz(a) int((a).size())
// #define pb push_back
// #define fill(a,v) memset(a,v,sizeof a)


#define trace(x) cout << '>' << #x << ':' << x << endl;
#define trace2(x,y) cout<< '>' << #x << ':' << x << " | " << #y << ':' << y << endl;

#define trace3(x,y,z) cout<< '>' << #x << ':' << x \
        << " | " << #y << ':' << y <<" | " << #z << ':' << z << endl;

#define trace4(x,y,z,w) cout<< '>' << #x << ':' << x \
    << " | " << #y << ':' << y <<" | " << #z << ':' << z << " | " << #w << ':' << w << endl;



inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

#define LSOne(S) (S&(-S))

const double pi = acos(-1);


template<class T> inline T gcd(T a,T b) //NOTES:__gcd(0,0) gives exception
  {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}

int cmp(double x, double y = 0, double tol = EPS) {
    return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}

/////////////////////////////////////////////////////////////////////

/*bool sortby(const pair<int,int> &a,const pair<int,int> &b)
{
    return (a.first < b.first);
}*/

const int MAX_N = 4123;

int arr[MAX_N];
 
int main() {
	int N,x;
	scanf("%d",&N);
	set<int> S;
	for(int i=0;i<N;i++){
		scanf("%d",&x);
		S.insert(x);
	}
	printf("%d",S.size());
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define INF 0x3f3f3f3f
#define mod 1000000009
#define e  2.718281828459045
#define eps 1.0e18
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define memset(x,y) memset(x,y,sizeof(x))
#define lson i << 1,l,m
#define rson i << 1 | 1,m + 1,r
#define ll long long
using namespace std;
ll r[4005]={0};
ll g[4005]={0};
ll b[4005]={0};
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("text1.in","r",stdin);
	//freopen("text1.out","w",stdout);
	int n;
	cin>>n;
	string s;
	cin>>s;
	ll ans=0;
	for(int i=s.size()-1;i>=0;i--){
		if(s[i]=='R'){
			r[i]=r[i+1]+1;
			g[i]=g[i+1];
			b[i]=b[i+1];
			ans=ans+g[i]*b[i];
		} 
		else if(s[i]=='G'){
			g[i]=g[i+1]+1;
			r[i]=r[i+1];
			b[i]=b[i+1];
			ans=ans+r[i]*b[i];
		} 
		else if(s[i]=='B'){
			g[i]=g[i+1];
			r[i]=r[i+1];
			b[i]=b[i+1]+1;
			ans=ans+r[i]*g[i];
		} 
	}
	for(int i=0;i<n;i++){
		int j=1;
		while(i+j*2<s.size()){
			if(s[i]!=s[i+j] && s[i+j]!=s[i+j+j] && s[i]!=s[i+j+j]){
				ans--;
			}
			j++;
		}	
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3708
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main()
{
	string hands;
	while( getline( cin, hands ) ){
		if( hands == "0" ) break;
		stringstream ss( hands );
		int ans = 0;
		int ex = 0;
		while( !ss.eof() ){
			int p;
			ss >> p;
			if( p > 10 ){
				p = 10;
			}
			if( p == 1 ){
				++ex;
			}
			ans += p;
		}
		while( ex > 0 ){
			if( 21 - ans >= 10 ){
				ans += 10;
			}
			--ex;
		}
		cout << ( ans > 21 ? 0 : ans ) << endl;
	}
}

Measured memory_bytes: 1224
import numpy as np

def is_ok(mid, k):
    s = a - mid // f
    s = s[s > 0].sum()
    if s <= k:
        return True
    else:
        return False

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]
a.sort()
f.sort(reverse=True)
a = np.array(a)
f = np.array(f)

l, r = -1, 10**12 # l:ng, r:ok
while l + 1 < r:
    mid = (l + r) // 2
    if is_ok(mid, k):
        r = mid
    else:
        l = mid
print(r)

Measured memory_bytes: 43564
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << 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 solve() {
	ll a, b, c; cin >> a >> b >> c;
    if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0) {
        cout << 0 << endl;
    } else {
        cout << min({a * b, b * c, c * a}) << endl;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  vector<string> A;
  A.push_back("Sunny");
  A.push_back("Cloudy");
  A.push_back("Rainy");
  A.push_back("Sunny");
  string s;
  cin>>s;
  for(int i=0;i<4;i++)
  {
    if(s==A[i]){cout<<A[i+1];break;}
  }
  return 0;
}

Measured memory_bytes: 256
/*I MAY NOT GET THE SUCCESS IMMEDIATELY BUT I WILL GET IT FOR SURE*/
#include<bits/stdc++.h>
#define opt std::ios_base::sync_with_stdio(false)
#define I int
#define li      int32_t
#define lli     long long
#define ulli unsigned long long
 
#define pn          printf("\n")
#define nl          cout<<'\n'
#define sf(N)       scanf("%lld",&N)
#define pf(N)       printf("%lld",N)
#define sl          cout<<' '
#define ps          printf(" ")
 
#define rep(i,a,b)  for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>b;i--)
#define elif        else if
#define mset(a,b)   memset(a,b,sizeof(a))
 
#define pb      push_back
#define pob     pop_back
#define itr     iterator
#define sz()    size()
#define szof    sizeof
#define lb      lower_bound
#define ub      upper_bound
#define mp      make_pair
#define vlli    vector<lli>
#define plli    pair<lli,lli>
#define vplli   vector<plli >
#define F       first
#define S       second
#define Dup erase(unique(V.begin(),V.end()),V.end())
 
#define TC int test; cin>>test; test++; while(--test)
 
#define Inf     1000000000000000
#define mod     1000000007
#define M1      1000000007
#define M2      1000000009
using namespace std;

char ch[105][105];

lli Power(lli a,lli b)
{
    lli result=1;
 
    while(b)
    {
        if(b%2)
        {
            result=(result*a)%mod;
        }
 
        b=b>>1;
        a=(a*a)%mod;
    }
 
 return result;
}
 
int main()
{
    opt;
 
    /*#ifndef ONLINE_JUDGE
    freopen("double_squares.txt","r",stdin);
    freopen("double_squares_out.txt","w",stdout);
    #endif // ONLINE_JUDGE*/
    
    lli l,b,i,j;
    cin>>l>>b;
    
    if(l%3==0 or b%3==0)
    {
        cout<<0;
        exit(0);
    }
    
    lli Ans=Inf;
    
    rep(i,1,l)
    {
        lli a1,a2,a3;
        a1=b*(l-i);
        a2=i*(b/2+b%2);
        a3=i*(b/2);
        
        lli Maximum,Minimum;
        Maximum=max(a1,max(a2,a3));
        Minimum=min(a1,min(a2,a3));
        
        Ans=min(Ans,Maximum-Minimum);
    }
    
    rep(i,1,b)
    {
        lli a1,a2,a3;
        a1=l*(b-i);
        a2=i*(l/2+l%2);
        a3=i*(l/2);
        
        lli Maximum,Minimum;
        Maximum=max(a1,max(a2,a3));
        Minimum=min(a1,min(a2,a3));
        
        Ans=min(Ans,Maximum-Minimum);
    }
        
    Ans=min(Ans,min(l,b));
        
    cout<<Ans;
    
    
 
 return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
#define PI 3.141592653589793

int depth[202020];
vector<int> to[202020], muka[202020];
bool seen[202020];
vector<int> order;

void rec(int v) {
    seen[v] = true;
    for (auto next : to[v]) {
        if (seen[next]) continue; // 既に訪問済みなら探索しない
        rec(next);
    }
    order.push_back(v);
}

int main(){
  int N, M; cin >> N >> M;
  rep(i, N+M-1){
    int a, b; cin >> a >> b;
    a--; b--;
    to[a].push_back(b); muka[b].push_back(a);
  }
  rep(i, N){
    if(muka[i].size()==0) rec(i);
  } 
  reverse(order.begin(), order.end());
  int ans[N] = {};
  for(int i: order){
    for(int c: to[i]){
      depth[c] = max(depth[c], depth[i]+1);
    }
  }
  rep(i, N){
    for(auto c: to[i]){
      if(depth[c]==depth[i]+1){
        ans[c] = i+1;
      }
    }
  }
  rep(i, N){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 22396
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<utility>
#include<stack>
#include<queue>
#include<map>
#include<set>

using namespace std;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    vector<long long> b(n);
    long long suma=0, sumb=0;
    REP(i, n){
        cin >> a[i];
        suma += a[i];
    }
    REP(i, n){
        cin >> b[i];
        sumb += b[i];
    }

    if(suma < sumb){
        cout << -1 << endl;
        return 0;
    }

    vector<long long> dif(n);
    REP(i, n){
        dif[i] = a[i] - b[i];
    }

    sort(all(dif));
    
    int ans = 0;
    long long sum1 = 0, sum2 = 0;
    for(int i = 0; dif[i] < 0; i++){
        sum1 += dif[i];
        ans++;
    }
    for(int i = n-1;sum1 + sum2 < 0; i--){
        sum2 += dif[i];
        ans++;
    }
    
    cout << ans << endl;
}



Measured memory_bytes: 2560
package main

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

func main() {
	N := readI()

	ans := 0
	for a := 1; a < N; a++ {
		for b := 1; b < N; b++ {
			if a*b >= N {
				break
			}
			ans++
		}
	}

	fmt.Println(ans)
}

/*-----------Input utils-----------*/

var sc = bufio.NewScanner(os.Stdin)

func init() {
	if len(os.Args) >= 2 {
		if os.Args[1] == "debug" {
			debug()
		}
	}
	const buf = 200100
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, buf), buf)
}

func debug() {
	testFile, err := os.Open("./test/sample-2.in")
	if err != nil {
		fmt.Fprintln(os.Stderr, "There is no testfile.")
		os.Exit(1)
	}
	sc = bufio.NewScanner(testFile)
}

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

func readR() []rune {
	return []rune(readS())
}

func readI() int {
	i, _ := strconv.Atoi(readS())
	return i
}

func readF() float64 {
	f, _ := strconv.ParseFloat(readS(), 64)
	return f
}


Measured memory_bytes: 1804
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int r, ans = 100000;

int main()
{
    cin >> r;
    for (int i = 0; i < r; i++)
    {
        ans *= 1.05;
        if (ans % 1000 != 0)
            ans = ans - ans % 1000 + 1000;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
signed main(){
  string a;
  cin>>a;
    for(int i=0;i<19;i++){
      if(a[i]==','){
	cout<<" ";
      }else{
	cout<<a[i];
      }
    }
    cout<<"\n";
    return(0);
}



Measured memory_bytes: 256
import java.util.Scanner;
class Main{
    public static void main(String[] a){
		int num1[] = new int[1000];
		int num2[] = new int[1000];
		int num3[] = new int[1000];
		int num,i = 0;
		Scanner scanner = new Scanner(System.in);
		num = Integer.parseInt(scanner.next());
		for(i=0; i<num; i++) {
			num1[i] = Integer.parseInt(scanner.next());
			num2[i] = Integer.parseInt(scanner.next());
			num3[i] = Integer.parseInt(scanner.next());
			if((Math.pow(num1[i], 2) + Math.pow(num2[i], 2) == Math.pow(num3[i], 2))
					|| (Math.pow(num1[i], 2) + Math.pow(num3[i], 2) == Math.pow(num2[i], 2))
					|| (Math.pow(num2[i], 2) + Math.pow(num3[i], 2) == Math.pow(num1[i], 2))){
				System.out.println("YES");
			} else{
				System.out.println("NO");	
			} 
		}
		scanner.close();
    }
}


Measured memory_bytes: 34508
import sys
import itertools

N,M,Ql = map(int, sys.stdin.readline().strip().split())
Q = []
for _ in range(Ql):
    Q.append(list(map(int, sys.stdin.readline().strip().split())))

max = 0
for A in itertools.combinations_with_replacement(range(1,M+1), N):
    ans = 0
    for Qi in Q:
        a,b,c,d = Qi

        if (A[b-1] - A[a-1]) == c:
            ans += d
    if max < ans:
        max = ans

print(max)


Measured memory_bytes: 67980
#include <bits/stdc++.h>
using namespace std;
 
int N;
int x[10], y[10];
 
double dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return pow(dx * dx + dy * dy, 0.5);
}
 
void solve() {
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> x[i] >> y[i];
    double sum = 0.0;
    vector<int> v(N);
    for(int i = 0; i < N; i++) v[i] = i + 1;
    do {
        for(int i = 0; i < N - 1; i++) sum += dist(v[i], v[i+1]);
    } while(next_permutation(v.begin(), v.end()));
    int Factorial = 1;
    for(int i = 2; i <= N; i++) Factorial *= i;
    cout << fixed << setprecision(10) << sum / Factorial << endl;
    return;
}
 
int main() {
    solve();
    return 0;
}

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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  int x,y,a,b,c;
  cin >> x >> y >> a >> b >> c;
  const int max_n = 1e5;
  vector<pair<int, char>> apple;
  for(int i = 0; i < a+b+c; i++){
    int p;
    cin >> p;
    if(i < a) apple.push_back(make_pair(p, 'r'));
    else if(i >= a && i < a+b) apple.push_back(make_pair(p, 'g'));
    else apple.push_back(make_pair(p, 'x'));
  }

  sort(apple.begin(), apple.end());
  reverse(apple.begin(), apple.end());

  int cnt = 0;
  int red = 0;
  int green = 0;
  long long ans = 0;
  bool red_flag = 0;
  bool green_flag = 0;
  for(int i = 0; i < a + b + c; i++){
    if(cnt >= x + y) break;

    if(red >= x) red_flag = 1;
    if(green >= y) green_flag = 1;

    if(red_flag == 1 && apple[i].second == 'r') continue;
    if(green_flag == 1 && apple[i].second == 'g') continue;

    if(apple[i].second == 'r') red ++;
    if(apple[i].second == 'g') green ++;
    cnt ++;
    ans += apple[i].first;
  }
  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 7432
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,n,h) for(int i = n; i < h; ++i)
#define rep3(l,n,h) for(int l = n; l <= h; ++l)
#define INF LLong_MAX // long long INF
#define inf INT_MAX // int inf

typedef pair<int,int> int_pair;
typedef pair<string,string> string_pair;


int main() {
    string s;
    char ans = '1';
    int k,i = 0;
    cin >> s >> k;
    while(i < k) {
        if(s[i] != '1') {
            ans = s[i];
            break;
        }
        i++;
    }
    cout << ans << endl;
}

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

#define POS(i,j) (((i)&1)*n+(j))

void run(void){
  int n;
  scanf("%d",&n);
  char *s=(char *)calloc(n,sizeof(char));
  scanf("%s",s);
  const int mod=1000000007;
  int *dp=(int *)calloc(2*n,sizeof(int));
  int i;
  for(i=0;i<n;i++) dp[POS(0,i)]=1;
  for(i=1;i<n;i++){
    memset(dp+POS(i,0),0,sizeof(int)*n);
    if(s[i-1]=='>'){
      for(int j=1;j<n+1-i;j++){
	dp[POS(i,0)]=(dp[POS(i,0)]+dp[POS(i-1,j)])%mod;
	dp[POS(i,j)]=(dp[POS(i,j)]+mod-dp[POS(i-1,j)])%mod;
      }
    } else {
      for(int j=0;j<n-i;j++){
	dp[POS(i,j)]=(dp[POS(i,j)]+dp[POS(i-1,j)])%mod;
	dp[POS(i,n-i)]=(dp[POS(i,n-i)]+mod-dp[POS(i-1,j)])%mod;
      }
    }
    for(int j=1;j<n;j++) dp[POS(i,j)]=(dp[POS(i,j)]+dp[POS(i,j-1)])%mod;
  }
  printf("%d\n",dp[POS(n-1,0)]);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
N = int(input())
A = map(int, input().split())
num = {i:0 for i in range(N+1)}
num[0] = 3
ans = 1
MOD = 1000000007
for a in A:
    ans *= num[a] % MOD
    num[a] -= 1
    num[a+1] += 1
print(ans%MOD)

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

int main() {
  int a,b;
  cin >> a>>b;
  
  for (int i=0; i<b+2;i++){
    cout << "#";
  }
  cout <<endl;

  for (int i=0; i<a;i++){
    string c;
    cin >> c;
    cout << "#" + c + "#" << endl;
  }
  
  for (int i=0; i<b+2;i++){
    cout << "#";
  }
  cout <<endl;
  
}




Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    ll a, b, n;
    cin >> a >> b >> n;
    if (n >= b) cout << a * (b - 1) / b - a * ((b - 1) / b);
    else cout << a * n / b - a * (n / b);
}


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

int main() {
	
	string s;
	cin >> s;
	
	while (s != "0") {
		int n = 0;
		if (s == "0") break;
		
		for (int i = 0; i < s.size(); i++) {
			n = n + s[i] - 48;
		}
		cout << n << endl;
		cin >> s;
	}
	
	return 0;
}


Measured memory_bytes: 3196
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair<int, int> pii;  // pair<int, int> に pii という別名を付ける
typedef long long ll;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H1, H2, M1, M2, K;
  cin >> H1 >> M1 >> H2 >> M2 >> K;
  int start, end;
  start = H1*60 + M1;
  end = H2*60 + M2 - K;
  cout << end-start << endl;
}

Measured memory_bytes: 3648
import java.io.IOException; 
import java.io.InputStream; 
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List; 

class Main{ 
	static class Edge{
		int to, cost;
		Edge(int t, int c){to=t;cost=c;}
	}

	static void solve(){
		int l = ni();
		List<Edge> edges[] = new List[21];
		for(int i=0;i<=20;++i)edges[i]=new ArrayList<>();
		for(int i=1;i<20;++i)edges[i].add(new Edge((i+1), 0));
		int[] ika = new int[21];
		for(int i=20;i>=1;--i)ika[i]=(1<<(20-i))-1;
		for(int i=19;i>=1;--i){
			if((1<<(19-i)) + ika[i+1]<l){
				edges[i].add(new Edge((i+1), (1<<(19-i))));
			}else{
				int v = i+1;
				int max = ika[v];
				for(int j=v+1;j<=20;++j){
					if(max+1 + ika[j]<l){
						edges[v].add(new Edge(j, (max+1)));
						max = max+1+ika[j];
					}
				}
				break;
			}
			if(i==1){
				int v = i;
				int max = ika[v];
				for(int j=v+1;j<=20;++j){
					if(max+1 + ika[j]<l){
						edges[v].add(new Edge(j, (max+1)));
						max = max+1+ika[j];
					}
				}
				break;
			}
		}
		int num = 0;
		for(int i=1;i<=20;++i)num+=edges[i].size();
		out.println(20+" "+num);
		for(int i=1;i<=20;++i){
			for(Edge e: edges[i])out.println(i+" "+e.to+" "+e.cost);
		}

 
	} 
 
 
 
 
	public static void main(String[] args){ 
		 solve(); 
		 out.flush(); 
	 } 
	 private static InputStream in = System.in; 
	 private static PrintWriter out = new PrintWriter(System.out); 
 
	 private static final byte[] buffer = new byte[1<<15]; 
	 private static int ptr = 0; 
	 private static int buflen = 0; 
	 private static boolean hasNextByte(){ 
		 if(ptr<buflen)return true; 
		 ptr = 0; 
		 try{ 
			 buflen = in.read(buffer); 
		 } catch (IOException e){ 
			 e.printStackTrace(); 
		 } 
		 return buflen>0; 
	 } 
	 private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;} 
	 private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);} 
	 private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;} 
 
	 private static double nd(){ return Double.parseDouble(ns()); } 
	 private static char nc(){ return (char)skip(); } 
	 private static String ns(){ 
		 StringBuilder sb = new StringBuilder(); 
		 for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b); 
		 return sb.toString(); 
	 } 
	 private static int[] nia(int n){ 
		 int[] res = new int[n]; 
		 for(int i=0;i<n;++i)res[i]=ni(); 
		 return res; 
	 } 
	 private static long[] nla(int n){ 
		 long[] res = new long[n]; 
		 for(int i=0;i<n;++i)res[i]=nl(); 
		 return res; 
	 } 
	 private static int ni(){ 
		 int res=0,b; 
		 boolean minus=false; 
		 while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); 
		 if(b=='-'){ 
			 minus=true; 
			 b=readByte(); 
		 } 
		 for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); 
		 return minus ? -res:res; 
	 } 
	 private static long nl(){ 
		 long res=0,b; 
		 boolean minus=false; 
		 while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); 
		 if(b=='-'){ 
			 minus=true; 
			 b=readByte(); 
		 } 
		 for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); 
		 return minus ? -res:res; 
	} 
} 



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

using namespace std;

using int64 = long long;

bool v[31][100005];
int con[100001];

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

  for(int i = 0; i < N; i++) {
    int S, T, L;
    cin >> S >> T >> L;
    for(int j = S; j <= T; j++) {
      if(v[L][j]++) continue;
      con[j]++;
    }
  }
  cout << *max_element(con, con + 100001) << endl;
}

Measured memory_bytes: 3584
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int n; cin >> n;
  ll ans = 0;
  FOR(i, 1, n + 1) {
    if (i % 3 != 0 && i % 5 != 0) ans += i;
  }
  cout << ans << '\n';
  return 0;
}


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

using namespace std;

typedef long long ll;

int main(){
	ll x, y;
	cin >> x >> y;
	if(y >= x){
		if(y * x >= 0)cout << y-x << endl;
		else cout << min(y-x, 1+abs(-y-x)) << endl;
	}
	else{
		if(x == 0)cout << -y+1 << endl;
		else if(y * x > 0)cout << 2+abs(y-x) << endl;
		else cout << 1+abs(abs(y)-x) << endl;
	}
    return 0;
}

Measured memory_bytes: 256
package main

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

var (
	n, k int
	ws   []int
)

func V(p int) int {
	i := 0
ENDFOR:
	for j := 0; j < k; j++ {
		t := 0
		for t+ws[i] <= p {
			t += ws[i]
			i++
			if i >= n {
				break ENDFOR
			}
		}
	}
	return i
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()

	var err error

	l1 := strings.Split(sc.Text(), " ")
	n, err = strconv.Atoi(l1[0])
	if err != nil {
		panic(err)
	}
	k, err = strconv.Atoi(l1[1])
	if err != nil {
		panic(err)
	}

	ws = make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		w, err := strconv.Atoi(sc.Text())
		if err != nil {
			panic(err)
		}
		ws[i] = w
	}

	left := 0
	right := math.MaxInt64
	for right-left > 1 {
		mid := (left + right) / 2
		v := V(mid)
		if v >= n {
			right = mid
		} else {
			left = mid
		}
	}

	fmt.Println(right)
}


Measured memory_bytes: 2328
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1000+10;
int a[MAXN],n,m;
vector<int> ans;

int main()
{
	scanf("%d %d",&n,&m);
	int cnt=0;
	for(int i=1;i<=m;++i) scanf("%d",&a[i]),cnt+=a[i]&1;
	if(cnt>2){printf("Impossible\n");return 0;};
	for(int i=2;i<m;++i) 
		if(a[i]&1) a[1]&1?swap(a[i],a[m]):swap(a[i],a[1]);
	for(int i=1;i<=m;++i) printf("%d ",a[i]);
	if(m==1&&a[1]==1) ans.push_back(1);
	else if(m==1) ans.push_back(a[1]-1),ans.push_back(1);
	else 
	{
		if(a[1]!=1) ans.push_back(a[1]-1);
		for(int i=2;i<m;++i) ans.push_back(a[i]);
		ans.push_back(a[m]+1);
	};
	printf("\n%d\n",ans.size());
	for(int i=0;i<ans.size();++i) printf("%d ",ans[i]);
 	return 0;
}

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

using namespace std;

const int K=300000;

class UnionFind{

    int par[K];
    int siz[K];
public:
    void init(int n){
        for(int i=0; i<n; i++) par[i]=i;
        for(int i=0; i<n; i++) siz[i]=1;
    }
    int find(int x){
        if(par[x]==x){
            return x;
        }else{
            return par[x]=find(par[x]);
        }
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
    void uni(int x, int y){
        x=find(x);
        y=find(y);
        if(x==y) return;

        if(siz[x]<siz[y]) swap(x, y);
        par[y]=x;
        siz[x]+=siz[y];
        //siz[y]=0;
    }
    int size(int x){
        return siz[find(x)];
    }
};

UnionFind uf;

int main(){

   int N, M;
   cin>> N>> M;
   uf.init(N+M);
   set<int> used;
   for(int i=0; i<N; i++){
      int k;
      cin>> k;
      for(int j=0; j<k; j++){
         int l;
         cin>> l;
         used.insert(l-1);
         uf.uni(l-1, i+M);
      }
   }

   cout<< (uf.size(M)==N+used.size()? "YES": "NO")<< endl;

   return 0;
}



Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<" ";
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll w,h,x,y;
    cin>>w>>h>>x>>y;
    ll a=w,b=h;
    double g=(double)w;
    double f=(double)h;
    doublecout(f*g/2);
    if(a%2==0 && b%2==0 && a/2==x && b/2==y){
        cout<<1<<endl;
    }
    else{
        cout << 0<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
int n,t,ans,maxx,sum;
int a[100007];
int main(){
    cin>>n>>t;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
    for(int i=n;i>=1;i--){
		maxx=max(a[i],maxx);
		sum=max(maxx-a[i],sum);
	}
	maxx=0;
    for(int i=n;i>=1;i--){
		maxx=max(a[i],maxx);
		if(maxx-a[i]==sum) {
			ans++;
		}	
	}
    cout<<ans<<endl;
    return 0 ;
}

Measured memory_bytes: 1148
//Bismillahir Rahmanir Rahim
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a>9 || b>9)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<a*b<<endl;
    }

}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << #x << ": " << x << '\n';
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i < n; ++i) {
    cin >> vec[i];
  }
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      ans += vec[i] * vec[j];
    }
  }
  cout << ans << '\n';
  
}


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

    retval = float("inf")
    for i in range(0, N - (K - 1)):
        left = x[i]
        right = x[i + K - 1]
        time = max(abs(left), abs(right))
        if abs(left + right) != abs(left) + abs(right):
            time += min(abs(left), abs(right)) * 2
        retval = min(retval, time)
    print(retval)


if __name__ == "__main__":
    main()


Measured memory_bytes: 62576
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	private static ArrayList<ArrayList<Byte>> adj_list   = new ArrayList<ArrayList<Byte>>(),
                                              adj_matrix = new ArrayList<ArrayList<Byte>>();

	private static final int U = 0,
			                 K = 1;

	public static void main(String[] args) {;
		 Scanner sc = new Scanner(System.in).useDelimiter(System.getProperty("line.separator"));
         Byte N = sc.nextByte();

         for(int i = 0;i < N;i++){
        	 ArrayList<Byte> ar = new ArrayList<Byte>();
        	 for(String s:sc.next().split("\\s")){
        		 ar.add(Byte.parseByte(s));
        	 }
        	 adj_list.add(ar);
        	 adj_matrix.add(new ArrayList<Byte>());
         }

//         for(ArrayList<Byte> l:adj_list){
//        	 for(byte b:l){System.out.print(b+" ");}
//        	 System.out.println();
//         }

         byte u,k,zero=0,one=1;
         ArrayList<Byte> il,o;
         for(int i = 0; i < N; i++){
        	 il = adj_list.get(i);
        	 u = il.get(U);
        	 k = il.get(K);
        	 o = new ArrayList<Byte>();
        	 for(int j = 0;j < N;j++){o.add(zero);}
        	 for(int j = 0;j < k;j++){
//        		 System.out.print("j:"+j+", k:"+k+", ");
//        		 System.out.println(il.get(j+2));
        		 o.set(il.get(j+2)-1,one);}
        	 adj_matrix.set(u-1,o);
         }

         for (ArrayList<Byte> ol:adj_matrix) {
			for(int i=0;i<N;i++){
				System.out.print(ol.get(i));
				if(i<N-1){System.out.print(" ");}
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 24292
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

set<ll>st, stcom;
void divisor(ll n) {
	for (ll i = 1; i*i <= n; i++) {
		if (n%i == 0) {
			if (i == n / i) {
				st.insert(i);
			}
			else {
				st.insert(i);
				st.insert(n / i);
			}
		}
	}
}
void divisor2(ll n) {
	for (ll i = 1; i*i <= n; i++) {
		if (n%i == 0) {
			if (i == n / i) {
				if(st.count(i))stcom.insert(i);
			}
			else {
				if(st.count(i))stcom.insert(i);
				if(st.count(n/i))stcom.insert(n / i);
			}
		}
	}
}

ll gcd(ll a, ll b) {
	if (a == 0 || b == 0)return 0;
	if (a%b == 0)return b;
	return gcd(b, a%b);
}



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

	ll A, B;
	cin >> A >> B;
	divisor(A);
	divisor2(B);
	
	set<int>tot;
	fore(x, stcom) {
		if (tot.size() == 0)tot.insert(x);
		else {
			int ok = 1;
			fore(y, tot) {
				if (gcd(y,x) != 1)ok = 0;
			}
			if (ok)tot.insert(x);
		}
	}
	puts(tot.size());

	return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define LL long long
#define PI 3.14159265359
template<class T> inline void chmax(T & a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> void print_vector(vector<T> vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << "]" << endl;
}
template<class T> void print_pair_vector(vector<pair<T, T> > vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << "(" << vec[i].first << "," << vec[i].second << ") ";
	}
	cout << "]" << endl;
}

int main(void) {
	int M;
	cin >> M;
	cout << 24 - M + 24 << endl;
	return 0;
}

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

int main(void){
	int h,m,s;
	int S;
	cin >> S;
	h = S / 3600; 
	m = (S % 3600) / 60;
	s = S % 60;

	cout << h << ":" << m << ":" << s << endl;

	return 0;
}

Measured memory_bytes: 1168
#include<algorithm>
#include <bits/stdc++.h>
#include <math.h>
#include <cstdio>
using namespace std;
int main(void){
	string s,ds[100];
	int j,c=0,n,m,i,di[100]={0};
	cin>>n;
	for(i=0;i<n;i++){
		cin>>s;
		int f=1;
		for(j=0;j<c;j++){
			if(ds[j]==s){
				di[j]++;
				f=0;
			}
		}
		if(f){
			ds[c]=s;
			di[c]++;
          	c++;
		}
	}
	cin>>m;
	for(i=0;i<m;i++){
		cin>>s;
		for(j=0;j<c;j++){
			if(ds[j]==s){
				di[j]--;
			}
		}
	}
	int ans=0;
	for(i=0;i<c;i++) ans=max(ans,di[i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
//! Generic utility for reading data from standard input, based on [voxl's
//! stdin wrapper](http://codeforces.com/contest/702/submission/19589375).
#![allow(unused_imports)]
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet, VecDeque};
use std::io::{self, BufWriter, Write};

#[derive(Default)]
struct Scanner {
    #[allow(dead_code)]
    buffer: Vec<String>,
}

impl Scanner {
    #[allow(dead_code)]
    fn next<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            io::stdin().read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

fn solve<T: Write>(scan: &mut Scanner, out: &mut BufWriter<T>) {
    // CODE HERE
    let x: u64 = scan.next();
    let five_hundreds = x / 500;
    let balance = x % 500;
    let fives = balance / 5;

    let happiness = five_hundreds * 1000 + fives * 5;
    writeln!(out, "{}", happiness);
}

fn main() {
    let mut scan = Scanner::default();
    let mut out = BufWriter::new(io::stdout());
    solve(&mut scan, &mut out);
}


Measured memory_bytes: 4352
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

sys.setrecursionlimit(10**6)
# def solve():
# 	n, m = read()
# 	graph = [[] for i in range(n+1)]
# 	for _ in range(m):
# 		u, v = read()
# 		graph[u].append(v)
# 	visited = [0 for i in range(n+1)]
# 	def dfs(node):
# 		if visited[node]:
# 			return(visited[node])
# 		if not graph[node]:
# 			visited[node] = 0
# 			return(0)
# 		m = 0
# 		for i in graph[node]:
# 			m = max(m, dfs(i))
# 		visited[node] = 1 + m#ax(dfs(i) for i in graph[node])
# 		# print(node, visited[node])
# 		return(visited[node])

# 	ans = 0
# 	for i in range(1, n+1):
# 		ans = max(ans, dfs(i))
# 	# print(visited)
# 	print(ans)


def grid():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	# dic = {}
	dp = [-1]*m*n
	# print(dp, len(dp))
	def count_paths(i, j):
		# key = str(i)+"-"+str(j)
		# if key in dic:
		# 	return(dic[key])
		key = (i*m + j)
		# print(key)
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "#":
			dp[key] = 0
			return(0)
		if dp[key] > -1:
			return(dp[key])
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		# dic[key] = paths
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))

def grid2():
	n, m = read()
	arr = []
	for i in range(n):
		arr.append(inp().strip())
	dp = {}
	# print(dp, len(dp))
	def count_paths(i, j):
		key = str(i)+"-"+str(j)
		if key in dp:
			return(dp[key])
		# key = (i*m + j)
		# print(key)
		if key in dp:
			return(dp[key])
		if i == n-1 and j == m-1:
			dp[key] = 1
			return(1)
		if i == n or j == m:
			return(0)
		if arr[i][j] == "#":
			dp[key] = 0
			return(0)
		
		paths = (count_paths(i+1, j) + count_paths(i, j+1)) % (10**9 + 7)
		# dic[key] = paths
		dp[key] = paths
		return(paths)
	print(count_paths(0, 0))



if __name__ == "__main__":
	# solve()
	grid2()

Measured memory_bytes: 188984
N,W = map(int,input().split())
w_in, v = map(int,input().split())
table = [[] for i in range(4)]
table[0].append(v)
for i in range(N-1):
    w, v = map(int,input().split())
    table[w-w_in].append(v)
for i in range(4):
    table[i].sort(reverse=True)
    for j in range(len(table[i])-1):
            table[i][j+1] += table[i][j]
    table[i].insert(0,0)
ans = 0
for i in range(len(table[0])):
    for j in range(len(table[1])):
        for k in range(len(table[2])):
            for l in range(len(table[3])):
                if w_in*i+(w_in+1)*j+(w_in+2)*k+(w_in+3)*l <= W:
                    ans = max(ans, table[0][i]+table[1][j]+table[2][k]+table[3][l])
print(ans)

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

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

using ll = long long;
using P = pair<int,int>;
using mp =  map<char,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;


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

    int x, y;
    cin >> x >> y;

    if(x == 2){
        x = 3;
    }else if(x == 4 || x == 6 || x == 9 || x == 11){
        x = 2;
    }else{
        x = 1;
    }

    if(y == 2){
        y = 3;
    }else if(y == 4 || y == 6 || y == 9 || y == 11){
        y = 2;
    }else{
        y = 1;
    }

    if(x == y){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

int main() {
    // input, ready
    ll N,A,B;
    cin >> N >> A >> B;

    ll mul = N / (A+B);

    // output
    ll resu = 0;
    if ((N-(A+B)*mul) > A) resu = A*(mul+1);
    else resu = A*mul + N-(A+B)*mul;
    cout << resu << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
int main(void){
int datasets,i,hit=0,out,remain=0;
std::string input;
std::cin >> datasets;
for(i=0;i<datasets;++i){
	out=0;
	while(out<3){
		std::cin >> input;
		if(input=="HIT"){
			++hit;
			++remain;
		}
		if(input=="HOMERUN"){
			++hit;
			remain=0;
		}
		if(input=="OUT") ++out;
	}
	if(remain>3) remain=3;
	std::cout << hit-remain << std::endl;
	hit=0;
	remain=0;
}
return 0;
}

Measured memory_bytes: 1208