akhauriyash/Code-Regression huggingface dataset:
// 重み0の辺とコストがかかる辺のグラフ経路問題かな？
// ただ、ロボットの向きもあるので頂点の数はグリッドの数×4方向になる
// このプログラムでは、
/*
    →x
↓y  * * * * * * 
    * * * * * *
    * * * * * *
*/
// になっているよ。
#include <bits/stdc++.h>
using namespace std;

const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};
int s[40][40];
int G[40][40][4];
int c[4];

using ptupl = pair<int, tuple<int, int, int>>;

int main() {
    int w, h;
    while (cin >> w >> h, w || h) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> s[i][j];
            }
        }
        cin >> c[0] >> c[1] >> c[2] >> c[3];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                memset(G[i][j], -1, sizeof(G[i][j]));
            }
        }
        priority_queue<ptupl, vector<ptupl>, greater<ptupl>> que;
        que.emplace(0, make_tuple(0, 0, 0));
        while (!que.empty()) {
            auto p = que.top();
            que.pop();
            int d = p.first,
                x = get<0>(p.second),
                y = get<1>(p.second),
                dir = get<2>(p.second);
            if (G[y][x][dir] != -1) continue;
            G[y][x][dir] = d;
            // 命令せずに進ませる場合
            if (s[y][x] != 4) {
                int ndir = (dir + s[y][x] + 4) % 4;
                int nx = x + dx[ndir];
                int ny = y + dy[ndir];
                if (!(nx < 0 || nx >= w || ny < 0 || ny >= h))
                    if (G[ny][nx][ndir] == -1) que.emplace(d, make_tuple(nx, ny, ndir));
            }
            // 直進、または右折左折命令をさせる場合
            for (int i = 0; i < 4; ++i) {
                int ndir = (dir + i + 4) % 4;
                int nx = x + dx[ndir];
                int ny = y + dy[ndir];
                if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
                if (G[ny][nx][ndir] == -1) que.emplace(d + c[i], make_tuple(nx, ny, ndir));
            }
        }

        int res = 1000000000;
        for (int i = 0; i < 4; ++i) {
            if (G[h - 1][w - 1][i] == -1) continue;
            res = min(res, G[h - 1][w - 1][i]);
        }
        cout << res << endl;
    }
    return 0;
}


