akhauriyash/Code-Regression huggingface dataset:
/*
 ──────────────────────────────────────
 ─▄▄▄───────────▄▄▄▄▄▄▄────────────────
 █▀░▀█──────▄▀▀▀░░░░░░░▀▀▄▄────────────
 █░░░░█───▄▀░░░░░░░░░░░░░░░▀▄───────▄▄▄
 █▄░░░▀▄▄▀░░██░░░░░░░░░░░░░░▀█────█▀▀░█
 ─█░░░░█▀░░░▀░░░░░░░░██░░░░░░▀█─▄█░░░░█
 ─▀█░░▄█░░░░░░░▄▄▄░░░░▀░░░░░░░███░░░░█▀
 ──█▄░█░░░░░▄███████▄░░░░░░░░░█▀░░░░▄▀─
 ──▀█░█░░░░▄██████████░░░░░░░▄█░░░░▄▀──
 ───███░░░░███████████░░░░░░▄█░░░░█▀───
 ────█░░░░░██████████▀░░░░░░█░░░░█▀────
 ────█░░░░░░▀███████▀░░░░░░░█▄▄▄▀──────
 ────█░░░░░░░░▀▀▀▀░░░░░░░░░░░▀█────────
 ────█░░░░░░░░░░░░░░░░░░░░░░░░█────────
 ────█░░░░░░░░░░░░░░░░░░░░░░░░█────────
 ────█░░░░░░░░░░░░░░░░░░░░░░░░█────────
 ──────────────────────────────────────
 */
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define jj pair<int, pair< int , int > >
#define f first
#define s second
using namespace std ;

void TIME();

int n;
struct Tnode
{
    int x, y, id;
};
Tnode A[100010];
struct Tnode1
{
    int rt1, rt2, val;
    Tnode1(int _rt1,int _rt2,int _val)
    {
        rt1 = _rt1;
        rt2 = _rt2;
        val = _val;
    }
};
bool cmp(Tnode1 a, Tnode1 b)
{
    return a.val < b.val;
}
bool xcmp(Tnode a, Tnode b)
{
    return a.x < b.x;
}
bool ycmp(Tnode a, Tnode b)
{
    return a.y < b.y;
}
vector <Tnode1> Canh;
int pa[100010];
int val[100010];

int root(int u)
{
    if(pa[u] == u) return u;
    return pa[u] = root(pa[u]);
}

bool DSU(int x, int y)
{
    // cout <<".";
    x = root(x);
    y = root(y);
    if(x == y)
    {
        return 0;
    }
    if(val[x] < val[y])
    {
        swap(x, y);
    }
    val[x] += val[y];
    pa[y] = x;
    return 1;
}
main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);

	// freopen("D_build.inp","r",stdin);
	// freopen("D_build.inp","w",stdout);
	// freopen("D_build.out","w",stdout);

    cin >> n;
    for(int i = 1, x, y ; i <= n ; i ++)
    {
        cin >> x >> y;
        A[i].x = x;
        A[i].y = y;
        A[i].id = i;
    }
    sort(A+1,A+1+n,xcmp);
    for(int i = 2 ; i <= n ; i ++)
    {
        Canh.push_back(Tnode1(A[i-1].id,A[i].id, min( abs(A[i-1].x-A[i].x),abs(A[i-1].y- A[i].y)))) ;
    }
    sort(A+1,A+1+n,ycmp);
    for(int i = 2 ; i <= n ; i ++)
    {
        Canh.push_back(Tnode1(A[i-1].id,A[i].id,min(abs(A[i-1].x-A[i].x), abs(A[i-1].y-A[i].y))));
    }
    sort(Canh.begin(), Canh.end(), cmp);
    int Ans = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        val[i] = 1;
        pa[i] = i;
    }
//    for(int i = 0 ; i < Canh.size() ; i ++)
//    {
//        cout << Canh[i].rt1 <<" "<< Canh[i].rt2 <<" " << Canh[i].val  << endl;
//    }
    for(int i = 0 ; i < Canh.size() ; i ++)
    {
        Tnode1 Res = Canh[i];
        //cout <<".";
        if(DSU(Res.rt1, Res.rt2))
        {
            Ans += Res.val;
        }
    }
    cout << Ans;
	return 0;
}

void TIME()
{
	cerr << "Time elapsed : " << clock() * 1000 / CLOCKS_PER_SEC << "ms\n";
}


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

int main(){
    int h1, h2, m1, m2 , k; cin >> h1 >> m1 >> h2 >> m2 >> k;
    m1 += 60 *  h1; m2 += h2 * 60;
    cout << m2 - m1 - k << '\n';
    return 0;
}

Measured memory_bytes: 3636
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int H = Integer.parseInt(in.next());
		int W = Integer.parseInt(in.next());
		int[][] c = new int[10][10];
		for(int x = 0; x <= 9; x++){
			for(int y = 0; y <= 9; y++){
				c[x][y] = Integer.parseInt(in.next());
			}
		}
		for(int i = 0; i < 10; i++){
			for(int j = 0; j < 10; j++){
				for(int k = 0; k < 10; k++){
					c[j][k] = Math.min(c[j][k],c[j][i] + c[i][k]);
				}
			}
		}
		int ans = 0;
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				int tmp = Integer.parseInt(in.next());
				if(tmp != -1&&tmp != 1)ans += c[tmp][1];
			}
		}

		System.out.println(ans);
	}
}

Measured memory_bytes: 39044
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;

