akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() /4;
const ll linf = numeric_limits<ll>::max() /4;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

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

int n,m,a,b,c,d[100005] = {};
string s,t;

int main(){
    cin >> n ;//>> m;
    rep(i,1,n+1)cin >> d[i];

    int ans = 0;
    rep(i,1,n+1){
        if(d[d[i]] == i)ans++;
    }
    P(ans/2);
	
	return  0;
}

Measured memory_bytes: 640
import java.util.*;
import java.io.*;

public class Main{

	public static void main(String[] args){
		solve();
	}

	public static void solve(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int rn = sc.nextInt();
			int wn = sc.nextInt();
			int c = sc.nextInt();
			int r = sc.nextInt();
			if(rn==0 && wn==0 && c==0 && r==0){
				break;
			}
			int ans = 0;
			while(true){
				if((rn + ans*r)/c - wn >= 0){
					break;
				}
				ans++;
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 26276
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader bw = new BufferedReader(new InputStreamReader(System.in));
		String s = bw.readLine();
		String[] w = s.split("\\s+");
		int S = Integer.parseInt(w[0]);
		int W = Integer.parseInt(w[1]);
		
		if (W >= S) {
			System.out.println("unsafe");
		}else {
			System.out.println("safe");
		}
		bw.close();
	}
	
	
}	



Measured memory_bytes: 33880
from collections import defaultdict
s = input()
n = len(s)
target = 2019
res = 0
dic = defaultdict(int)
dic[0] = 1
s = s[::-1]
num, d = 0, 1
for char in s:
    num += int(char) * d
    num %= target
    d *= 10
    d %= target
    dic[num] += 1
for i in dic.values():
    res += i * (i -1) //2
print(res)

Measured memory_bytes: 9784
#include <iostream>
#include <algorithm>
#include <time.h>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cassert>

using namespace std;

const int N = 100005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

string s;
string ss;

int main(){
    cin>>s;
    if((int)s.size() < 4){
        cout<<"No"<<endl;
        return 0;
    }
    for(int i=0;i<4;i++) ss += s[i];
    if(ss == "YAKI")
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;

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

int main(){
    ll sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    ll xd = tx-sx, yd =ty-sy;
    bool x=true,y = true;
    if(xd < 0)x = false;
    if(yd < 0)y = false;
    xd = abs(xd); yd = abs(yd);

    rep(i,0,xd){
        if(x)cout<<"R";
        else cout<<"L";
    }
    rep(i,0,yd){
        if(y)cout<<"U";
        else cout<<"D";
    }
    rep(i,0,xd){
        if(x)cout<<"L";
        else cout<<"R";
    }
    rep(i,0,yd+1){
        if(y)cout<<"D";
        else cout<<"U";
    }


    rep(i,0,xd+1){
        if(x)cout<<"R";
        else cout<<"L";
    }
    rep(i,0,yd+1){
        if(y)cout<<"U";
        else cout<<"D";
    }

    if(x)cout<<"L";
    else cout<<"R";
    if(y)cout<<"U";
    else cout<<"D";

    rep(i,0,xd+1){
        if(x)cout<<"L";
        else cout<<"R";
    }
    rep(i,0,yd+1){
        if(y)cout<<"D";
        else cout<<"U";
    }
    if(x)cout<<"R";
    else cout<<"L";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int a, long long int b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

long long int lcm(long long int a, long long int b) {
  return (a / gcd(a, b)) * b;
}

long long int combination(long long int n, long long int r) {
  if ( r * 2 > n ) r = n - r;
  long long int dividend = 1;
  long long int divisor  = 1;
  for ( unsigned int i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}
long long int tmp(long long int n, long long int r) {
  return combination(n+r-1, r);
}


int main() {

  while(1) {
    int N;
    cin >> N;
    if (N == 0) break;
    vector<vector<int>> area_v(500, vector<int>(500, 0));
    vector<vector<int>> box_pos_v;
    box_pos_v.push_back({250, 250});
    area_v[box_pos_v[0][0]][box_pos_v[0][1]] = 1;

    vector<int> n_v, d_v;
    for (int i = 0; i < N-1; i++) {
      int n, d;
      cin >> n>> d;
      //n_v.push_back(n);
      //d_v.push_back(d);
      vector<int> diff;
      switch(d) {
      case 0:
        diff.push_back(-1);
        diff.push_back(0);
       break;
      case 1:
        diff.push_back(0);
        diff.push_back(-1);
        break;
      case 2:
        diff.push_back(1);
        diff.push_back(0);
        break;
      case 3:
        diff.push_back(0);
        diff.push_back(1);
        break;
      }
      vector<int> orig = box_pos_v[n];
      vector<int> next(2,0);
      //cout << orig[0] << " " << orig[1] << endl;
      next[0] = orig[0]+diff[0];
      next[1] = orig[1]+diff[1];
      //cout << next[0] << " " << next[1] << endl;
      box_pos_v.push_back({next[0], next[1]});
      //cout << "ss" << endl;
      area_v[box_pos_v[i][0]][box_pos_v[i][1]] = 1;
    }
    int y_max = box_pos_v[0][1];
    int y_min = box_pos_v[0][1];
    int x_max = box_pos_v[0][0];
    int x_min = box_pos_v[0][0];
    for (int i = 0; i < N; i++) {
      if (y_max < box_pos_v[i][1]) {
        y_max = box_pos_v[i][1];
      }
      if (y_min > box_pos_v[i][1]) {
        y_min = box_pos_v[i][1];
      }

      if (x_max < box_pos_v[i][0]) {
        x_max = box_pos_v[i][0];
      }
      if (x_min > box_pos_v[i][0]) {
        x_min = box_pos_v[i][0];
      }      
      // printf("%d, %d\n", box_pos_v[i][0], box_pos_v[i][1]);
    }
    printf("%d %d\n", x_max-x_min+1, y_max-y_min+1);
  }
  return 0;
}



Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2010,p=1e9+7;
int f[N][N];
int main()
{
    int n,k;scanf("%d%d",&n,&k);
    for(int i=2;i<=n;i++)f[1][i]=1;
    for(int i=1;i<k-1;i++)
    {
        int ss=f[i][n-i+1];
        for(int j=n-i;j>=2;j--)
            ss=(ss+f[i][j])%p,f[i+1][j]=ss;
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=(ans+f[k-1][i])%p;
    if(k==1)ans=1;
    for(int i=1;i<=n-k-1;i++)ans=(ans+ans)%p;
    printf("%d\n",ans);
}


Measured memory_bytes: 15360
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n % 2 == 0) {
            System.out.println(n / 2);
        } else {
            System.out.println(n / 2 + 1);
        }
        sc.close();
    }
}

Measured memory_bytes: 21332
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static final int INF = Integer.MAX_VALUE;
	public static List<Integer>[] sideArray;
	public static int[] dp;

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int vertexCount = scan.nextInt();
		int sideCount = scan.nextInt();

		sideArray = new List[vertexCount];

		for (int i = 0; i < vertexCount; i++) {

			sideArray[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < sideCount; i++) {

			int start = scan.nextInt();
			int end = scan.nextInt();

			sideArray[start - 1].add(end - 1);
		}

		// 各頂点から始めた場合の最長の長さを記録する
		dp = new int[vertexCount];
		Arrays.fill(dp, INF);

		for (int i = 0; i < vertexCount; i++) {

			calculationMaxLength(i);
		}

		int answer = Arrays.stream(dp).max().getAsInt();
		System.out.println(answer);
	}

	public static int calculationMaxLength(int vertexNumber) {

		int dpNumber = dp[vertexNumber];

		if (dpNumber != INF) {
			return dpNumber;
		}

		int result = 0;

		for (Integer endVertex : sideArray[vertexNumber]) {

			int maxLength = calculationMaxLength(endVertex) + 1;
			result = Math.max(result, maxLength);
		}

		dp[vertexNumber] = result;
		return result;
	}
}


Measured memory_bytes: 105668
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

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