Measured memory_bytes: 3148
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr auto INF = INT_MAX / 2;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	ll x;
	cin >> x;
	ll a = 100;
	ll k = 0;

	while (true) {
		a *= 1.01;
		k++;
		if (a >= x)break;
	}

	cout << k << endl;

}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    string S, T;
    cin >> S >> T;
    if (S == T.erase(T.size() - 1)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
x, k, d = list(map(int, input().split()))

if abs(x) > k * d:
    print(abs(x) - k * d)
    exit()

a = abs(x) % d

nokori = k - abs(x) // d
if nokori % 2 == 0:
    print(a)
else:
    print(abs(a - d))

Measured memory_bytes: 9136
#include<stdio.h>

#define max 100001
#define nil -1

typedef struct{
  int right;
  int left;
  int parent;
}Node;

Node Tree[max];

int depth[max],length,child[max];

int main(){
  int i,own,numberchild,j;
  scanf("%d",&length);
  for(i=0;i<length;i++){
    Tree[i].parent=nil;
    Tree[i].right=nil;
    Tree[i].left=nil;
  }
  for(i=0;i<length;i++){
    scanf("%d %d",&own,&numberchild);
    for(j=0;j<numberchild;j++){
      scanf("%d",&child[j]);
      Tree[child[j]].parent=own;
      if(j == 0){
	Tree[own].left = child[0];
      }
      else{
	Tree[child[j - 1]].right = child[j];
      }
    }
  }
  
  for(i=0;i<length;i++){
    int count=0,subi;
    subi=i;
    while(1){
      if(Tree[subi].parent==nil){
	break;
      }
      subi=Tree[subi].parent;
      count++;
    }
    depth[i]=count;
  }
  
  for(i=0;i<length;i++){
    int hantei=0,sub2i;
    printf("node %d: parent = %d, depth = %d, ",i,Tree[i].parent,depth[i]);
    if(Tree[i].parent==nil){
      printf("root, [");
    }
    else if(Tree[i].left==nil){
      printf("leaf, [");
    }
    else {
      printf("internal node, [");
    }
    sub2i=Tree[i].left;
    while(sub2i!=nil){
      if(hantei==0){
	printf("%d",sub2i);
      }
      else{
	printf(", %d",sub2i);
      }
      sub2i=Tree[sub2i].right;
      hantei++;
    }
    printf("]");
    if(sub2i==nil){
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 2552
#include <iostream>
using namespace std;
int main(){
    int A,B,C,D;
    cin >> A >> B >> C >> D;
    int L = A + B;
    int R = C + D;
    if (L > R){
        cout << "Left" << endl;
    }
    else if (L == R){
        cout << "Balanced" << endl;
    }
    else{
        cout << "Right" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int n, k;
double ans;
int main(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        if(i >= k){
            ans += 1;
        }else{
            int num = i;
            int cnt = 0;
            while(num < k)num *= 2, cnt++;
            double num2 = 1.0;
            REP(j, cnt)num2 /= 2;
            ans += num2;
        }
    }
    ans /= n;

    cout << fixed << setprecision(13) << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

string solve(string s)
{
    rep(i,26)
    {
        char c = 'a'+i;
        bool found = false;
        rep(j,s.size())
        {
            if(s[j]==c)
            {
                found = true;
                break;
            }
        }
        if(!found) return string(1,c);
    }
    return "None";
}

int main()
{
    string s;
    cin >>s;
    cout << solve(s) << endl;
    return 0;
}


Measured memory_bytes: 512
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
}
// ここから編集しろ
int p[510];
int main(){
	int ret=0;
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	for(int i=0;i<a;i++)for(int j=i+1;j<a;j++)ret+=p[i]*p[j];
		
	printf("%d\n",ret);
}

Measured memory_bytes: 128
/*
Author: Golam Rahman Tushar
........Aust Cse 27th batch.........
*/

//{ Template

//{ C-headers
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cfloat>
#include <cctype>
#include <cassert>
#include <ctime>
//}
//{ C++-headers
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>

using namespace std;
//}

//}
//{ Floating-points
#define EPS DBL_EPSILON
#define abs(x) (((x) < 0) ? - (x) : (x))
#define zero(x) (abs (x) < EPS)
#define equal(a,b) (zero ((a) - (b)))
#define PI 2 * acos (0.0)
#define INF (1<<29)
#define ll long long
#define CountOne(mask) __builtin_popcountll(mask)

template<class T1> void debug(T1 e){cout<<e<<endl;}
template<class T1,class T2> void debug(T1 e1,T2 e2){cout<<e1<<"\t"<<e2<<endl;}
template<class T1,class T2,class T3> void debug(T1 e1,T2 e2,T3 e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
template <typename T>
std::string to_string(T const& value) {
    stringstream sstr;
    sstr << value;
    return sstr.str();
}
//}
template <class T> T gcd(T a,T b){if(b==0) return a;else return gcd(b,a%b);}
template <class T> T lcm(T a,T b){return (a*b)/gcd(a,b);}
template <class T> T power( T a, T b){if(b==0) return 1; T x=a;for(T i=2;i<=b;i++) a=a*x;return a;}
template <class T> T BigMod(T a,T b,T c){if(a==0) return 0;if(b==0) return 1;if(b%2==0){T x=BigMod(a,b/2,c)%c;return (x*x)%c;}else return  ((a%c)*BigMod(a,b-1,c)%c)%c;}
template <class T, class U> inline T swap (T &a, U &b) { T tmp = a; a = b; b = tmp; }

bool isVowel(char ch){ch=tolower(ch);if(ch=='a' | ch=='e' || ch=='i' || ch=='o' || ch=='u')return true;return false;}

///int dx[]= {-1,-1,0,0,1,1};
///int dy[]= {-1,0,-1,1,0,1};
///int dx[]= {0,0,1,-1};/*4 side move*/
///int dy[]= {-1,1,0,0};/*4 side move*/
///int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
///int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
///int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/
///int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/
/*................Code Starts Here................*/

int par[10000+7];

int findR (int x) {
    return par[x] == x? x : findR(par[x]);
}


int main() {
    //freopen("input.txt","r",stdin);
    int n, m, i, f, u, v;
    scanf("%d %d", &n, &m);

    for(i=0; i<n; i++) par[i] = i;

    while(m--) {
        scanf("%d %d %d", &f, &u, &v);
        int repu = findR(u);
        int repv = findR(v);

        if(f) {
            if(repu == repv) cout<<'1'<<endl;
            else cout<<'0'<<endl;
        } else {
            if(repu != repv) par[repu] = repv;
        }
    }
    return 0;
}

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

using namespace std;

# define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<ll, ll> pll;

# define S second
# define F first
# define kill(x) return(cout << x << endl, 0LL)
# define debug(x) cerr<< #x << " : " << x << endl
# define ddebug(x, y) cerr<< #x << " : " << x  << ", " << #y << " : " << y << endl
# define sz(s) (int)s.size()
# define sq(x) (x) * (x)
# define PB(x) push_back(x)
# define smax(x, y) (x) = max((x), (y))
# define smin(x, y) (x) = min((x), (y))
# define all(x) x.begin(), x.end()
# define SP fixed << setprecision(10)
# define MP make_pair

const int MAXN = 100 * 1000 + 10;
string a[MAXN];

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

	int n;
	cin >> n;

	cout << 0 << endl;
	cin >> a[0];
	a[n] = a[0];

	int l = 0, r = n;
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		cout << mid << endl;
		cin >> a[mid];
		if (a[mid] == "Vacant")
			return 0;

		if (a[l] == a[r])
		{
			if ((a[mid] == a[l]) ^ ((mid - l) & 1 ^ 1))
				r = mid;
			else
				l = mid;
		}
		else
		{
			if (((mid - l) & 1 ^ 1) ^ (a[mid] == a[l]))
				r = mid;
			else
				l = mid;
		}
	}

	return 0;
}



Measured memory_bytes: 1620
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string input;

            while (!string.IsNullOrEmpty(input = Console.ReadLine()))
            {
                string[] temp = input.Split(' ');

                int y = int.Parse(temp[0]);
                int m = int.Parse(temp[1]);
                int d = int.Parse(temp[2]);

                DateTime dt = new DateTime(y, m, d);

                if (dt < DateTime.Parse("1868/9/8"))
                {
                    Console.WriteLine("pre-meiji");
                }
                else if (dt < DateTime.Parse("1912/7/30"))
                {
                    int tempY = y - 1868 + 1;
                    Console.WriteLine("meiji {0} {1} {2}", tempY, m, d);
                }
                else if (dt < DateTime.Parse("1926/12/25"))
                {
                    int tempY = y - 1912 + 1;
                    Console.WriteLine("taisho {0} {1} {2}", tempY, m, d);
                }
                else if (dt < DateTime.Parse("1989/1/8"))
                {
                    int tempY = y - 1926 + 1;
                    Console.WriteLine("showa {0} {1} {2}", tempY, m, d);
                }
                else
                {
                    int tempY = y - 1989 + 1;
                    Console.WriteLine("heisei {0} {1} {2}", tempY, m, d);
                }
            }
        }
    }
}

Measured memory_bytes: 10048
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF = 1000000000000000;
const int MAX = 300010;
vector<pair<ll,ll>> G[MAX];//（cost、行き先）
ll d[MAX];
priority_queue<P,vector<P>,greater<P>> que;//(距離、位置)
void dijkstra(int s){
	que.push({0,s});
	while(!que.empty()){
		P p = que.top();
		que.pop();
		ll x = p.second;
		if(d[x]!=INF) continue;
		d[x] = p.first;
		for(P e: G[x]){
			que.push({d[x]+e.second,e.first});
		}
	}
}

int main(){
	int i,n,m,s,t;
	cin >> n >> m;
	for(i=0;i<m;i++){
		int a,b; cin >> a >> b; a--; b--;
		G[a].push_back({b + n,1});
		G[a + n].push_back({b + 2*n,0});
		G[a + 2*n].push_back({b,0});
	}
	cin >> s >> t; s--; t--;
	for(i=0;i<3*n;i++){
		d[i] = INF;
	}
	dijkstra(s);
	if(d[t]!=INF){
		cout << d[t] << endl;
	}else{
		cout << -1 << endl;
	}
}
		

Measured memory_bytes: 20340
#include <iostream>
using namespace std;
int main(){
int k,s,c=0;
cin>>k>>s;
            for(int x=0;x<=k;x++){
                    for(int y=0;y<=k;y++){
                       int z=s-(x+y);
                            if((z>=0)  && (z<=k) ) {
                                if(0<=s<=(k*3)){
                                     if((x+y+z)==s){
                                         c++;

                    }
            }
    }
   }
}cout<<c<<"\n";

}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

int n;
P pts[353];

int check(P c){
  int ret = 0;
  REP(i,n){
    if(abs(c-pts[i])<=1.00001)ret++;
  }
  return ret;
}

int main(){
  while(true){
    scanf("%d",&n);
    if(n==0)break;
    REP(i,n){
      double x,y;
      scanf("%lf%lf",&x,&y);
      pts[i] = P(x,y);
    }
    int ans = 1;
    REP(i,n)REP(j,i){
      P a,b;
      a = pts[i];
      b = pts[j];
      double l = abs(b-a);
      if(l>2.0)continue;
      double h = sqrt(1.0-l*l/4.0);
      P c;
      c = a + (b-a)/2.0 + (b-a)*P(0,1)*h/l;
      ans = max(ans,check(c));
      c = a + (b-a)/2.0 + (b-a)*P(0,-1)*h/l;
      ans = max(ans,check(c));
    }
    printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 1248
# https://atcoder.jp/contests/agc036/tasks/agc036_a
# 原点を固定すると、p1×p2=Sが成り立つ。
# 式変形するとS=x1y2-x2y1⇔x1y2-S=x2y1である。ここで、x1y2を仮にint(√S+1)^2としてみると、
# int(√S+1)^2 -S=x2y1 が成り立つx2とy1を見つければ良い。(int(√S+1)^2 -S の約数を見つければ良い)
# int(√S+1)^2-S <= 1+2int(√S)程度であり,これの約数列挙はO(√√S)であるため、S<=10^18という非常な大きな制約でも10^4.5回程度のループで処理が可能
# でもこれってint(√S+1)^2-Sが10^9~2*10^9内の素数だと死ぬよね

# 解説解法
# 原点固定もう一つの点を10^9,1に固定したとする。これを外積の式に代入すると
# S=10^9 y2 - x2となる。ちょっと式変形するとS=10^9 (y2-1) + (10^9-x2)なので、3つ目の点は
# y2-1, 10^9-x2 = S divmod 10^9 である。

ra = range
enu = enumerate
S = int(input())
a, b = divmod(S, 10 ** 9)
if b == 0:
    y2 = a
    x2 = 0
else:
    y2 = a + 1
    x2 = 10 ** 9 - b

print(0, 0, 10 ** 9, 1, x2, y2)


Measured memory_bytes: 2940
#include<stdio.h>

int main(){
  int a[31]={};
  int i,x;

  for(i=0;i<28;i++){
    scanf("%d",&x);
    a[x]++;
  }
  for(i=1;i<31;i++){
    if(!a[i])
      printf("%d\n",i);
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define mo 1000000007
#define ll long long
int power(int x,ll y){
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo; 
	return s;
}
struct Mat{
	int a[2][2];
	Mat(){
		memset(a,0,sizeof(a));
	} 
}a;
Mat operator *(Mat a,Mat b){
	Mat c;
	for (int i=0;i<2;i++)
		for (int j=0;j<2;j++)
			for (int k=0;k<2;k++)
				c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%mo;
	return c;
}
Mat power(Mat a,ll k){
	Mat b;
	b.a[0][0]=b.a[0][1]=1;
	for (;k;k/=2,a=a*a)
		if (k&1) b=b*a;
	return b;
}
int h,w,cnt,cnt2,cnt3,cnt4;
char mp[1005][1005];
ll k;
int main(){
	scanf("%d%d%lld",&h,&w,&k);
	if (k<=1) return puts("1"),0;
	for (int i=1;i<=h;i++){
		scanf("%s",mp[i]+1);
		for (int j=1;j<=w;j++)
			cnt+=(mp[i][j]=='#');
	}
	for (int i=1;i<=h;i++)
		if (mp[i][1]=='#'&&mp[i][w]=='#') cnt3++;
	for (int i=1;i<=w;i++)
		if (mp[1][i]=='#'&&mp[h][i]=='#') cnt4++;
	if (cnt3&&cnt4) return puts("1"),0;
	if (!cnt3&&!cnt4) return printf("%d",power(cnt,k-1)),0;
	if (cnt3){
		for (int i=1;i<=h;i++)
			for (int j=1;j<w;j++)
				if (mp[i][j]=='#'&&mp[i][j+1]=='#')
					cnt2++;
	}
	else{
		cnt3=cnt4;
		for (int i=1;i<h;i++)
			for (int j=1;j<=w;j++)
				if (mp[i][j]=='#'&&mp[i+1][j]=='#')
					cnt2++;
	}
	a.a[0][0]=cnt;
	a.a[1][0]=(mo-cnt2)%mo;
	a.a[1][1]=cnt3;
	a=power(a,k-1);
	printf("%d\n",a.a[0][0]);
} 

Measured memory_bytes: 1280
# AOJ 0059: Intersection of Rectangles
# Python3 2018.6.28 bal4u

def inside(x, y, xl, yd, xr, yu):
	return xl <= x and x <= xr and yd <= y and y <= yu

def judge(xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2):
	if inside(xb1, yb1, xa1, ya1, xa2, ya2): return True
	if inside(xb2, yb1, xa1, ya1, xa2, ya2): return True
	if inside(xb2, yb2, xa1, ya1, xa2, ya2): return True
	if inside(xb1, yb2, xa1, ya1, xa2, ya2): return True

	if inside(xa1, ya1, xb1, yb1, xb2, yb2): return True
	if inside(xa2, ya1, xb1, yb1, xb2, yb2): return True
	if inside(xa2, ya2, xb1, yb1, xb2, yb2): return True
	if inside(xa1, ya2, xb1, yb1, xb2, yb2): return True

	if xb1 <= xa1 and xa1 <= xb2 and xb1 <= xa2 and xa2 <= xb2 and \
	   ya1 <= yb1 and ya2 >= yb2: return True
	if xa1 <= xb1 and xb1 <= xa2 and xa1 <= xb2 and xb2 <= xa2 and \
	   yb1 <= ya1 and yb2 >= ya2: return True
	return False

while True:
	try: xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2 = list(map(float, input().split()))
	except: break

	if xa1 > xa2: xa1, xa2 = xa2, xa1
	if ya1 > ya2: ya1, ya2 = ya2, ya1
	if xb1 > xb2: xb1, xb2 = xb2, xb1
	if yb1 > yb2: yb1, yb2 = yb2, yb1
	print("YES" if judge(xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2) else "NO")




Measured memory_bytes: 5580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD (int) (1e9+7)
#define INF (int) 2e9

int main(){
    ll n;
    cin >> n;    
    cout << n*(n-1)/2 << endl;
    // printf("%d\n", N);
    return 0;
}

Measured memory_bytes: 256
def binary_search(key):
    bad, good = -1, len(ans)
    while good - bad > 1:
        mid = (bad + good) // 2
        if ans[mid][-1] < key:
            good = mid
        else:
            bad = mid
    return good


N = int(input())
ans = []
for _ in range(N):
    A = int(input())
    idx = binary_search(A)
    if idx == len(ans):
        ans.append([A])
    else:
        ans[idx].append(A)
print(len(ans))


Measured memory_bytes: 20660
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

template<class T>
struct Edge {
	int to;
	T cost;
	Edge() {}
	Edge(int to, T cost) : to(to), cost(cost) {}
	bool operator>(const Edge &r) const { return this->cost > r.cost; }
};

template<class T>
vector<T> Dijkstra(const vector<vector<Edge<T>>> &edges, const int st) {

	const int V = (int)edges.size();
	const T inf = numeric_limits<T>::max() / 2;
	vector<T> cost(V, inf);
	cost[st] = 0;

	priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> pq;
	pq.emplace(st, cost[st]);

	while (!pq.empty()) {

		Edge<T> now(pq.top().to, pq.top().cost);
		pq.pop();

		if (cost[now.to] < now.cost) continue;
		for (const Edge<T> &e : edges[now.to]) {
			T tmp_cost = now.cost + e.cost;
			if (cost[e.to] > tmp_cost) {
				cost[e.to] = tmp_cost;
				pq.emplace(e.to, cost[e.to]);
			}
		}
	}

	return cost; // min cost to vertex idx from st
}

template<class T>
inline bool chmax(T &a, const T b) { return a < b && (a = b, true); }

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int t, a;
	cin >> t >> a;
	t--, a--;

	vector<vector<Edge<int>>> edges(N);
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		edges[u].emplace_back(v, 1);
		edges[v].emplace_back(u, 1);
	}

	auto d_t = Dijkstra(edges, t);
	auto d_a = Dijkstra(edges, a);

	int max_d = 0;

	auto dfs = [&](auto &&f, int now, int prev) -> void {
	
		chmax(max_d, d_a[now] - 1);

		for (const auto &e : edges[now]) {
			if (e.to == prev) continue;

			if (d_t[e.to] < d_a[e.to]) f(f, e.to, now);
			else if (d_t[e.to] == d_a[e.to]) chmax(max_d, d_a[e.to]);

		}

	};
	dfs(dfs, t, -1);

	cout << max_d << "\n";

	return 0;
}


Measured memory_bytes: 8320
N=int(input())
a = list(map(int, input().split()))

a.sort()
a.append(0)

T=[]
j=0
t=0
s=0
for i in range(N):
    j+=1
    if a[i] != a[i+1]:
        if j-s > a[i]:
            t+=(j-s)-a[i]
        elif j-s < a[i]:
            t += j-s
        s=j

print(t)


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

using namespace std;
using ii = pair<int, int>;
using iii = pair<ii, int>;

const int MAX { 60 };
const vector<ii> dirs { ii(1, 0), ii(0, 1), ii(-1, 0), ii(0, -1) };

int dist[MAX][MAX];

int solve(const vector<string>& S, int H, int W)
{
    if (S[0][0] == '#' or S[H - 1][W - 1] == '#')
        return -1;

    memset(dist, -1, sizeof dist);
    int whites = 0;

    for (int i = 0; i < H; ++i)
        for (int j = 0; j < W; ++j)
            whites += (S[i][j] == '.' ? 1 : 0);

    queue<iii> q;
    q.push(iii(ii(0, 0), 1));
    dist[0][0] = 1;

    while (not q.empty())
    {
        auto p = q.front();
        q.pop();

        auto x = p.first.first, y = p.first.second;
        auto d = p.second;

        if (x == H - 1 and y == W - 1)
            break;

        for (auto dir : dirs)
        {
            int u = dir.first + x, v = dir.second + y;

            if (u < 0 or u >= H or v < 0 or v >= W or dist[u][v] > -1 or S[u][v] == '#')
                continue;

            dist[u][v] = d + 1;
            q.push(iii(ii(u, v), d + 1));
        }
    }

    /*cout << "brancos = " << whites << endl;
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
            cout << dist[i][j] << "  ";
        cout << endl;
    }
    */

    return dist[H - 1][W - 1] == -1 ? -1 : whites - dist[H - 1][W - 1];
}

int main()
{
    int H, W;
    cin >> H >> W;

    vector<string> S(H);

    for (int i = 0; i < H; ++i)
        cin >> S[i];

    cout << solve(S, H, W) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<functional>
#include<utility>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;
const auto MOD = 1000000007;
const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i,n) for(int i = 0; i < (n);i++)
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VLL;

struct edge {
	int from;
	int to;
	int weight;
};

VI to[2505];
VI ot[2505];
bool ok[2505];
bool rcbFrom1[2505];
bool rcbToN[2505];


void dfs(int v) {
	if (rcbFrom1[v]) return;
	rcbFrom1[v] = true;
	for (int u : to[v]) {
		dfs(u);
	}
}
void ndfs(int v) {
	if (rcbToN[v])return;
	rcbToN[v] = true;
	for (int u:ot[v]) {
		ndfs(u);
	}
}


int main() {
	int n, m, p;
	cin >> n >> m >> p;
	vector<edge> hen(m);
	VI destination(n, -INF);
	destination[0] = 0;
	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		hen[i].from = a-1;hen[i].to =b- 1;hen[i].weight =c- p;
		to[a-1].push_back(b-1);
		ot[b-1].push_back(a-1);
	}
	dfs(0);
	ndfs(n - 1);
	rep(i, n)ok[i] = rcbFrom1[i] & rcbToN[i];
	int cnt = 0;
	bool upd = true;
	while(upd)
	{
		upd = false;
		for (int j = 0; j < m; j++)
		{
			edge tmp = hen[j];
			if (!ok[hen[j].to])continue;
			if (!ok[hen[j].from])continue;
			if (destination[tmp.from] + tmp.weight > destination[tmp.to]) {
				upd = true;
				destination[tmp.to] = destination[tmp.from] + tmp.weight;
			}
		}
		cnt++;
		if (cnt > n) {
			puts("-1");
			return 0;
		}
	}
	cout << max(destination[n-1], 0) << endl;
}


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

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

  bool ans = true;
  rep (i, s.size()) {
    if (i % 2 == 0) {
      if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D') {
        ans = false;
        break;
      }
    } 
    if (i % 2 == 1) {
      if (s[i] != 'L' && s[i] != 'U' && s[i] != 'D') {
        ans = false;
        break;
      }
    } 
  }

  if (ans) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include "cstdio"
#include "iostream"
using namespace std;

#define REP(i,m,n)  for(int i = m; i < n ; i++)



int main()
{


    int a, b, c;
    int ans = 0;

    cin >> a >> b >> c;



    if (a == b)
        ans = c;
    else if (b == c)
        ans = a;
    else
        ans = b;


    cout << ans << endl;


    return 0;
}



Measured memory_bytes: 256
N,M=map(int,input().split())
path=[list(map(int,input().split())) for i in range(M)]
l=[0]*N
#print(path)
for i in range(M):
    l[path[i][0]-1]=l[path[i][0]-1]+1
    l[path[i][1]-1] = l[path[i][1]-1] + 1

for i in range(N):
    print(l[i])

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int N, K; cin >> N >> K;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    auto doit = [&](int mask) {
        Int ans = 0;
        for (int i = 0; i < N; i++) {
            if ((A[i] | mask) == mask) {
                ans += B[i];
            }
        }
        return ans;
    };
    Int ans = doit(K);
    for (int i = 0; i < 30; i++) {
        int mask = K;
        if (K & (1 << i)) {
            mask &= ~(1 << i);
            mask |= (1 << i) - 1;
            ans = max(ans, doit(mask));
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 1024
n = int(input())

h = []
h_li = input().split()

for i in range(n):
    h.append(int(h_li[i]))
    
ans = "Yes"

memo = 0
for i in range(n):
    if memo >= h[i] +2:
        ans = "No"
        break
    
    if memo <= h[i]:
        memo = h[i]
    
print(ans)

Measured memory_bytes: 14252
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		String S = sc.next();
		sc.close();
		System.out.println(S.substring(0,K-1) + String.valueOf(S.charAt(K-1)).toLowerCase()+ S.substring(K));
	}

}


Measured memory_bytes: 39260
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;}
using ll = long long;
using P = pair<int,int>;