const ll Mod = 1e9 + 7;
ll dp[maxn][13];
int main()
{
    FASTIO
    /*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
//*/
    int T;
    //cin >> T;
    T = 1;
    for (int cs = 1; cs <= T; cs++) {
        string s;
        cin >> s;
        int n = s.length();

        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            int c;
            if (s[i] == '?') c = -1;
            else c = s[i] - '0';
            for (int j = 0; j < 10; j++) {
                if (c != -1 && c != j) continue;
                for (int k = 0; k < 13; k++) {
                    dp[i + 1][(k * 10 + j) % 13] += dp[i][k];
                }
            }

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

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
    return 0;
}

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

void solve()
{
    string st; cin >> st;
    int n = st.size();
    if(st[n-1] == 's')
    {
        cout << st<< "es" << endl;
    }
    else
    {
        cout << st <<"s" << endl;
    }
}
int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 3632
# include <stdio.h>
int n,m;
int a[2521],b[2521],c[2521];
long long INF = 1000000001;
long long INFLL = (long long)INF * INF;
 
long long dist[1252];
int over[1252];
int main(void){
    // Here your code !
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        a[i]--;b[i]--;
    }
    for(int i=0;i<n;i++)dist[i] = -INFLL;
    dist[0] = 0;
    for(int k=0;k<=(2 * n - 2);k++)for(int i=0;i<m;i++){
        if(dist[a[i]] != -INFLL && dist[b[i]] < dist[a[i]] + c[i]){
            dist[b[i]] = dist[a[i]] + c[i];
            if(k == 2*n - 2){
                over[b[i]] = 1;
            }
        }
    }
    if(over[n-1])printf("inf\n");
    else printf("%lld\n",dist[n-1]);
    return 0;
}

Measured memory_bytes: 256
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(N)]

counter = 0

for i in range(N):
    num = 0
    for j in range(M):
        num += B[j] * A[i][j]

    num += C
    if num > 0:
        counter += 1

print(counter)


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

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

	long long int r,d,x;

	cin >> r >> d >> x;

	for(int i=0;i<10;i++)
	{
		x = r*x - d;
		cout << x << '\n';
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    string S,s;
    long long K,i,c1,c2,n,a,t;
    cin>>S>>K;
    s=S+S;
    c1=0;c2=0;
    n=S.length();
    t=1;
    for(i=0;i<n-1;i++){
        if(S[i]!=S[i+1]){
            t=0;
        }
    }
    if(t){
        a=(n*K)/2;
        cout<<a<<endl;
        return 0;
    }
    for(i=0;i<n-1;i++){
        if(S[i]==S[i+1]){
            c1++;
            S[i+1]='0';
        }
    }
    for(i=0;i<n*2-1;i++){
        if(s[i]==s[i+1]){
            c2++;
            s[i+1]='0';
        }
    }
    c2=c2-c1;
    a=c1+c2*(K-1);
    cout<<a<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s; 
    cin >> s;
    int n=s.size();
    vector<ll> a(n+1);
    int tmp=1;
    ll c[2019]={1};
    for(int i=n-1;0<=i;i--){
        a[i]=a[i+1];
        a[i]+=(s[i]-'0')*tmp;
        a[i]%=2019;
        tmp*=10;
        tmp%=2019;
        c[a[i]]++;
    }
    ll ans=0;
    for(int i=0;i<2019;i++){
        ans+=c[i]*(c[i]-1)/2;
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 5180
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args)throws IOException {

		BufferedReader br =
			new BufferedReader(new InputStreamReader(System.in));

		int x = Integer.parseInt(br.readLine());
		
			x = x * x * x;
			
		System.out.println(x);
	}

}



Measured memory_bytes: 24308
H,W,K=map(int,input().split())
S=[[] for i in range(0,H)]
for i in range(0,H):
    S[i]=input()

sumtable=[[0 for i in range(0,W)] for j in range(0,H+1)]
for i in range(1,H+1):
    for j in range(0,W):
        sumtable[i][j]=sumtable[i-1][j]+(int(S[i-1][j])&1)


ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sumtable[end+1][j]-sumtable[start][j]
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sumtable[end+1][j]-sumtable[start][j]
            if max(white)>K:
                break
    else:
        test=count+len(segment)-1
        if test<ans:
            ans=test

print(ans)

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

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

  bool ans = a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0];
  cout << (ans ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let s: Vec<char> = iterator.next().unwrap().chars().collect();
    let t: Vec<char> = iterator.next().unwrap().chars().collect();

    for i in 0..s.len() {
        if s[i] != t[i] {
            return "No".to_string();
        }
    }

    return "Yes".to_string();
}


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

int main(){
  string S;
  cin >> S;
  if(S.at(0) == 'R' && S.at(0) == S.at(1) && S.at(1) == S.at(2)){
  	cout << 3 << endl;
  }else if(S.at(0) == 'S' && S.at(0) == S.at(1) && S.at(1) == S.at(2)){
    cout << 0 << endl;
  }else if(S.at(1) == 'R'&& (S.at(0) == S.at(1) || S.at(1) == S.at(2))){
    cout << 2 << endl;  
  }else{
    cout << 1 << endl;
  }
}

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

