akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.lang.Math;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        FS reader = new FS();
        // write reader
        long X = reader.nextLong();
        long Y = reader.nextLong();
        if (X % Y == 0) System.out.println(-1);
        else System.out.println(X);
    }

    // Read Class
    static class FS {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
    
        private int readByte() { return hasNextByte() ? buffer[ptr++] : -1;}
        private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
        private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public int nextInt() {
            return (int)nextLong();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while(true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if(b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
    }
}



Measured memory_bytes: 20564
n = gets.to_i
ary = []

n.times do |i|
  k,pe = gets.split(" ").map(&:to_i)
  if(k >= pe)
    if(k%pe === 0)
      ary.push(pe)
    else
      ary.push(k%pe)
    end
  else
    ary.push(k)
  end
end

puts ary

Measured memory_bytes: 8664
#include <bits/stdc++.h>
#define PI 3.141592653589793
using namespace std;

int main() {
	// your code goes here
	int a,b,C;
	cin >> a >> b >> C;
	double c = C/180.0*PI;
	double S = a*b*sin(c)/2.0;
	double L = a+b+sqrt(a*a+b*b-2*a*b*cos(c));
	double h = b*sin(c);
	printf("%.6lf\n%.6lf\n%.6lf\n",S,L,h);
	return 0;
}


Measured memory_bytes: 3512
# ABC099D - Good Grid
import sys
input = sys.stdin.readline

from collections import defaultdict
from itertools import product


def main():
    N, C = map(int, input().split())
    D = [0] + list([0] + list(map(int, input().split())) for _ in range(C))
    grid = tuple(tuple(map(int, input().split())) for _ in range(N))
    cost = {i: defaultdict(int) for i in range(3)}
    for i, g in enumerate(grid):
        for j, x in enumerate(g):
            cost[(i + j) % 3][x] += 1
    dist = [[] for _ in range(3)]
    for i, tgt in product(range(3), range(1, C + 1)):
        cur = sum(D[src][tgt] * cnt for src, cnt in cost[i].items())
        dist[i].append(cur)
    ans = 1 << 60
    for i, j in product(range(C), repeat=2):
        if i == j:
            continue
        cur = dist[0][i] + dist[1][j]
        cur += min(x for k, x in enumerate(dist[2]) if k not in (i, j))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 5356
#include<stdio.h>
#include<string.h>
int main()
{
    char s[10];
    scanf("%s", s);
    int i;
    for(i=0;i<strlen(s)-1;i++)
        if (s[i] == 'A' && s[i + 1] == 'C')
        {
            printf("Yes\n");
            return 0;
        }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 128
b = input()
a = ''
for i in range(len(b)):
    if b[i] == 'A':
        a += 'T'
    elif b[i] == 'T':
        a += 'A'
    elif b[i] == 'C':
        a += 'G'
    elif b[i] == 'G':
        a += 'C'
print(a)


Measured memory_bytes: 2940
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
 
using namespace std;
int MOD = 1000000007;

signed main(){
    int n,c;
    cin >> n >> c;
    int ans = 0;

    int left1[100010] = {0};
    int left2[100010] = {0};
    int right1[100010] = {0};
    int right2[100010] = {0};

    vector<pair<int,int>> s;

    rep(i,n){
        int x,v;
        cin >> x >> v;
        s.push_back(MP(x,v));
    }
    int wal = s[0].se;
    left1[0] = max(0LL,wal-s[0].fi);
    left2[0] = max(0LL,wal-2*s[0].fi);
    ans = max(ans,left1[0]);
    for(int i = 1;i < n;i++){
        wal += s[i].se;
        left1[i] = max(left1[i-1],wal-s[i].fi);
        left2[i] = max(left2[i-1],wal-2*s[i].fi);
        ans = max(ans,left1[i]);
        // cerr << i << " " << ans << endl;
    }

    int war = s[n-1].se;
    right1[0] = max(0LL,war-c+s[n-1].fi);
    right2[0] = max(0LL,war-2*c+2*s[n-1].fi);
    ans = max(ans,right1[0]);
    for(int i = 1;i < n;i++){
        war += s[n-1-i].se;
        right1[i] = max(right1[i-1],war-c+s[n-1-i].fi);
        right2[i] = max(right2[i-1],war-2*c+2*s[n-1-i].fi);
        ans = max(ans,right1[i]);
        // cerr << i << " " << ans << endl;
    }

    for(int i = 0;i <= n-2;i++){
        ans = max(ans,left2[i]+right1[n-2-i]);
        //cerr << i << " " << ans << endl;
        ans = max(ans,left1[n-2-i]+right2[i]);
        // cerr << i << " " << ans << endl;
    }
    // cerr << "left1" << endl;
    // rep(i,n) cerr << left1[i] << endl;
    // cerr << "left2" << endl;
    // rep(i,n) cerr << left2[i] << endl;
    // cerr << "right1" << endl;
    // rep(i,n) cerr << right1[i] << endl;
    // cerr << "right2" << endl;
    // rep(i,n) cerr << right2[i] << endl;
    
    
    cout << ans << endl;

    return 0;   
}
// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://ddcc2019-final.contest.atcoder.jp/tasks/ddcc2019_final_a
// rm -r -f test;oj dl http://arc096.contest.atcoder.jp/tasks/arc096_b


Measured memory_bytes: 5492
let n, k = Scanf.scanf "%d %d" (fun n k -> n, k)
let a = Array.init n (fun _ -> Scanf.scanf " %d" (fun i -> i))

let rec f d x =
  if d = -1 then x
  else
    let rec g i c =
      if i = n then c
      else g (i + 1) (c + (a.(i) lsr d) land 1) in
    let c = g 0 0 in
    f (d - 1) (x lor if c < n - c then 1 lsl d else 0)

let rec g d x =
  if d = -1 then x
  else
    let k = (k lsr d) land 1 in
    let b = (x lsr d) land 1 in
    if k = 1 && b = 0 then x
    else if k = 0 && b = 1 then g (d - 1) (x lxor (1 lsl d))
    else g (d - 1) x

let rec h i x s =
  if i = n then s
  else h (i + 1) x (s + a.(i) lxor x)

let () =
  let x = f 39 0 in
  let x = g 39 x in
  let a = h 0 x 0 in
  Printf.printf "%d\n" a


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

int main(){
	double l;
	cin >> l;
	
	double ans = l/3;
	cout << fixed << setprecision(10) << ans*ans*ans << endl;

	return 0;
}

Measured memory_bytes: 256
# -*- coding:utf-8 -*-
import copy

def solve():
    N = int(input())
    Ps = tuple(map(int, input().split()))
    Qs = tuple(map(int, input().split()))

    available_list = [i for i in range(1, N+1)]

    permutations = []  # 順列
    def _dfs(rest_list, p):
        if len(rest_list) == 0:
            permutations.append(tuple(p))
            return

        for i in range(1, N+1):
            if i in rest_list:
                tmp_rest_list = copy.deepcopy(rest_list)
                tmp_rest_list.remove(i)
                tmp_p = copy.deepcopy(p)
                tmp_p.append(i)
                _dfs(tmp_rest_list, tmp_p)


    _dfs(available_list, [])

    permutations.sort()

    for i, p in enumerate(permutations):
        if p == Ps:
            a = i+1
        if p == Qs:
            b = i+1

    print(abs(a-b))


if __name__ == "__main__":
    solve()


Measured memory_bytes: 8432
import os
import sys

def main():
    n = int(input())
    for i in range(1,n+1):
        x = int(input())
        print("Case {}:".format(i))
        for j in range(10):
            x = x**2
            out = '{0:08d}'.format(x)
            print(int(out[2:6]))
            x = int(out[2:6])

main()

Measured memory_bytes: 5612
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define erep(i, n) for (int i = 0; i <= (n); i++)
#define erep1(i, n) for (int i = 1; i <= (n); i++)
using namespace std;
using ll = long long;

int main() {
    int k, a, b;
    cin >> k;
    cin >> a >> b;
    for (int i = a; i <= b; i++) {
        if (i % k == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}

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

///******************************** C o n t a i n e r ********************************///

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef map<int,int> mii;
typedef map<ll,int> mli;

///*********************************** C o n s t ***********************************///

const int       N=1e6+3;
const double    PI = acos(-1);
const ll        MOD=1000000007;  ///1e9+7

///********************************** M a r c o ***********************************///

#define pb push_back
#define F first
#define S second
#define test int tc; cin>>tc; while(tc--)
#define forn(i,n) for(i=0;i<n;i++)
#define rforn(i,n) for(i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) x.size()
#define el <<'\n'
#define sp <<' '
#define print(a) {for(auto x:a)cout<<x<<" ";cout<<endl;}
#define mem(a,b) memset(a, b, sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define sqr(a) (a)*(a)

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

///*********************************** F u n c t i o n ***********************************///

ll powmod(ll a,ll b){ll p=MOD;a%=p;if(!a) return 0;ll pr=1;while(b>0){if(b&1){pr*=a;pr%=p;--b;}a*=a;a%=p;b/=2;}return pr;}
bool isPrime(ll n){ if(n<=1)return false;if(n<=3)return true;if(n%2==0 or n%3==0)return false;for(ll i=5;i*i<=n;i+=6){if(n%i==0 or n%(i+2)==0)return false;}return true;}
void seive(bool a[]){ll mx=sqrt(N),ii,jj;for(ii=3;ii<=mx;ii+=2)if(!a[ii])for(jj=ii*ii;jj<=N;jj+=2*ii)a[jj]=true;}
void numofdiv(ll a[]){ll mx=sqrt(N),ii,jj;for(ii=1;ii<=mx;ii++){for(jj=ii*ii;jj<=N;jj+=ii){if(jj==ii*ii) a[jj]++; else a[jj]+=2;}}}
void sumofdiv(ll a[]){ll mx=sqrt(N),ii,jj;for(ii=1;ii<=mx;ii++){for(jj=ii*ii;jj<=N;jj+=ii){if(jj==ii*ii) a[jj]+=ii; else a[jj]+=ii+jj/ii;}}}

///**************************************************** C o d e ****************************************************///
///-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=///



void _case()
{
    ll g=0,n;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++) cin>>a[i],g=gcd(g,a[i]);
    cout<<g el;
}

main()
{
//    fastio();
        _case();

}


///Thank you.


///Brainless_Loco Terminates Here!


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;

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

const int inf = 1e9 + 1;
const double eps = 1e-9;
const int MAXN = 2e5 + 1;

int n, m;
string s;
vector <int> va[MAXN], vb[MAXN];
vector <int> okv;
bool ok[MAXN];
int okN, vaN[MAXN], vbN[MAXN];

void del(int cvor){

    if (!ok[cvor]) return;

    ok[cvor] = 0;
    okN--;

    for (int i = 0; i < va[cvor].size(); i++){

        if (s[cvor] == 'A'){
            vaN[va[cvor][i]]--;
            if (vaN[va[cvor][i]] == 0) del(va[cvor][i]);
        }
        else{
            vbN[va[cvor][i]]--;
            if (vbN[va[cvor][i]] == 0) del(va[cvor][i]);
        }

    }

    for (int i = 0; i < vb[cvor].size(); i++){

        if (s[cvor] == 'A'){
            vaN[vb[cvor][i]]--;
            if (vaN[vb[cvor][i]] == 0) del(vb[cvor][i]);
        }
        else{
            vbN[vb[cvor][i]]--;
            if (vbN[vb[cvor][i]] == 0) del(vb[cvor][i]);
        }

    }

}

int main(){

    cin >> n >> m;
    cin >> s;

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

        int a, b;

        cin >> a >> b;
        a--; b--;
        if (s[a] == 'A') va[b].pb(a);
        else vb[b].pb(a);
        if (s[b] == 'A') va[a].pb(b);
        else vb[a].pb(b);

    }

    for (int i = 0; i < n; i++){
        if (va[i].size() && vb[i].size()){
            okv.pb(i);
            ok[i] = 1;
        }
    }

    okN = okv.size();
    for (int i = 0; i < n; i++){
        for (int j = 0; j < va[i].size(); j++) if (ok[va[i][j]]) vaN[i]++;
        for (int j = 0; j < vb[i].size(); j++) if (ok[vb[i][j]]) vbN[i]++;
    }

    for (int i = 0; i < okv.size(); i++){

        int idx = okv[i];

        if (!ok[idx]) continue;

        bool a = 0, b = 0;

        for (int j = 0; j < va[idx].size(); j++){
            if (ok[va[idx][j]]) a = 1;
        }

        for (int j = 0; j < vb[idx].size(); j++){
            if (ok[vb[idx][j]]) b = 1;
        }

        if (!a || !b) del(idx);

    }

    if (okN) cout << "Yes";
    else cout << "No";

    return 0;

}

Measured memory_bytes: 27388
#include<bits/stdc++.h>
using namespace std;
#define ALL(A) A.begin(),A.end()
const long long mod=1000000007;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> P_T;//Pair and times
int h,w,ans=0;
char a[1001][1001];
queue<P_T> Q;
int bfs(){
    while(Q.size())
    {
        P_T now=Q.front();
        Q.pop();
        if((now.first).first>0)
        {
            if(a[now.first.first-1][now.first.second]=='.')
            {
                Q.push(make_pair(make_pair(now.first.first-1,now.first.second),now.second+1));
                a[now.first.first-1][now.first.second]='#';
            }
        }
        if((now.first).first<h-1)
        {
            if(a[now.first.first+1][now.first.second]=='.')
            {
                Q.push(make_pair(make_pair(now.first.first+1,now.first.second),now.second+1));
                a[now.first.first+1][now.first.second]='#';
            }
        }
        if((now.first).second>0)
        {
            if(a[now.first.first][now.first.second-1]=='.')
            {
                Q.push(make_pair(make_pair(now.first.first,now.first.second-1),now.second+1));
                a[now.first.first][now.first.second-1]='#';
            }
        }
        if((now.first).second<w-1)
        {
            if(a[now.first.first][now.first.second+1]=='.')
            {
                Q.push(make_pair(make_pair(now.first.first,now.first.second+1),now.second+1));
                a[now.first.first][now.first.second+1]='#';
            }
        }
        ans=max(ans,now.second);
    }
    return 0;
}
int main(){
    cin>>h>>w;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a[i][j];
            if(a[i][j]=='#')
            Q.push(make_pair(make_pair(i,j),0));
        }
    }
    bfs();
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 13328
def main():
    N = int(input())
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
#     print(N)
#     print(A)
    for num in A:
        if num % 2 == 0:
            if num % 3 == 0 or num % 5 == 0:
                pass
            else:
                print("DENIED")
                exit()
    print("APPROVED")


main()


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

int n;

int main(){
	scanf("%d", &n);
	
	if(n % 2 == 0){
		printf("%d\n", n * (n - 2) / 2);
		for(int i = 1; i <= n; i++){
			for(int j = i + 1; j <= n; j++){
				if(i + j == n + 1)continue;
				printf("%d %d\n", i, j);
			}
		}
	}else{
		printf("%d\n", (n - 1) * (n - 3) / 2 + n - 1);
		for(int i = 1; i <= n - 1; i++){
			for(int j = i + 1; j <= n; j++){
				if(i + j == n)continue;
				printf("%d %d\n", i, j);
			}
		}
	}
	
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll mod=1e9+7;
const int inf=1<<30;

ll rui(ll a,ll n){
  ll ans=1;
  while(n>0){
    if(n&1) ans=ans*a%mod;
    a=a*a%mod;
    n/=2;
  }
  return ans;
}
ll modinv(ll a,ll m){
  ll b=m,u=1,v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  u%=m;
  if(u<0) u+=m;
  return u;
}

int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  ll coma1=1;
  ll coma2=1;
  ll comb1=1;
  ll comb2=1;
  for(int i=1;i<=a;i++){
    coma1*=(n-i+1); coma1%=mod;
    coma2*=i; coma2%=mod;
  }
  ll coma=coma1*modinv(coma2,mod)%mod;
  for(int i=1;i<=b;i++){
    comb1*=(n-i+1); comb1%=mod;
    comb2*=i; comb2%=mod;
  }
  ll comb=comb1*modinv(comb2,mod)%mod;
  ll ans=rui(2,n)-1-coma-comb;
  while(ans<0){
    ans+=mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
//Look at my code, my code is clean :3
//Khánh đẹp trai
#include <bits/stdc++.h>
#define FORUP(i, start, end) for (int i = start; i <= end; i++)
#define FORDOWN(i, end, start) for (int i = end; i >= start; i--)
#define mem(a, v) memset(a, v, sizeof a)
#define ll long long
#define ld long double
#define pir pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const ll MAX = 1000009, MOD = 1000000007, BASE = 311, inf  = 1e9;

int du[] = {1, 0}, dv[] = {0, 1};
struct node {
    ll v; ll d; ll e;
};

using namespace std;

int n, cnt, p[MAX], res;

void sieve() {
    p[1] = 1;
    FORUP(i, 2, 1000000) {
        if(!p[i]) for(int j = i; j <= 1000000; j += i)
            if(!p[j]) p[j] = i;
    }
    FORUP(i, 2, 1000000) if(!p[i]) p[i] = i;
}

int calc(int x) {
    if(x == 1) return 1;
    int res = 1, cnt = 0, prev = p[x];
    while(x != 1) {
        if(p[x] == prev) cnt++;
        else {
            res *= (cnt+1);
            cnt = 1;
        }
        prev = p[x];
        x /= p[x];

    }
    return res * (cnt+1);
}

int main()
{
    fast_io;
    sieve();
//    cout << calc(9) << endl;
    cin >> n;
    FORUP(i, 1, n-1) res += calc(i);
    cout << res;
    return 0;
}


Measured memory_bytes: 7548
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<cstdio>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

typedef pair<int,int> ii;

const string roulette = "abcdef";
int dx[] = {-1,-1,+0,+1,+1,+0};
int dy[] = {+1,+0,-1,-1,+0,+1};
string line1,line2;
int N;
vector<int> Index[2];

bool check(vector<ii> v1,vector<ii> v2)
{
  sort(v1.begin(),v1.end());
  sort(v2.begin(),v2.end());
  rep(i,N)if(v1[i] != v2[i])return false;
  return true;
}

void compute()
{
  if(line1.size() != line2.size())
    {
      cout << "false" << endl;
      return;
    }
  N = line2.size();
  
  vector<ii> ori;
  int mx,my;
  ori.push_back(ii(0,0));
  
    int x = 0, y = 0;
    mx = my = 0;
    rep(i,N)
      {
	x += dx[line1[i]-'a'];
	y += dy[line1[i]-'a'];
	mx = min(mx,x);
	my = min(my,y);
	ori.push_back(ii(x,y));
      }
  

  rep(i,ori.size())ori[i].first -= mx, ori[i].second -= my;


  rep(j,7)//dir
    {
      vector<ii> cont;
      cont.push_back(ii(0,0));
      x = y = 0;
      mx = x, my = y;
      rep(i,N)
	{
	  x += dx[(line2[i]-'a'+j)%6];
	  y += dy[(line2[i]-'a'+j)%6];
	  mx = min(mx,x);
	  my = min(my,y);
	  cont.push_back(ii(x,y));
	}
      
      rep(i,cont.size())cont[i].first -= mx,cont[i].second -= my;
      
      if(check(ori,cont))
	{
	  cout << "true" << endl;
	  return;
	}
      
    }
      
    
  
  
  cout << "false" << endl;
}


int main()
{
  int n; 
  while(cin >> n)
    {
      cin.ignore();
      string blank;
      while(n--)
	{
	  line1.clear();
	  line2.clear();
	  char c;
	  while((c = getchar()) != '\n')line1 += c;
	  while((c = getchar()) != '\n')line2 += c;
	  cin >> blank;
	  cin.ignore();
	  compute();
	}
    }
  return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
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; }
typedef long long ll;
int main()
{
  ll d; cin >> d;
  vector<ll> c(26);
  rep(i,26) cin >> c[i];
  vector<vector<ll>> s(d, vector<ll>(26));
  rep(i,d) {
    rep(j,26) {
      cin >> s[i][j];
    }
  }

  vector<ll> t(d, 0);
  
  ll res = 0;
  vector<ll> last(26, -1);
  rep(i,d) {
    ll ss = 0;
    rep(j,26) {
      if(chmax(ss, s[i][j])) {
	t[i] = j;
      }
    }
    res += s[i][t[i]];
    last[t[i]] = i;
    rep(j,26) {
      res -= c[j] * (i - last[j]);
    }
  }

  for(auto val: t) cout << val+1 << "\n";
  return 0;
}


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

int main(){
	int x[3], k = 1, a, b;
	
	while(cin >>x[1]>>x[2]){
		if(x[2] > x[1]) swap(x[1], x[2]);
		a = x[1];
		b = x[2];
		while(x[3 - k] != 0){
			x[k] = x[k] % x[3 - k];
			k = 3 - k;
		}
		cout <<x[k]<<" "<<a / x[k] * b<<endl;
		k = 1;
	}
	
	return 0;
}

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

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

int main() {
  ll n, ans = 0;
  string s;
  vector<char> c;
  cin >> s;
  rep(i, s.size()) if (s[i] != 'x') c.push_back(s[i]);
  bool ok = false;
  for (int i = 0; i < c.size() / 2; ++i) {
    if (c[i] == c[c.size() - 1 - i])
      continue;
    else
      ok = true;
  }

  if (s.size() == 1) {
    puts("0");
    return 0;
  }

  if (ok) {
    puts("-1");
    return 0;
  }
  int i = 0, j = s.size() - 1;
  do {
    if (s[i] == s[j]) {
      i++, j--;
    } else {
      if (s[i] == 'x') {
        i++;
        ans++;
      } else {
        j--;
        ans++;
      }
    }
  } while (i <= j);

  cout << ans << endl;
  return 0;
}


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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  int n;
  vector<LL> a, b, c;
  Solver(LL n) : n(n), a(n), b(n + 1), c(n + 1){};

  void solve() {
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      c[a[i]]++;
    }
    LL sum = 0;
    for (int i = 1; i <= n; ++i) {
      b[i] = c[i] * (c[i] - 1) / 2;
      sum += b[i];
    }
    for (int i = 0; i < n; ++i) {
      int tmpc = c[a[i]];
      cout << sum - tmpc * (tmpc - 1) / 2 + (tmpc - 1) * (tmpc - 2) / 2 << endl;
    }
  }
};

}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0;
  std::cin >> n;

  Problem::Solver sol(n);
  sol.solve();
  return 0;
}