	ll x, y;
	cin >> x >> y;
	ll ans = 1;
	while (2 * x <= y) {
		x *= 2;
		ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/29 08:26:26 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

// TOP
void	Main()
{
	int	n, m;
	cin >> n >> m;

	bitset<10>	each_bulb_p;
	vector<bitset<10>> switches(n);

	rep(i, m)
	{
		int	k;
		cin >> k;
		rep(j, k)
		{
			int	x;
			cin >> x;
			x--;
			switches.at(x).set(i);
		}
	}
	rep(i, m)
	{
		int	p;
		cin >> p;
		if (!p)
		each_bulb_p.set(i);
	}
	ll	cnt;
	cnt = 0;
	rep(i, 1 << n)
	{
		bitset<10>	bulbs_state;
		bitset<10>	turned_switches;
		turned_switches = i;
		bulbs_state = each_bulb_p;
		rep(j, n)
		{
			if (turned_switches.test(j))
			{
				rep(k, m)
				{
					if (switches.at(j).test(k))
						bulbs_state.flip(k);
				}
			}
		}
		if (bulbs_state.count() == m)
			cnt++;
	}
	cout << cnt << endl;
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=100100100;
const int MOD=(int)1e9+7;
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,a,b) for(int i=a; i<b; i++)

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(a>0 and c>0){
        c-=b;
        if(c<=0)break;
        a-=d;
    }
    if(a<=0) cout<<"No"<<endl;
    if(c<=0) cout<<"Yes"<<endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define si size()
#define bk back()
#define popb pop_back()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define ump unordered_map
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define fore(i,a,n) for(int i=a;i<=n;i++)
#define len length()
const int N=1e9+7;

// dp[i][j] means we are at position i and total sum in knapsack is j
// so aat position i we can take the element i or leave it
// if we take it the transiotio nto dp[i][j]--->dp[i-1][j-weight[i]] other wise dp[i][j]-->dp[i-1][j]
//iterative approach   time-O(n*W)  space-O(n*W)


//Note at given (i,j) we only need to store the value in previous row i.e (i-1,j)
//so storing info about the row is not required
//with this  observation we think we can reduce space
//time-O(n*W) space-O(W)

int main()
{

   
   int n,w;
   cin>>n>>w;
   ll arr[n][2];
   forl(i,0,n)forl(j,0,2)cin>>arr[i][j];

   //O(N*W) space
//    ll dp[n+1][w+1];
   
//    forl(i,0,w+1) dp[0][i]=0;
//    forl(i,0,n+1) dp[i][0]=0;
//    forl(i,1,n+1)
//    {
//        forl(j,0,w+1)
//        {
//            if(j>=arr[i-1][0])dp[i][j]=max(dp[i-1][j],dp[i-1][j-arr[i-1][0]]+arr[i-1][1]);
//            else dp[i][j]=dp[i-1][j];
//        }
//    }
    //cout<<dp[n][w]<<endl;




    //Printing which elements are taken using the above dp

    // vector<int>v;
    // ll wt=w;
    // rfor(i,n,1)
    // {
    //     if(dp[i][wt]==dp[i-1][wt-arr[i-1][0]]+arr[i-1][1]) 
    //     {   
    //      //this means if i have included the last object then value at (i,wt) must be equal to (i-1,wt-weight[i])+val[i]
    //      //else it would e equal to (i-1,wt);
    //         v.pb(1);
    //         wt=wt-arr[i-1][0];

    //     } 
    //     else
    //     {
    //          v.pb(0);
    //     }
    // }

    // rfor(i,v.si-1,0)
    // {
    //     cout<<v[i]<<" ";
    // }
    // cout<<endl;

   



    //O(W) space soln

    ll dp [w+1];
    forl(i,0,w+1)dp[i]=0;
    forl(i,0,n)
    {   
        rfor(j,w,0)
        {
            if(j-arr[i][0]>=0) dp[j]=max(dp[j],dp[j-arr[i][0]]+arr[i][1]);
        }
    }

    cout<<dp[w]<<endl;

}


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

using namespace std;

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

    if (b==1) {
        cout << 0 << endl;
        return 0;
    }

    int outlet=a;
    for (int i=1;;i++) {
        if (outlet>=b) {
            cout << i << endl;
            break;
        } else {
            outlet -= 1;
            outlet += a;
        }
    }

    return 0;
}

Measured memory_bytes: 256
def main():
    n,m = map(int,input().split())
    graph = {}
    for i in range(n):
        graph[i+1] = []
    for i in range(m):
        x,y,z = map(int,input().split())
        graph[x] += [y]
        graph[y] += [x]
    dis = [-1 for i in range (n)]
    ans = 0
    for i in range(n):
        if dis[i]==-1:
            ans += 1
            que = [i]
            dis[i] = 0
            while len(que)>0:
                s = que.pop(0)
                for nv in graph[s+1]:
                    if dis[nv-1]!=-1:
                        continue
                    dis[nv-1] = 0
                    que.append(nv-1)
    print(ans)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 35536
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>

using namespace std;

int main() {
  string s;
  cin >> s;

  for (int i=0; i<s.length(); i++) {
    if (s[i] == '1') cout << '9';
    else cout << '1';
  }

  cout << endl;
}


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

using namespace std;


struct abcd {
  int a, b, c, d;
  abcd() {}
  abcd(int a_, int b_, int c_, int d_): a(a_), b(b_), c(c_), d(d_) {}
};

int ans = 0;

int n, m, q;

vector<abcd> dat;

void dfs(vector<int> A) {
  if ((int)A.size() == n) {
    int sum = 0;
    for (int i = 0; i < q; ++i) {
      abcd cur = dat[i];
      if (A[cur.b] - A[cur.a] == cur.c) sum += cur.d;
    }
    ans = max(ans, sum);
    return;
  }


  int start = A.size() > 0? A.back(): 1;
  for (int i = start; i <= m; ++i) {
    vector<int> A_ = A;
    A_.push_back(i);
    dfs(A_);
  }
}

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