int main() {
	int N, count = 0, maxv = 0, ans = 1,j, v;cin >> N;
	for (int i = 1;i <= N;i++) {
		v = i;
		j = i;
		while (j % 2 == 0) {
			++count;
			j = j / 2;
        }if (maxv < count) {
			maxv = count;
			ans = v;
		}count = 0;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

using ll = long long;

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

    int n;
    cin >> n;

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

    vector<ll> dp(1 << n), group(1 << n);
    for (int s = 0; s < 1 << n; ++s)
        for (int v = 0; v < n; ++v) {
            if (!(s >> v & 1)) continue;
            for (int u = v + 1; u < n; ++u)
                if (s >> u & 1) group[s] += a[u][v];
        }

    for (int s = 0; s < 1 << n; ++s) {
        int sub = s;
        do {
            dp[s] = max(dp[s], dp[s & ~sub] + group[sub]);
            sub = (sub - 1) & s;
        } while (sub != s);
    }

    cout << dp[(1 << n) - 1] << endl;

    return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll h, w, d;std::cin >> h >> w >> d;
  ll N = max(h, w) * 2;
  vvl dat = VV(N, N, 0, ll);
  vvl ans = VV(h, w, -1, ll);
  map<ll, char> c;
  c.emplace(0, 'R');
  c.emplace(1, 'G');
  c.emplace(2, 'Y');
  c.emplace(3, 'B');
  for(ll i=0;i<N;i++){
    for(ll j=0;j<N;j++){
      if((i/d)%2==0) dat[i][j] = ((j/d)%2==0?0:1);
      else dat[i][j] = ((j/d)%2==0?2:3);
    }
  }
  /*
  re(i, N){
    re(j, N) std::cout << dat[i][j];
    std::cout << '\n';
  }
  */
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      ans[i][j] = dat[i-j+N/2][i+j];
    }
  }

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++) std::cout << c.at(ans[i][j]);
    std::cout << '\n';
  }
  return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    n -= k;
    cout << ( n + k - 2 )  / ( k - 1 ) + 1 << endl;

    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(){
	
	int in = 0;
	
	scanf("%d",&in);
	
	if(in%2 == 0){
		printf("0.5000\n");
	}else{
		printf("%f\n",((double)(in-1)/2.0+1.0) / (double)in);
	}
	
	return 0;
}

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

class UnionFind {
    vector<int> data;
    ll num;
public:
    UnionFind(int size) : data(size, -1), num(size) { }
    bool unite(int x, int y) {//xとyの集合を統合する
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        num -= (x != y);
        return x != y;
    }
    bool findSet(int x, int y) {//xとyが同じ集合か返す
        return root(x) == root(y);
    }
    int root(int x) {//xのルートを返す
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    ll size(int x) {//xの集合のサイズを返す
        return -data[root(x)];
    }
    ll numSet() {//集合の数を返す
        return num;
    }
};

int main(){
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a--;b--;
    uf.unite(a,b);
  }
  cout<<uf.numSet()-1<<endl;
}

Measured memory_bytes: 3784
N = int(input())
W = [input() for i in range(N)]

hantei = 0

for i in range(N):
    for j in range(i+1,N):
        if W[i] == W[j]:
            hantei = 1
            break

for j in range(N-1):
    if W[j][-1] != W[j+1][0]:
        hantei = 1
        break

if hantei == 1:
    print("No")
else:
    print("Yes")

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n,a;
    cin >> a >> n;
    if(a>12)
        cout << n;
    else if(a>=6)
        cout << n/2;
    else
        cout << "0";
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int a[3];

