akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdint>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int abs( int a ) { return a < 0 ? -a : a; }

int main() {
	uint64_t r, d, x;
	cin >> r >> d >> x;
	for ( int i = 0; i < 10; i++ ) {
		x = r * x - d;
		cout << x << endl;
	}
	return 0;
}

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

int main(){
  int n, a[10000], ans = 0;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  for(int i = 0; i < n; i++){
    while (!(a[i] % 2)) {
      a[i] /= 2;
      ans++;
    }
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a<b?b:a)
#define abs(x) (x<0?(-x):x)
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define RF(i,L,R) for (int i = L; i > R; i--)
#define RFE(i,L,R) for (int i = L; i >= R; i--)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define ll long long
#define INF 2000000000
#define nINF -2000000000
#define MOD 1e9+7
#define PI 3.1415926535897932384626
int main(){
	int n;
	while(~getI(n)){
		int arr[n],maxV=0,ans=0;
		F(i,0,n) getI(arr[i]);
		F(i,0,n) if(arr[i]>maxV) maxV=arr[i];
		F(i,0,n) if(arr[i]==maxV){
			arr[i]/=2;
			break;
		}
		F(i,0,n) ans+=arr[i];
		printf("%d\n",ans);
	}
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#pragma warning(disable:4996)
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
vector<int> g[N];
long long visited[N], dp[N][3];

enum {WHITE, BLACK};

void add(int& a, int b) {
	a += b;
	if (a >= mod)
		a -= mod;
}

void go(int u, int par) {
	dp[u][0] = 1;
	dp[u][1] = 1;
	for (auto v : g[u]) {
		if (v == par)continue;
		go(v, u);
		dp[u][1] = dp[u][1] * dp[v][0] % mod;
		dp[u][0] = (dp[u][0] * ((dp[v][0] + dp[v][1]) % mod)) % mod;
	}
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	go(1, -1);
	cout << (dp[1][0] + dp[1][1]) % mod;
}


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

int main()
{
    int h, w;
    cin >> h >> w;
    char c[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> c[i][j];
        }
    }
    for(int k=0;k<h;k++){
        for(int l=0;l<w;l++){
            cout << c[k][l];
        }
        cout << endl;
        for(int m=0;m<w;m++){
            cout << c[k][m];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fo(i,n) for(int i=0;i<(n);i++)
#define inp(a) int a;cin>>a;
#define inpa(a,n)vector<int> a(n);fo(i,n)cin>>a[i];
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
#define int ll
// #define MAX 20
#define INF (int)1e18

template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.F<<','<< P.S<<')';}

int modpow(int a,int n,int m=mod)
{
	int ans=1;
	while(n)
	{
		if(n%2)
			ans=((long long)ans*a)%m;
		a=((long long)a*a)%m;
		n/=2;
	}
	return ans;
}

vector<int> ct(2019);
string s;

void f(int ind,int rem)
{
	if(ind==-1)
		return;
	rem=(modpow(10,(int)s.size()-ind,2019)*(s[ind]-'0'))+rem;
	rem%=2019;
	ct[rem]++;
	
	// cerr<<ind<<','<<rem<<'\n';
	
	f(ind-1,rem);
}

signed main()
{
	fio
	cin>>s;
	ct[0]=1;
	f(s.size()-1,0);
	int ans=0;
	fo(i,2019)
	{
		ans+=(ct[i]*(ct[i]-1))/2;
	}
	cout<<ans<<'\n';
	printclock;
}

Measured memory_bytes: 3940
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

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

int main(){
    string s;
    cin >> s;
    if (s[0] == 'S') cout << "Cloudy" << endl;
    else if (s[0] == 'C') cout << "Rainy " << endl;
    else if (s[0] == 'R') cout << "Sunny" << endl;
}

Measured memory_bytes: 256
N = int(input())
flag = 0
for h in range(1,3501):
    for w in range(1,3501):
        if 4*h*w-N*w-N*h>0 and (N*h*w)%(4*h*w-N*w-N*h)==0:
            x = h
            y = w
            z = (N*h*w)//(4*h*w-N*w-N*h)
            flag = 1
            break
    if flag==1:break
print(x,y,z)

Measured memory_bytes: 66404
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

s = ns()
alfa = [chr(i) for i in range(97,123)]
ans = [chr(i) for i in range(97,123)]
for i in s:
    if i in alfa:
        if i in ans:
            ans.remove(i)

if len(ans) == 0:
    print("None")
else:
    print(ans[0])


Measured memory_bytes: 3188
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ENDL '\n'
#define print(i) std::cout << (i) << '\n'

#define int long long // at least int64 > 9*10^18
#define all(v) (v).begin(), (v).end()
/* libraries */

// ceil of a/b
inline int ceil(int a, int b) { return (a%b?a/b+1:a/b); }


signed main() {
	int h,w,k;
	std::cin >> h >> w >> k;
	std::vector<std::string> g(h);
	rep(i,h) std::cin >> g[i];
	std::pair<int,int> spos;
	rep(i,h) rep(j,w) if(g[i][j]=='S') spos = {i,j};

	int min = h;

	// bfs
	std::vector<std::vector<int> > went(h,std::vector<int> (w,false));
	std::queue<std::pair<std::pair<int,int>,int> > que;
	que.emplace(spos, 0);
	while(!que.empty()) {
		auto c = que.front(); que.pop();
		int x = c.first.first; int y = c.first.second;
		int d = c.second;
		went[x][y] = true;
		if(d<=k) min = std::min({min,x,y,h-x-1,w-y-1});
		for(int dx = -1; dx<=1;dx++) {
			for(int dy = -1; dy<=1;dy++) {
				if(dx*dy==0 && x+dx>=0 && x+dx<h && y+dy>=0 && y+dy<w && went[x+dx][y+dy]==0 && g[x+dx][y+dy]=='.') {
					went[x+dx][y+dy] = true;
					que.emplace(std::make_pair(x+dx,y+dy),d+1);
				}
			}
		}
	}
	print(ceil(min,k)+1);

	return 0;
}


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

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int x=s.nextInt();
		while(x-->0){
			double[][] n = new double[4][3];
			for(int i=0;i<3;i++){
				for(int j=0;j<2;j++){n[i][j]=s.nextDouble();}
				n[i][2]=-(n[i][0]*n[i][0]+n[i][1]*n[i][1]);
			}
			for(int i=0;i<2;i++)for(int j=0;j<3;j++)n[i][j]-=n[2][j];
			n[3][0]=(n[0][2]*n[1][1]-n[0][1]*n[1][2])/(((n[0][0]*n[1][1]-n[0][1]*n[1][0])==0)?(1):(n[0][0]*n[1][1]-n[0][1]*n[1][0]));
			n[3][1]=(n[0][2]*n[1][0]-n[0][0]*n[1][2])/(((n[0][1]*n[1][0]-n[0][0]*n[1][1])==0)?(1):(n[0][1]*n[1][0]-n[0][0]*n[1][1]));
			n[3][2]=n[2][2]-n[3][0]*n[2][0]-n[3][1]*n[2][1];
			n[3][0]/=(-2);n[3][1]/=(-2);
			n[3][2]=Math.sqrt(n[3][0]*n[3][0]+n[3][1]*n[3][1]-n[3][2]);
			System.out.printf("%.3f %.3f %.3f\n",n[3][0],n[3][1],n[3][2]);
		}
	}
}

Measured memory_bytes: 11000
#include <cstdio>
#include <vector>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 5005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int N, Num, A[MN], Fac[MN];
std::vector<int> G[MN];
int M, B[MN];

int vis[MN];
void DFS(int u) {
	++B[M], vis[u] = 1;
	for (int v : G[u]) DFS(v);
}
void DFS2(int u, int o) {
	vis[u] = 1;
	for (int v : G[u])
		if (!vis[v]) DFS2(v, o);
		else if (v == o) ++Num;
}

int dp[MN][MN];

int main() {
	scanf("%d", &N), Fac[0] = 1;
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), Fac[i] = (LL)Fac[i - 1] * i % Mod;
	for (int i = 1; i <= N; ++i) if (~A[i]) G[A[i]].push_back(i);
	for (int i = 1; i <= N; ++i) if (!~A[i]) ++M, DFS(i);
	for (int i = 1; i <= N; ++i) if (!vis[i]) DFS2(i, i);
//	printf("Num = %d\n", Num);
//	for (int i = 1; i <= M; ++i) printf("%d, ", B[i]); puts("");
	dp[0][0] = 1;
	for (int i = 1; i <= M; ++i) {
		dp[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			dp[i][j] = (dp[i - 1][j] + (LL)dp[i - 1][j - 1] * B[i]) % Mod;
	}
//	for (int j = 1; j <= M; ++j) printf("%d, ", dp[M][j]); puts("");
	dp[M][1] -= M;
	int Ans = (LL)Num * qPow(N - 1, M) % Mod;
	for (int j = 1; j <= M; ++j) Ans = (Ans + (LL)dp[M][j] * Fac[j - 1] % Mod * qPow(N - 1, M - j)) % Mod;
	Ans = ((LL)N * qPow(N - 1, M) % Mod - Ans + Mod) % Mod;
	printf("%d\n", Ans);
	return 0;
}

Measured memory_bytes: 70156
data = list(map(int, input().split()))
order = list(input())

up = 1
front = 2
right = 3

move = "NSEW"

for m in order:
    i = move.index(m)
    if i == 0:
        up, front = front, 7 - up
    elif i == 1:
        up, front = 7 - front, up
    elif i == 2:
        up, right = 7 - right, up
    else:
        up, right = right, 7 - up

print(data[up - 1])

Measured memory_bytes: 7740
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
using ll = long long;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N;
    cin>>N;
    vector<int> A(N),B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    
    ll cnt = 0, sum = 0;
    vector<int> C;
    REP(i,N){
        if(A[i] < B[i]) {
            ++cnt; sum += (B[i] - A[i]);
        } else {
            C.push_back(A[i] - B[i]);
        }
    }
    sort(C.rbegin(),C.rend());
    REP(i,C.size()){
        if(sum <= 0) break;
        sum -= C[i];
        ++cnt;
    }
    if(sum > 0) cout << -1;
    else cout << cnt;
    cout << endl;
    return 0;
}