ll n,m,k,h,w,a,b,c;
string s,t;

int main() {
  cin >> h >> w;
  if(w==1 || h==1)
  cout << 1 << endl;
  else
  cout << (w*h+1)/2 << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
long a,b,k;
scanf("%ld %ld %ld",&a,&b,&k);
if(a>=k)
printf("%ld %ld",a-k,b);
else if(a+b<=k)
printf("0 0");
else printf("0 %ld",a+b-k);
    printf("\n");
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main()
{
    string S;
    cin >> S;
    int i = S.length();
    while (i > 0) {
        if (i >= 7 && S.substr(i - 7, 7) == "dreamer") i -= 7;
        else if (i >= 6 && S.substr(i - 6, 6) == "eraser") i -= 6;
        else if (i >= 5 && S.substr(i - 5, 5) == "dream") i -= 5;
        else if (i >= 5 && S.substr(i - 5, 5) == "erase") i -= 5;
        else {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 512
#coding;:utf-8

N=input()
s=raw_input()

def f(i):
    return i%len(s)

def ok(buf):
    for i in range(len(buf)):
        if buf[i]:
            if s[i] == "o":
                if buf[f(i-1)] != buf[f(i+1)]: return False
            else:
                if buf[f(i-1)] == buf[f(i+1)]: return False
        else:
            if s[i] == "o":
                if buf[f(i-1)] == buf[f(i+1)]: return False
            else:
                if buf[f(i-1)] != buf[f(i+1)]: return False            
    return True

OK=[]
# True: sheep; False: wolf
for b in range(1<<3):
    buf=[None] * N
    if b&0b001:buf[0]=True
    else:buf[0]=False
    if (b&0b010)>>1:buf[1]=True
    else:buf[1]=False
    if (b&0b100)>>2:buf[-1]=True
    else:buf[-1]=False

    for i in range(2, N-1):
        if s[i-1] == "o":
            if buf[i-1]:
                buf[i]=buf[i-2]
            else:
                buf[i]=not buf[i-2]
        else:
            if buf[i-1]:
                buf[i]=not buf[i-2]
            else:
                buf[i]=buf[i-2]
    if ok(buf):
        OK.append("".join("S" if b else "W" for b in buf))
if len(OK)==0:
    print(-1)
else:
    print(OK[0])




    


Measured memory_bytes: 7636
m, n = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
mod = int(1e+9 + 7)
Sx, Sy = 0, 0
for i in range(1, m):
  Sx += (i * X[i] - (m - i) * X[i - 1]) % mod
  Sx %= mod
for i in range(1, n):
  Sy += (i * Y[i] - (n - i) * Y[i - 1]) % mod
  Sy %= mod
print((Sx * Sy) % mod)

Measured memory_bytes: 18556
//BISMILLAHIR RAHMANIR RAHIM
#include <bits/stdc++.h>
#define mem(a, b) (memset(a, b, sizeof(a)))
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define PI acos(-1)
#define INF 2147483647
#define MOD 1000000007
#define MAX 100005
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
typedef vector<ii> vii;
typedef priority_queue<int,vector<int>,greater<int> > PQ;

int Set(int mask, int pos){return mask = mask | (1<<pos);}
bool check(int mask, int pos){return (bool)(mask & (1<<pos));}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;

    cin>>s;

    int n = s.size();

    for(int i = 0; i < n; i++)
        cout<<"x";
    cout<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

//重みある時
using Edge = pair<int,int>;
using Graph = vector<vector<Edge> >;

vector<bool> beki(1010);

int main() {
    int a,b;
    cin >> a >> b;
    string s;
    cin >> s;
    if(s[a] != '-'){
        cout << "No" << endl;
        return 0;
    }
    for (int i = 0; i < a+b+1; ++i) {
        if(i != a){
            if((s[i]-'0') < 0 || (s[i]-'0') > 9){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.List;
import java.util.Scanner;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<blidge> path = new ArrayList<blidge>();
        for (int i = 0; i < m; i++) {
            int s = sc.nextInt() - 1;
            int g = sc.nextInt() - 1;
            path.add((new blidge(s, g)));
        }
        Collections.sort(path);

        boolean conect[] = new boolean[n - 1];
        int ans = 0;
        Arrays.fill(conect, true);
        int pos = -1;
        for (int i = 0; i < m; i++) {
            int left = path.get(i).s;
            int right = path.get(i).g;
            if (pos < left) {
                pos = right - 1;
                conect[pos] = true;
                ans++;
            }

        }
        System.out.println(ans);

        sc.close();
    }
}

class blidge implements Comparable<blidge> {
    int s, g;

    blidge(int s, int g) {
        this.s = s;
        this.g = g;
    }

    @Override
    public int compareTo(blidge other) {
        if (this.g < other.g) {
            return -1;
        } else if (this.g == other.g) {
            return this.s - other.s;
        } else {
            return 1;
        }
    }
}


Measured memory_bytes: 85164
n = int(input())
a, w, t, r = 0, 0, 0, 0
for i in range(n):
    s = input()
    if s == "AC":
        a += 1
    elif s == "WA":
        w += 1
    elif s == "TLE":
        t += 1
    else:
        r += 1

print(f"AC x {a}")
print(f"WA x {w}")
print(f"TLE x {t}")
print(f"RE x {r}")


Measured memory_bytes: 74868
def main():
    N, X, Y = map(int, input().split())
    ans = {i: 0 for i in range(1, N)}
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            cost = min(j - i, abs(i - X) + 1 + abs(Y - j))
            ans[cost] += 1
    for a in ans:
        print(ans[a])


if __name__ == '__main__':
    main()

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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

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

int main() {
  string s;
  cin >> s;
  string res;
  if (s.back() == 's') {
    res = s + "es";
  } else {
    res = s + "s";
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define r1(i, n) for (int i=0;i<n;i++)
#define r2(i, n) for (int i=1;i<n;i++)
#define intc(n) int n; cin >> n;
#define ll long long
#define llc(n) ll n; cin >> n;
using namespace std;
int main() {
  ll h, w;
  cin >> h >> w;
  if(h==1 || w==1) cout << 1 << endl;
  else cout << (h*w+1)/2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 200000
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000000;
const int MOD = 1000000007;
int main(){
	int k,x;
    cin>>k>>x;
    REP(i,2*k-1){
        OUT(i+x-k+1);
    }
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

using namespace std;

#include<iostream>
#include<fstream>

using namespace std;

int main()
{

  int m, n;
  cin >> m >> n;

  int count = 0;
  int hairetu[n] = {0};

  for (int i = 0; i < n;i++)
  {
    hairetu[i] = i+1;
  }
  for (int i = 0; i < n;i++)
  {
    if(hairetu[i] >= 22)
    {
      int iti = 0;
      int zyuu;

      iti = hairetu[i] % 10;
      zyuu = hairetu[i] / 10;
      if(iti >= 2 && zyuu >= 2)
      {

      	for (int i = 1; i < m + 1;i++)
        {
        	if(i == iti * zyuu)
        	{
          		count++;
        	}
        }
      }
    }
  }

  cout << count << endl;
  return 0;
}



Measured memory_bytes: 256
N=int(input())
h=list(map(int,input().split()))

dp=[-1]*(N+1)
dp[1]=0
dp[2]=abs(h[2-1]-h[1-1])

for i in range(3,N+1):
  dp[i]=min(abs(h[i-1]-h[i-2])+dp[i-1],abs(h[i-1]-h[i-3])+dp[i-2])

print(dp[N])

Measured memory_bytes: 20700
using System;

namespace ALDS1_4_A
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            string[] s = getsplit();
            Console.ReadLine();
            string[] t = getsplit();
            
            int count = 0;

            foreach (string T in t)
            {
                foreach (string S in s)
                {
                    if (S == T)
                    {
                        count++;
                        break;
                    }
                }
            }
        
            Console.WriteLine(count);

        }
        public static int getint(string a)
        {

            if (a == null)
            {
                int x = int.Parse(Console.ReadLine());
                return x;
            }
            else
            {
                int x = int.Parse(a);
                return x;
            }
        }
        public static string[] getsplit()
        {
            string[] x = Console.ReadLine().Split(' ');
            return x;
        }
    }
}

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

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int main(){
  int a,b,c;
  cin >> a >> b>>c;
  cout << max(c-a+b, 0) <<endl;
}

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

using namespace std;

int n;
int ar[100005];
int a, b, c;
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d", ar+i);
    for(int i=1;i<=n;i++){
        if(ar[i]%4==0)a++;
        else if(ar[i]%2==0)b++;
        else c++;
    }
    if(a == c-1 && a+c == n)puts("Yes");
    else if(a<c)puts("No");
    else puts("Yes");
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

#define maxs(x,y) (x=std::max(x,y))
#define mins(x,y) (x=std::min(x,y))

int main() {
  ll N;
  cin >> N;
  ll N_keta {};
  for (ll n = N;n != 0;n/=10) {
    ++N_keta;
  }

  ll answer {};
  if (N_keta % 2 == 1) {
    answer += N - std::pow(10, N_keta-1) + 1;
    --N_keta;
  }
  --N_keta;
  for (ll num = 1;N_keta >= 0;num *= 10) {
    if (N_keta %2==1) {
      answer -= num;
    } else {
      answer += num;
    }
    --N_keta;
  }
  cout << answer << '\n';
}


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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int x;
    cin >> x;

    set<int> se;
    map<int, int> mp;
    For(i, 0, 2000) {
        int val = pow<int>(i, 5);
        se.insert(val);
        mp[val] = i;
    }

    For(i, 0, 2000) {
        int a = pow<int>(i, 5);
        if (x >= a) {
            int b5 = x - a;
            if (se.find(b5) != se.end()) {
                print(i, -mp[b5]);
                return 0;
            }
        } else {
            int b5 = a - x;
            if (se.find(b5) != se.end()) {
                print(i, mp[b5]);
                return 0;
            }
        }
    }

    return 0;
}


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

int main(){
    string s; cin >> s;
    int N = s.size();
    ll dp[1000005][2];
    dp[0][1] = 1;
    REP(i,N) {
        int num = s[i] - '0';
        int num2 = 10 - num;
        dp[i+1][0] = min(dp[i][0] + num, dp[i][1] + num2);
        dp[i+1][1] = min(dp[i][0] + num + 1, dp[i][1] + num2 - 1);
    }
    cout << dp[N][0] << endl;
    return 0;
}

Measured memory_bytes: 17028
prime_table = [True]*(2*(10**5)+1)
prime_table[0], prime_table[1] = False, False
i = 2
while i * i <= 2*(10**5):
  if prime_table[i]:
    j = i*i
    while j <= 2*(10**5):
      prime_table[j] = False
      j += i
  i += 1
x = int(input())
ans = x
while not prime_table[ans]:
  ans += 1
print(ans)


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

int main(){
    int n, m;
    cin>>n >>m;
    vector<vector<int> > a(n, vector<int>(m));
    vector<int> b(m), c(n, 0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    
    for(int i=0;i<m;i++)cin>>b[i];
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            c[i]+=a[i][j]*b[j];
        }
    }
    
    for(int i=0;i<n;i++){
        cout<<c[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3184
x,n = map(int,input().split())
p = list(map(int,input().split()))
if(n == 0):
    print(x)
else:
    t = [0]*102
    q = -1
    for i in range(n):
        t[p[i]] += 1
    if(t[x] == 0):
        q = x
    i = 1
    while(q == -1):
        if(t[x-i] == 0):
            q = x-i
        elif(t[x+i] == 0):
            q = x+i
        i += 1
    print(q)

Measured memory_bytes: 61828
using System;

class Program
{
    static void Main(string[] args)
    {
        var nm = Console.ReadLine().Split(' ');
        var n = int.Parse(nm[0]);
        var m = int.Parse(nm[1]);
        var d = new int[m];
        var s = Console.ReadLine().Split(' ');
        for (int i = 0; i < m; i++)
        {
            d[i] = int.Parse(s[i]);
        }

        Array.Sort(d);

        var e = new int[m - 1];
        for (int i = 1; i < m; i++)
        {
            e[i - 1] = d[i] - d[i - 1];
        }

        Array.Sort(e, (a, b) => b - a);

        var ans = 0;
        for (int i = n - 1; i < m - 1; i++)
        {
            ans += e[i];
        }

        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 17504
#include<bits/stdc++.h>
using namespace std;
inline int gcd(int a,int b) {
	return b==0?a:gcd(b,a%b);
}
int main() {
	int n,x;
	int a[100005];
	cin>>n>>a[1];
	for(int i=2;i<=n+1;i++)
		cin>>a[i];
	++n;
	sort(a+1,a+n+1);
	int res=a[2]-a[1];
	for(int i=3;i<=n;i++)
		res=gcd(res,a[i]-a[i-1]);
	cout<<res<<"\n";
}

Measured memory_bytes: 640