akhauriyash/Code-Regression huggingface dataset:
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

#####################################


#1:25
n = int(input())
ss=[]
ans=0
counta=0
countb=0
countab=0

for i in range(n):
    ss.append(input())
    ca = 'A' == ss[-1][-1]
    cb = 'B' == ss[-1][0]
    for i in range(len(ss[-1])-1):
        if(ss[-1][i]=='A' and ss[-1][i+1]=='B'):
            ans+=1
            #print(ss[-1])
    if(ca and cb):
        countab+=1
    elif(ca):
        counta+=1
    elif(cb):
        countb+=1
if(counta+countb==0):
    print(ans+max(countab-1,0))
elif(counta>=1 and countb>=1):
    print(ans+min(counta,countb)+countab)
else:
    print(ans+countab)
#print(ans,counta,countab,countb)

Measured memory_bytes: 55384
#include <bits/stdc++.h>
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define len(x) (sizeof(x) / sizeof(x[0]))
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define scanln(x) fgets(x, sizeof x, stdin)
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define i_str(x) atoi(x.c_str())
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
using namespace std;
const int MOD = 1000000007; 
typedef long long ll;
typedef string str;
  
int main(){
  str push; cin >> push;
  str ans = "";
  rep(i,push.length()){
    if(push[i] == 'B'){
      if(ans.length() > 0)
        ans.pop_back();
    }else{
      ans.pb(push[i]);
    }
  }
  cout << ans;
}

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

int main() {
  
  string S;
  cin >> S ;
  if (S == "abc" || S == "acb" || S == "bac" || S == "bca" || S == "cab" || S == "cba") {
    cout << "Yes" << endl;    
  }
  else {
    cout << "No" << endl;   
  }
  


return 0;
}

Measured memory_bytes: 3632
module DoublyLinkedList = struct
  type t = {
    mutable data : int;
    mutable next : t;
    mutable prev : t;
  }

  let make () =
    let rec head = { data = 0; next = head; prev = head } in
    head

  let insert data head =
    let x = { data = data; next = head.next; prev = head } in
    head.next.prev <- x;
    head.next <- x

  let delete x =
    x.next.prev <- x.prev;
    x.prev.next <- x.next

  let delete_first head = delete head.next

  let delete_last head = delete head.prev

  let delete_node data head =
    let rec doit ite =
      if ite == head then None
      else if ite.data = data then Some ite
      else doit ite.next
    in
    match doit head.next with
    | None -> ()
    | Some ite -> delete ite

  let iteri head ~f =
    let rec doit i ite =
      if ite == head then ()
      else (f i ite.data; doit (i + 1) ite.next)
    in
    doit 0 head.next
end

module L = DoublyLinkedList

let split str delim =
  let rec doit s acc =
    match
      try Some (String.rindex s delim) with _ -> None
    with
    | None -> s :: acc
    | Some i ->
        let s1 = String.sub s 0 i in
        let s2 = String.sub s (i + 1) (String.length s - String.length s1 - 1) in
        doit s1 (s2 :: acc)
  in
  doit str []

let () =
  let n = read_int () in
  let head = L.make () in
  let rec read i =
    if i >= n then ()
    else begin
      match split (read_line ()) ' ' with
      | ["insert"; n] -> (L.insert (int_of_string n) head; read (i + 1))
      | ["delete"; n] -> (L.delete_node (int_of_string n) head; read (i + 1))
      | ["deleteFirst"] -> (L.delete_first head; read (i + 1))
      | ["deleteLast"] -> (L.delete_last head; read (i + 1))
      | _ -> exit 1
    end
  in
  read 0;
  L.iteri head ~f:(fun i n -> Printf.printf (if i = 0 then "%d" else " %d") n);
  print_newline ()