  for (int i = 0; i < q; ++i) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--; b--;
    dat.push_back(abcd(a, b, c, d));
  }
  vector<int> tmp;
  dfs(tmp);
  cout << ans << '\n';
  return 0;
}



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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair


int main() {
  int k;
  cin >> k;
  if (k == 1) {
    cout << 1 << endl;
    cout << 1 << endl;
    return 0;
  }
  int n = 2;
  while (!(n <= k && k <= 2*n)) n += 2;
  vii c(n, vi(n));
  rep (i, n) {
    rep (j, n) {
      if (i % 2 == 0) {
        c[i][j] = (i + j) % n + 1;
      }
      else {
        c[i][j] = (i + j) % n + n + 1;
      }
    }
  }
  cout << n << endl;
  rep (i, n) {
    rep (j, n) {
      if (c[i][j] > k) {
        cout << c[i][j] - n << " ";
      }
      else {
        cout << c[i][j] << " ";
      }        
    }
    cout << endl;
  }
    
}  


Measured memory_bytes: 2176
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] sort = new String[n];
		for(int i = 0 ; i < n ; i++) {
			String name = sc.next();
			int point = sc.nextInt();
			point = 100 - point;
			String pointStr = String.format("%03d", point);
			int num = i + 1;
			// ソート用の文字列として上記をつなげる
			String forSort = name + pointStr + "/" + num;
			sort[i] = forSort;
		}

		Arrays.sort(sort);
		for(int i = 0 ; i < n ; i++) {
			String[] splited = sort[i].split("/");
			System.out.println(splited[splited.length - 1]);
		}

		sc.close();

	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define ll long long