Measured memory_bytes: 7424
import java.io.*;

public class Main{

	// Point class
	static class Point{
		public double x;
		public double y;

		public Point(double x, double y){
			this.x = x;
			this.y = y;
		}

		public Point(Point p){
			x = p.x;
			y = p.y;
		}

		public void printPoint(){
			System.out.printf("%.8f %.8f\n", x, y);
		}
	}

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n;
		Point zero = new Point(0, 0);
		Point hyaku = new Point(100, 0);
		int i, j, k;

		n = Integer.parseInt(br.readLine());
		
		zero.printPoint();
		divisionPoint(n, zero, hyaku);
		hyaku.printPoint();
	}

	static void divisionPoint(int n, Point p1, Point p2){
		double x = p2.x - p1.x;
		double y = p2.y - p1.y;

		Point s = new Point((x/3)+p1.x, (y/3)+p1.y);
		Point t = new Point(2*(x/3)+p1.x, 2*(y/3)+p1.y);
		Point u = new Point(getKoch(s, t));

		if(n > 0){
			divisionPoint(n-1, p1, s);
			s.printPoint();

			divisionPoint(n-1, s, u);
			u.printPoint();

			divisionPoint(n-1, u, t);
			t.printPoint();

			divisionPoint(n-1, t, p2);
		}
	}

	static Point getKoch(Point s, Point t){
		double x = t.x - s.x;
		double y = t.y - s.y;

		double moveX = (Math.cos(Math.toRadians(60)) * x - Math.sin(Math.toRadians(60)) * y) + s.x;
		double moveY = (Math.sin(Math.toRadians(60)) * x + Math.cos(Math.toRadians(60)) * y) + s.y;

		Point u = new Point(moveX, moveY);
		return u;
	}
}

