akhauriyash/Code-Regression huggingface dataset:
import copy
H,W=map(int,input().split())
List = []
for i in range (H):
  List.append(input())
resList = copy.deepcopy(List)

def bombCheck(x,y,ListX):  
  a = 0
  b = 0
  res = 0
  if ListX[x][y] == "#":
    return "#"
  for i in range(-1,2,1):
    a = x+i
    if 0<= a < H:
      for j in range(-1,2,1):
        b = y+j
        if 0<= b < W:
          if i == 0 and j ==0:
            pass
          else:
            if List[a][b] == "#":
              res +=1
  return str(res)

for i in range(H):
  resList[i] =""
  for j in range(W):
    resList[i] += bombCheck(i,j,List)
for i in resList:
  print(i)

Measured memory_bytes: 9228
use proconio::input;
use proconio::marker::Usize1;

fn traverse(
  result: &mut Vec<usize>,
  routes: &Vec<Vec<(usize, usize)>>,
  index: usize,
  val: usize,
  last_index: usize,
) {
  result[index] = val;
  for v in routes[index].iter() {
    if last_index == v.0 { continue }
    traverse(result, routes, v.0, val ^ v.1, index);
  }
}

fn main() {
  input! {
    n: usize,
    mut edges: [(Usize1, Usize1, usize);n-1]
  }
  let mut routes: Vec<Vec<(usize, usize)>> = vec![vec![];n];
  
  let edges: Vec<(usize, usize, usize)> = edges
  .into_iter()
  .map(|(a,b,c)| (a,b,c % 2))
  .collect();
  
  for (from, to, parity) in edges {
    routes[from].push((to, parity));
    routes[to].push((from, parity));
  }
  let mut result = vec![0;n];
  
  for v in routes[0].iter() {
    traverse(&mut result, &routes, v.0, 0 ^ v.1, 0);
  }
  
  for v in result {
    println!("{}", v);
  }
}

Measured memory_bytes: 15068
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
inline long toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline long toLong(string s) {long v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-12;
const int INF = 10000;

struct edge{
	int l,r,h;
	bool operator<( const edge& right ) const {
        return h == right.h ? r < right.r : h < right.h;
    }
};


int main(){
	int a,L;
	while(cin>>a>>L){
		if(a==0&&L==0)break;
		map<string,int>mp;
		int cnt=0;
		int res1,res2,res3;
		while(1){
			string tmp=toString(a);
			string str;
			REP(i,L-SZ(tmp))str+='0';
			str+=tmp;
			if(mp.find(str)!=mp.end()){
				res1=mp[str];
				res2=toInt(str);
				res3=cnt-mp[str];
				break;
			}
			mp.insert(MP(str,cnt));
			sort(ALL(str),greater<char>());
			string maxi=str;
			sort(ALL(str));
			string mini=str;
			a=toInt(maxi)-toInt(mini);
			cnt++;
		}
		cout<<res1<<" "<<res2<<" "<<res3<<endl;
	}
	return 0;
}

Measured memory_bytes: 1256
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include <string>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;
ll mod=1e9+7;

int main(){
	int x,y,z,k; cin >>x>>y>>z>>k;
	ll a[x],b[y],c[z];
	cinf(x,a); cinf(y,b); cinf(z,c);
	vector<ll> sum;
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			sum.push_back(a[i]+b[j]);
		}
	}
	sort(sum.begin(),sum.end());
	reverse(sum.begin(),sum.end());
	if(sum.size()>k)sum.resize(k);
	vector<ll> res;
	for(int i=0;i<sum.size();i++){
		for(int j=0;j<z;j++){
			res.push_back(sum[i]+c[j]);
		}
	}
	sort(res.begin(),res.end());
	reverse(res.begin(),res.end());
	for(int i=0;i<k;i++){
		cout << res[i] << endl;
	}
}

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

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

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

constexpr long long mod = 1000000007;

#define rep(i, n) for (int i = 0; i < n; i++)

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

    double r;
    cin >> r;

    r = 2 * 3.1415926535 * r;

    printf("%.4lf\n", r);
}