using namespace std;

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

	int wt[n], val[n];
	ll sum_value = 0;
	for(int i=0;i<n;i++){
		cin >> wt[i] >> val[i];
		sum_value += val[i];
	}

	vector<ll> dp(sum_value+1, 1e18);
	dp[0] = 0;
	for(ll i=0;i<n;i++){
		for(int j=sum_value;j>=val[i];j--){
			dp[j] = min(dp[j], dp[j-val[i]]+wt[i]);
		}
	}

	ll res = -1;
	for(ll i=0;i<=sum_value;i++){
		if(dp[i] <= w){
			res = max(res, i);
		}
	}

	cout << res << endl;
	return 0;
}	

Measured memory_bytes: 4052
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	string s;
	cin >> s;
	int n = s.length(), i, j, k, ans = 0;
	for (i = 0; i < n; i++) {
		if (s[i] != s[n - 1 - i]) {
			ans++;
			s[i] = s[n - 1 - i];
		}
	}
	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M, Q;
vector<int> A, B, C, D;
int a[10];
ll ans;
void f(int p, int x) {
	if (p == N) {
		ll res = 0;
		for (int i = 0; i < Q; ++ i) {
			if (a[B[i]] - a[A[i]] == C[i]) res += D[i];
		}
		ans = max(ans, res);
		return;
	}
	for (a[p] = x; a[p] <= M; ++ a[p]) {
		f(p+1, a[p]);
	}
}
int main() {
	cin >> N >> M >> Q;
	A.resize(Q);
	B.resize(Q);
	C.resize(Q);
	D.resize(Q);
	for (int i = 0; i < Q; ++ i) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		-- A[i];
		-- B[i];
	}
	f(0, 1);
	cout << ans << endl;
}


Measured memory_bytes: 3604
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
#include<utility>
#include<queue>

using namespace std;


int main(){

	int ans=0;
	int n,a;
	cin>>n>>a;
	if(n%a==0)ans=n/a;
	else ans=n/a+1;



	cout<<ans;

	cout<<endl;

	return 0;
}


Measured memory_bytes: 256
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<int,int> P;
ll longinf=1ll<<60;
int inf=1<<29;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

class unionFindWeight{
      private:
      vector<int> par;
      vector<int> rank;
      vector<ll> diff_weight;
      
      int root(int x){
            if(par[x] == x) return x;
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];//累積和
            par[x] = r;
            return par[x];
      }
      ll weight(int x){
            root(x);//経路圧縮
            return diff_weight[x];
      }
      public:
      unionFindWeight(int n){
            rep0(i,n){
                  par.push_back(i);
                  rank.push_back(0);
                  diff_weight.push_back(0);
            }
      }
      ll diff(int x,int y){
            return weight(y) - weight(x);
      }
      bool issame(int x,int y){
            return root(x) == root(y);
      }
      bool merge(int x,int y,ll w){
            //xとyそれぞれについてrootとの重み差分を補正
            w += weight(x); w -= weight(y);
            x = root(x); y = root(y);
            if(x == y) return false;
            //rank[x]>=rank[y]となるように入れ替える
            if(rank[x] < rank[y]) swap(x,y),w = -w;
            //yのrootをxのrootの下にくっつける
            if(rank[x] == rank[y]) rank[x]++;
            par[y] = x;
            diff_weight[y] = w;
            return true;
      }
};
int main (){
      int N,M;
      cin>>N>>M;
      unionFindWeight u(N);
      bool ok=1;
      rep0(i,M){
            int l,r,d;
            cin>>l>>r>>d;
            l--,r--;
            if(u.issame(l,r)){
                  if(u.diff(l,r)!=d){
                        ok=0;
                  }
            }
            else{
                  u.merge(l,r,d);
            }
      }
      cout<<(ok? "Yes":"No")<<endl;
      return 0;
}