int main()
{
	in >> a[0] >> a[1] >> a[2];

	std::sort(a, a + 3);
	if (a[0] + a[1] == a[2])
	{
		out << "Yes" << std::endl;
	}
	else
	{
		out << "No" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;
const int INF = pow(2, 30) - 1;

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

  ll A, B, C;
  cin >> A >> B >> C;

  ll num1 = 4*A*B;
  ll num2 = (C-A-B)*(C-A-B);
  ll num3 = C - A - B;

  if(num3<0){
    cout << "No" << endl;
  }
  else{
    if (num2 - num1 > 0)
    {
      cout << "Yes" << endl;
    }
    else
    {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

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

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

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

    sort(a, a+n);

    for (int i = 0; i < n-1; i++) {
        a[i+1] = gcd(a[i], a[i+1]);
    }

    cout << a[n-1] << "\n";
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main()
{
  string s,t;
  cin >> s >> t;
  if(s.size() > t.size()){
    cout << "GREATER" << endl;
    return 0;
  }
  else if(s.size() < t.size()){
    cout << "LESS" << endl;
    return 0;
  }
  for(int i=0; i<s.size(); i++){
	if(s[i] > t[i]){
      cout << "GREATER" << endl;
      return 0;
    }
    else if(s[i] < t[i]){
      cout << "LESS" << endl;
      return 0;
    }
  }
  cout << "EQUAL" << endl;
  
  return 0;
}

Measured memory_bytes: 256
import sys
import math

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    K = int(input())
    A = list(map(int, input().split()))

    # ラウンドiにおける通過者を保存
    m = 2
    M = 2
    for i in range(K - 1, -1, -1):
        n = (m + A[i] - 1) // A[i]
        tmp_m = n * A[i]
        tmp_M = (M // A[i]) * A[i] + A[i] - 1
        if tmp_m > M or tmp_M < m:
            print(-1)
            return
        m = tmp_m
        M = tmp_M

    print(m, M)


if __name__ == "__main__":
    main()


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

from itertools import combinations

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

gcd_n = gcd(a,b)

#L = [i for i in range(1,gcd_n+1) if gcd_n%i==0]

def div(num):
    l = [1]
    if(num==1):
        return [1]
    while(num%2==0):
        num //=2
        l.append(2)
    f = 3
    while(f*f<=num):
        if num%f==0:
            num //= f
            l.append(f)
        else:
            f += 2
    
    if num!=1:
        l.append(num)
    return l

l = div(gcd_n)
cnt = 0
pre = 0
for i in range(len(l)):
    if pre==l[i]:
        continue
    pre = l[i]
    cnt += 1
print(cnt)


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

int main() {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll x = a * c;
	x = max(x, a * d);
	x = max(x, b * c);
	x = max(x, b * d);
	cout << x << endl;
	return 0;
}

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

double n;

signed main() {
    cin >> n;
    rep(i,50001) if ((int)(i*1.08) == n) {
        cout << i << endl;
        return 0;
    }
    cout << ":(" << endl;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll L, R;
  cin >> L >> R;
  ll v = 2019;
  ll m = L + min(R - L, 2019ll);
  for (ll i = L; i <= m - 1; i++) {
    for (ll j = i + 1; j <= m; j++) {
      ll t = (i % 2019) * (j % 2019);
      t %= 2019;
      v = min(t, v); 
    }
  }
  cout << v << "\n";
  return 0;
}

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

typedef long long int ll;

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

    ll s;
    cin>>s;

    ll val = ceil(sqrt(s));
    ll diff = val*val-s;


    cout<<val<<" "<<1<<" "<<diff<<" "<<val<<" "<<"0 0"<<endl;

}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
	int n,m,i,j,k;
	scanf("%d %d",&n,&m);
	int a[n][m],b[m],c[m],term;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(i=0;i<m;i++){
		scanf("%d",&b[i]);
	}
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			c[i]=a[i][j]*b[j];
			term=0;
			for(k=0;k<m;k++){
				term=term+a[i][k]*b[k];
			}
			
		}
		c[i]=term;
		printf("%d\n",c[i]);
	}
	return 0;
}


Measured memory_bytes: 2048
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	for (int n; cin >> n&&n;) {
		int y; cin >> y;
		double max = 0, ans = -1;
		rep(i, 0, n) {
			int b, r, t; cin >> b >> r >> t;
			if (t == 1) {
				if (max < 1 + y*(double)r / 100) {
					max = 1 + y*(double)r / 100;
					ans = b;
				}
			}
			else {
				if (max < pow(1 + (double)r / 100, y)) {
					max = pow(1 + (double)r / 100, y);
					ans = b;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3428
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int main() {
	int N, A;
	cin >> N >> A;
	puts(N % 500 <= A ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 256
///******* In the name of Allah *******///

#include <bits/stdc++.h>
using namespace std;

//long long int ar[100013];
long int gcd(long int a, long int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
//int sieve(long long int a)
//{
//    long long int i,j;
//    memset(ar,0,sizeof(ar));
//    for(i=2; i<=a; i++)
//    {
//        if(ar[i]==0)
//        {
//            for(j=i+i; j<=a; j+=i)
//            {
//                ar[j] = 1;
//            }
//        }
//    }
//    if(ar[a]==0)
//        return 1;
//    else
//        return 0;
//}

void Ok()
{
    long int a[10013],b,c,d,e,f,g,h,t,i = 0,j = 0,k,l,m,n,r,rcv,lo,hi,mid,w,ab;
    long int sum = 0,ans_1,ans_2,ans_3,cnt_1 = 0,cnt_2 = 0,cnt_3 = 0,Max,Min,flag = 0,div,temp;
    long double aa,bb,cc,dd,ee,ff,gg;
    char aaa[1013],bbb,ccc,ddd;
    string spc,in[113],rev;

    for(i=1; i<=6; i++)
    {
        cin>>aaa[i];
    }
    for(i=3; i<=6; i+=2)
    {
        if(aaa[3]==aaa[4] && aaa[5]==aaa[6])
            flag = 1;
    }
    if(flag)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

    return;
}

int main()
{
    Ok();

    return 0;
}


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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}


int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	string s;
	cin >>s;
	
	int r = count(all(s), '1');
	int b = sz(s) - r;
	cout << 2 * min(r, b) <<"\n";
	return 0;
}


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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back

template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

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

const int inf=1e9;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};	

int main(){
	int n,m;
	cin>>n>>m;

	int sum=0,a[100];
	for (int i = 0; i < n; i++){
		cin>>a[i];
		sum+=a[i];
	}

	double t=(double)sum/(4*m);
	int cnt=0;
	for (int i = 0; i < n; i++){
		if((double)a[i]>=t)cnt++;
		if(cnt==m){
			cout<<"Yes"<<endl;
			return 0;
		}
	}

	cout<<"No"<<endl;

	return 0;
}



Measured memory_bytes: 256
def abs_diff(T):
    # 番号がT以下
    S1 = sum([W[i] for i in range(N) if i+1 <= T])
    # 番号がT以降
    S2 = sum([W[i] for i in range(N) if i +1 > T])
    # 絶対値の差
    return abs(S1 - S2)

def min_diff(absolute_diff):
    return min(absolute_diff)
  
  
# 2 <= N <= 100
N = int(input())

# 1 <= Wi <= 100
W = list(map(int, input().split()))

# 1 <= T < N
T = list(range(1, N))

T_list = list(range(1, N))
output = []
for T in T_list:
    absolute_diff = abs_diff(T)
    output.append(absolute_diff)
    
print(min_diff(output))

Measured memory_bytes: 3064
#include <stdio.h>

int main()
{
    int age, a, b;
    scanf("%d", &age);
    if (age == 1)
    {
        printf("Hello World\n");
    } else {
        scanf("%d%d", &a, &b);
        printf("%d\n", a+b);
    }
    return 0;
}


Measured memory_bytes: 128
import java.util.*;
import java.util.Collections;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();
        String A[] = new String [N];
        for(int i = 0;i < N;i++){
            A[i] = sc.next();
        }
        Arrays.sort(A);
        StringBuilder B = new StringBuilder();
        for(int i = 0;i < A.length;i++){
            B.append(A[i]);
        }
        System.out.println(B);
    }
}


Measured memory_bytes: 22100
#include<bits/stdc++.h>
using namespace std;
int main(){
  int W; int A; int B;
  cin>>W>>A>>B;
  int L=max(A,B);
  int R=min(A+W,B+W);
  if(L-R>=0)
    cout<<L-R<<endl;
  else cout<<0<<endl;
}


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

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


Measured memory_bytes: 3100
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 平均点を代入する配列
		int[] average;
		average = new int[19];

		// 平均点を代入する要素の個数
		int numDataSet = 0;

		// データ読み込みループ
		for (int k = 0; k < 19; k++) {

			// 審判の数読み込み
			String str = br.readLine();
			int numJudges = Integer.parseInt(str);

			// 審判の数が０なら終了
			if (numJudges == 0)
				break;

			// 点数を代入する配列
			int[] score;
			score = new int[numJudges];

			// 点数代入、最大値・最小値は最初の２つに格納
			for (int i = 0; i < numJudges; i++) {
				String str1 = br.readLine();
				int point = Integer.parseInt(str1);
				score[i] = point;

				if (score[0] < score[i]) {
					int temp = score[0];
					score[0] = score[i];
					score[i] = temp;
				}

				if (score[1] > score[i]) {
					int temp = score[1];
					score[1] = score[i];
					score[i] = temp;
				}
			}

			// 最大値と最小値を除いた合計点÷（審判の数ー２）
			int sum = 0;
			for (int i = 2; i < numJudges; i++) {
				sum += score[i];
			}
			int ave = sum / (numJudges - 2);

			// 平均的配列に格納
			average[k] = ave;

			numDataSet++;

		}

		for (int l = 0; l < numDataSet; l++) {
			System.out.println(average[l]);

		}

	}

}



Measured memory_bytes: 24312
s = input().strip()
t = input().strip()

length = int(len(t))
slist = []
tlist = []

for i in range(length - 1):
  slist.append(s[i])
  tlist.append(t[i])
  
if slist == tlist:
  print('Yes')
else:
  print('No')
  




 




Measured memory_bytes: 9116
#include <stdio.h>
#include <string.h>

int lcs(char x[], char y[]){
 int i,j;
 int m = strlen(x);
 int n = strlen(y);
 int c[m+1][n+1];


 for(i = 0;i <= m; i++)
  c[i][0] = 0;
 for(j = 0;j <= n; j++)
  c[0][j] = 0;

 for(i = 1;i <= m; i++){
  for(j = 1;j <= n; j++){
    if(x[i-1] == y[j-1])
     c[i][j] = c[i-1][j-1] + 1;
    else if(c[i-1][j] >= c[i][j-1])
     c[i][j] = c[i-1][j];
    else
     c[i][j] = c[i][j-1];
  }
 }
 return c[m][n];
}

int main(){
 char x[1000],y[1000];
 int n,i,j;
 scanf("%d",&n);
 for(i = 0;i < n;i++){
    scanf("%s %s",x, y);
   printf("%d\n",lcs(x,y));
 }

 return 0;

     
}

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

#define ABS(X) ((X)<0?-(X):(X))
#define MIN(X,Y) ((X)<(Y)?(X):(Y))

int main(void){
  long long q,h,s,d,n;
  long long ans;
  
  cin >> q >> h >> s >> d >> n;
  s = MIN(s,MIN(q*4,h*2));
  ans = MIN(s*n, n/2*d+(n%2*s));
  cout << ans << endl;
  return 0;
}


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

using namespace std;

void Swap(vector<int>& v, int index1, int index2) {
    int tmp = v[index1];
    v[index1] = v[index2];
    v[index2] = tmp;
}


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

    vector<int> v(w);
    for(int i = 0; i < v.size(); ++i) {
        v[i] = i + 1;
    }
    
    int n;
    cin >> n;

    for(int i = 0, a, b; i < n; ++i) {
        cin >> a;
        cin.ignore();
        cin >> b;

        Swap(v, a - 1, b - 1);
    }

    for(auto x : v) {
        cout << x << '\n';
    }

    return 0;
}

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