Measured memory_bytes: 42956
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
#define vci vector<ll>
#define vcs vector<string>
#define vcp vector<pair<ll, ll>>
#define vct vector<tuple<ll, ll, ll>>
using namespace std;
//vector<vector<ll>> vv(n, vector<ll>(n));

typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

int main()
{
	string s;
	cin >> s;
	map<char, ll> mp;
	REP(i, s.size()) mp[s[i]]++;
	FOR(i, 'a', 'z' + 1) {
		if (!mp[i]) {
			cout << static_cast<char>(i) << endl;
			return 0;
		}
	}
	cout << "None" << endl;
}


Measured memory_bytes: 512
import copy

H, W = map(int,input().split())
root_list = []
for _ in range(H):
    root_list.append(list(str(input())))


change_list = copy.deepcopy(root_list)
DP_list = []

for i, line in enumerate(root_list):
    DP_line = []
    str_pt = root_list[i][0]
    if i == 0:
        DP_line.append(0) # 初期値
    else:
        if root_list[i-1][0] == line[0]: # 1文字目が上下一致
            DP_line.append(DP_list[i-1][0])
        else:
            DP_line.append(DP_list[i-1][0] + 1)

    for j, pt in enumerate(line[1:], 1): # 先頭は抜かす
        if i == 0: # 1行目
            if str_pt == pt: # 前の文字と一致
                DP_line.append(DP_line[j-1]) # 前の値を入れる
            else:
                DP_line.append(DP_line[j-1] + 1) # 違ったら1足す
                str_pt = pt
        else: # 2行目以降（上下左右比較）
            # 横比較
            if str_pt == pt:
                yoko_pt = DP_line[j-1]
            else:
                yoko_pt = DP_line[j-1] + 1
            
            # 縦比較
            if pt == root_list[i-1][j]:
                tate_pt = DP_list[i-1][j]
            else:
                tate_pt = DP_list[i-1][j] + 1
            
            DP_line.append(min(yoko_pt, tate_pt))
            str_pt = pt

    DP_list.append(DP_line)