Measured memory_bytes: 2028
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const ll INF = ll(1e15)+10;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;

using Graph = vector<vector<P>>;

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

	Graph G(N);
	for (int i = 0; i < N-1; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		G[a].push_back(P(i, b));
		G[b].push_back(P(i, a));
	}

  int s = 0;

	vector<int> cl(N-1, -1);
	queue<P> que;
	que.push(P(0, -1));
	while (!que.empty()) {
		auto v = que.front(); que.pop();
    int vid = v.first;
    int vc = v.second;
    int c = 0;
		for (auto nv : G[vid]) {
      int eid = nv.first;
      int eto = nv.second;
			if (cl[eid] == -1) {
        if (c == vc) c++;
				que.push(P(eto, c));
        cl[eid] = c;
        c++;
			}
		}
	}
  int K = *max_element(ALL(cl)) + 1;
  cout << K << endl;
  rep(i, N-1) {
    cout << (cl[i]+1) << endl;
  }
}

Measured memory_bytes: 7040
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        x: isize,
        k: isize,
        d: isize,
    }

    let quot = isize::abs(x) / d;

    let ans = if k < quot {
        isize::abs(x) - isize::abs(d * k)
    } else {
        let k2 = k - quot;
        if k2 % 2 == 0 {
            isize::abs(x) - isize::abs(d * quot)
        } else {
            isize::abs(isize::abs(x) - isize::abs(d * quot) - d)
        }
    };

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


Measured memory_bytes: 2156
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int mm=1000000007;
int i,j,k,n,a[200001],f[200001],w;
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	for (i=2,f[1]=1,w=0;i<=n;i++){
		k=(a[i-1]+1)/2;w=max(w,i-k-1);
		f[i]=(ll)f[i-1]*(ll)(i-w)%mm;
	}
	printf("%d\n",f[n]);
	return 0;
}

Measured memory_bytes: 896
import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons;

void main() {
    auto N = readln.chomp.to!long;
    auto a = N.iota.map!(_ => readln.chomp.to!long-1).array;
    long c = 0;
    foreach (i; 0..N) {
        c = a[c];
        if (c == 1) {
            writeln(i+1);
            return;
        }
    }
    writeln(-1);
}



Measured memory_bytes: 3964
import sys

v, e = map(int, input().split( ))

Edge = [[] for _ in range(v)]

for i in range(e):
    inpt = list(map(int, input().split( )))
    Edge[inpt[0]].append(inpt[1:])

inf = 10**12


dp = [[inf for _ in range(v)] for __ in range(v)]
for i in range(v):
    for ed in Edge[i]:
        dp[i][ed[0]] = ed[1]
for i in range(v):
    dp[i][i] = 0
"""
・for k,for i, for jの順。for i,j,kだと別物
・dpはkによらず使い回しでよい
"""
for k in range(v):
    for j in range(v):
        for i in range(v):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

for i in range(v):
    if dp[i][i]<0:
        print("NEGATIVE CYCLE")
        sys.exit()

for i in range(v):
    for j in range(v-1):
        if dp[i][j] >inf//2:###
            print("INF",end = " ")
        else:
            print(dp[i][j], end = " ")
    if dp[i][v-1] >inf//2:
            print("INF",end = "")
    else:
        print(dp[i][v-1], end = "")
    print()
    



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

int main() {
	int n; cin >> n;
	vector<int>a(n), b(n); for (auto&& x : a)cin >> x;
	for (int i = 0; i < n; i++) {
		b[i] = a[i] - i + 1;
	}
	sort(b.begin(), b.end());
	int B = b.size() % 2 == 0 ? (b[b.size() / 2] + b[b.size() / 2 - 1]) / 2 : b[b.size() / 2];
	long long sum = 0; for (auto&& x : b)sum += abs(x - B);	
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a=nxtl(),b=nxtl(),n=nxtl();
    ll x=min(n,b-1)*a;
    x/=b;
    cout<<x<<endl;
    
    return 0;   
}




 
 


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

int main()
{
  int a, b;

  cin >> a >> b;

  if(a < b) cout << "a < b" << endl;
  if(a > b) cout << "a > b" << endl;
  if(a == b) cout << "a == b" << endl;

  return 0;

}