Measured memory_bytes: 39204
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=100,MAX_X=1e7;
int N;
int sto[2][MAX_N*2],ston[2];
vector<int> G[MAX_N*2];
bool used[MAX_N*2];
int pa[MAX_N*2];
bool isp[MAX_X+1];
bool dfs(int v){
	used[v]=true;
	for(auto e:G[v]){
		if (pa[e]==-1 || (!used[pa[e]] && dfs(pa[e]))){
			pa[v]=e;
			pa[e]=v;
			return true;
		}
	}
	return false;
}
int matching(){
	int ret=0;
	memset(pa,-1,sizeof(pa));
	REP(v,ston[0]){
		fill(used,used+ston[0]+ston[1],false);
		if (pa[v]==-1 && dfs(v)){
			ret++;
		}
	}
	return ret;
}
int main(){
	cin>>N;
	{
		vector<bool> a((int)1e7+2),b((int)1e7+1);
		REP(i,N){
			int x;
			cin>>x;
			a[x]=1;
		}
		REP(i,(int)1e7+1){
			b[i]=a[i]^a[i+1];
		}
		REP(i,(int)1e7+1){
			if (b[i]){
				if (i&1){
					sto[1][ston[1]]=i;
					ston[1]++;
				}else{
					sto[0][ston[0]]=i;
					ston[0]++;
				}
			}
		}
	}
	memset(isp,1,sizeof(isp));
	isp[0]=isp[1]=false;
	FOR(i,2,MAX_X+1){
		if (isp[i]){
			for(int j=i*2;j<=MAX_X;j+=i){
				isp[j]=false;
			}
		}
	}
	REP(i,ston[0]){
		REP(j,ston[1]){
			int n=abs(sto[0][i]-sto[1][j]);
			if (n%2 && isp[n]){
				G[i].push_back(j+ston[0]);
				G[j+ston[0]].push_back(i);
			}
		}
	}
	int mat=matching();
	int ans=mat+(ston[0]-mat)/2*2+(ston[1]-mat)/2*2;
	if ((ston[0]-mat)%2){
		ans+=3;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 10096
#include <cstdio>
#include <array>

using namespace std;

int main()
{
    int N, K;
    scanf("%d %d\n", &N, &K);

    array<bool, 10> is_invalid; is_invalid.fill(false);
    for (int i = 0; i < K; ++i){
        int D;
        scanf("%d", &D);
        is_invalid[D] = true;
    }

    for (int num = N; num < 100000; ++num){
        bool continue_flag = false;
        for (int temp = num; temp > 0; temp /= 10){
            if (is_invalid[temp % 10]){
                continue_flag = true;
                break;
            }
        }
        if (continue_flag) continue;
        printf("%d\n", num);
        break;
    }
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<chrono>
 
using namespace std;
using namespace std::chrono;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define REP(i,a,b) for(i=a;i<=b;i++)
#define RAP(i,a,b) for(i=a;i>=b;i--)
ll mod=1000000007;
const int MX=0x3f3f3f;

int main(){
	IOS;
    ll n,m,i;
    cin>>n>>m;
    ll b[n];
    ll a[n];
    REP(i,0,n-1) {
        cin>>a[i];
        b[i]=a[i];
    }
    ll c=0,temp=0;
    a[0]>>=1;
    while(b[0]%2==0) b[0]>>=1, c++;
    REP(i,1,n-1){
        temp=0;
        a[i]>>=1;
        while(b[i]%2==0) b[i]>>=1,temp++;
        if(temp!=c){
            cout<<0;
            return 0;
        }
    }
    ll res=1,lc=1;
    REP(i,0,n-1){
        lc=res;
        temp=a[i];
        while(a[i]){
            res%=a[i];
            swap(res,a[i]);
        }
        res=(temp/res)*lc;
        if(res>m||res<0){
            cout<<0;
            return 0;
        }
    }
    c=0;
    for(i=0;res*(2*i+1)<=m;i++) c++;
    cout<<c;
	return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>

void swapRange(int* aiData);
void vdSwap(int* iValue1, int* iValue2);

// iInputN個の要素を持つ配列の要素を0以上(e−b)未満のそれぞれのkについて、
// (b+k)にある要素と(t+k)にある要素を入れ替える動作をiInputQ回続ける
// 最後に全要素を出力
int main()
{
	int iInputN;
	int* piData;
	int iInputQ;
	int iCnt;

	scanf("%d", &iInputN);
	piData = (int*)malloc(sizeof(int) * iInputN);
	
	for (iCnt = 0; iCnt < iInputN; iCnt++)
	{
		scanf("%d", &piData[iCnt]);
	}

	scanf("%d", &iInputQ);

	for (iCnt = 0; iCnt < iInputQ; iCnt++)
	{
		swapRange(piData);
	}

	for (iCnt = 0; iCnt < iInputN; iCnt++)
	{
		if (iCnt != iInputN - 1)
		{
			printf("%d ", piData[iCnt]);
		}
		else
		{
			printf("%d\n", piData[iCnt]);
		}
	}

	return 0;
}

// 配列の要素を0以上(e−b)未満のそれぞれのkについて、(b+k)にある要素と(t+k)にある要素を入れ替え
void swapRange(int* aiData)
{
	int iInputB;
	int iInputE;
	int iInputT;
	int iCnt;

	// 読み込み
	scanf("%d %d %d", &iInputB, &iInputE, &iInputT);
	
	// 指定範囲でデータを一つずつ入れ替え
	for (iCnt = 0; iCnt < iInputE - iInputB; iCnt++)
	{
		vdSwap(&aiData[iInputB + iCnt], &aiData[iInputT + iCnt]);
	}

	return;
}

// iValue1, iValue2を入れ替え
void vdSwap(int* iValue1, int* iValue2)
{
	int iValueTmp = *iValue1;
	*iValue1 = *iValue2;
	*iValue2 = iValueTmp;

	return;
}


Measured memory_bytes: 2044
def resolve():
    N = int(input())
    dpt=[0]*(N+1)
    dpt[0]=1
    md = 10**9+7
    for i in range(N+1):
        for j in range(i+3,N+1):
            dpt[j]+=dpt[i]
            dpt[j]%=md
    print(dpt[-1])
resolve()

Measured memory_bytes: 9216
#include<bits/stdc++.h>
#define MAX ((ll)(2e9))
using namespace std;

typedef long long ll;

ll dp[102][(ll)(1e5)+7], c[105], v[105];

ll call(ll n, ll rem)
{
    if(rem<=0) return 0;
    if(n==0){
        return MAX;
    }
    if(dp[n][rem]!=-1) return dp[n][rem];
    dp[n][rem] = MAX;
    dp[n][rem] = min(dp[n][rem],call(n-1,rem));
    dp[n][rem] = min(dp[n][rem],call(n-1,rem-v[n])+c[n]);
    return dp[n][rem];
}

int main()
{
    ll n, w;
    scanf("%lld %lld",&n,&w);
    for(ll i = 1; i<=n; i++) scanf("%lld %lld",&c[i],&v[i]);
    memset(dp,-1,sizeof dp);
    for(ll i = ((ll)(1e5)+2); i>=0; i--){
        if(call(n,i)<=w){
            printf("%lld\n",i);
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 80000
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <functional>
#include <iostream>
using namespace std;
int main()
{	
	long long int n, a[200020], b = 0, c = 0, ans;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (i == 1)b = a[1];
		else c += a[i];
	}
	ans = abs(b - c);
	for (int i = 2; i < n; i++) {
		b += a[i];
		c -= a[i];
		ans = min(ans, abs(b - c));
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long n;
	cin>>n;
	long long a[n+1],l[n+1],r[n+2];
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	l[0]=0;
	r[n+1]=0;
	for(int i=1;i<=n;i++){
		l[i]=__gcd(l[i-1],a[i]);
	}
	for(int i=n;i>=1;i--){
		r[i]=__gcd(r[i+1],a[i]);
	}
	long long ma=-1;
	for(int i=1;i<=n;i++){
		ma=max(ma,__gcd(l[i-1],r[i+1]));
	}
	cout<<ma<<endl;
}

Measured memory_bytes: 2560
//Nice Shopping

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / __gcd(a, b) * b
#define range(a) (a).begin(),(a).end()
const int inf = 2147483647;

int main (){
    int A,B,M;cin >> A >> B >> M;
    vector<int> a(A),b(B);
    rep(i,0,A)cin >> a[i];
    rep(i,0,B)cin >> b[i];
    vector<vector<int>> x(M,vector<int>(3));
    rep(i,0,M)rep(j,0,3)cin >> x[i][j];
    int Ans = *min_element(range(a));
    Ans += *min_element(range(b));
    rep(i,0,M)Ans=min(Ans,a[x[i][0]-1]+b[x[i][1]-1]-x[i][2]);  
    cout << Ans <<endl;
    return 0;
}

Measured memory_bytes: 6528
import java.util.Scanner; 


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int N = sc.nextInt();
        int[] p = new int[N];
        int[] px = new int[101];
        int[] nx = new int[101];
        int[] dpx = new int[N];
        int[] dnx = new int[N];
        int cp = 0;
        int cn = 0;
        for (int i = 0; i < N; i++) {
            p[i] = sc.nextInt();
        }
        for (int i = 0 ; i < 101; i++) {
            px[i] = X + i;
            nx[i] = X - i;
            for (int j = 0; j < N; j++) {
                dpx[j] = px[i] - p[j];
                dnx[j] = nx[i] - p[j];
                if (dpx[j] == 0) {
                    cp = cp;
                } else {
                    cp = cp+1;
                }
                if (dnx[j] == 0) {
                    cn = cn;
                } else {
                    cn =cn + 1;
                }
            }
            if ( cp == N && cn == N) {
                System.out.println(Math.min(px[i],nx[i]));
                break;
            } else if (cp == N && cn != N){
                System.out.println(px[i]);
                break;
            } else if (cn == N && cp != N) {
                System.out.println(nx[i]);
                break;
            } else {
                cp = 0;
                cn = 0;
            }
        }
    }
}

Measured memory_bytes: 35852
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
typedef vector<int> VE;
const ll mod = 10000000007; //10^9+7

int main(){
  string s;
  cin>>s;
  int num[4];
  REP(i,4)num[i]=s[i]-'0';
  int ans[8];
  if(num[0]+num[1]+num[2]+num[3]==7){print(num[0]<<"+"<<num[1]<<"+"<<num[2]<<"+"<<num[3]<<"=7");}
  else if(num[0]+num[1]+num[2]-num[3]==7){print(num[0]<<"+"<<num[1]<<"+"<<num[2]<<"-"<<num[3]<<"=7");}
  else if(num[0]+num[1]-num[2]+num[3]==7){print(num[0]<<"+"<<num[1]<<"-"<<num[2]<<"+"<<num[3]<<"=7");}
  else if(num[0]-num[1]+num[2]+num[3]==7){print(num[0]<<"-"<<num[1]<<"+"<<num[2]<<"+"<<num[3]<<"=7");}
  else if(num[0]-num[1]-num[2]+num[3]==7){print(num[0]<<"-"<<num[1]<<"-"<<num[2]<<"+"<<num[3]<<"=7");}
  else if(num[0]+num[1]-num[2]-num[3]==7){print(num[0]<<"+"<<num[1]<<"-"<<num[2]<<"-"<<num[3]<<"=7");}
  else if(num[0]-num[1]+num[2]-num[3]==7){print(num[0]<<"-"<<num[1]<<"+"<<num[2]<<"-"<<num[3]<<"=7");}
  else if(num[0]-num[1]-num[2]-num[3]==7){print(num[0]<<"-"<<num[1]<<"-"<<num[2]<<"-"<<num[3]<<"=7");}
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def lcm(a, b):
    return a * b // gcd(a, b)

L = 1
for a in A:
    L = lcm(L, a)

L %= MOD
coef = 0
for a in A:
    coef += pow(a, MOD - 2, MOD)
print((L * coef) % MOD)


Measured memory_bytes: 4084
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int main(){
	//freopen("in.txt","r", stdin);
	int n, t;
	while (~scanf("%d%d", &n, &t))
	{
		ll ans = t;
		int x;
		ll pre = t;
		scanf("%d", &x);
		
		for (int i = 1; i < n; i++)
		{
			scanf("%d", &x);
			if (x > pre)
			{
				pre = x + t;
				ans += t;
			}else
			{
				ans -= pre - x;
				ans += t;
				pre = x + t;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
 
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;}
 
const ll INF=1e9+7;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> s(n+1);
    rep(i,n){
        ll x;
        cin >> x;
        a[x-1]++;
    }
    sort(a.begin(),a.end());
    rep(i,n){
        s[i+1]=s[i]+a[i];
    }
    for(ll k=1;k<=n;k++){
        ll le=0,ri=n/k+1;
        while(ri-le>1){
            ll mid=(le+ri)/2;
            auto it=lower_bound(a.begin(),a.end(),mid)-a.begin();
            if(s[it]+(n-it)*mid>=mid*k){
                le=mid;
            }
            else{
                ri=mid;
            }
        }
        cout << le << endl;
    }
    return 0;
}

Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define all(x) x.begin(),x.end()
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
using namespace std;
typedef long long ll;
const int N=1005,M=N*N;
vector<int> g[N];
int n,m,ans[M],vis[N],clk;
int a[M],b[M],tim[N],del;
void dfs(int v){
	vis[v]=clk;
	for (int d:g[v]){
		if((!vis[d])&&d!=del)dfs(d);
	}
}
void gao(int x){
	del=x;
	mem(vis,0);
	clk=0;
	for(int d:g[x]){
		++clk;
		tim[d]=clk;
		if(!vis[d])dfs(d);
	}
	rep(i,1,m)if(a[i]==x&&vis[b[i]]!=tim[b[i]])ans[i]=1;

}
int main(int argc,char*argv[]){
	scanf("%d%d",&n,&m);
	rep(i,1,m){
		scanf("%d%d",a+i,b+i);
		g[a[i]].pb(b[i]);
	}
	rep(x,1,n){
		gao(x);
		reverse(all(g[x]));
		gao(x);
	}
	rep(x,1,n){
		del=0,clk=1;
		mem(vis,0);
		dfs(x);
		rep(i,1,m)if(b[i]==x)ans[i]^=vis[a[i]];
	}
	rep(i,1,m)printf("%s\n",ans[i]?"diff":"same");
	return 0;
}


Measured memory_bytes: 11776
n = gets.chomp.to_i
h = gets.chomp.split(' ').map(&:to_i)
max = -1
result = 0
for i in 0..n-1 do
  if (h[i] >= max)
    max = h[i]
  else
    result += max
    result -= h[i]
    max = h[i]
  end
end
puts result+max

Measured memory_bytes: 1788
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int a,b;
    scanf("%d %d",&a,&b);
    if (a<b) {//if：もし
        printf("a < b");
    }
    if (a>b) {
        printf("a > b");
    }
    if (a==b) {
        printf("a == b");
    }
    printf("\n");

    return 0;
}



Measured memory_bytes: 2100
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <assert.h>

using namespace std;

typedef long long ll;

const int N=1010,P=1e9+7;

struct mat{
  int a[2][2];
  mat(){ a[0][0]=a[1][1]=a[0][1]=a[1][0]=0; }
  int *operator [](int x){
    return a[x];
  }
  friend mat operator *(mat a,mat b){
    mat c;
    c[0][0]=(1LL*a[0][0]*b[0][0]+1LL*a[0][1]*b[1][0])%P;
    c[0][1]=(1LL*a[0][0]*b[0][1]+1LL*a[0][1]*b[1][1])%P;
    c[1][0]=(1LL*a[1][0]*b[0][0]+1LL*a[1][1]*b[1][0])%P;
    c[1][1]=(1LL*a[1][0]*b[0][1]+1LL*a[1][1]*b[1][1])%P;
    return c;
  }
};

mat u;
int n,m;
char a[N][N],b[N][N];
ll k;

inline int judge(){
  for(int i=1;i<=n;i++)
    if(a[i][1]=='#' && a[i][m]=='#') return 1;
  return 0;
}

inline void turn(){
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
      b[m-j+1][i]=a[i][j];
  swap(n,m); memcpy(a,b,sizeof(a));
}

inline int Pow(int x,ll y){
  int ret=1;
  for(;y;y>>=1,x=1LL*x*x%P) if(y&1) ret=1LL*ret*x%P;
  return ret;
}

inline mat Pow(mat x,ll y){
  mat ret=u;
  for(;y;y>>=1,x=x*x) if(y&1) ret=ret*x;
  return ret;
}

int main(){
  u[0][0]=u[1][1]=1;
  scanf("%d%d%lld",&n,&m,&k);
  int cnt=0;
  for(int i=1;i<=n;i++){
    scanf("%s",a[i]+1);
    for(int j=1;j<=m;j++)
      cnt+=a[i][j]=='#';
  }
  int A=judge(),B=(turn(),judge()); turn();
  if((A && B) || !k) return puts("1"),0;
  if(!A && !B) return printf("%d\n",Pow(cnt,k-1)),0;
  if(!A) turn();
  int c=0,b=0; for(int i=1;i<=n;i++) c+=(a[i][1]=='#' && a[i][m]=='#');
  for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++)
      b+=(a[i][j]=='#' && a[i][j+1]=='#');
  mat w,ans; w[0][0]=cnt; w[0][1]=b; w[1][1]=c;
  ans=Pow(w,k-1);
  printf("%d\n",(ans[0][0]+P-ans[0][1])%P);
  return 0;
}


Measured memory_bytes: 2176
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

long long  lcm(long long x,long long y){
  long long mindata,maxdata;
  mindata=min(x,y);
  maxdata=max(x,y);
  while(maxdata%mindata!=0){
    long long temp;
    temp=maxdata%mindata;
    maxdata=mindata;
    mindata=temp;
  }
  return x*y/mindata;
}

int main(){
  int N,M,flag=1;
  cin>>N>>M;
  string S,T;
  cin>>S>>T;
  ll length=lcm(S.size(),T.size());
  ll difS=length/T.size();
  ll difT=length/S.size();
  for(int i=0;difS*i<S.size() || difT*i<T.size();i++){
    if(S[i*difS]!=T[i*difT]){
      flag=0;
      break;
    }
  }
  if(flag) cout<<length<<endl;
  else cout<<-1<<endl;
}


Measured memory_bytes: 512
import java.io.*
import java.util.*
import java.lang.*
import java.lang.Math.*


fun solve() {
    val N = rd.readInt()
    val A = IntArray(N)
    for (i in 0 until N) {
        A[i] = rd.readInt()
    }

    var ok = A[0]==0
    for (i in 1 until N) {
        if (A[i] <= A[i-1]+1 && A[i] <= i) continue
        ok = false
        break
    }
    if (!ok) {
        println(-1)
        return
    }

    var from = IntArray(N){0}
    var idx = 0
    for (i in 1 until N) {
        if (A[i] == A[i-1] + 1) {
            from[i] = idx
        } else if (A[i] == 0) {
            idx = i
            from[i] = idx
        } else {
            idx = i-A[i]
            from[i] = idx
        }
    }

    errPrintln(from.joinToString(" "))

    var cnt = 0L
    var pre = INF
    for (i in N-1 downTo 0) {
        if (from[i] == pre) {
            pre = from[i]
            continue
        }
        cnt += i - from[i]
        pre = from[i]
    }

    val ans = cnt
    println(ans)
}


//val rd = debug.Reader("agc", "024", "c", "sample-3")
val rd = Reader()


fun main(args: Array<String>) {
    try {
        var exception: Throwable? = null
        val sth = Thread(null, SolveThread(), "solveThread", 128 * 1024 * 1024)
        sth.setUncaughtExceptionHandler { _, e -> exception = e }
        sth.start(); sth.join()
        if (exception != null) throw exception!!
    } catch (e: Exception) { throw e }
}
const val MOD = 1_000_000_007L; const val INF = Int.MAX_VALUE/2; const val LINF = Long.MAX_VALUE/2
const val EPS = 1e-9; fun DBLEQ(a: Double, b: Double): Boolean {return abs(a - b) < EPS}
data class IntPair(val first: Int, val second: Int)
data class To(val idx: Int, val cost: Long)
typealias ALI = ArrayList<Int>
fun <T>edge(V: Int): Array<ArrayList<T>> { return Array(V){ArrayList<T>()} }
val errPrintln: (Any) -> Unit = { msg -> System.err.println(msg) }
fun rAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("EAssert Error: $msg"); throw Error(msg) }
}
fun tAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("TAssert Error: $msg"); Thread.sleep(3000) }
}
class SolveThread : Runnable {
    override fun run() { solve() }
}
class Reader {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val readString: () -> String = { br.readLine() }
    val readInt: () -> Int = { br.readLine().toInt() }
    val readLong: () -> Long = { br.readLine().toLong() }
    val readIntArray: () -> IntArray = { br.readLine().split(' ').map { it.toInt() }.toIntArray() }
    val readLongArray: () -> LongArray = { br.readLine().split(' ').map { it.toLong() }.toLongArray() }
    val readListInt: () -> List<Int> = { br.readLine().split(' ').map { it.toInt() } }
    val readListLong: () -> List<Long> = { br.readLine().split(' ').map { it.toLong() } }
}


Measured memory_bytes: 61312
#include "bits/stdc++.h"
using namespace std;
int main() {
	int N, P;
	cin >> N >> P;
	vector<int>A(N);
	bool odd = false;
	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
		if (A.at(i) % 2 != 0) odd = true;
	}
	if (odd) {
		long long ans = pow(2, N - 1);
		cout << ans << endl;
	}
	else {
		long long ans = pow(2, N);
		if (P == 0) cout << ans << endl;
		else cout << 0 << endl;
	}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FASTIO
#define endl "\n"  // Since endl forces a buffer flush which slows down large I/O operations.
#define ff first
#define ss second
#define pb push_back
#define input(c, n) for (int i = 0; i < n; i++) cin >> c[i];
#define exit_message(s) return 0*printf(s)
#define show(c) for (auto i: c) cout << i << " "; cout << "\n";
#define display(c, n) for (int i = 0; i < n; i++) cout << c[i] << " "; cout << "\n";
#define forl(i, a, n) for (int i = a; i < n; i++)
#define dugbe(k) cout << "-\t> " << #k << " = " << k << "\n";

/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/

using namespace std;
typedef long long ll;
typedef pair<int, int> pr;
typedef pair<ll, ll> prll;
typedef vector<int> vi;
typedef vector<ll> vill;
typedef vector<pr> vpr;
ifstream in("input.txt");
const ll mod = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long true_rand(long long n)
{
	// Returns a random number between 0 and n - 1 inclusive using mt19937.
    uniform_int_distribution<long long> uid(0, n - 1);
    return uid(rng);
}

ll mod_pow(ll a, ll b)
{
	if (b == 0)
		return 1LL;

	ll res = mod_pow(a, b>>1);
	res = (res*res)%mod;
	if (b&1LL)
		res = (res*a)%mod;
	
	return res;
}

const int N = 2e5 + 5;

int n;
vi g[N] = {};
int vis[N] = {};

void dfs(int s)
{
	if (!vis[s])
		vis[s] = 1;
	for (auto e: g[s])
	{
		if (!vis[e])
		{
			vis[e] = vis[s] + 1;
			dfs(e);
		}
	}
}

int32_t main()
{
	#ifdef FASTIO
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
	#endif
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	cin >> n;
	forl(i, 0, n - 1)
	{
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(1);
	int mx = 0;
	forl(i, 1, n + 1)
	{
		if (vis[i] > vis[mx])
			mx = i;
	}
	memset(vis, 0, sizeof vis);
	dfs(mx);
	mx = 0;
	forl(i, 1, n + 1)
	{
		if (vis[i] > vis[mx])
			mx = i;
	}
	int diam = vis[mx];
	if (diam % 3 == 2)
		cout << "Second\n";
	else
		cout << "First\n";

	return 0;
}

Measured memory_bytes: 18176
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<30;

int main() {
  int n;
  while(cin >> n,n) {
    int a[10] = {};
    REP(i,n) {
      int b;
      cin >> b;
      a[b]++;
    }
    REP(i,10) {
      if (a[i]) {
        cout << string(a[i],'*') << endl;
      } else
        cout << "-" << endl;
    }
  }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
ll N;
const ll MOD=998244353,MAX_N=1e7;
ll fact[MAX_N+1],ifact[MAX_N+1];
ll cmb(ll n,ll m){
	return fact[n]*ifact[m]%MOD*ifact[n-m]%MOD;
}
ll mpw(ll n,ll m){
	ll r=1;
	while(m){
		if(m&1){
			r*=n;
			r%=MOD;
		}
		n*=n;
		n%=MOD;
		m>>=1;
	}
	return r;
}
ll minv(ll n){
	return mpw(n,MOD-2);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>N;
	fact[0]=1;
	REP(i,N){
		fact[i+1]=fact[i]*(i+1)%MOD;
	}
	ifact[N]=minv(fact[N]);
	for(ll i=N-1;i>=0;i--){
		ifact[i]=ifact[i+1]*(i+1)%MOD;
	}
	ll ans=0,pw2=1;
	for(ll k=N;k>N/2;k--){
		ans+=cmb(N,k)*pw2%MOD;
		pw2*=2;
		pw2%=MOD;
	}
	ans*=2;
	ans%=MOD;
	ans=MOD-ans;
	ans%=MOD;
	ans+=mpw(3,N);
	ans%=MOD;
	cout<<ans<<endl;
}


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

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

// n^m%MOD を求める。O( log(m) )
// mに負の数を指定すると逆元を求める
ll modpow(ll n, int m){
	ll ret=1;
	if( m < 0 ) m = MOD-1 + m;
	for(int i=1; i<=m; i<<=1){
		if( m&i ) ret = ret * n % MOD;
		n = n*n % MOD;
	}
	return ret;
}



vector<pii> edge[30];
set<int> lens;
void dfs(int n, int N, int sum=0){
	if( n == N-1 ){
		lens.insert(sum);
	}else{
		for(auto p: edge[n]) dfs(p.X, N, sum + p.Y);
	}
}

int main(){
	//ios_base::sync_with_stdio(false);
	int N, L, ans=0;

	cin >> L;

	N = 20;
	//rep(i, N) rep(j, N-i-1){
	//	ll k = (j == 0 ? 0 : modpow(2,j-1));
	//	edge[i].emplace_back(N-j-1, k);
	//}
	edge[N-2].emplace_back(N-1, 0);
	edge[N-2].emplace_back(N-1, 1);
	edge[N-2].emplace_back(N-1, 2);
	edge[N-2].emplace_back(N-1, 3);
	rep(i,N-2) if(i){
		ll k = modpow(2, N-i-1);
		edge[i].emplace_back(i+1, 0);
		edge[i].emplace_back(i+1, k);
	}

	ll s = 0;
	for(int j = 20; j >= 0; j--) if( (1<<j) & L ){
		if( j == 0 ){
			edge[0].emplace_back(N-1, s + 0);
		}else if( j == 1 ){
			edge[0].emplace_back(N-1, s + 0);
			edge[0].emplace_back(N-1, s + 1);
		}else{
			edge[0].emplace_back(N-j, s);
		}
		s += modpow(2, j);
	}

	ll M = 0;
	rep(i,N) M += edge[i].size();

	cout << N << " " << M << endl;
	rep(i,N) for(auto p: edge[i]){
		cout << i+1 << " " << p.X+1 << " " << p.Y << endl;
	}

	// test
	if(false){
		dfs(0, N);
		if( lens.empty() ){
			cout << "error!" << endl;
			return 0;
		}
		bool check = true;
		check &= (lens.size() == L);
		check &= (*lens.begin() == 0);
		check &= (*lens.rbegin() == L-1);
		cout << "len=" << lens.size() << " ";
		cout << "min=" << *lens.begin() << " ";
		cout << "max=" << *lens.rbegin() << " ";
		cout << (check ? "OK" : "NG");
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
 
int main() {
  int n;
  std::cin >> n;
  
  bool f;
  if (n % 10 == 7) {
    f = true;
  } else if ((n/10) % 10 == 7) {
    f = true;
  } else if ((n/100) == 7) {
    f = true;
  } else {
    f = false;
  }
  
  if (f) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 3624
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>

#define X first
#define Y second
#define PB push_back

using namespace std;

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

int x, y;

int main(){
	scanf("%d%d", &x, &y);
	printf("%d\n", (max(0, 4 - x) + max(0, 4 - y)) * (int)1e5 + (x + y == 2) * (int)4e5);
	return 0;
}


Measured memory_bytes: 128
k=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(k[int(input())-1])

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

int main() {
 int a,b;
 cin >> a >> b;
 
 int x = 0;
 
 for(int i = 1; i < 1009; i++) {
 if(i * 8/100  == a && i * 10/100 == b) {
  x = i;
  break;
  }
   }
   
   if(x != 0) {
    cout << x;
    }
    else {
     cout << -1;
     }
  
  
}

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

int main() {
    int a, b;
    cin >> a >> b;
    int ans;
    ans = max(max(a+b,a-b),a*b);
    cout << ans << endl;

    return 0;
}

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

using namespace std;

const int MaxN = 1e5 + 15;
const int MOD = 1e9 + 7;
const long long INF = 1e18;



int main()
{
//    freopen("output.txt", "r", stdin);

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    long long a, b, c, k;

    cin >> a >> b >> c >> k;

    if(k % 2)
        cout << b - a << '\n';
    else
        cout << a - b << '\n';

    return 0;

    for(int t1 = 0; t1 < k; ++t1)
    {
        long long ab = a + b;
        long long ac = a + c;
        long long bc = b + c;

        a = bc;
        b = ac;
        c = ab;

        cout << a - b << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

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

  string s;
  cin >> s;

  vector<int> E(N + 1, 0);
  vector<int> W(N + 1, 0);

  REP(i,N){
    if(s[i]=='E'){
      E[i + 1] = E[i] + 1;
      W[i + 1] = W[i];
    }else{
      E[i + 1] = E[i];
      W[i + 1] = W[i] + 1;
    }
  }

  int min = 1145141919;

  REP(i,N){
    int sum = W[i] + E[N] - E[i + 1];
    if(min>sum){
      min = sum;
    }
  }

  cout << min << endl;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

int main()
{
	string s;
	bool flag=true;
	cin>>s;
	for(int i=0;i<s.length();i++)
	{
		if(i%2==0&&s[i]=='L')flag=false;
		else if(i%2&&s[i]=='R')flag=false;
	}
	if(flag)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

int main() {
    int n, m; cin >> n >> m;
    vector<int> e[3*n];
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        e[u].emplace_back(v+n);
        e[u+n].emplace_back(v+n*2);
        e[u+n*2].emplace_back(v);
    }
    int s, t; cin >> s >> t; s--; t--;
    vector<int> d(3*n, 1e9);
    d[s] = 0;
    queue<int> q; q.push(s);
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        for (auto &to: e[curr]) {
            if (d[to] > d[curr] + 1) {
                d[to] = d[curr] + 1;
                q.push(to);
            }
        }
    }
    if (d[t] != 1e9) cout << d[t] / 3 << endl;
    else cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 17792
import java.util.Scanner;

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

        if (n == 100) {
            n++;
        }
        
        int ans;
        if (d == 0) {
            ans = n;
        } else if (d == 1) {
            ans = 100 * n;
        } else {
            ans = 10000 * n;
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
 
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000000000
#define MAXN        100000
#define mod         998244353  
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if(s[0]=='7' || s[1]=='7' || s[2]=='7'){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
}

Measured memory_bytes: 3636
/*
    Author: aksayushx
*/

#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mod 998244353
using namespace std;
typedef long long ll;
typedef long double ld;

bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second); 
}
ll power(ll x, ll y)  
{  
    ll res = 1; 
    x = x % mod;
    if (x == 0) return 0;
    while (y > 0)  
    {  
        if (y & 1)  
            res = (res*x)%mod;  
        y = y>>1; 
        x = (x*x)%mod;  
    }  
    return res;  
} 

string s,t;
vector<vector<ll>> dp;

void aksayushx()
{
    cin>>s;
    cin>>t;
    int n=s.length();
    int m=t.length();
    dp.assign(n+1,vector<ll>(m+1,-1));
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0 || j==0)
            dp[i][j]=0;
            else if(s[i-1]==t[j-1])
            dp[i][j]=1+dp[i-1][j-1];
            else
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    vector<char> final(dp[n][m],'0');
    int i=n,j=m;
    int ind=dp[n][m]-1;
    while(i>0 && j>0)
    {
        if(s[i-1]==t[j-1])
        {
            //cout<<s[i]<<' ';
            final[ind]=s[i-1];
            i--;
            j--;
            ind--;
        }
        else if(dp[i-1][j]>dp[i][j-1])
        i--;
        else
        j--;
    }
    for(int i=0;i<dp[n][m];i++)
    cout<<final[i];
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test=1;
    //cin>>test;
    while(test--)
        aksayushx();
    return 0;
}


Measured memory_bytes: 73692
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const Arr = (input.trim()).split("\n");
const N1 = Number(Arr[0]);
const arr1 = Arr[1].split(" ").map(Number);
const arr2 = Arr[3].split(" ").map(Number);

const binarySearch = (function(arr, N) {
  return (key) => {   
    let mid;
    let left = 0;
    let right = N;
    if (key < arr[0] || arr[N-1] < key) return 0;
    while (left < right) {
      mid = Math.floor((left + right) / 2);
      if (key < arr[mid]) right = mid;
      else if (key > arr[mid]) left = mid + 1;
      else return 1;
    }
    return 0;
  }
})(arr1, N1);

const summing = (a, b) => a + b;
console.log(arr2.map(binarySearch).reduce((a, b) => a + b, 0));



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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N, M;
    cin >> N >> M;
    string S;
    cin >> S;
    vector<ll> ans;
    ll now = N;
    while (now != 0) {
        ll t = -1;
        rrep(i, now - 1, max(0LL,now - M)) {
            if (S[i] == '0') {
                t = i;
            }
        }
        if (t == -1) {
            cout << -1 << '\n';
            return;
        } else {
            ans.push_back(now - t);
            now = t;
        }
    }
    reverse(ans.begin(), ans.end());
    rep(i, ans.size()) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

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


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

int main(){
  int h1, m1, h2, m2, k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  int wake = h1 * 60 + m1;
  int sleep = h2 * 60 + m2;
  cout << sleep-wake-k;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int Ccount = 0;
  int komoji = 0;
  bool ok = false;
  if(s.at(0)=='A'){
    for(int i=2;i<s.size()-1;i++){
      if(s.at(i)=='C'){
        Ccount++;
      }
    }
    if(Ccount==1){
      for(int i=0;i<s.size();i++){
        if(islower(s.at(i))!=0){
          komoji++;
        }
      }
      if(komoji==s.size()-2){
        ok = true;
      }
    }
  }
  if(ok){
    cout<<"AC"<<endl;
  }
  else{
    cout<<"WA"<<endl;
  }
  return 0;
}
        

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

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int X; 
  cin >> X;

  int now = 100;
  int ans = 0;
  while(1){
    now = 1.01*now;
    ans++;
    if(now >= X) {
      cout << ans << "\n";
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 3640
'use strict'
function Main(input) {
    let Nums = input.trim().split(' ').map(x => x*1);
  	// 2数の最大公約数gcdを求める式
  	let gcd = (a1,a2) => {
    	return a2 == 0 ? a1 : gcd(a2 , a1 % a2);
    }
    
    // 最大公約数を求める
  	let targetNum = gcd( Nums[0] , Nums[1]);
  
  	let answer = 1;
  
  	// 最大公約数を素因数分解
    for(let i = 2; i <=  Math.sqrt(targetNum); i++) {
        if(targetNum % i === 0) {
            answer++;
          	// 素因数が2乗以上の時を考慮した処理
          	while(targetNum % i === 0){
            	targetNum /= i;
            }
        }
    }
  	  
	if(targetNum !== 1){
    	answer++;
    }
      
  	// 回答の出力
   	console.log(answer);
}


Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  
  if ((a+b) > (c+d)){
    cout << "Left" << endl;
  }
  else if ((a+b) == (c+d)){
    cout << "Balanced" << endl;
  }
  else{
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for (int i = a; i < b; i++)

using ld = long double;
const int mod = 1e9+7;

int main() {
int N; cin>>N;
ld ans = 0;
f(i,0,N) {
int a; cin>>a;
ans += ld(1)/a;
}
cout << setprecision(20) << 1/ans << endl;
return 0;
}

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

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

Measured memory_bytes: 3624
# 木の高さをソート, それぞれの差をリストに格納する, 小さい方から数えてK番目の値が可能な最小値

N, K = map(int, input().split())

h = sorted([int(input()) for _ in range(N)])

# print('h =', h)
dif_h = []

K = K -1

for i in range(K, N):
    dif_h.append(h[i]-h[i-K])

ascending_dif_h = dif_h.sort()
# print('as_dif_h =', dif_h)

print(dif_h[0])


Measured memory_bytes: 11256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int x[n + 1];
    for(int i = 0; i < n; i++) cin >> x[i];
    int ans = INF;
    for(int y = -100; y <= 100; y++)
    {
        int cost = 0;
        for(int i = 0; i < n; i++)
        {
            cost += (x[i] - y) * (x[i] - y);
        }
        ans = min(cost, ans);
    }
    cout << ans << endl;
    return 0;
}



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

static const int MAX = 100;
static const ll INF = 10000000;
ll d[MAX][MAX];
int N, M;

struct  Data {
  int u, v;
  ll c;
  Data() {}
  Data(int u, int v, ll c) : u(u), v(v), c(c){}
};

void warshall_floyd() {
  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      if (d[i][k] == INF) continue;
      for (int j = 0; j < N; j++) {
        if (d[k][j] == INF) continue;
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if(i == j) d[i][j] = 0;
      else d[i][j] = INF;
    }
  }

  Data data[M];
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    data[i] = Data(a, b, c);
    d[a][b] = c;
    d[b][a] = c;
  }
  int cnt = 0;
  warshall_floyd();

  for (int i = 0; i < M; i++) {
    int a = data[i].u;
    int b = data[i].v;
    bool flag = true;
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        ll d1 = d[j][a] + data[i].c + d[b][k];
        ll d2 = d[j][k];
        if(d1 == d2) {
          flag = false;
          goto loop;
        }
      }
    }
    loop:
    if(flag) cnt++;
  }
  cout << cnt << "\n";
  return 0;
}

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

using namespace std;

int main(){
    string s;
    int64_t k,i;
    cin >> s >>k;

    for(i=0;s[i]=='1';i++){
        if(i==k-1){
            cout << '1' <<endl;
            return 0;
        }
    }

    cout << s[i]<<endl;


}

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

using namespace std;
using namespace boost::multiprecision;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPI(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define ALL(x) (x).begin(),(x).end()

int main () {
  int a,b;

  cin >> a >> b;

  int count;
  int acc = 1;

  for(count = 0; acc < b; count++) {
    acc += (a - 1);
  }

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


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

int main(){
	long N;
	long long C;
	cin >> N >> C;
	
	long long x0 = 0;
	long long x[N+2];
	long long upcum[N+2];
	long long dncum[N+2];
	long long upx[N+2];
	long long dnx[N+2];
	long v[N+2];
	
	for(int i=1; i<=N; ++i){
		cin >> x[i] >> v[i];
	}
	
	x[0] = 0;
	x[N+1] = C;
	v[0] = 0;
	v[N+1] = 0;
	upcum[0] = 0;
	dncum[N+1] = 0;
	upx[0] = 0;
	dnx[N+1] = 0;
	
	long long vi = 0;
	for(long i=1;i<=N;++i){
		vi += v[i];
		long cum = vi-x[i];
		if(cum>upcum[i-1]){
			upcum[i] = cum;
			upx[i] = x[i];
		}else{
			upcum[i] = upcum[i-1];
			upx[i] = x[i-1];
		}
	}
	vi = 0;
	for(long i=N;i>=1;--i){
		vi += v[i];
		long cum = vi-C+x[i];
		if(cum>dncum[i+1]){
			dncum[i] = cum;
			dnx[i] = C-x[i];
		}else{
			dncum[i] = dncum[i+1];
			dnx[i] = C-x[i+1];
		}
	}
	
	long long result = 0;
	for(long i=0;i<=N;++i){
		result = max(upcum[i]+dncum[i+1]-min(upx[i],dnx[i+1]),result);
	}
	
	cout << result << endl;
	return 0;
}

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

bool isPrime(long long n);

int main(){
    long long count2 = 0, N;
    cin >> N;
    vector<long long> a(N);
    for(int i=0; i<N; i++){
        cin >> a.at(i);
    }

    bool count;
    for(int i=0; i<N; i++){
        count = isPrime(a.at(i));
        if(count){
            count2++;
        }
    }
    cout << count2 << '\n';
    return 0;
}

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


Measured memory_bytes: 3164