const int MAXV = 6.1e5;
const int MAXN = 13;
int p3[MAXN];
int n;

struct node {
	union {
		int idx;
		node* c[3];
	};
	bool lazy;
};
node node_pool[MAXV * 3];
int node_idx = 0;

node* init(int cur, int pos) {
	node* v = &(node_pool[node_idx++]);
	if (cur == n) {
		// leaf
		v->idx = pos;
	} else {
		for (int x = 0; x < 3; x++) {
			v->c[x] = init(cur+1, pos + p3[cur] * x);
		}
	}
	return v;
}

void apply(node* v) {
	assert(v);
	v->lazy = !v->lazy;
	swap(v->c[1], v->c[2]);
}

void propagate(node* v) {
	if (!v->lazy) return;
	v->lazy = false;
	for (int x = 0; x < 3; x++) apply(v->c[x]);
}

void upd(node* v, int cur) {
	if (cur == n) {
		// leaf
	} else {
		propagate(v);
		swap(v->c[1], v->c[2]);
		swap(v->c[0], v->c[1]);
		upd(v->c[0], cur+1);
	}
}

int ans[MAXV];

void dfs(node* v, int cur, int pos) {
	if (cur == n) {
		ans[v->idx] = pos;
	} else {
		propagate(v);
		for (int x = 0; x < 3; x++) dfs(v->c[x], cur+1, pos + x * p3[cur]);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string t;
	cin >> n >> t;
	p3[0] = 1;
	for (int i = 1; i <= n; i++) p3[i] = p3[i-1] * 3;
	node* tr = init(0, 0);
	for (char op : t) {
		if (op == 'R') {
			upd(tr, 0);
		} else if (op == 'S') {
			apply(tr);
		} else assert(false);
	}
	dfs(tr, 0, 0);
	for (int i = 0; i < p3[n]; i++) {
		cout << ans[i] << " \n"[i+1==p3[n]];
	}
}


Measured memory_bytes: 31372
function Main(input) {
  input = input.split("\n");
  var a = splitBigInt(input[0]);
  var b = splitBigInt(input[1]);
  result = "EQUAL";
  for(var i = 0, len = a.length; i < len; i++) {
    if(result !== "EQUAL") {
      break;
    }
    var aa = parseInt(a[i], 10);
    var bb = parseInt(b[i], 10);
    if(aa < bb) {
      result = "LESS";
    } else if(aa > bb) {
      result = "GREATER";
    } else {
      result = "EQUAL";
    }
  }
  console.log(result);
}
function normalize(str) {
  while(str.length <= 101) {
    if(str.length == 101) break;
    str = "0" + str;
  }
  return str;
}
function splitBigInt(str) {
  str = normalize(str);
  var ret = [];
  
  for(var i = 0; i < 11; i++) {
    ret.push(str.substring(0 + i * 10, 10 + i * 10));
  }
  return ret;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
S = input()
K = input()

L = []
tmp = []
pre = ""
for s in S:
    if len(tmp) == 0:
        pre = s
        tmp.append(s)
    elif pre == s:
        tmp.append(s)
    else:
        L.append(tmp)
        pre = s
        tmp = [s]
L.append(tmp)

count = 0
for l in L:
    count += int(len(l) / 2)
    # print(l)
count *= int(K)
if len(L) == 1:
    if len(L[0]) == 1:
        count = int(int(K) / 2)
    elif len(L[0]) % 2 == 1:
        count += int(int(K) / 2)

elif L[0][0] == L[len(L)-1][0]:
    if len(L[0]) % 2 == 1 and len(L[len(L)-1]) % 2 == 1:
        count = count + int(K) - 1
print(count)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int,int> P;
const ll MOD = (int)1e9+7;
const ll INF = MOD*MOD;
const ll powll = 1LL<<1;

int main(){
  long double a,b,c; cin >> a >> b >> c;
  if(2*sqrtl(a)*sqrtl(b) < c-a-b) cout << "Yes\n";
  else cout << "No\n";
}


Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
    long answer = 0;

    for(int i = 0; i < n; i++)
    {
      if(i == 0) answer += nums[0];
      else if(i == n-1) answer += nums[n-2];
      else answer += Math.Min(nums[i-1],nums[i]);
    }

		Console.WriteLine(answer);
	}
}