Measured memory_bytes: 3080
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
   
        int n;
        cin >> n;
        int a[n];
        for(int i=0;i<n;i++){
            cin >> a[i]; 
        }
        for(int i=n-1;i>=0;i--){
            if(i==0){
                cout << a[i] << endl;
            }
            else
                cout << a[i] << " ";
        }
        
    
}



Measured memory_bytes: 3112
def resolve():
    N, Y = map(int, input().split())
    for i in range(N+1):
        for j in range(N+1-i):
            if 10000*i + 5000*j + 1000*(N-i-j) == Y:
                print(i, j, N-i-j)
                exit()
    print("-1 -1 -1")
resolve()

Measured memory_bytes: 3060
l,r = map(int,input().split())
mod = 2019
ans = l*r%mod

for i in range(l,r):
    for j in range(i+1,r+1):
        tmp = i*j%mod
        if(ans>tmp):
            ans = tmp
        if(ans == 0):
            break
    if(ans == 0):
        break
print(ans)
    


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <ostream>
#include <istream>
#include <typeinfo>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <limits>
#include <fstream>
#include <array>
#include <list>
#include <bitset>
#include <functional>
#include <random>
#include <cstring>
#include <chrono>
#include<string>
using namespace std;
#define endl "\n"
#define ll long long int
#define ld long double
#define AREA(a,b) (a*b)
#define f(i, n) for (int i = 0; i < (n); i++)
#define rof(i, n) for (int i = ((n) - 1); i >= 0; i--)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define vi vector<ll>
#define pb push_back
#define mx 1000005
#define ASCII 256

ll pos[100001],a[100001];

void testcases(){
    string s;
    cin>>s;
    ll len=s.length();
    if(s[len-1]=='s'){
        cout<<s<<"es";
//        s.append(1,'es');
    }
    else{
        s.append(1,'s');
        cout<<s;
    }
}

int main(){
    boost;


//    int test;
//    cin>>test;
//    int t=1;
//    while(test--){
//        //cout<<"Case #"<<t<<": ";
//        testcases();
//        t++;
//    }


  testcases();
}