Measured memory_bytes: 3824
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define LL long long
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
int main(){
  LL N,M;
  cin>>N>>M;
  if(N==1||M==1){
    if(N==1&&M==1){
      cout<<1<<endl;
    }else if(N==1){
      cout<<M-2<<endl;
    }else{
      cout<<N-2<<endl;
    }
  }else{
    cout<<(N*M-(N+N+M+M-4))<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
h,w = map(int,input().split())
s =["."*(w+2)]+["."+input()+"." for i in range(h)]+["."*(w+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] !="#":
            a=s[i][j-1]+s[i][j+1]+s[i-1][j-1:j+2]+s[i+1][j-1:j+2]
            s[i]=s[i][:j]+str(a.count("#"))+s[i][j+1:]

[print(s[i][1:w+1]) for i in range(1,h+1)]


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

const int MAX_N = 100000;
int f[MAX_N], s[MAX_N];

long long int compo;
int ff(int x) {
    return (f[x] == x) ? f[x] : (f[x] = ff(f[x]));
}

void merge(int a, int b) {
    a = ff(a), b = ff(b);
    if (a == b)
        return;
    compo--;
    if (s[a] > s[b])
        swap(a, b);
    f[a] = b, s[b] += s[a];
}

int cnt0 = 0, cnt1 = 0;
int ans = 0;

int main() {
    long long int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < n; i++)
        f[i] = i, s[i] = 1;
    compo = n;
    vector<pair<int, pair<int, int> > > V;
    for (int i = 0; i < q; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        V.emplace_back(c, make_pair(a, b));
    }
    sort(V.begin(), V.end());
    for (auto p : V) {
        int c = p.first, a = p.second.first, b = p.second.second;
        if (c == 0) {
            merge(a, b);
            cnt0 = 1;
        }
        else {
            if (ff(a) == ff(b))
                ans = -1;
            else
                cnt1 = 1;
        }
    }
    long long int MAXM = n - compo + compo * (compo - 1) / 2;
    if (ans == -1)
        cout << "No\n";
    else if (cnt1 == 1 && m == n - 1)
        cout << "No\n";
    else if (cnt1 == 1 && compo == 2)
        cout << "No\n";
    else if (m > MAXM)
        cout << "No\n";
    else
        cout << "Yes\n";
}


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

ll N, K, S;
const int MAX = 1.0e5 + 10;
const int INF = 1.0e9;

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

    if (K == 0) {
        if (S == INF) {
            for (int i = 0; i < N; i++) {
                cout << 1 << " ";
            }
            cout << endl;
        }
        else {
            for (int i = 0; i < N; i++) {
                cout << S+1 << " ";
            }
            cout << endl;
        }
    }
    else {
        for (int i = 0; i < N; i++) {
            if (S == INF) {
                if (i < K) cout << S << " ";
                else cout << 1 << " ";
            }
            else {
                if (i < K) cout << S << " ";
                else cout << INF << " ";
            }
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 1280
from heapq import *

N, M, S = map(int, input().split())

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = map(int, input().split())
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    # 両替の結果2450枚を超えるなら2450枚として扱って問題なし。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

for i in range(1, N):
  print(min(T[i]))


Measured memory_bytes: 25992
#include<bits/stdc++.h>
#define inf 1000000000
#define N 209
#define M 30009
using namespace std;

int m,n,tot=1,gol,fst[N],cur[N],pnt[M],len[M],nxt[M],d[N],h[N];
char ch[N];
void add(int x,int y,int z){
	pnt[++tot]=y; len[tot]=z; nxt[tot]=fst[x]; fst[x]=tot;
}
bool bfs(){
	int head=0,tail=1,i,x,y; h[1]=0;
	memset(d,-1,sizeof(d)); d[0]=1;
	memcpy(cur,fst,sizeof(fst));
	while (head<tail){
		x=h[++head];
		for (i=fst[x]; i; i=nxt[i]) if (len[i]){
			y=pnt[i];
			if (d[y]==-1){
				d[y]=d[x]+1; h[++tail]=y;
			}
		}
	}
	return d[gol]!=-1;
}
int dfs(int x,int rst){
	if (x==gol || !rst) return rst;
	int &i=cur[x],y,tmp,flow=0;
	for (; i; i=nxt[i]) if (len[i]){
		y=pnt[i];
		if (d[x]+1==d[y] && (tmp=dfs(y,min(rst,len[i])))){
			flow+=tmp; len[i]-=tmp;
			len[i^1]+=tmp; rst-=tmp;
			if (!rst) break;
		}
	}
	if (!flow) d[x]=-1; return flow;
}
void check(int &x,int &y,int i,int j){
	if (x==-1){
		x=i; y=j;
	} else if (x==i || y==j){
		puts("-1"); exit(0);
	}
}
int main(){
	scanf("%d%d",&m,&n);
	int i,j,x=-1,y;
	gol=m+n+1;
	for (i=1; i<=m; i++){
		scanf("%s",ch+1);
		for (j=1; j<=n; j++) if (ch[j]=='o'){
			add(i,j+m,1); add(j+m,i,1);
		} else if (ch[j]=='S'){
			check(x,y,i,j);
			add(0,i,inf); add(i,0,0);
			add(0,j+m,inf); add(j+m,0,0);
		} else if (ch[j]=='T'){
			check(x,y,i,j);
			add(i,gol,inf); add(gol,i,0);
			add(j+m,gol,inf); add(gol,j+m,0);
		}
	}
	int flow=0;
	while (bfs()) flow+=dfs(0,gol);
	printf("%d\n",flow);
	return 0;
}


Measured memory_bytes: 512
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

const int MOD = 1000000007;

struct Edge {
    int to;
    int weight;

    Edge(int t, int w) : to(t), weight(w) {}
};

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

    long long ans = (N * (N - 1)) / 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

var N int
var a map[int]int

func main() {
	fmt.Scan(&N)
	a = make(map[int]int)
	var tmp int

	for i := 0; i < N; i++ {
		fmt.Scan(&tmp)
		if _, ok := a[tmp]; !ok {
			a[tmp] = 0
		}
		a[tmp]++
	}
	result := 0
	for num, count := range a {
		if num > count {
			result += count
		} else {
			result += count - num
		}
	}
	fmt.Println(result)
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define llu unsigned long long int
#define sa(a,n,t) for(int ii=0;ii<n;ii++) scanf("%"#t"",&(a)[ii])
#define rep(i,n) for(int i=0;i<n;i++) 
#define reps(i,a,n) for(int i=a;i<n;i++) 
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rreps(i,a,n) for(int i=n-1;i>=a;i--)
#define validl(i,a,b) ((i>=a)&&(i<=b))?1:0
#define validmat(x,y,a,b,c,d) (validl(x,a,b) && validl(y,a,b))?1:0
#define validmn(x,y,m,n) validmat(x,y,0,m,0,n)
#define valid(i,n) validl(i,0,n)
#define v(t) vector<t>
#define vv(t) vector<vector<t> >
#define mk make_pair
#define pb push_back
#define pa(a,n,t)  for(int i=0;i<n;i++) printf("%"#t"",a[i])
#define p2 pair<int,int>
#define p3 pair<p2,int>
#define fi first
#define se second
#define sd(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld",a)
#define pd(a) printf("%d",a)
#define sf(a) scanf("%lf",&a)
#define pf(a) printf("%lf",a)
#define nline printf("\n")
#define ss(a) scanf("%s",a)
#define ps(a) printf("%s",a)
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",&a)
#define mf(m,f) m.find(f)!=m.end()
#define pp3(m) cout<<m.fi.fi<<" "<<m.fi.se<<" "<<m.se<<" "
#define pp2(m) cout<<m.fi<<" "<<m.se<<" "
#define debug 0
/*v(int) adj[200001];
void dfs(int i,int p){
    rep(j,adj[i].size()){
        if(p!=adj[i][j])
            dfs(adj[i][j],i);
    }
}*/
int main()
{
  int x;
  cin>>x;
  int y=__gcd(x,360);
  cout<<x*360/y/x<<endl;
  return 0;
}


Measured memory_bytes: 3620
#include<cstdio>
#include<algorithm>
typedef unsigned long long ull;
int N;
char S[50];
ull B,S1[1<<18],S2[1<<18];
int main(){
	scanf("%d%s",&N,S);
	for(int i=B=1;i<=N;i++)B*=233;
	for(int s=0;s<1<<N;s++){
		ull Sr=0,Sb=0;
		for(int j=0;j<N;j++){
			if(s>>j&1)Sb=Sb*233+S[j];
			else Sr=Sr*233+S[j];
		}
		S1[s]=Sr*B+Sb;
		Sr=Sb=0;
		for(int j=N*2;j-->N;){
			if(s>>j-N&1)Sb=Sb*233+S[j];
			else Sr=Sr*233+S[j];
		}
		S2[s]=Sr*B+Sb;
	}
	std::sort(S1,S1+(1<<N));
	std::sort(S2,S2+(1<<N));
	long long ans=0;
	for(int l1=0,r1=0,l2=0,r2=0;l1<1<<N;l1=r1){
		for(;r1<(1<<N)&&S1[l1]==S1[r1];r1++);
		while(l2<(1<<N)&&S2[l2]<S1[l1])l2++;
		while(r2<(1<<N)&&S2[r2]<=S1[l1])r2++;
		ans+=1ll*(r1-l1)*(r2-l2);
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 4224
#pragma region header
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cctype>
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#include <cstring>
#include <array>
// ===============================================================
//using系
#pragma region header
using namespace std;
using lint = long long;
using ld = long double;
using ulint = unsigned long long;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
constexpr lint mod = 1000000007;
constexpr long double pi = 3.141592653589793238462643383279;
#pragma endregion
// ========================================================================
//define
#define INF (lint)10000000000000000;
#define mod (int)1000000007
#pragma endregion



int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	lint n, m, k; cin >> n >> m >> k;
	vector<int> a(n), b(m);
	vector<lint> x(n + 1), y(m + 1);
	y[0] = 0;
	x[0] = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		x[i + 1] = x[i] + a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
		y[i + 1] = y[i] + b[i];
	}
	lint ans = 0;
	int c = m;
	for (lint i = 0; i < n + 1; i++) {
		lint cnt = 0;
		if (x[i] > k)  
			break;
		for (int j = c; j >= 0; j--) {
			if (x[i] + y[j] <= k) {
				cnt = i + j;
				c = j;
				break;
			}
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7924
/*
PM 06:18 - 06:53
 */
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<climits>
#include<queue>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define ULLINF (ULLONG_MAX)
#define MAX_V 500

using namespace std;

typedef unsigned long long ull;

// Library - max_flow - begin

int V;

struct edge{
  int to,rev;
  ull cap;
  edge(int to=IINF,ull cap=ULLINF,int rev=IINF):to(to),cap(cap),rev(rev){}
};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,ull cap){
  G[from].push_back(edge(to,cap,G[to].size()));
  G[to].push_back(edge(from,0,G[from].size()-1));
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  que.push(s);
  level[s] = 0;
  while(!que.empty()){
    int v = que.front(); que.pop();
    for(int i=0;i<G[v].size();i++){
      edge &e = G[v][i];
      if(e.cap > 0 && level[e.to] < 0){
	level[e.to] = level[v] + 1;
	que.push(e.to); 
      }
    }
  }
}

ull dfs(int v,int t,ull f){
  if(v == t)return f;
  for(int &i=iter[v];i<G[v].size();i++){
    edge &e = G[v][i];
    if(e.cap > 0 && level[v] < level[e.to]){
      ull d = dfs(e.to,t,min(f,e.cap));
      if(d > 0ULL){
	e.cap -= d;
	G[e.to][e.rev].cap += d;
	return d;
      }
    }
  }
  return 0;
}

ull max_flow(int s,int t){
  ull flow = 0;
  for(;;){

    bfs(s);
    if(level[t] < 0)return flow;
    memset(iter,0,sizeof(iter));
    ull f;
    while( ( f = dfs(s,t,ULLINF) ) > 0ULL ){
      flow += f;
    }
  }
}


// Library - max_flow - end

int N,c;
ull W,t;
string day;

inline int getIndex(const string& a)
{
  if(a[0] == 'M')return 1;
  if(a[0] == 'F')return 5;
  if(a[0] == 'W')return 3;
  if(a[0] == 'S')
    {
      if(a[1] == 'u')return 0;
      else           return 6;
    }
  if(a[0] == 'T')
    {
      if(a[1] == 'u')return 2;
      else           return 4;
    }
}

void init(){
  rep(i,V)G[i].clear();

}

int main(){
  
  while(cin >> N >> W,N|W){

    int sp = N + 7, gp = N + 8;
    ull sum = 0;
    V = gp + 1;

    init();

    for(int i=0;i<N;i++){
      cin >> t >> c;
      add_edge(sp,i,t);
      sum += t;
      for(int j=0;j<c;j++){
	cin >> day;
	int index = getIndex(day);
	add_edge(i,N+index,W);
      }
    }

    for(int i=0;i<7;i++){
      add_edge(N+i,gp,W);
    }
    /*
    cout << "graph---" <<endl;
    rep(i,V)
      {
	cout << "node = " << i << endl;
	rep(j,G[i].size())
	  {
	    cout << "( idex =" << G[i][j].to << "," << G[i][j].cap << ") ";
	  }
	cout << endl;
      }
    */
    ull res = max_flow(sp,gp);
    //cout << "res = " << res << endl;
    cout << ( ( res == sum ) ? "Yes" : "No" ) << endl;

  }
  return 0;
}

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

int n, m;
int ansX, ansY;
int t[102][102], s[52][52], tmp[52][52];

void rotate(){
  for(int i = 0; i < m; i++){
    for(int j = 0; j < m; j++){
      tmp[i][j] = s[i][j];
    }
  }

  for(int i = 0; i < m; i++){
    for(int j = 0; j < m; j++){
      s[j][m - i - 1] = tmp[i][j];
    }
  }
}

void update(int sx, int sy){
  for(int i = 0; i < m; i++){
    for(int j = 0; j < m; j++){
      if(s[i][j] != -1){
        int x = sx + j;
        int y = sy + i;

        if(y < ansY || y == ansY && x < ansX){
          ansX = x;
          ansY = y;
          return;
        }
      }
    }
  }
}

bool check(int sx, int sy){
  for(int i = sy; i < sy + m; i++){
    for(int j = sx; j < sx + m; j++){
      if(s[i - sy][j - sx] == -1) continue;
      if(s[i - sy][j - sx] != t[i][j]){
        return false;
      }
    }
  }

  return true;
}

void solve(){
  for(int sx = 0; sx <= n - m; sx++){
    for(int sy = 0; sy <= n - m; sy++){
      for(int i = 0; i < 4; i++){
        if(check(sx, sy)){
          update(sx, sy);
        }
        rotate();
      }
    }
  }

  if(ansX == INT_MAX){
    cout << "NA\n";
  }
  else{
    cout << ansX + 1 << " " << ansY + 1 << endl;
  }
}

void show(){
  for(int i = 0; i < m; i++){
    for(int j =0; j < m; j++){
      printf("%3d", s[i][j]);
    }
    cout<<endl;
  }
  cout<<"--\n";
}

int main(){
  while(cin >> n >> m, n || m){
    ansX = INT_MAX;
    ansY = INT_MAX;

    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        cin >> t[i][j];
      }
    }

    for(int i = 0; i < m; i++){
      for(int j = 0; j < m; j++){
        cin >> s[i][j];
      }
    }

    solve();
  }
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll dp[101][5][5][5];
ll mo=1000000007;

void solve() {
    int i,j,k,l,r,x,y,z; string s;
    
    cin>>N;
    dp[0][3][3][3]=1;
    
    FOR(i,N) {
        FOR(x,4) FOR(y,4) FOR(z,4) FOR(j,4) {
            if(y==0 && z==1 && j==2) continue;
            if(y==0 && z==2 && j==1) continue;
            if(y==1 && z==0 && j==2) continue;
            if(x==0 && y==1 && j==2) continue;
            if(x==0 && z==1 && j==2) continue;
            (dp[i+1][y][z][j]+=dp[i][x][y][z])%=mo;
        }
    }
    
    ll ret=0;
    FOR(x,4) FOR(y,4) FOR(z,4) ret+=dp[N][x][y][z];
    cout<<ret%mo<<endl;
}


int main(int argc,char** argv){
    string s;int i;
    if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
    FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
    cout.tie(0); solve(); return 0;
}


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

inline ll f(string s) {
    ll ret = 0;
    ll tmp = 0;
    char prev = s[0];
    s += ".";
    rep(i, s.size()) {
        if (prev == s[i]) {
            tmp++;
        }
        else {
            prev = s[i];
            ret += tmp/2;
            tmp = 1;
        }
    }
    return ret;
}

int main() {
    string S;
    ll K;
    cin >> S >> K;

    map<char, int> num;
    rep(i, S.size()) {
        num[S[i]]++;
    }

    if (num.size() == 1) {
        cout << S.size()*K/2 << endl;
    }
    else {
        ll x = f(S);
        ll d = f(S+S) - x;

        cout << x+d*(K-1) << endl;
    }
}


Measured memory_bytes: 256
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

void solve(){
	int n = read.to!int;
	
	long[] as, bs;
	foreach(i; 0 .. n) as ~= read.to!long;
	foreach(i; 0 .. n) bs ~= read.to!long;
	
	X[] xs;
	foreach(i; 0 .. n) xs ~= new X(i, as[i], bs[i]);
	
	foreach(i; 0 .. n - 1){
		xs[i].next = xs[i + 1];
		xs[i + 1].prev = xs[i];
	}
	xs[n - 1].next = xs[0];
	xs[0].prev = xs[n - 1];
	
	auto xh = new RedBlackTree!(X, "a.isLargerThan(b)", true);
	
	foreach(x; xs){
		if(x.b > x.a){
			xh.insert(x);
		}
	}
	log("xh:", xh[], "xs:", xs);
	
	long ans = 0;
	while(xh.length > 0){
		X x = xh.front;
		xh.removeFront;
		long bsum = x.prev.b + x.next.b;
		long bmax = max(x.prev.b, x.next.b);
		if(bsum > x.b - x.a){
			"-1".writeln;
			return;
		}
		if(x.a >= bmax){
			if((x.b - x.a) % bsum == 0){
				ans += (x.b - x.a) / bsum;
				x.b = x.a;
			}
			else{
				"-1".writeln;
				return;
			}
		}
		else{
			long k = (x.b - bmax + bsum - 1) / bsum;
			long b2 = x.b - k * bsum;
			if(b2 < x.a){
				"-1".writeln;
				return;
			}
			else{
				ans += k;
				x.b = b2;
				if(x.a < x.b) xh.insert(x);
			}
		}
		log("xh:", xh[], "xs:", xs, "ans:", ans);
		
	}
	
	ans.writeln;
	
	
	
	

}

class X{
	int id;
	long a;
	long b;
	X prev, next;
	this(int id, long a, long b){
		this.id = id;
		this.a = a;
		this.b = b;
	}
	bool isLargerThan(X y){
		if(this.b > y.b) return 1;
		if(this.b < y.b) return 0;
		return this.id > y.id;
	}
	override string toString(){
		return b.to!string ~ "(" ~ a.to!string ~ ")";
	}
}


Measured memory_bytes: 74728
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_H 90
#define MAX_W 90

int H, W, Ans; bool Ice[MAX_H][MAX_W];

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

void dfs(int x, int y, int depth, bool found[][MAX_W])
{
	if (Ice[y][x] == true)
	{
		Ans = max(depth, Ans);

		for (int dir = 0; dir < 4; dir++)
		{
			if (0 <= x + dx[dir] && x + dx[dir] < W && 0 <= y + dy[dir] && y + dy[dir] < H)
			{
				if (Ice[y + dy[dir]][x + dx[dir]] == true && found[y + dy[dir]][x + dx[dir]] == false)
				{
					bool found2[MAX_H][MAX_W];

					for (int i = 0; i < H; i++)
					{
						for (int j = 0; j < W; j++)
						{
							found2[i][j] = found[i][j];
						}
					}

					found2[y + dy[dir]][x + dx[dir]] = true;

					dfs(x + dx[dir], y + dy[dir], depth + 1, found2);
				}
			}
		}
	}
}

int main()
{
	while (true)
	{
		cin >> W >> H;

		if (W == 0 && H == 0) { break; }

		int tmp;

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				cin >> tmp;

				if (tmp == 1)
				{
					Ice[i][j] = true;
				}
				else
				{
					Ice[i][j] = false;
				}
			}
		}

		Ans = 0;

		bool tmpfound[MAX_H][MAX_W];

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				for (int i1 = 0; i1 < H; i1++)
				{
					for (int j1 = 0; j1 < W; j1++)
					{
						tmpfound[i1][j1] = false;
					}
				}

				tmpfound[i][j] = true;

				dfs(j, i, 1, tmpfound);
			}
		}

		cout << Ans << endl;
	}

	return 0;
}

Measured memory_bytes: 3320
import java.util.Scanner;

class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        // 3 <= n <= 10,000
        int n = sc.nextInt();
        StringBuilder output = new StringBuilder();
        int num = 0;
        for (int i = 3; i <= n; i++) {
            num = i;

            // ３で割り切れる数を格納
            if (num%3 == 0) {
                output.append(" " + i);
                num = 0;
            }

            // 3で割り切れない、3が含まれる数を格納
            while(num > 0) {
                if (num%10 == 3) {
                    output.append(" " + i);
                    break;
                }
                else num /= 10;
            }

        }

        System.out.println(output);

        sc.close();
    }
}


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