result = DP_list[H-1][W-1] // 2

if root_list[0][0] == "#":
    result += 1
if root_list[H-1][W-1] == "#":
    result += 1
if  root_list[0][0] == "#" and root_list[H-1][W-1] == "#":
    if result == 2 or (H == 1 and W == 1):
        result = 1
    else:
        result -= 1

print(result)


Measured memory_bytes: 44528
//#include <algorithm>
//#include <cstdio>
//#include <functional>
#include <iostream>
//#include <cfloat>
//#include <climits>
//#include <cstdlib>
//#include <cstring>
//#include <cmath>
//#include <map>
//#include <queue>
//#include <set>
//#include <sstream>
//#include <stack>
//#include <string>
//#include <time.h>
//#include <vector>
//#include <random>
//#include <unordered_set>
//#include <complex>
#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define LL long long
using namespace std;
int main()
{
	int a,b,x;
	cin>>a>>b>>x;
	if((x>=a)and(x<=(a+b))) cout<<"YES";
	else cout<<"NO"; 
    rt0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,x,ans;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>ans;
    for(int i=2;i<=n;i++){
        cin>>x;
        ans=ans*(x/__gcd(ans,x));
    }
    cout<<ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>

#define rep(i, b) for(int i = 0; i < b; i++)
#define repi(i, a, b) for(int i = a; i < b; i++)
#define all(c) c.begin(),c.end()
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define MAX_V 1001
#define MAX_E 401
#define INF INT_MAX
#define MOD 1000000007
#define EPS 1e-7

typedef long long ll;
inline int toInt(std::string s) { int v; std::istringstream sin(s); sin >> v; return v; }
template<class T> inline std::string toString(T x) { std::ostringstream sout; sout << x; return sout.str(); }
using namespace std;

typedef double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
#define X real()
#define Y imag()
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template< typename T >
struct edge {
	int src, to;
	T cost;

	edge(int to, T cost) : src(-1), to(to), cost(cost) {}

	edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

	edge &operator=(const int &x) {
		to = x;
		return *this;
	}

	operator int() const { return to; }
};
template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

int main()
{
	ll n;
	cin >> n;
	string s = toString(n);
	ll res = 0;
	
	rep(i, s.size())
	{
		res += s[i] - '0';
	}
	if (res == 1 && n >= 10)
	{
		res = 10;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005;
int n,len[N],c[26]; string s[N]; long long ans;
class Trie
{
	private:
		struct Trie_Node
		{
			int ch[26],ct[26];
		}node[N]; int rt,tot=1;
		#define next(x,y) node[x].ch[y]
		#define C(x,y) node[x].ct[y]
	public:
		inline void reroot(void)
		{
			rt=1; for (RI i=0;i<26;++i) if (c[i]) ++C(rt,i);
		}
		inline void insert(const char& ch)
		{
			if (next(rt,ch-'a')) rt=next(rt,ch-'a'); else rt=next(rt,ch-'a')=++tot;
			for (RI i=0;i<26;++i) if (c[i]) ++C(rt,i);
		}
		inline int query(const string& s,CI len)
		{
			rt=1; for (RI i=len-1;i;--i)
			if (next(rt,s[i]-'a')) rt=next(rt,s[i]-'a'); else return 0;
			return C(rt,s[0]-'a');
		}
		#undef next
		#undef C
}T;
int main()
{
	RI i,j; ios::sync_with_stdio(0); for (cin>>n,i=1;i<=n;++i)
	{
		for (cin>>s[i],len[i]=s[i].size(),j=0;j<len[i];++j) ++c[s[i][j]-'a'];
		for (T.reroot(),j=len[i]-1;~j;--j) --c[s[i][j]-'a'],T.insert(s[i][j]);
	}
	for (i=1;i<=n;++i) ans+=T.query(s[i],len[i]); return cout<<ans-n,0;
}

Measured memory_bytes: 238720
package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	k := make([]int, m)
	s := make([][]int, m)
	p := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Scan(&k[i])
		s[i] = make([]int, k[i])
		for j := 0; j < k[i]; j++ {
			fmt.Scan(&s[i][j])
			s[i][j]--
		}
	}
	for i := 0; i < m; i++ {
		fmt.Scan(&p[i])
	}

	ans := 0
L:
	for i := 0; i < 1<<uint(n); i++ {
		for j := 0; j < m; j++ {
			cnt := 0
			for _, v := range s[j] {
				if i>>uint(v)&1 == 1 {
					cnt++
				}
			}
			cnt %= 2
			if cnt != p[j] {
				continue L
			}
		}
		ans++
	}

	fmt.Println(ans)
}


Measured memory_bytes: 512
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	int H, W;
	
	cin >> H >> W;

	int a[H][W];

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

	int cnt = 0;
	int m[300000][4];
	memset(m, -1, sizeof(m));

	for (int i = 0; i < H - 1; i++)
	{
		for (int j = 0; j < W; j++)
		{
			if (a[i][j] & 1)
			{
				a[i+1][j]++;
				a[i][j]--;
				m[cnt][0] = i;
				m[cnt][1] = j;
				m[cnt][2] = i+1;
				m[cnt++][3] = j;
			}
		}
	}

	for (int i = 0; i < W - 1; i++)
	{
		if (a[H-1][i] & 1)
		{
			a[H-1][i+1]++;
			a[H-1][i]--;
			m[cnt][0] = H-1;
			m[cnt][1] = i;
			m[cnt][2] = H-1;
			m[cnt++][3] = i+1;
		}
	}

	cout << cnt << endl;
	rep(i, cnt)
	{
		cout << m[i][0]+1 << " " << m[i][1]+1 << " " << m[i][2]+1 << " " << m[i][3]+1 << endl;
	}
	
	return 0;
}


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