Measured memory_bytes: 3648
/*
(1)for binary shift operator always use 'LL' 1LL<<63

*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set_pair tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define Luv(...) [&] (auto &&u, auto &&v) { return __VA_ARGS__; }
  const double  pi=3.1415926535; 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;ll p=1;ll mx=1e18;cin>>n;
	ll i,j;
	ll v[n];
	bool f=false;
	for(i=0;i<n;i++){
		cin>>v[i];
		if(v[i]==0)
			f=true;
	}
	if(f) cout<<0;
	else {
		for(i=0;i<n;i++){
			//double x=(double)v[i]*p;
			//cout<<(double)p*v[i]<<endl;
			if(p*v[i]<=mx and p*v[i]>0)
				p*=v[i];
			else {
				cout<<-1;
				return 0;
			}
		}
		cout<<p;
		//cout<<v[0]*v[1]*v[2];
	}

	return 0;
} 

Measured memory_bytes: 4420
import java.util.*;

class Main{
	public static void main(String[] args){
      	Scanner sc = new Scanner(System.in);
		String S = sc.next();
		if(S.length() % 2 != 0){
			System.out.println("No");
			return;
		}
		for(int i = 0; i < S.length(); i += 2){
			int tmp = i + 2;
			String str = S.substring(i, tmp);
			if(str.equals("hi")){
				continue;
			}else{
				System.out.println("No");
				return;
			}
		}
		
		System.out.println("Yes");
	}

}

Measured memory_bytes: 22228
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <cstdlib>
#include <cmath>

#define _USE_MATH_DEFINES
#define REP(i,n) for(i = 0;i<n;i++)

using namespace std;


int main() {

	string a, b, c;

	cin >> a >> b >> c;

	if (a[a.length() - 1] == b[0] && b[b.length() - 1] == c[0])
		cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}



Measured memory_bytes: 256
// ITP1_11_B Dice 2
import java.io.*;

public class Main {
   public static void main(String[] args) {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      Dice dice;

      try {
         String[] input = br.readLine().split(" ");
         int[] roll = new int[input.length];
         for (int i = 0; i < input.length; i++)
            roll[i] = Integer.parseInt(input[i]);
         dice = new Dice(roll[0], roll[1], roll[2], roll[3], roll[4], roll[5]);

         int q = Integer.parseInt(br.readLine());
         for (int i = 0; i < q; i++) {
            input = br.readLine().split(" ");
            int[] question = new int[2];
            question[0] = Integer.parseInt(input[0]);
            question[1] = Integer.parseInt(input[1]);
            if (question[0] != dice.TOP) {
               if ((question[0] == dice.RIGHT) || (question[0] == dice.LEFT))
                  while (question[0] != dice.TOP)
                     dice.east();
               else
                  while (question[0] != dice.TOP)
                     dice.north();
            }
            if (question[1] != dice.FRONT) {
               if (question[1] == dice.RIGHT)
                  System.out.println(dice.BACK);
               else if (question[1] == dice.BACK)
                  System.out.println(dice.LEFT);
               else if (question[1] == dice.LEFT)
                  System.out.println(dice.FRONT);
            } else
                  System.out.println(dice.RIGHT);
         }
      }

      catch (Exception e) {
         e.printStackTrace();
      }                      
   }
}

class Dice {
   static int TOP;
   static int FRONT; 
   static int RIGHT;
   static int LEFT;
   static int BACK;
   static int BOTTOM;
   static int work;

   public Dice(int top, int front, int right, int left, int back, int bottom) {
      this.TOP = top;
      this.FRONT = front;
      this.RIGHT = right;
      this.LEFT = left;
      this.BACK = back;
      this.BOTTOM = bottom;
   }

   static void north() {
      work = TOP;
      TOP = FRONT;
      FRONT = BOTTOM;
      BOTTOM = BACK;
      BACK = work;
   }
   static void east() {
      work = TOP;
      TOP = LEFT;
      LEFT = BOTTOM;
      BOTTOM = RIGHT;
      RIGHT = work;
   }
   static void west() {
      work = TOP;
      TOP = RIGHT;
      RIGHT = BOTTOM;
      BOTTOM = LEFT;
      LEFT = work;
   }
   static void south() {
      work = TOP;
      TOP = BACK;
      BACK = BOTTOM;
      BOTTOM = FRONT;
      FRONT = work;
   }
}

Measured memory_bytes: 16924
while 1:
	n,a,b,c,x=map(int,raw_input().split())
	if n==0:break
	reel=map(int,raw_input().split())
	roop,i=-1,0
	while i<n:
		roop+=1
		if roop>10000:
			roop=-1
			break
		if x==reel[i]:
			i+=1
		x=(a*x+b)%c
	print roop

Measured memory_bytes: 4212
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    int n, x;
    int l[110];
    cin >> n >> x;
    imfor(i, n) {
        cin >> l[i];
    }
    int ans = 1;
    int tmp = 0;
    imfor(i, n) {
        tmp += l[i];
        if (tmp > x) {
            break;
        }
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))

int main() {
  int n; cin >> n;
  vector<int> a(n+1,0);
  vector<int> b(n,0);
  rep(i,n+1) cin >> a[i];
  rep(i,n) cin >> b[i];
  long long ans = 0;
  rep(i,n) 
  if(a[i] >= b[i]){
    ans+=b[i];
  }else{
    ans += ((a[i+1] -(b[i]-a[i]))>=0)?b[i]:(a[i]+a[i+1]);
    a[i+1] = ((a[i+1] -(b[i]-a[i]))>=0)?a[i+1]-(b[i]-a[i]):0;
  }
  cout << ans;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define pb push_back
#define mk make_pair
const ll mod = 1e9 + 7;
int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	int dp[n + 1][m + 1];
	char a[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			dp[i][j] = 0;
		}
	}
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		if (a[i][0] == '.')
			dp[i][0] = 1;
		else
			break;
	}
	for (int i = 0; i < m; i++) {
		if (a[0][i] == '.')
			dp[0][i] = 1;
		else
			break;
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (a[i][j] == '.') {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				dp[i][j] %= mod;
			}
		}
	}
	cout << dp[n - 1][m - 1] << endl;
}

Measured memory_bytes: 5120
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
cnt1 = defaultdict(int)
cnt2 = defaultdict(int)
for i in range(N):
    cnt1[A[i] + i + 1] += 1
    cnt2[i + 1 - A[i]] += 1
ans = 0
for k, v in cnt1.items():
    ans += v * cnt2[k]
print(ans)

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

using namespace std;

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

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

  string s;
  cin >> s;

  int sub1 = stoi(s.substr(0, 2));
  int sub2 = stoi(s.substr(2, 2));

  if (sub1 <= 12 && sub1 > 0 && sub2 <= 12 && sub2 > 0) cout << "AMBIGUOUS" << "\n";
  else if ((sub1 > 12 || sub1 == 0) && sub2 <= 12 && sub2 > 0) cout << "YYMM" << "\n";
  else if ((sub2 > 12 || sub2 == 0) && sub1 <= 12 && sub1 > 0) cout << "MMYY" << "\n";
  else cout << "NA" << "\n";

  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _0006
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            string[] str1 = new string[str.Length];
            for (int i = 0; i < str.Length; ++i)
            {
                str1[i] = str.Substring(i, 1);
            }
            Array.Reverse(str1);
            foreach(string item in str1)
            {
                Console.Write(item);
            }
            Console.Write("\n");
        }
    }
}



Measured memory_bytes: 13792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


int main(){
  int n;
  cin >> n;
  int a[n+1];
  rep(i,n+1) cin >> a[i];
  int b[n];
  rep(i,n) cin >> b[i];
  ll ans=0;
  if(a[0]>=b[0]){
    ans+=b[0];
    b[0]=0;
  }
  else{
    ans+=a[0];
    b[0]-=a[0];
  }
  rep1(i,n){
    if(a[i]>=b[i-1]){
      ans+=b[i-1];
      a[i]-=b[i-1];
      if(i==n) continue;
      if(a[i]>=b[i]){
	ans+=b[i];
	b[i]=0;
      }
      else{
	ans+=a[i];
	b[i]-=a[i];
      }
    }
    else{
      ans+=a[i];
    }
    //    cout << ans << endl;
  }
  cout << ans << endl;
      
      

  

  
  return 0;

}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define EM 100000000
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
LL LINF = 1e18;
int INF = 1e9;
using vint = vector<int>;
using vLL = vector<LL>;

int main(){
	int A, B, Q;
	cin >> A >> B >> Q;
	vLL s(A+2), t(B+2);
	s[0] = -LINF, t[0] = -LINF;
	s[A+1] = LINF, t[B+1] = LINF;
	for(int i = 1;i <= A;i++)	cin >> s[i];
	for(int i = 1;i <= B;i++)	cin >> t[i];
	for(int i = 0;i < Q;i++){
		LL xi;
		cin >> xi;
		vLL a(2), b(2);
		a[1] = upper_bound(s.begin(), s.end(), xi)-s.begin();
		b[1] = upper_bound(t.begin(), t.end(), xi)-t.begin();
		a[0] = a[1]-1;
		b[0] = b[1]-1;
		LL ans = LINF;
		for(int j = 0;j < 2;j++)	for(int k = 0;k < 2;k++)	ans = min(ans, abs(xi-s[a[j]])+abs(s[a[j]]-t[b[k]]));
		for(int j = 0;j < 2;j++)	for(int k = 0;k < 2;k++)	ans = min(ans, abs(xi-t[b[j]])+abs(t[b[j]]-s[a[k]]));
		cout << ans << endl;
	}
}

Measured memory_bytes: 2944
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int main(void) {
    map<char,int> dic;

    string s;
    cin>>s;

    for(int i = 0;i < s.size();i++) {
        dic[s[i]]++;
    }

    if(dic.size() == 2) {
        auto it = dic.begin();
        if(it->second == 2) {
            cout<<"Yes"<<endl;
        } else {
            cout<<"No"<<endl;
        }
    } else {
        cout<<"No"<<endl;
    }

    return 0;
}


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

#define pi 3.14159265358979323846264

#define ll long long
#define fori(n) for(long long i=0;i<n;i++)
#define forj(n) for(long long j=0;j<n;j++)

#define sp(n) setprecision(n)
#define d7 1000000007
#define mkp make_pair
#define mkt make_tuple

using namespace std;

bool isPrime(long long k){
    if(k<=1){return false;}
    if(k==2){return true;}
    if(k%2==0){return false;}
    long long i = 3;
   while (i*i <= k) {if (k % i == 0) {return false;}i += 2;}
return true;
}

ll binomialCoeff(ll n, ll k){
    ll C[n + 1][k + 1];ll i, j;
    for (i = 0; i <= n; i++){
        for (j = 0; j <= min(i, k); j++){
            if (j == 0 || j == i){C[i][j] = 1;}
            else{C[i][j] = (C[i - 1][j - 1]%d7 + C[i - 1][j]%d7)%d7;}}}
    return C[n][k]%d7;
 }

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

ll srihrg(ll n,ll k,ll m){
    ll ans;
    ans=1;
    fori(k){
        ans=(ans*n)%m;
    }
    return ans;
}


int main(int argc, const char * argv[]) {
 //cout<<"Om\n";
 //Praise to Lord
 //make cin/cout faster
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);cout.tie(NULL);
// code now
   
    
    ll n,k;
    vector<ll> a={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cin>>k;
    cout<<a[k-1];
    
//code ends
    return 0;
}


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

signed main(){
  
  int N, K;
  cin>>N>>K;
  
  int ans = 0;
  
  for(int i=K+1;i<=N;i++){
    
    ans += ( ( N - K ) / i + 1 ) * ( i - K );
    
    if( N % i >= K ) ans -= i - N % i - 1;
    
  }
  
  if( K == 0 ) ans -= N;
  
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 256