using namespace std;
typedef long long ll;

#define rep(i , j , n) for(long long i = j ; i <= n ; i++)
const int N = 123456;
int a[N];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n , k;
    cin >> n >> k;

    int ans = INT_MAX;

    rep(i , 1 , n) cin >> a[i];

    sort(a + 1 , a + n + 1);

    rep(i , 1 , n) {
        if(i + k - 1 > n) break;
        ans = min(ans , a[i + k - 1] - a[i]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i < (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define repb(bit, n, init) for (ll bit = init; bit < (1 << n); ++bit)

int main()
{
    string s, loop = "abcdefghijklmnopqrstuvwxyz";
    map<char, int> character;
    while (cin >> s)
    {
        repi(i, s.length(), 0)
        {
            s.at(i) = tolower(s.at(i));
            if ('a' <= s.at(i) && s.at(i) <= 'z')
            {
                if (character.count(s.at(i)))
                {
                    character[s.at(i)]++;
                }
                else
                {
                    character.insert(make_pair(s.at(i), 1));
                }
            }
        }
    }
    repi(i, loop.length(), 0)
    {
        cout << loop.at(i) << " : " << (character.count(loop.at(i)) ? character.at(loop.at(i)) : 0) << endl;
    }
    return 0;
}


Measured memory_bytes: 3172
#include<stdio.h>
#include<string.h>
#define N 1130
#define max(a,b) a>b?a:b
int p[1000],n,k,dp[16][N][190];

void mp()
{
	int n[N]={1,1},q,i,j;
	for(i=q=0;i<N;i++)
		if(!n[i])
		{
			p[q++]=i;
			for(j=i*2;j<N;j+=i)
				n[j]=1;
		}
}

int ds(int x,int q,int d)
{
	int i,res=0;
	if(p[q]<=x&&dp[d][x][q]!=-1)
		res=dp[d][x][q];
	else if(d==0)
		return x==0?1:0;
	else
		for(i=q;p[i]<=x;i++)
			res+=ds(x-p[i],i+1,d-1);
	return dp[d][x][q]=res;
}

int main()
{
	memset(dp,-1,sizeof(dp));
	mp();
	for(;scanf("%d%d",&n,&k),n+k;)
		printf("%d\n",ds(n,0,k));
	return 0;
}

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

using namespace std;

using ll = long long;

const long double PI = 3.1415926535;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<long double> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    std::random_device rnd;
    std::mt19937 mt(rnd());
    const long double R = 1e15;
    uniform_real_distribution<> rand_real(-R, R);
    vector<int> cnt(n, 0);
    const int MAX_LOOP = 1000000;
    for (int i = 0; i < MAX_LOOP; i++) {
        long double X = R * cos(2 * PI * i / MAX_LOOP);
        long double Y = R * sin(2 * PI * i / MAX_LOOP);
        int idx = 0;
        long double mind = 1e100;
        for (int j = 0; j < n; j++) {
            long double dx = x[j] - X, dy = y[j] - Y;
            long double d = dx * dx + dy * dy;
            if (mind > d) {
                idx = j;
                mind = d;
            }
        }
        cnt[idx]++;
    }

    for (int i = 0; i < n; i++) {
        cout << setprecision(10) << (long double)cnt[i] / MAX_LOOP << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <set>
#include <functional>
#include <cmath>
#include <set>
#include <map>


//マクロ
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define REPS(i,n) for(int i=1; i<=(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n)-1; i>=0; --i)
#define RREPS(i,n) for(int i=(int)(n); i>0; --i)
#define FOR(i,s,e) for(int i=(int)(s); i<(int)(e); ++i)
#define RFOR(i,s,e) for(int i=(int)(e)-1; i>=(int)(s); --i)
#define All(a) (a).begin(),(a).end()
#define RAll(a) (a).rbegin(),(a).rend()
#define dump(x)  cerr << #x << " = " << (x) << endl;

//定数
#define INF 1e9
#define INFL 1e18
#define MOD (int)(1e9+7)

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using pii = pair<int, int>;
using Graph = vector<vector<int>>;

//とりあえず書いておく変数
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//今回の変数

//使用する関数
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;
}

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

	string s, t;
	cin >> s >> t;

	int ans = 0;
	REP(i, s.size()) {
		if (s[i] != t[i])ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3792
#include<iostream>

int main(void){
    std::string s, t, u;
    int a, b;
    std::cin >> s >> t >> a >> b >> u;
    if(s == u){
	a--;
    }else{
	b--;
    }
    std::cout << a << " " << b << std::endl;
    return 0;
}



Measured memory_bytes: 3624
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
const ll M=1000000007;
using namespace std;


ll n,k,ans=0;
int main()
{
    cin>>n>>k;
    for (int i=k; i<=n+1; ++i)
    {
        ll l=(0+i-1);
        l = l*i/2;
        ll r=(n+n+1-i);
        r=r*i/2;
        //cout<<i<<' '<<l<<' '<<r<<endl;
        ans = ((ans) + (r-l+1))%M;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3628
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	for i := 0; i*4 <= n; i++ {
		if (n-i*4)%7 == 0 {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 512
l,r=map(int,input().split())
hantei=20202
if r-l+1>=2019:
  print(0)
else:
  for i in range(l,r+1):
    for j in range(l,r+1):
      if i!=j and (i*j)%2019<hantei:
        hantei=(i*j)%2019
  print(hantei)

Measured memory_bytes: 3060
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
using namespace std;

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


Measured memory_bytes: 256
n, m = [int(i) for i in input().split(' ')]
sc = [[int(i) for i in input().split(' ')] for j in range(m)]
sc = list(map(list, set(map(tuple, sc))))
s = [i[0] for i in sc]
c = [i[1] for i in sc]

fl1 = len(set(s)) != len(s)
if 1 in s:
  fl2 = c[s.index(1)]==0
else:
  fl2 = False

if (n==1) & (m==0):
  print('0')
elif (fl1 | fl2) & (not((n==1) & (m==1))):
  print('-1')
else:
  ans = ['0' for i in range(n)]
  if 1 not in s:
    ans[0] = '1'
  for i in sc:
    ans[i[0]-1] = str(i[1])
  print(''.join(ans))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define f(i,a,b) for(int i=a;i<b;i++)
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,p;
    cin>>a>>p;
    int ans = (3*a+p)/2;
    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;

struct Graph
{
    int n;
    vector<vector<int>> g;
    
    Graph(int n) : n(n){
        g.resize(n);
    }
    
    void init(int n_){
        n = n_;
        g.resize(n_);
    }
    
    void add_edge(int from, int to){
        g[from].push_back(to);
    }
};

struct Tree	//create tree(directed) from graph(undirected)
{
    int n;
    int root;
    vector<vector<int>> t;
    vector<int> par;
    vector<int> dpt;
    
    void init(Graph &g, int root_){
        n = g.n;
        root = root_;
        t.resize(n);
        par.resize(n);
        dpt.resize(n);
        fill(dpt.begin(), dpt.end(), -1);
        queue<int> que;
        par[root] = -1;
        dpt[root] = 0;
        que.push(root);
        while(que.size()){
            int pa = que.front();
            que.pop();
            for(int ch : g.g[pa]){
                if(dpt[ch] == -1){
                    t[pa].push_back(ch);
                    par[ch] = pa;
                    dpt[ch] = dpt[pa] + 1;
                    que.push(ch);
                }
            }
        }
    }

    Tree(){}
    
    Tree(Graph &g, int root_){
        init(g, root_);
    }
};

int main()
{
    int n;
    cin >> n;
    Graph g(n);
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        g.add_edge(a, b);
        g.add_edge(b, a);
    }
    Tree t;
    bool f = false;
    for(int i = 0; i < n; i++){
        if((int)g.g[i].size() >= 3){
            t.init(g, i);
            f = true;
            break;
        }
    }
    if(!f){
        cout << 1 << endl;
        return 0;
    }
    vector<P> v(n);
    for(int i = 0; i < n; i++) v[i] = P(t.dpt[i], i);
    sort(v.begin(), v.end(), greater<P>());
    bool b[100002];
    int ans = 0;
    for(int i = 0; i < n; i++){
        int u = v[i].second;
        if((int)t.t[u].size() == 0) b[u] = true;
        else if((int)t.t[u].size() == 1){
            if(b[t.t[u][0]]) b[u] = true;
            else b[u] = false;
        }
        else{
            int s = 0;
            for(int v : t.t[u]) if(b[v]) s++;
            ans += max(0, s - 1);
            b[u] = false;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 12288
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int tmp=0;
		int[] b=new int[a]; 
		int[] c=new int [a];
		int sum=0;
		// スペース区切りの整数の入力
		for(int i=0;i<a*2;i++){
		if(i%2==0)
		 b[i/2] = sc.nextInt();
		else
		c[i/2]=sc.nextInt();
		}
		//int c = sc.nextInt();
		// 文字列の入力
		    Arrays.sort(b);
		    Arrays.sort(c);


	
	sum=b[a-1]-b[0]+1;
	sum+=c[0];
	sum+=b[0]-1;

		//String s = sc.next();
		// 出力
		System.out.println(sum);
	}
}

Measured memory_bytes: 65236
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
}
 
int32_t main()
{
    c_p_c();
    int h1,p1,h2,p2;
    cin>>h1>>p1>>h2>>p2;
    int turn=1;
    while(1)
    {
        if(h1<=0)
        {
            cout<<"No";
            return 0;
        }
        if(h2<=0)
        {
            cout<<"Yes";
            return 0;
        }
        if(turn==1)
        {
            h2-=p1;
        }
        if(turn==0)
        {
            h1-=p2;
        }
        turn=1-turn;
        
    }
    
    return 0;
}

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

using namespace std;
typedef long long ll;

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

int main(){
// ここに処理を記述
    int N;
    cin >> N;

    int A[N];
    REP(i,N) cin >> A[i];

    double sum = 0;

    REP(i,N){
        sum += (double)1.0 / A[i];
        // cout << A[i] << "\n";
    }

    cout << setprecision(16) <<  1 / sum << "\n";

return 0;
}

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

using ll = long long;

constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;

ll add(ll& a, ll b) {
    return a = min(a + b, INFLL * 2);
}

int main() {
    string S;
    ll K;
    cin >> S >> K;
    int const n = S.size();
    vector<vector<int>> len(n, vector<int>(n, INF));
    for(int i = n - 1; i >= 0; --i) {
        len[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                len[i][j] = (i + 1 == j ? 2 : len[i + 1][j - 1] + 2);
            }
            len[i][j] = min(len[i][j], min(len[i + 1][j], len[i][j - 1]) + 2);
        }
    }
    vector<vector<ll>> dp(n, vector<ll>(n));
    for(int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                add(dp[i][j], (i + 1 == j ? 1 : dp[i + 1][j - 1]));
            } else {
                int min_len = min(len[i + 1][j], len[i][j - 1]);
                if(len[i + 1][j] == min_len) {
                    add(dp[i][j], dp[i + 1][j]);
                }
                if(len[i][j - 1] == min_len) {
                    add(dp[i][j], dp[i][j - 1]);
                }
            }
        }
    }

    if(dp[0][n - 1] < K) {
        cout << "NONE" << endl;
        return 0;
    }

    ll t = 1;
    string l_ans;
    int l = 0, r = n - 1;
    while(l < r) {
        if(S[l] == S[r]) {
            l_ans += S[l++];
            r--;
        } else {
            if(len[l + 1][r] < len[l][r - 1]) {
                l_ans += S[l++];
            } else if(len[l + 1][r] > len[l][r - 1]) {
                l_ans += S[r--];
            } else {
                ll t2 = t + (S[l] < S[r] ? dp[l + 1][r] : dp[l][r - 1]);
                if(t2 > K && S[l] < S[r] || t2 <= K && S[l] > S[r]) {
                    l_ans += S[l++];
                } else {
                    l_ans += S[r--];
                }
                if(t2 <= K) {
                    t = t2;
                }
            }
        }
    }
    auto r_ans = l_ans;
    reverse(begin(r_ans), end(r_ans));
    if(l == r) {
        l_ans += S[l];
    }
    cout << l_ans + r_ans << endl;
}


Measured memory_bytes: 49936
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

signed main(){

    int H,W;
    string C[100];

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

    for(int i=0;i<H;i++){
        cout<<C[i]<<endl<<C[i]<<endl;
    }
}



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

namespace Practice
{
    class Program
    {
        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);


        }
        private struct Pos
        {
            public int row;
            public int col;
        }
        private const long MOD = 1000000007;
        static void SolveA(string[] args)
        {
            int[][] c = new int[3][];
            c[0] = ReadAndParseIntArr();
            c[1] = ReadAndParseIntArr();
            c[2] = ReadAndParseIntArr();
            for(int b1 = 0; b1<=100;++b1)
            {
                int[] a = new int[3];
                int[] b = new int[3];
                b[0] = b1;
                a[0] = c[0][0] - b1;
                a[1] = c[1][0] - b1;
                a[2] = c[2][0] - b1;
                b[1] = c[0][1] - a[0];
                b[2] = c[0][2] - a[0];
                if(IsValid(a, b, c))
                {
                    Console.WriteLine("Yes");
                    return;
                }
            }
            Console.WriteLine("No");
        }
        private static bool IsValid(int[] a, int [] b, int[][] c)
        {
            for(int i=0;i<3;++i)
            {
                for(int j=0;j<3;++j)
                {
                    if( c[i][j] != a[i] + b[j]) { return false; }
                }
            }
            return true;
        }
    }
}

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

int main() {
  long N,A,B;
  long X;
  cin >> N >> A >> B;
  long Y = N % (A + B);
  if (Y == 0)
    X = (N / (A + B)) * A;
  else if (Y <= A)
    X = (N / (A + B)) * A + Y;
  else if (Y > A)
    X = (N / (A + B)) * A + A;
  cout << X << endl;
}

Measured memory_bytes: 256
# include <iostream>
using namespace std;
typedef long long ll;
ll *w; 	int n,k;
int solve(ll p)
{
	int cnt = 0,i = 0,sum = 0;
	while(i < n)
	{
		if(w[i] > p) return k+1;
		if(sum + w[i] <= p) sum += w[i++];
		else {sum = 0; cnt++;}
	}
	if(sum != 0) cnt++;
	return cnt;
}
int main(void)
{
	scanf("%d %d",&n,&k);
	w = new ll [n];
	for(int i = 0;i < n;i++) scanf("%lld",&w[i]);
	ll left = 0,right = 1e10;
	while(right-left > 3)
	{
		ll mid = (left+right)/2;
		ll ans = solve(mid);
		if(ans > k) left = mid;
		else right = mid;
	} 
	for(ll i = left;i <= right;i++)
	{
		if(solve(i) <= k)
		{
			printf("%lld\n",i);
			return 0;
		}
	}
}


Measured memory_bytes: 4012
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	topological_sort
# CreatedDate:  2020-05-18 14:33:31 +0900
# LastModified: 2020-05-18 14:50:54 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    v,e = map(int,input().split())
    path_list = [[] for _ in range(v)]
    to_there = [0]*v
    for _ in range(e):
        s,t = map(int,input().split())
        path_list[s].append(t)
        to_there[t]+=1

    stack_list = [i for i,x in enumerate(to_there) if x==0]
#    print(to_there)
    while stack_list:
        u = stack_list.pop()
        for v in path_list[u]:
            to_there[v]-=1
            if to_there[v]==0:
                stack_list.append(v)
        print(u)


if __name__ == "__main__":
    main()



Measured memory_bytes: 8668
n = int(input())
h = list(int(i) for i in input().split())

dp = [0] * n

for i in range(0, n - 1):
  if(i > 0):
    dp[i + 1] = min(dp[i] + abs(h[i + 1] - h[i]), dp[i - 1] + abs(h[i + 1] - h[i - 1]))
  else:
    dp[i + 1] = (abs(h[i + 1] - h[i]))

print(dp[n - 1])



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

public class Main
{
	public static void main(String[] Arguments) throws IOException 
	{
		Scanner sc = new Scanner(System.in);
		int[] freq = new int[(int)1e5 + 5];
		int N = sc.nextInt();
		for (int i = 0; i < N; i++)
		{
			int number = sc.nextInt(); number++;
			freq[number]++;
			freq[number - 1]++;
			freq[number + 1]++;
		}
		int best = 0;
		for (int i = 0; i < freq.length; i++)
		{
			best = Math.max(freq[i], best);
		}
		System.out.println(best);
	}
}


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

int main() {
	int a, b;
	cin >> a >> b;
	int negative = 0, positive = 0, zero = 0;
	for(int i = a; i <= b; i++) {
		if(i > 0) positive++;
		if(i < 0) negative++;
		if(i == 0) zero = 1;
	}
	if(zero) cout<<"Zero\n";
	else if(negative % 2 == 0) cout<<"Positive\n";
	else if(negative % 2 != 0) cout<<"Negative\n";
	else if(positive > 0 && negative == 0) cout<<"Positive\n";
	return 0;
}

Measured memory_bytes: 256
N = int(input())
s = [int(input()) for i in range(N)]
ten = [a for a in s if a%10==0]
oth = [a for a in s if a not in ten]
oth.sort()
sum = sum(s)
if sum%10==0 and sum!=0 and len(oth)!=0:
    print(sum-oth[0])
elif sum%10!=0:
    print(sum)
else:
    print(0)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#define range(i, l, r) for(int i=l;i<r;i++)
using namespace std;

int main(int argc, char const *argv[]) {
  int N, M, C, summ, count=0;
  std::cin >> N >> M >> C;
  std::vector<int> B(M);
  for(int i=0;i<M;i++) std::cin >> B[i];
  std::vector<std::vector<int> > As(N, vector<int>(M));
  range(i, 0, N){
    range(j, 0, M){
      std::cin >> As[i][j];
    }
  }
  for(int i=0;i<N;i++) {
    summ = 0;
    for(int j=0;j<M;j++){
      summ += As[i][j] * B[j];
    }
    summ += C;
    if(summ>0)count++;
  }
  std::cout << count << '\n';


  return 0;
}


Measured memory_bytes: 888
fn gcd(x: usize, y: usize) -> usize {
    if x == 0 {y} else {gcd(y%x, x)}
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let n: usize = s.trim().parse().unwrap();
    let mut a: usize = 0;
    for i in 0..n{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let t = s.trim().parse().unwrap();
        if i == 0 {a = t}
        else {
            a /= gcd(a, t);
            a *= t;
        }
    }
    println!("{}", a);
}



Measured memory_bytes: 4352