#define ll long long
#define mk make_pair
#define pb push_back


using namespace std;


int main(){
   
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   
   int s, w; cin >> s >> w;
   if(w < s){
      cout << "safe";
   }else{
      cout << "unsafe";
   }

   return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <cmath>

int main()
{
	long double x1, y1, x2, y2;
	std::cin >> x1 >> y1 >> x2 >> y2;
	long double d = sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
	std::cout << std::fixed << d << std::endl;
		
	return 0;
}




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

using namespace std;
int a[1001],b[1001],e[1001];
int main()
{
      int n;
      cin>>n;
      for(int i=0;i<n;i++)
      {
          cin>>a[i];
      }
      int q;
      cin>>q;
      for(int i=0;i<q;i++)
      {
          cin>>b[i];
          cin>>e[i];
      }
      for(int i=0;i<q;i++)
      {
          reverse(a+b[i],a+e[i]-1+1);
      }
      for(int i=0;i<n-1;i++)
      {
          cout<<a[i]<<" ";
      }
      cout<<a[n-1];
      cout<<endl;
      return 0;
}





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

set<int> D;

bool contains_digit(int n) {
    bool flag = false;
    while (n > 0) {
        flag |= D.count(n % 10) > 0;
        n /= 10;
    }
    return flag;
}

int main() {
    int N, K; cin >> N >> K;
    for (int i = 0; i < K; ++i) {
        int d; cin >> d;
        D.insert(d);
    }

    for (int i = N; i < N*10; ++i) {
        if (!contains_digit(i)) {
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
from collections import defaultdict
from itertools import combinations

d = defaultdict(int)

n = int(input())

for _ in range(n):
    initial = input()[0]
    if initial in 'MARCH':
        d[initial] += 1

a = list(d.values())

ans = 0

for x in combinations(range(len(a)),3):
    ans += a[x[0]] * a[x[1]] * a[x[2]]

print(ans)

Measured memory_bytes: 3316
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

# lines = list(map(lambda s: s.strip(), sys.stdin.readlines()))
a,b,c,d = get_all_int()

x = (c+b-1)//b
y = (a+d-1)//d

print("Yes" if x <= y else "No")

Measured memory_bytes: 67608
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"


int main(){

    ll n,W;
    cin>>n>>W;
    ll w[n],v[n];

    for(ll i=0;i<n;i++)
    cin>>w[i]>>v[i];

    ll dp[n+1][W+1];

    for(ll i=0;i<=n;i++)
    {
        for(ll j=0;j<=W;j++)
        {
            if(i==0 || j==0)
            dp[i][j]=0;

            else if(w[i-1]<=j)
            {
                dp[i][j]= max(v[i-1]+ dp[i-1][j-w[i-1]],dp[i-1][j]);
            }
            else
            dp[i][j]=dp[i-1][j];

        }
    }
    cout<<dp[n][W]<<endl;


    return 0;
}

Measured memory_bytes: 79104
#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main() {
  double x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;

  double dx = x2 - x1;
  double dy = y2 - y1;
  auto dist = sqrt(dx * dx + dy * dy);
  printf("%.8f\n", dist);
  fflush(stdout);
  return 0;
}



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

public class Main {

    private void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        String S = sc.next();
        char[] SCharArray = S.toCharArray();
        int[] left = new int[Q];
        int[] right = new int[Q];
        for (int i = 0; i < Q; i++) {
            left[i] = sc.nextInt();
            right[i] = sc.nextInt();
        }

        int[] accumCounts = new int[N];
        for (int i = 0; i < N - 1; i++) {
            if (SCharArray[i] == 'A' && SCharArray[i + 1] == 'C') {
                accumCounts[i + 1] = (accumCounts[i] + 1);
            }
            else {
                accumCounts[i + 1] = accumCounts[i];
            }
        }
        //accumCounts[N - 1] = accumCounts[N - 2];

        //for (int i = 0; i < N; i++) {
        //   System.out.println(accumCounts[i]);
        //}
        for (int i = 0; i < Q; i++) {
            System.out.println(accumCounts[right[i] - 1] - accumCounts[left[i] - 1]);
        }
    }

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

}


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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

ll P = 1000000007;
ll dp[101010][13] = {0};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int n = s.size();
  int po10[101010] = {0};
  po10[0] = 1;
  for (int i = 0; i <= n; i++) po10[i + 1] = (po10[i] * 10) % 13;

  reverse(s.begin(), s.end());
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 13; j++) {
      if (s[i] == '?') {
        for (int k = 0; k < 10; k++) {
          dp[i + 1][(j + k * po10[i]) % 13] += dp[i][j];
          dp[i + 1][(j + k * po10[i]) % 13] %= P;
        }
      } else {
        dp[i + 1][(j + (s[i] - '0') * po10[i]) % 13] += dp[i][j];
        dp[i + 1][(j + (s[i] - '0') * po10[i]) % 13] %= P;
      }
    }
  }
  cout << dp[n][5] << endl;
  return 0;
}