Measured memory_bytes: 13140
import itertools

N, K = map(int, input().split())
MOD = 10**9 + 7
a = [i for i in range(N+1)]

ma = list(itertools.accumulate(a))
Ma = list(itertools.accumulate(a[::-1]))

ans = 1
for k in range(K, N+1):
    m = ma[k-1]
    M = Ma[k-1]
    ans += (M - m + 1) % MOD
    ans %= MOD

print(ans)

Measured memory_bytes: 39864
#include <iostream>
using namespace std;
int check(int n,int A, int B){
	int t=0;
	do{t+=n%10;
	}while(n/=10);
	return (A<=t and t<=B);
}

int main() {
	int N,A,B,ans=0;
	cin>>N>>A>>B;
	for(int i=1;i<=N;i++){
		ans+=check(i,A,B)?i:0;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
a = [input() for _ in range(H)]

for i in range(H-1, -1, -1):
    if "#" not in a[i]:
        a.pop(i)

flag = False
for j in range(W-1, -1, -1):
    for i in range(len(a)):
        if a[i][j] == "#":
            flag = True
    if not flag:
        for i in range(len(a)):
            a[i] = a[i][:j] + a[i][j+1:]
    flag = False

for b in a:
    print(b)

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

int main()
{
	double a, b, c, d, e, f;
	while (cin >> a >> b >> c >> d >> e >> f) {
		double x = (c*e - b*f) / (a*e - b*d);
		double y = (a*f - c*d) / (a*e - b*d);
		if (x == 0)x = 0;
		if (y == 0)y == 0;
		printf("%.3f %.3f\n", x, y);
	}
    return 0;
}

Measured memory_bytes: 1236
#include<iostream>
#include<stack>

using namespace std;

int main() {

	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int A[10];
		for (int j = 0; j < 10; j++)cin >> A[j];
		stack<int> B, C;
		B.push(A[0]);
		for (int j = 1; j < 10; j++) {
			if (B.top() < A[j])B.push(A[j]);
			else if (C.empty() == 1)C.push(A[j]);
			else if (C.top() < A[j])C.push(A[j]);
			else {
				cout << "NO" << endl;
				break;
			}
			if (j == 9)cout << "YES" << endl;
		}
	}

	return 0;
}


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


int main()
{
  int n;
  cin>>n;
  vector<int> a(n);
  vector<int> b(n);
  vector<int> c(n);
  for(int i=0;i<n;i++)
    cin>>a[i]>>b[i]>>c[i];
  int sum[n][3];
  
  for(int i=0;i<n;i++)
  {
    if(i==0)
    {
      sum[i][0]=a[i];
      sum[i][1]=b[i];
      sum[i][2]=c[i];
    }
    else
    {
      sum[i][0]=a[i]+max(sum[i-1][1],sum[i-1][2]);
      sum[i][1]=b[i]+max(sum[i-1][0],sum[i-1][2]);
      sum[i][2]=c[i]+max(sum[i-1][0],sum[i-1][1]);
    }
  }
  cout<<max(sum[n-1][0],max(sum[n-1][1],sum[n-1][2]))<<endl;
}
  
  
  

Measured memory_bytes: 2560
// Problem : D - Redistribution
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define db double
#define mod 1000000007
#define pb push_back
#define pp pair<int,int>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=b;i>=a;i--)
#define maxn 200005
#define ss second
#define ff first
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
int inv(int a, int b){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}
int dp[2005];
int fun(int x)
{
	if(x == 0)
		return 1;
	if(x < 3)
		return 0;
	if(dp[x]!=-1)
		return dp[x];
	int tmp =0;
	for(int i=3;i<=x;i++)
	{
		tmp += fun(x-i);
		tmp %=mod;
	}
	dp[x]=tmp;
	return tmp;
}
void solve()
{
	memset(dp,-1,sizeof dp);
	int s;
	cin >> s;
	fun(s);
	if(dp[s]==-1)
	cout << 0 <<"\n";
	else cout << dp[s] <<"\n";
}
signed main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}