Measured memory_bytes: 1660
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cmath>
#include <map>
#define ull unsigned long long
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    int cmp1=c*2*max(x,y);
    int cmp2;
    int cmp3=a*x+b*y;
    if(x>y){
        cmp2=c*2*min(x,y)+a*abs(x-y);
    }
    else{
        cmp2=c*2*min(x,y)+b*abs(x-y);
    }
    cout << min(min(cmp1,cmp2),min(cmp2,cmp3)) << endl;


    return 0;
}

Measured memory_bytes: 256
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
  int i,j,k,l;
  int n,s,t;
  while(cin>>n>>s>>t,n||s||t){
    s=s/100*60+s%100;
    t=t/100*60+t%100;
    vector<pair<int,int> > a;
    a.push_back(make_pair(0,2400));
    for(i=0;i<n;i++){
      int m;
      cin>>m;
      vector<pair<int,int> > b;
      for(j=0;j<m;j++){
	int p,q;
	cin>>p>>q;
	p=p/100*60+p%100;
	q=q/100*60+q%100;
	b.push_back(make_pair(p,q));
      }
      vector<pair<int,int> > c;
      for(k=0;k<(int)a.size();k++){
	for(l=0;l<(int)b.size();l++){
	  if(0){
	  }else if(a[k].second<=b[l].first){
	  }else if(a[k].first>=b[l].second){
	  }else if(b[l].first<=a[k].first&&a[k].second<=b[l].second){
	    c.push_back(a[k]);
	  }else if(a[k].first<=b[l].first&&b[l].second<=a[k].second){
	    c.push_back(b[l]);
	  }else if(a[k].first<b[l].first){
	    c.push_back(make_pair(b[l].first,a[k].second));
	  }else if(a[k].first>b[l].first){
	    c.push_back(make_pair(a[k].first,b[l].second));
	  }
	}
      }
      a=c;
    }
    a.push_back(make_pair(0,s));
    a.push_back(make_pair(t,2400));
    sort(a.begin(),a.end());
    for(i=1;i<(int)a.size();i++){
      if(a[i-1].second>=a[i].first){
	a[i-1].second=max(a[i-1].second,a[i].second);
	a.erase(a.begin()+i);
	i--;
      }
    }
    int mx=0;
    for(i=1;i<(int)a.size();i++)
      mx=max(mx,a[i].first-a[i-1].second);
    cout<<mx<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <stdio.h>
using namespace std;

void bubble_sort(int a[], int n)
{
	bool flag=1;
	int temp;
	int change_count=0;

	while(flag){	//if??????????????????????????°???????????¶????????????????????±????????????
		flag=0;
		for (int j = n-1; j > 0; j--)
		{
			if (a[j]<a[j-1])
			{
				change_count++;
				temp=a[j];	a[j]=a[j-1];	a[j-1]=temp;
				flag=1;
			}
		}
	}

	//??????
	for (int i = 0; i < n; i++)	//???????????????????????¢????????????????????????????????????
	{
		if (i==n-1)
		{
			cout << a[i] << endl;
		}
		else
		{
			cout << a[i] << " ";
		}
	}
	cout << change_count << endl;
}

int main(int argc, char const *argv[])
{
	int n;

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

	bubble_sort(a,n);
	
	return 0;
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define MOD 1000000007
#define RMAX 100005

using namespace std;

typedef long long ll;

bool judgePrime(int n)
{
    if (n == 1) return false;

    int sqN = (int)sqrt(n);
    int res = true;
    for (int i = 2; i <= sqN; ++i)
    {
        if (n % i == 0)
        {
            res = false;
            break;
        }
    }

    return res;
}

int main()
{
    int Q;
    cin >> Q;
    int l[Q], r[Q];
    REP(i, Q)
    {
        cin >> l[i] >> r[i];
    }
    bool isPrime[RMAX];
    REP(i, RMAX)
    {
        isPrime[i] = judgePrime(i);
    }

    map<int, bool> isTSMap;
    map<int, int> sumTSMap;
    for (int i = 1; i <= RMAX; i += 2)
    {
        int j = (i + 1) / 2;
        if (isPrime[i] && isPrime[j])
        {
            isTSMap[i] = true;
        }
        else
        {
            isTSMap[i] = false;
        }

        if (i == 1)
        {
            sumTSMap[i] = 0;
        }
        else
        {
            if (isTSMap[i])
            {
                sumTSMap[i] = sumTSMap[i-2] + 1;
            }
            else
            {
                sumTSMap[i] = sumTSMap[i-2];
            }
            
        }
    }

    REP(i, Q)
    {
        int ans;
        if (isTSMap[l[i]])
        {
            ans = sumTSMap[r[i]] - sumTSMap[l[i]] + 1;
        }
        else
        {
            ans = sumTSMap[r[i]] - sumTSMap[l[i]];
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 6144
def fib(n):
    F = {0:1, 1:1}
    def fibonacci(n):
        ans = F.get(n,-1)
        if ans > 0: return ans
        F[n] = fibonacci(n-1) + fibonacci(n-2)
        return F[n]
    return fibonacci(n)
        
if __name__=='__main__':
    print(fib(int(input())))

Measured memory_bytes: 7720
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var sc *bufio.Scanner

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func ufRoot(e []int, x int) int {
	i := x
	for {
		if e[i] == i {
			e[x] = i
			return i
		}
		i = e[i]
	}
}

func ufUnite(e []int, x int, y int) {
	rx := ufRoot(e, x)
	ry := ufRoot(e, y)
	if rx != ry {
		e[rx] = ry
		e[x] = ry
	}
}

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	n := nextInt()
	m := nextInt()
	t := make([]int, n)
	for i := 0; i < n; i++ {
		t[i] = i
	}

	for i := 0; i < m; i++ {
		x := nextInt()
		y := nextInt()
		_ = nextInt()
		x--
		y--
		ufUnite(t, x, y)
	}
	//fmt.Printf("%v\n", t)
	count := 0
	for i := 0; i < n; i++ {
		if t[i] == i {
			count++
		}
	}
	_, _ = fmt.Fprintf(writer, "%d", count)
}

func main() {
	answer(os.Stdin, os.Stdout)
}


Measured memory_bytes: 2944
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
s = 0

for i in range(N):
	s = s + B[A[i] - 1]

for j in range(N - 1):
	if A[j + 1] == A[j] + 1:
		s = s + C[A[j] - 1]

print(s)

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

int main() {

	string s;
	string ans;
	int w;

	cin >> s >> w;
	for (int i = 0; i < s.size(); i += w)
		ans += s[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i()
a = gets.split(' ')

s = 0
a.each do |str|
  s += str.to_i
end

s = s * s 
a.each do |str|
  s -= str.to_i * str.to_i 
end
s /= 2

puts(s % 1000000007)

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

int main(){
    int N;
    cin >> N;
    vector<int>p(N);

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

    sort(p.begin(), p.end());

    int p_sum = 0;

    for(int i=0; i<N-1; i++){
        p_sum += p[i];
    }

    p_sum += p[N-1]/2;

    cout << p_sum << endl;

    return 0;
}

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

const long long MOD = 1000000007;
vector<long long> dp(100001, -1);
vector<bool> broken(100001);

long long fibo(int a) {
  if (broken.at(a)) {
    return 0;
  } else if (a == 0 || a == 1) {
    return 1;
  }

  if (dp.at(a) >= 0) {
    return dp.at(a);
  }
  return dp.at(a) = (fibo(a - 1) % MOD + fibo(a - 2) % MOD) % MOD;
}

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

  int N, M;
  cin >> N >> M;

  for (int i = 0; i < M; i++) {
    int a;
    cin >> a;
    broken.at(a) = true;
  }

  cout << fibo(N) <<endl;

}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define N 200001
#define ll long long
#define int ll 
#define pi pair<int , int>
#define pip pair<pair ,int>
#define mp make_pair 
#define f first
#define s second
#define mod 998244353
ll Mod(ll x, ll y, int p) 
{ll res = 1; x = x % p;
while (y > 0) 
{if(y & 1) res = (res*x) % p; 
y = y>>1;x = (x*x) % p; 
}return res; 
}
int* getlps(string pattern){
 int len = pattern.length();
 int * lps = new int[len];
 lps[0] = 0;
 int i = 1 , j = 0;
 while(i < len){
  if(pattern[i] == pattern[j]){
	  lps[i] = j+1;
   i++;
   j++;
  }
  else{
		if(j != 0){
		 j = lps[j-1];
		}
		else{
		 lps[i] = 0;
		 i++;
		}
  }
 }
 return lps;
}
class Triplet{
 public:
 int x ;
 int y ;
 int gcd;
};
Triplet extendedEuclid(int a , int b){
 if(b == 0){Triplet ans; ans.gcd = a;ans.x = 1;ans.y = 0;return ans;}
 Triplet smallAns = extendedEuclid(b , a%b);
 Triplet ans;
 ans.gcd = smallAns.gcd;
 ans.x = smallAns.y;
 ans.y = smallAns.x - (a/b)*smallAns.y;
 return ans;
}
int mmInverse(int a , int m){
 Triplet ans = extendedEuclid(a , m);
 return (ans.x+m)%m;
}
int fact[N];
void calfac(int n ){
fact[0] = 1;
for(int i = 1 ; i <= n+2; i++){
 fact[i] = (((fact[i-1]%mod)*(i%mod))%mod + mod)%mod;
}
 }
int calc(int n , int r){
 if(r > n)return 0;
 if(r == n)return 1;
 int ans = 1;
 ans = ((ans%mod)*(fact[n])%mod + mod)%mod;
 ans = ((ans%mod)*(mmInverse(fact[n-r] , mod)%mod) + mod)%mod;
 ans = ((ans%mod)*(mmInverse(fact[r] , mod)%mod) + mod)%mod;
 return (ans+mod)%mod;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin>>k;
int a , b;
cin>>a>>b;
if((b/k) - (a-1)/k){
 cout<<"OK"<<endl;
 return 0;
}
cout<<"NG"<<endl;
}


Measured memory_bytes: 3624
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<ctype.h>
#include<stack>
#include<math.h>
#include <string>
#include<algorithm>
#include<iomanip>
#define _for(i,a,b) for(int i = (a);i < (b);i++)
#define mset(x) memset(x,0,sizeof(x));
using namespace std;
#define len 100005
typedef struct pp{
	char name[100];
	int t;
}p;
p Q[len];
int head,tail,n;
void enqueue(p x)
{
	Q[tail] = x;
	tail = (tail + 1 )% len;
 } 
 p dequeue()
 {
 	p x = Q[head];
 	head = (head + 1)%len;
 	return x;
 }
int main() {
	int total = 0,c;
	int i,q;
	p u;
	cin>>n>>q;
	for(i = 1; i <= n;i++)
	{
		cin>>Q[i].name>>Q[i].t;
		}	
		head = 1; tail = n + 1;
		while(head != tail)
		{
			u = dequeue();
			c = min(q,u.t);
			u.t -= c;
			total += c;
			if(u.t > 0)
			enqueue(u);
			else
			cout<<u.name<<" "<<total<<endl;			
		}
	return 0;
}


Measured memory_bytes: 13256
#include <stdio.h>

int main(void)
{
	int a, b, c, d;

	scanf("%d %d %d", &a, &b, &c);

	if (a > b) {
		d = a;
		a = b;
		b = d;
	}
	if (b > c) {
		d = b;
		b = c;
		c = d;
	}
	if (a > b) {
		d = a;
		a = b;
		b = d;
	}

	printf("%d %d %d\n", a, b, c);

	return 0;
}



Measured memory_bytes: 2692
import sys
input = sys.stdin.readline
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

d = defaultdict(int)

for ai in a:
    d[ai] += 1
s = sum(a)

for b, c in bc:
    nb = d[b]
    nc = d[c]
    s += (c - b) * nb
    print(s)
    d[b] = 0
    d[c] += nb



Measured memory_bytes: 40064
n = int(input())
s = input()
r,g,b = [0]*(n+1),[0]*(n+1),[0]*(n+1)
for i in range(1,n+1):
    if s[i-1]=='R':
        r[i] =r[i-1]+1
        g[i] = g[i-1]
        b[i] = b[i-1]
    elif s[i-1] =='G':
        r[i] =r[i-1]
        g[i] = g[i-1]+1
        b[i] = b[i-1]
    else:
        r[i] =r[i-1]
        g[i] = g[i-1]
        b[i] = b[i-1]+1
ans = 0
for i in range(1,n+1):
    for j in range(i+1,n+1):
        p = ['R','G','B']
        if s[i-1] ==s[j-1]:
            continue
        else:
            p.remove(s[i-1])
            p.remove(s[j-1])
            if 2*j-i-1 <n and p[0] ==s[2*j-i-1]:
                ans -=1
            if p[0]=='R':
                ans += r[-1]-r[j]
            elif p[0]=='B':
                ans += b[-1]-b[j]
            else:
                ans += g[-1]-g[j]
print(ans)
            

Measured memory_bytes: 74152
n = int(input())
a = [int(input()) for _ in range(5)]
q_max = 0
res = 5
for i in range(len(a)):
  q = n // a[i]
  r = n % a[i]
  if r > 0:
    q_max = max(q_max, q)
  else:
    q_max = max(q_max, q - 1)
print(res + q_max)

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

ll mylog2(ll n)
{
  ll ret = 0;

  while (n < 0) {
    n = n >> 1;
    ret++;
  }

  return ret;
}

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

  ll H;
  cin >> H;

  ll n = log2(H) + 1;
  ll ans = pow(2, n) - 1;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll  long long
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define pb push_back
#define Max(x,y,z) max(x,max(y,z))
#define f first
#define s second
#define lbd lower_bound
#define sz(x)       (ll)x.size()
#define pi 3.1415926536
#define mod 1000000007
using namespace std;

void solve()
{
    ll n,m,k,x,y,res=0,l,a=0,b=0,c=0,d=0,cnt=0,sum=0,z;
    cin>>x>>y>>z;
    if((z>=x && z<=y) || (z<=x && z>=y))
        cout<<"Yes";
    else
        cout<<"No";

}
int main()
{
    ll t;
    //cin>>t;
    t=1;
    while(t--)
        solve();
}


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

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

  string text;
  int cnt = 0;
  for (;;) {
    cin >> text;
    
    if (text == "END_OF_TEXT") break;
    
    for (int i = 0; i < text.size(); i++) {
      text[i] = tolower(text[i]);
    }

    if (text == w) cnt++;
    
  }

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


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(z) for(int i=1;i<=z;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define pb push_back
#define si set<int>
#define mod  1000000007
#define cl(n,m) (int)(ceil(double(n)/double(m)))
#define T() int TT; cin>>TT; while(TT--)
#define P pair<int,int>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

signed main(){
	int n ,k;
	string s ;
	cin>>n ;
	cin>>s >>k;
	for(int i=0 ;i<n ;i++){
		if(s[i]!=s[k-1]) s[i] = '*' ;
	}
	cout<<s ;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i,j,k,n;
	int ain[10];
	int bin[10];
	int cin[10];
	int aout[10];
	int bout[10];
	int cout[10];
	j=0;k=0;
	for(i=1;i<=6;i++){
		scanf("%d",&ain[i-1]);
	}
	for(i=1;i<=6;i++){
		scanf("%d",&bin[i-1]);
	}
	for(i=1;i<=6;i++){
		scanf("%d",&cin[i-1]);
	}
	n=ain[5]-ain[2];
	if(n<0){
		n+=60;
		j++;
	}
	aout[2]=n;
	n=ain[4]-ain[1];
	if(n<0){
		n+=60;
		k++;
	}
	if(j==1){
		if(n==0){
			n=59;
		}else{
			n-=1;
		}
	}
	aout[1]=n;
	n=ain[3]-ain[0];
	if(n<0){
		n+=60;
	}
	if(k==1){
		if(n==0){
			n=23;
		}else{
			n-=1;
		}
	}
	aout[0]=n;
	
	j=0;k=0;
	n=bin[5]-bin[2];
	if(n<0){
		n+=60;
		j++;
	}
	bout[2]=n;
	n=bin[4]-bin[1];
	if(n<0){
		n+=60;
		k++;
	}
	if(j==1){
		if(n==0){
			n=59;
			k++;
		}else{
			n-=1;
		}
	}
	bout[1]=n;
	n=bin[3]-bin[0];
	if(n<0){
		n+=60;
	}
	if(k==1){
		if(n==0){
			n=23;
		}else{
			n-=1;
		}
	}
	bout[0]=n;
	
	j=0;k=0;
	n=cin[5]-cin[2];
	if(n<0){
		n+=60;
		j++;
	}
	cout[2]=n;
	n=cin[4]-cin[1];
	if(n<0){
		n+=60;
		k++;
	}
	if(j==1){
		if(n==0){
			n=59;
			k++;
		}else{
			n-=1;
		}
	}
	cout[1]=n;
	n=cin[3]-cin[0];
	if(n<0){
		n+=60;
	}
	if(k==1){
		if(n==0){
			n=23;
		}else{
			n-=1;
		}
	}
	cout[0]=n;
	
	for(i=1;i<=3;i++){
		printf("%d",aout[i-1]);
		if(i==3){
			printf("\n");
			break;
		}
		printf(" ");
	}
	for(i=1;i<=3;i++){
		printf("%d",bout[i-1]);
		if(i==3){
			printf("\n");
			break;
		}
		printf(" ");
	}
	for(i=1;i<=3;i++){
		printf("%d",cout[i-1]);
		if(i==3){
			printf("\n");
			break;
		}
		printf(" ");
	}
	return 0;
}

Measured memory_bytes: 604
from math import floor, log
def solve():
    N = int(input()) - 1
    
    ans = []

    while N >= 26:
        ans.append(chr(N % 26 + ord('a')))
        N //= 26
        N -= 1
    else:
        ans.append(chr(N % 26 + ord('a')))

    print("".join(ans[::-1]))
    
if __name__ == '__main__':
    solve()


Measured memory_bytes: 61872
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define FORD(i, a, b) for (int i=a; i>(int)(b); i--)
#define PPC(x) __builtin_popcount(x)
#define MSB(x) (31 - __builtin_clz(x))
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;

const int maxN = 1 << 18;

int tax(int n, int b)
{
	return n * b / 100;
}

void solve()
{
	int a, b;
	scanf ("%d%d", &a, &b);
	FOR(i, 1, maxN)
	{
		if (tax(i, 8) == a and tax(i, 10) == b)
		{
			printf("%d\n", i);
			return;
		}
	}
	
	printf("-1\n");
} 

 
int main()
{
    int t;
    t=1;//scanf ("%d", &t);
    while (t--)
    	solve();
    return 0;    
}


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

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

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

	int a;
	if(n % 2 == 0) cout << 1.0 / 2.0;
	else cout << (n / 2 + 1.0) / n;

	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int k;

int main() {
  cin >> n >> k;
  vector<int> p(n);
  for(int i = 0; i < n; ++i) {
    cin >> p[i];
  }
  sort(p.begin(), p.end());
  auto it = lower_bound(p.begin(), p.end(), k);
  int res = distance(it, p.end());
  cout << res << endl;
}


Measured memory_bytes: 640
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wtr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()
	a := make([]uint, n)

	for i := 0; i < n; i++ {
		a[i] = uint(scanInt())
	}

	cnt := make([]uint, 61)
	for _,ai:=range a{
		for i:=uint(0);i<=60;i++{
			cnt[i] +=(uint(ai) >> i)&1
		}
	}
 
	ans :=uint(0)
	for i, v:=range cnt{
		ans = (ans + ((v*(uint(n)-v))%mod * ((1<<uint(i)) % mod))) %mod
	}

	fmt.Println(ans)
}

const mod = 1000000007


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

namespace Atcoder
{
    class Atcoderrrrrrr
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string ans = "AC";
            if(s.StartsWith("A")==false){
                ans="WA";
            }
            int cnt=0;
            for(int i =1;i<s.Length;i++){
                if(Char.IsUpper(s[i])){
                    if(i==1||i==s.Length-1||s[i] != 'C'){
                        ans = "WA";
                    }
                    cnt++;
                }
            }
            if(cnt!=1){
                ans="WA";
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 11348
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <iomanip>
#include <limits>
#include <sstream>
#include <bitset>

#define roop(i, n) for(int i=0;i<n;i++)
#define DIV 1000000007
#define MOD ((int)1e9+7)
//static const long double pi = 3.1415926535897932;

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

char toSmall(char c) { // 大文字を小文字へ
	return (c + 0x20);
}

char toLarge(char c) { // 小文字を大文字へ
	return (c - 0x20);
}

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

struct Combination {
	const int num=51e4;			//要素数
	const int mod=1e9+7;
	vector<ll> fact,inv,finv; //階乗,逆元,逆元の階乗.
	
	Combination():fact(num),inv(num),finv(num){
		fact[0]=fact[1]=1;
		inv[1]=1;
		finv[0]=finv[1]=1;
		for(int i=2;i<num;++i){
			fact[i]=fact[i-1]*i%mod;
			inv[i]=mod-inv[mod%i]*(mod/i)%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	
	int nCk(int n,int k){
		if(n<k) return 0;
		if(n<0 or k<0) return 0;
		return fact[n]*(finv[k]*finv[n-k]%mod)%mod;
	}
	int big_nCk(int n,int k){ //nが大きいとき
		ll res=1LL;
		for (int i = 0; i < k; i++) {
			res=res*(n-i)%mod;
		}
		res = res*finv[k]%mod;
		return res;
	}
	int nHk(int n,int k){return nCk(n+k-1,n-1);}//重複組み合わせ.
};

vector<string> split(const string& src, const char* delim = ",") { //カンマ区切り
	vector<string> vec;
	string::size_type len = src.length();

	for (string::size_type i = 0, n; i < len; i = n + 1) {
		n = src.find_first_of(delim, i);
		if (n == string::npos) {
			n = len;
		}
		vec.push_back(src.substr(i, n - i));
	}

	return vec;
}

bool check_int(string str)
{
	if (all_of(str.cbegin(), str.cend(), [](char ch) { return isdigit(ch);}))
	{
		return true;
	}
	return false;
}

struct rest {
	string s;
	int p;
	int num;

	/* -------------------------------------
	sort関数を使用したときのソートの定義をする。
	まずは文字列sでソートする。
	文字列sが同じだった場合、pでソートする。
	この条件を参考演算子で表現(ifでもOK)
	-------------------------------------*/
	bool operator<(const rest& right) const {
		return s == right.s ? p > right.p : s < right.s;
	}
};

ll pow_mod(ll n, ll k, ll p) { // n^k(mod p)
	if (k == 0) {
		return 1;
	}
	ll res = pow_mod(n * n % p, k / 2, p);
	if (k & 1) {
		res = res * n % p;
	}
	return res;
}

bool vector_finder(std::vector<int> vec, int number) { // vector 内にnumberがあるかどうか
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance( vec.begin(), itr );
	if (index != vec.size()) { // 発見できたとき
		return true;
	}
	else { // 発見できなかったとき
		return false;
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> d(n+1);
	d[0] = 101;
	for (int i = 1; i <= n; i++) {
		cin >> d[i];
	}

	sort(d.begin(), d.end(), greater<int>());
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (d[i-1] > d[i]) {
			ans++;
		}
	}
	return cout << ans, 0;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
struct ss{
	int to,next;
}e[400010];
int first[200010],num;
int val[200010];
int N,Q;
void build(int ,int );
void dfs(int ,int );
int main()
{
	int i,j,k;
	scanf("%d%d",&N,&Q);
	for(i=1;i<N;i++){
		scanf("%d%d",&j,&k);
		build(j,k),build(k,j);
	}
	for(i=1;i<=Q;i++){
		scanf("%d%d",&j,&k);
		val[j]+=k;
	}
	dfs(1,0);
	for(i=1;i<=N;i++)	printf("%d ",val[i]);
	
	return 0;
}
void build(int f,int t){
	e[++num].next=first[f];
	e[num].to=t;
	first[f]=num;
}
void dfs(int now,int fa){
	val[now]+=val[fa];
	int i;
	for(i=first[now];i;i=e[i].next)
		if(e[i].to!=fa)
			dfs(e[i].to,now);
}

Measured memory_bytes: 13184
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


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

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
typedef pair<pii,pii> P;

#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;
vint co(4);
vvint vv;
int w,h;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dp[32][32][4];
int dijkstra(){
	rep(i,32){
		rep(j,32){
			rep(k,4){
				dp[i][j][k]=INF;
			}
		}
	}
	dp[0][0][0]=0;
	priority_queue<P> pq;
	pq.push(mkp(mkp(0,0),mkp(0,0)));
	while(!pq.empty()){
		P top=pq.top();
		// cout<<top.S.F<<" "<<top.S.S<<endl;
		pq.pop();
		if(dp[top.S.F][top.S.S][top.F.S]<-top.F.F) continue;
		if(top.S.F==h-1&&top.S.S==w-1) return -top.F.F;
		rep(i,4){
			P tmp=top;
			if(vv[tmp.S.F][tmp.S.S]==i){
			}
			else{
				tmp.F.F-=co[i];
			}
			tmp.F.S=(tmp.F.S+i)%4;
			tmp.S.F+=dx[tmp.F.S];
			tmp.S.S+=dy[tmp.F.S];
			if(tmp.S.F<0||tmp.S.F>h-1||tmp.S.S<0||tmp.S.S>w-1) continue;
			if(dp[tmp.S.F][tmp.S.S][tmp.F.S]<=-tmp.F.F){
				continue;
			}
			else{
				pq.push(tmp);
				dp[tmp.S.F][tmp.S.S][tmp.F.S]=-tmp.F.F;
			}
		}
	}
	return 0;
}
void mainmain(){
	while(cin>>w>>h,w||h){
		initvv(vv,h,w);
		rep(i,h){
			rep(j,w){
				cin>>vv[i][j];
			}
		}
		rep(i,4){
			cin>>co[i];
		}
		cout<<dijkstra()<<endl;
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

Measured memory_bytes: 1352
from collections import deque
h,w=map(int,input().split())
ch,cw=map(lambda x:int(x)-1,input().split())
dh,dw=map(lambda x:int(x)-1,input().split())
tizu=[]
d=deque()
d.appendleft([ch,cw])
cost=[[-1 for i in range(w)]for j in range(h)]
dx=[1,0,-1,0,-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
dy=[0,1,0,-1,-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
for i in range(h):
    tizu.append(input())
cost[ch][cw]=0
while(d):
    x,y=d.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        ####行ったことある、かつ、コストが手前より高い
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]
            d.appendleft([nx,ny])
    
    for i in range(4,24):
        nx=x+dx[i]
        ny=y+dy[i]
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]+1
            d.append([nx,ny])

print(cost[dh][dw])

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

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

int h, w, c;

int solve(int mass[8][8], int num){

  int res = 0;
  if(num == 5){
    bool used[8][8] = {};
    REP(i,h){
      REP(j,w){
        int sum = 0;
        if(mass[i][j] == c && !used[i][j]){
          queue<pii> que;
          que.push({i,j});
          used[i][j] = true;
          sum++;

          while(!que.empty()){
            pii tmp = que.front();
            int y = tmp.first, x = tmp.second;
            que.pop();
            REP(i,4){
              int nx = x + dx[i], ny = y + dy[i];
              if(nx >= 0 && nx < w && ny >= 0 && ny < h && !used[ny][nx]){
                if(mass[ny][nx] == c){
                  que.push({ny, nx});
                  used[ny][nx] = true;
                  sum++;
                }
              }
            }
          }

          res = max(res, sum);
        }
      }
    }
    return res;
  }

REP(color,6){
  //最後は指定された色である必要がある
  if(num == 4 && color != c){
    continue;
  }

  //同じ色には変えない
  if(color == mass[0][0]) continue;

  int tmp_mass[8][8];
  REP(i,h){
    REP(j,w){
      tmp_mass[i][j] = mass[i][j];
    }
  }

  queue<pii> que;
  que.push({0, 0});
  int cur_color = tmp_mass[0][0];
  tmp_mass[0][0] = color;

  while(!que.empty()){
    pii tmp = que.front();
    int y = tmp.first, x = tmp.second;
    que.pop();
    REP(i,4){
      int nx = x + dx[i], ny = y + dy[i];
      if(nx >= 0 && nx < w && ny >= 0 && ny < h){
        if(tmp_mass[ny][nx] == cur_color){
          tmp_mass[ny][nx] = color;
          que.push({ny, nx});
        }
      }
    }
  }

  res = max(res, solve(tmp_mass, num+1));
} 
return res;
}

int main(){

  while(true){
    cin >> h >> w >> c;
    if(h == 0 && w == 0 && c == 0) break;

    c--;

    int mass[8][8];
    REP(i,h){
      REP(j,w){
        int tmp;
        cin >> tmp;
        mass[i][j] = tmp - 1;
      }
    }

    cout << solve(mass, 0) << endl;
  }
  return 0;
}



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

using namespace std;
using ll = long long;

int main() {
	int R, G, B, N;
	cin >> R >> G >> B >> N;

	int res = 0;
	for (int r = 0; r * R <= N; ++r) {
		for (int g = 0; g * G <= N; ++g) {
			int b = N - r*R - g*G;
			if ((b >= 0) && (b % B == 0)) { ++res; }
		}
	}

	cout << res << endl;

	return 0;
}


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

int main(void){
    int i, j, k, N, SORT[100]={}, v;
    cin >> N;
    for(i=0; i<N; i++){
        cin >> SORT[i];
        cout << SORT[i];
        if(i != N-1) cout << " ";
    }
    cout << endl;
    for(i=1; i<=N-1; i++){
        v = SORT[i];
        j = i - 1;
        while(j >= 0 && SORT[j] > v){
            SORT[j+1] = SORT[j];
            j--;
        }
        SORT[j+1] = v;
        for(k=0; k<N; k++){
            cout << SORT[k];
            if(k != N-1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}
    



Measured memory_bytes: 3092
// inputに入力データ全体が入る
function Main(input) {
  // 1行目がinput[0], 2行目がinput[1], …に入る
  input = input.split(" ");

  //文字列から10進数に変換するときはparseIntを使います
  var N = parseInt(input[0], 10);
  var K = parseInt(input[1], 10);

  //出力
  if(N % K === 0) {
    console.log(0);
  } else {
    console.log(1);
  }
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main() {
  int n;
  cin >> n;
  vector<int> renga(n);
  for (int i = 0; i < n; i++) {
    cin >> renga.at(i);
  }
  
  int m = 0;
  int ans = 0;
  bool bo = false;
  bool bo2 = false;
  for (int i = 1; ; i++) {
    for (int j = m; j < n; j++) {
      if (i == renga.at(j)) {
        ans += j - m;
        m = j + 1;
        bo = true;
        bo2 = true;
        break;
      }
      else if (i == 1 && j == n - 1) {
        break;
      }
      else if (j == n - 1) {
        ans += n - m;
        bo = true;
        bo2 = false;
        break;
      }
    }
    if (!bo2 || m >= n) {
      break;
    }
  }
  if (bo) {
    cout << ans << endl;
  }
  else {
    cout << -1 << endl;
  }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
    using namespace std;
    int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    string s;
    int h,w;
    char x='A';
    cin>>h>>w;
    for(int i=1;i<=h;i++){
    for(int j=0;j<w;j++){
    cin>>s;
    if(s=="snuke"){
    cout<<char(x+j)<<i<<'\n';
    }
    }
    }
    return 0;
    }

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

int main() {
  int n;
  cin >> n;
  vector<int> b(n-1);
  rep(i,n-1) cin >> b.at(i);
  vector<int> a(n);
  for(int i = 1; i < n-1; i++) a.at(i) = min(b.at(i-1), b.at(i));
  int ans = 0;
  for(int i = 1; i < n-1; i++) ans += a.at(i);
  cout << ans + b.at(0) + b.at(n-2) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
//#include<string.h>

int main(int argc, char const *argv[])
{
	int n, b, f, r, v;
	int i, j, k;
	int count[4][3][10]= {};
	//memset(count,0,sizeof(count));

	scanf("%d", &n);
	for(i=0;i<n;i++) {
		scanf("%d %d %d %d", &b, &f, &r, &v);
		count[b-1][f-1][r-1] += v;
	}
	
	
	for(i = 0; i<4; i++) {
		for(j=0; j<3; j++){
			for(k=0; k<9; k++) {
				printf(" %d", count[i][j][k]);
			} printf(" %d\n", count[i][j][9]);
		}
		if(i!=3) printf("####################\n");
	}

	return 0;
}



Measured memory_bytes: 2140
#include "iostream"
#include "math.h"
#include "algorithm"
#include "string"
#include "vector"
#include "deque"
#include "cmath"
using namespace std;
typedef long long ll;

int main() {
	int n, m;
	cin >> n >> m;
	if (n == m) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	cout << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<set>
#include<cstring>
#include<cmath>
#include<vector>
#include<cstdio>
#include<stack>
#include<map>
using namespace std;
int main()
{
   long long int n,s,k;
   cin>>n>>k>>s;
   if(k==0)
   {
       if(s==1)
        {
            long long t=s+1;
            for(int i=0;i<n-k;i++)
           cout<<t<<" ";
        }
       else
       {
           long long t=s-1;
           for(int i=0;i<n-k;i++)
           cout<<t<<" ";
       }
   }
   else
   {
   if(n==k)
   {
       for(int i=0;i<k;i++)
        cout<<s<<" ";
   }
   else if(n>k&&k!=0)
   {
       for(int i=0;i<k;i++)
        cout<<s<<" ";
        if(s==1)
        {
            long long t=s+1;
            for(int i=0;i<n-k;i++)
           cout<<t<<" ";
        }
       else
       {
           long long t=s-1;
           for(int i=0;i<n-k;i++)
           cout<<t<<" ";
       }

   }
   }
   return 0;
}


Measured memory_bytes: 1280
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int[] a=new int[n];
		int index=0;
		int max=0;
		for(int i=0; i<n; i++){
			a[i]=sc.nextInt();
			if(Math.abs(max)<Math.abs(a[i])){
				max=a[i];
				index=i;
			}
		}
		ArrayList<String> list=new ArrayList<>();
		if(max<0){
			for(int i=0; i<n; i++){
				if(a[i]>=0){
					a[i]+=max;
					list.add((index+1)+" "+(i+1));
				}
			}
		}else{
			for(int i=0; i<n; i++){
				if(a[i]<0){
					a[i]+=max;
					list.add((index+1)+" "+(i+1));
				}
			}
		}
		System.out.println(list.size()+n-1);
		for(int i=0; i<list.size(); i++){
			System.out.println(list.get(i));
		}
		if(max<0){
			for(int i=n-1; i>0; i--){
				System.out.println((i+1)+" "+i);
			}
		}else{
			for(int i=0; i<n-1; i++){
				System.out.println((i+1)+" "+(i+2));
			}
		}
	}
}


Measured memory_bytes: 23892
import bisect

n = int(input())
A = [int(_) for _ in input().split()]

A.sort()
x = A[-1]
y = bisect.bisect(A, x / 2)

if abs(A[y] - x / 2) < abs(A[y-1] - x / 2):
    print(x, A[y])
else:
    print(x, A[y-1])


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

typedef long long ll;
const int MAXN = (int)2e5 + 500;

int n;
set<int> S;
int bas = 0, num[MAXN];

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &num[i]);
    }
    if(num[0] != 0) return !printf("-1");
    for(int i = 0; i < n-1; i++){
        if(num[i+1] > num[i] + 1) return !printf("-1");
    }
    ll res = 0;
    for(int i = n-1; i >= 0; i--){
        S.insert(num[i] + bas);
        bas ++;
        auto it = S.begin();
        while(!S.empty() && it != S.end() && *it < bas) it = S.erase(it);
        res += S.size();

    }
    cout << res;
}

Measured memory_bytes: 5760
#include <cstdio>

inline int f(int x, int y, int z) {
	return x * (x + y + z) + y * (y + z) + z * z;
}

int main() {
	int N;
	scanf("%d", &N);
	for (int n = 1; n <= N; n++) {
		int cnt = 0;
		for (int i = 1; f(i, 1, 1) <= n; i++) {
			for (int j = i; f(i, j, 1) <= n; j++) {
				for (int k = j; f(i, j, k) <= n; k++) {
					if (i * (i + j + k) + j * (j + k) + k * k == n) {
						if (i != j && j != k) {
							cnt += 6;
						} else if (i != k) {
							cnt += 3;
						} else {
							cnt++;
						}
					}
				}
			}
		}
		printf("%d\n", cnt);
	}
	return 0;
}


Measured memory_bytes: 1684
import sys
input = sys.stdin.readline
print = sys.stdout.write
x, y = [int(_) for _ in input().split()]
a = [4, 6, 9, 11]
if x == 2 or y == 2:
    ans = "No"
elif x in a and y in a:
    ans = "Yes"
elif not x in a and not y in a:
    ans = "Yes"
else:
    ans = "No"

print(ans)



Measured memory_bytes: 3060