Measured memory_bytes: 11088
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

int H, W;
string s[1010];
int dp[1010][1010];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> H >> W;
  REP(i, H) cin >> s[i];
  dp[0][0] = 1;
  REP(i, H) REP(j, W) if (s[i][j]=='.') {
    if (i+1<H && s[i+1][j] == '.') (dp[i+1][j] += dp[i][j]) %= MOD;
    if (j+1<W && s[i][j+1] == '.') (dp[i][j+1] += dp[i][j]) %= MOD;
  }
  cout << dp[H-1][W-1] << endl;

  return 0;
}

Measured memory_bytes: 9216
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  s <- getLine
  t <- getLine
  let t' = take (length s) t
  if s == t'
    then putStrLn "Yes"
    else putStrLn "No"


Measured memory_bytes: 3724
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define endl '\n'
#define N 200005
using namespace std;
vector<int>adj[N];
int dp[N],vis[N];
int  dfs (int s)
{
	int ans = 0;
	vis[s] = 1;
	for(int i=0;i<adj[s].size();i++){
		if(vis[adj[s][i]]==0) 
		ans = max (ans, 1 + dfs(adj[s][i]));
		else 
		ans = max(ans,1+dp[adj[s][i]]);
	}
	return dp[s] = ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0,x,y;i<m;i++){
    	cin>>x>>y;
    	adj[x].pb(y);
    }
    
    int ans = 0;
    for(int i=1;i<=n;i++)
    ans = max(ans,dfs(i));
    cout<<ans<<endl;
}

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