Measured memory_bytes: 3664
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    int sr, sc;
    cin >> sr >> sc;
    string s, t;
    cin >> s >> t;

    vi vs(4);
    bool check = true;
    rep(i, n) {
        if(s[i] == 'L') {
            vs[0]++;
        }
        if(s[i] == 'R') {
            vs[1]++;
        }
        if(s[i] == 'U') {
            vs[2]++;
        }
        if(s[i] == 'D') {
            vs[3]++;
        }
        if(vs[0] >= sc) check = false;
        if(vs[2] >= sr) check = false;
        if(vs[1] >= w-sc+1) check = false;
        if(vs[3] >= h-sr+1) check = false;
        if(t[i] == 'L') {
            vs[1]--;
            if(sc + vs[1] == 0) vs[1] = 1-sc; 
        }
        if(t[i] == 'R') {
            vs[0]--;
            if(sc - vs[0] == w+1) vs[0] = sc-w;
        }
        if(t[i] == 'U') {
            vs[3]--;
            if(sr + vs[3] == 0) vs[3] = 1-sr;
        }
        if(t[i] == 'D') {
            vs[2]--;
            if(sr - vs[2] == h+1) vs[2] = sr-h;
        }
        
    }

    
    

    cout << (check ? "YES":"NO") << endl;
}

Measured memory_bytes: 776
#include <iostream>
#include <array>

int main() {
  std::array<int, 9> grid;
  for(auto &g: grid)
    std::cin >> g;
  for (int a1 = 0; a1 <= 100; a1++) {
    int b1 = grid[0] - a1;
    int b2 = grid[1] - a1;
    int b3 = grid[2] - a1;
    for (int a2 = 0; a2 <= 100; a2++) {
      if (grid[3] - a2 != b1)continue;
      if (grid[4] - a2 != b2)continue;
      if (grid[5] - a2 != b3)continue;
      for (int a3 = 0; a3 <= 100; a3++) {
        if (grid[6] - a3 != b1)continue;
        if (grid[7] - a3 != b2)continue;
        if (grid[8] - a3 != b3)continue;
        std::cout << "Yes" << std::endl;
        return 0;
      }
    }
  }
  std::cout << "No" << std::endl;
  return 0;
}


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

int main(){
 map<int, bool> memo;

 int N;
 cin >> N;

 int cnt = 0;
 
 for(int i=0; i<N; i++){
  int p[3];
  cin >> p[0] >> p[1] >> p[2];

  sort(p, p+3);

  int k = ((p[0]-1)*1000+(p[1]-1))*1000+(p[2]-1);

  if(memo.find(k)!=memo.end()){
   cnt++;
  }else{
   memo[k] = true;
  }
 }

 cout << cnt << endl;
 
 return 0;
} 

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

using namespace std;

string conv(string s){
    string res="";
    int i=1;
    res+=s[0];
    for(;i<(int)s.length()-3;i++){
        string sub=s.substr(i,3);
        if(sub=="mew") i+=2;
        else res+=s[i];
    }
    for(;i<(int)s.length();i++) res+=s[i];
    return res;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;cin>>s;
  if(s=="mew"){
    cout << "Cat"<<endl;
    return 0;
  }
  int pre=s.length();
  while(true){
      s=conv(s);
      if((int)s.length()==pre){
          cout<<"Rabbit"<<endl;
          return 0;
      }
      if(s=="mew"){
          cout<<"Cat"<<endl;
          return 0;
      }
      pre=s.length();
  }
  return 0;
}