int main(){
  string S;
  long long K;
  cin>>S;
  cin>>K;
  vector <int> a(100,0);
  long long ans=0;
  long long serial=0;
  long long temp=0;
  int on=0;
  
  //全部同じか　※　要検討
  bool flag=1;
  for(int i=1;i<S.length();i++){
    if(S.at(i)!=S.at(0)){
      flag=0;
    }
  }
  if(flag){
    cout<<S.length()*K/2<<endl;
    return 0;
  }
  
  on=0;
  temp=1;
  for(int i=0;i<S.length()-1;i++){
    if(S.at(i)==S.at(i+1)){
      temp++;
      on=1;
    }
    else if(on==1){
      serial=serial+temp/2;
      temp=1;
      on=0;
    }
  }
  if(on==1){
    serial=serial+temp/2;
  }
  
    //Sの最初としっぽが別の場合
  if(S.at(0)!=S.at(S.length()-1)){
    //cout<<"$"<<serial<<endl;
    cout<<serial*K<<endl;
    return 0;
  }

  long long temp1=1;//冒頭の連続文字数
  for(int i=0;i<S.length()-1;i++){
    if(S.at(i+1)==S.at(0)){
        temp1++;
    }
    else break;
  }
  
  long long temp2=0;//末尾の連続文字数
  for(int i=S.length()-1;i>-1;i--){
    if(S.at(i)==S.at(S.length()-1)){
      temp2++;
    }
    else break;
  }
  
  //cout<<serial<<" "<<temp1<<" "<<temp2<<" "<<endl;
  cout<<setprecision(20)<<serial*K-(temp1/2+temp2/2-(temp1+temp2)/2)*(K-1);
  return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int i = 1;
		do {
			int x = i;
			if (x % 3 == 0) {
				System.out.print(" " + i);
			} else {
				while (true) {
					if (x % 10 == 3) {
						System.out.print(" " + i);
						break;
					} else {
						x /= 10;
						if (x != 0) {
							continue;
						} else {
							break;
						}
					}
				}
			}
		} while (++i <= n);
		System.out.println("");
	}
}