Measured memory_bytes: 3200
import bisect
import copy
import heapq
import statistics
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,x=map(int,input().split())
if x==1 or x==2*n-1:
    print("No")
    exit()
print("Yes")
if n==2:
    for i in range(n+1):
        print(i+1)
elif x==2:
    cnt=5
    for i in range(2*n-1):
        if i<n-2 or n+1<i:
            print(cnt)
            cnt+=1
        else:
            if i==n-2:
                print(x+1)
            elif i==n-1:
                print(x)
            elif i==n:
                print(x-1)
            else:
                print(x+2)
else:
    lst=[0]*(2*n-1)
    cnt=1
    for i in range(2*n-1):
        if i<n-2 or n+1<i:
            if cnt<x-2 or x+1<cnt:
                lst[i]=cnt
            else:
                cnt=x+2
                lst[i]=cnt
            cnt+=1
        else:
            if i==n-2:
                lst[i]=x-1
            elif i==n-1:
                lst[i]=x
            elif i==n:
                lst[i]=x+1
            else:
                lst[i]=x-2
    for i in range(2*n-1):
        print(lst[i])

Measured memory_bytes: 82280
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#define _USE_MATH_DEFINES
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;

struct edge {
    int to, cost;
};

int V;
vector<edge> G[1000000];
ll d[1000000];

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii> > que;
    fill(d, d + V + 10, llmax);
    d[s] = 0;
    que.push(pii(0, s));

    while (!que.empty()) {
        pii p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) {
            continue;
        }
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(pii(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int E, r;
    cin >> V >> E >> r;
    for (int i = 0; i < E; i++) {
        int s, t, d;
        cin >> s >> t >> d;
        edge e;
        e.to = t;
        e.cost = d;
        G[s].push_back(e);
    }
    dijkstra(r);
    for (int i = 0; i < V; i++) {
        if (d[i] == llmax) {
            cout << "INF" << endl;
        } else {
            cout << d[i] << endl;
        }
    }
}



Measured memory_bytes: 34604
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;

ll moP(ll x, ll n) {
  ll res=1;
  while(n>0) {
    if(n&1) moC(res, *, x);
    moC(x, *, x);
    n>>=1;
  }
  return res;
}


int main(void) {
  ll i, j, k;
  ll N;
  cin >> N;
  ll a[MAX], d[MAX];
  ll s=0;
  
  for(i=0; i<N; i++) {
    cin >> a[i];
    s+=a[i];
  }
  
  ll f=1;
  
  if(s%(N*(N+1)/2)!=0) f=0;
  
  ll K=s/(N*(N+1)/2);
  for(i=0; i<N; i++) d[(i+1)%N]=a[(i+1)%N]-a[i%N];
  for(i=0; i<N; i++) d[i]-=K;
  
  
  k=0;
  for(i=0; i<N; i++) {
    if(d[i]>0) f=0;
    
    ll t=abs(d[i]);
    if(t%N!=0) f=0;
    
    k+=t/N;
  }
  
  if(k!=K) f=0;
  
  
  if(f) pt("YES");
  else pt("NO");
  
  
  
}





Measured memory_bytes: 1792
N, X = list(map(int,input().split(" ")))
L = list(map(int,input().split(" ")))
l_sum = 0
flag = False
for i in range(N):
    l_sum += L[i]
    if l_sum>X:
        print(i+1)
        flag = True
        break
if not flag:    
    print(N+1)

Measured memory_bytes: 40732
void main(){
	int n, m;
	readf("%d %d", &n, &m);
	writeln(n==m? "Yes": "No");
}

import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math;

// 1要素のみの入力
T _scan(T= int)(){
	return to!(T)( readln().chomp() );
}

// 1行に同一型の複数入力
T[] _scanln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split()){
		ln ~= elm.to!T();
	}
	return ln;
}


Measured memory_bytes: 2744
using System;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            var AB = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var A = AB[0]; var B = AB[1];
            Console.WriteLine(A <= 9 && B <= 9 ? A * B : -1);
        }
    }
}


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

int main() {
  int n;
  cin >> n;
  std::vector<int> vec;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    vec.push_back(x);
  }
  int now = 0, c = 0;
  for (;;) {
    if (now == 1) {
      cout << c << endl;
      break;
    }

    if (c >= n) {
      cout << -1 << endl;
      break;
    }
    c++;
    now = vec[now];
  }
}


Measured memory_bytes: 3900
import java.util.*;

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

        int[] cities = new int[n];
        for(int i = 0 ;i < m;i++){
            int l = sc.nextInt();
            int r = sc.nextInt();
            cities[l-1] ++;
            cities[r-1] ++;
        }
        for(int j = 0 ;j < n;j++) {
            System.out.println(cities[j]);
        }
    }
}

Measured memory_bytes: 21844
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(true){
			int H = sc.nextInt();
			int W = sc.nextInt();
			if(H==0 && W==0){
				break;
			}
			for(int i=0;i<H;i++){
				for(int j=0;j<W;j++){
					if((i+j)%2==0){
						System.out.print("#");
					}else{
						System.out.print(".");
					}
				}
				System.out.print("\n");
			}
			System.out.print("\n");
		}
	}
}


Measured memory_bytes: 37904