Measured memory_bytes: 28576
h,w=map(int,input().split())
lis=[list(input()) for i in range(h)]

fin=[]
num=[0]*w

for l in lis:
  if l.count(".") != w:
    fin.append(l)
  for i in range(w):
    if l[i]==".":
      num[i]+=1

for f in fin:
  ans=[]
  for i in range(len(num)):
    if num[i]!=h:
      ans.append(f[i])
  print(*ans,sep='')
    

Measured memory_bytes: 9180
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))
ans = 0
for i in range(N):
    diff = abs(A - (T-H[i]*0.006))
    if i == 0:
        temp = diff
        ans = i+1
    else:
        if diff < temp:
            temp = diff
            ans = i+1

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int>arr(5);
	for(int i=0;i<5;i++)
		cin>>arr[i];
	int k;
	cin>>k;
	if(arr[4]-arr[0]<=k){
		cout<<"Yay!";
	}else
		cout<<":(";
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
l = gets.split.map(&:to_i).sort
ans = 0
n.times do |i|
  (i+1).upto(n - 2) do |j|
    a = l[i] + l[j]
    b = l.bsearch_index{|x| x >= a}
    b = n if b.nil?
    ans += b - j - 1
  end
end
p ans

Measured memory_bytes: 14304
import itertools
N = int(input())
P = tuple(map(int, input().split(' ')))
Q = tuple(map(int, input().split(' ')))
ls = [ x for x in itertools.permutations(range(1, N + 1), N) ]
a = [ key for key, val in enumerate(ls) if val == P ][0] + 1
b = [ key for key, val in enumerate(ls) if val == Q ][0] + 1
print(abs(a - b))

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

int main(){
    string s;
    cin >> s;
    ll n = s.size();
    ll i,j;
    if(n == 1){
        cout << 0;
        return 0;
    }
    i = 0,j = n- 1;
    ll ans = 0;
    while(i < j){
        if(s[i] != s[j]){
            if(s[i] == 'x'){
                i++;
                ans++;
            }else if(s[j] == 'x'){
                j--;
                ans++;
            }else{
                cout << -1;
                return 0;
            }
        }else{
            i++;
            j--;
        }
    }
    cout << ans;
}


Measured memory_bytes: 512