akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

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

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#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 range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int nexts=1;
map<string,int> dir[10010];
bool page[10010];

void insert(void){
	int cur=0;
	int index=0;
	int prev=-1;
	string in;
	cin >> in;
	int n=in.size();
	while(index+1<n){
		int num=1;
		while(index+num<n&&in[index+num]!='/')num++;
		string nx=in.substr(index+1,num-1);
		if(dir[cur].find(nx)==dir[cur].end())
			dir[cur][nx]=nexts++;
		dir[cur]["."]=cur;
		if(prev!=-1) dir[cur][".."]=prev;
		prev=cur;
		cur=dir[cur][nx];
		index+=num;
	}
	page[cur]=true;
}

int find(){
	int cur=0;
	int index=0;
	string in;
	cin >> in;
	int n=in.size();
	while(index+1<n){
		int num=1;
		while(index+num<n&&in[index+num]!='/')num++;
		string nx=in.substr(index+1,num-1);
		if(dir[cur].find(nx)==dir[cur].end())
			return -1;
		cur=dir[cur][nx];
		index+=num;
	}
	if(in[n-1]=='/'||in[n-1]=='.'||!page[cur]){
		if(dir[cur].find("index.html")==dir[cur].end())
			return -1;
		else{
			cur=dir[cur]["index.html"];
			if(page[cur])
				return cur;
			else
				return -1;
		}
	}else
		return cur;
}


int main(void){
	int n,m;
	while(cin >> n >> m){
		if(n==0&&m==0)
			break;
		rep(i,10010) dir[i].clear(),page[i]=false;
		nexts=1;
		rep(i,n) insert();
		rep(i,m){
			int a=find();
			int b=find();
			if(a==-1||b==-1)
				cout << "not found" << endl;
			else if(a==b)
				cout << "yes" << endl;
			else
				cout << "no" << endl;
		}
	}
	return 0;
}

// '.' or '..' '/' is directory therefore check index.html
// otherwise if this is page check page otherwise this is directory check directory/index.html and is directory/index.html page?

Measured memory_bytes: 1712
s = list(input())
s = set(s)
s = list(s)

if "N" in s and "S" in s and "W" in s and "E" in s:
    print("Yes")
elif "N" in s and "S" in s and "W" not in s and "E" not in s:
    print("Yes")
elif "N" not in s and "S" not in s and "W" in s and "E" in s:
    print("Yes")
elif "N" not in s and "S" not in s and "W" not in s and "E" not in s:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<(int)N;i++)
#define p(S) cout<<(S)<<endl
using namespace std;
const int inf=1e9;

int main(){
	int n;
	cin>>n;
	int dp[100010], effect[100010];
	REP(i,0,n) cin>>effect[i];
	REP(i,1,n) dp[i]=inf;
	queue<int> q;
	dp[0]=0;
	q.push(0);
	//bfs
	while(!q.empty()){
		int now=q.front();q.pop();
		REP(i,1,7){
			int next=now+i;
			if(next>n-1) break;
			while(dp[next]==inf){
				if(effect[next]==0)	q.push(next);
				dp[next]=dp[now]+1;
				next+=effect[next];
			}
		}
		if(dp[n-1]<inf)	break;
	}
	p(dp[n-1]);
	return 0;
}

Measured memory_bytes: 3928
#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())

#define ll long long
#define ALL(a)  (a).begin(),(a).end()

#define pb(a) push_back(a)

int now,n,q;

int main(){
  int ans=0;
  cin >> n >> q;
  string s;cin>>s;

  vector<int> l(q),r(q),a(n),c(n);
  REP(i,q) cin>>l[i]>>r[i];
  REP(i,n-1){
    if (s[i]=='A'){
      if (s[i+1]=='C'){
        a[i]=1;
      }
    }
  } 

  int b=0;
  REP(i,n){
    b+=a[i];
    c[i]=b;
  }


  REP(i,q){
    int tmp=0;
    if (a[l[i]-2]==1)
      l[i]++;
    if (a[r[i]-1]==1)
      r[i]--;
    
      if ((l[i])<3){
        tmp=0;
      }else{
        tmp=c[l[i]-3];
      }

      ans=c[r[i]-2]-tmp;
	  cout<<ans<<endl;
  }
  return 0;
}

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

int n;
string s;
int c[101];
int l,r,x;

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


  for(int i=0;i<n;i++){
    if(s[i]=='(') l++;
    else r++;
    c[i] = l-r;
    if(x>c[i]) x = c[i];
  }

  for(int i=0;i<-x;i++)
    s = '(' +s;

  for(int i=0;i<c[n-1]-x;i++)
    s+= ')';

  cout<<s<<endl;

  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
main()
{
char S[3];
int i,a=0,b=0;
cin>>S;
for(i=0;i<3;i++)
{
 if(S[i]=='A')
 {
    a++;
 }

 else if(S[i]=='B')
 {
    b++;
 }

}
if(a==2 || b==2)
{
    cout<<"Yes";
}
else
{
    cout<<"No";
}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
const int INF = 1001001001;
int main()
{
    int h,n;
    cin >> h >> n;
    
    vector<int> dp(h+1,INF);
    dp[0] = 0;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        rep(j,h){
            int nj = min(j+a,h);
            dp[nj] = min(dp[nj],dp[j]+b);

        }
    }
    cout << dp[h] << endl;


    return 0;
}

Measured memory_bytes: 256
function gcd(a,b)
  if a<b then
    return gcd(b,a)
  elseif a%b==0 then
    return b
  else
    return gcd(b,a%b)
  end
end
n=io.read():match("%d+")
for i in io.read():gmatch("%d+") do
  if ans==nil then
    ans=i*1
  end
  ans=gcd(ans,i*1)
end
print(string.format("%d",ans))

Measured memory_bytes: 5296
#include <bits/stdc++.h>
#define ll long long
#define lld long double
#define MOD 1000000007
#define CAP 10000000
#define inf 1000000000000000000LL
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(v) v.size()
#define all(v)    v.begin(),v.end()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y>0){if(y&1)res = (res*x)%md;x = (x*x)%md;y = y>>1;}return res%md;}

#define int ll

int ncr(int n, int r) {
	if(r>n) return 0;

	int fact[2000002];
	fact[0] = 1;
	for(int i=1;i<=2000000;i++) fact[i] = (fact[i-1]*i)%MOD;

	int ans = fact[n];
	ans *= power(fact[r],MOD-2); ans %= MOD;
	ans *= power(fact[n-r], MOD-2); ans %= MOD;
	return ans;
}

signed main() {
	fast;

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

	int moves = (n+m);

	if(moves%3!=0) {
		cout<<0;
		return 0;
	}

	moves /= 3;
	n -= moves;
	m -= moves;

	int ans = ncr(n+m,n);
	cout<<ans;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 1e5+7;
const int MOD = 1e9+7;
const int INF = (~(1<<31));

int fre(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}

inline int read(){
	int x=0,f=-1;char ch=getchar();
	for(;ch<'0'||'9'<ch;ch=getchar())if(ch=='-') f=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}

#define lal puts("****");
#define pb  push_back
#define mp  make_pair

/*****************************************************************/

LL n,m,A,B;
LL a[N];

bool check(LL mid){

	LL sum = 0;
	for(int i=1;i<=n;i++){
		if(a[i]-mid*B<=0) continue;
		sum+=(a[i]-mid*B+A-1)/A;
	}
	if(sum<=mid) return true;
	return false;
}

int main(){
	scanf("%lld%lld%lld",&n,&A,&B);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	A-=B;

	LL l=1,r=1000000000,ans,mid;
	while(l<=r){
		mid = r+l >> 1;
		if(check(mid)) ans = mid ,r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n", ans);
	return 0;
}




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

int main() {
   long long N;
   cin >> N;
   vector<long long> vec(N);
   for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
    vec.at(i) = vec.at(i) * 1000000 + i + 1;
   }
   
   sort(vec.begin(),vec.end());
   for(int i = 0; i < N; i++) {
    cout << vec.at(i) % 1000000 << endl;
   }
}


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

int main(){
    int t, n, h[100];
    cin >> t;
    while( t-- > 0 ){
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> h[i];
        }
        int max = -1001, min = 1001;
        for(int i = 0; i < n-1; i++){
            int g = h[i+1] - h[i];
            if( g > max ){
                max = g;
            }
            if( g < min ){
                min = g;
            }
        }
        cout << (max < 0 ? 0 : max) << ' '
             << (min > 0 ? 0 : -min) << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    int N, Q;
    string S;
    cin >> N >> Q >> S;
    vector<int> sumAC(S.size(), 0);

    int sum = 0;
    rep(si, 1, S.size()) {
        if (S[si-1] == 'A' and S[si] == 'C')
            ++sum;
        
        sumAC[si] = sum;
    }

    rep(qi, 0, Q) {
        int l, r;
        cin >> l >> r;

        cout << sumAC[r-1] - sumAC[l-1] << "\n";
    }
}

Measured memory_bytes: 1488
function Main(input) {
	var input = parseInt(input);
	var paper = 0;
	if(input % 2 == 0) {
		paper = input / 2;
	} else {
		paper = parseInt(input / 2) + 1;
	}

	console.log(paper);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,dp[200005],last[30],pre[200005],mi;
char ans[200005];
string st;
void print(int x)
{
	cout<<ans[x];
	if (pre[x]<st.length()) print(pre[x]+1);
}
int main()
{
	cin>>st;
	for (i=1;i<=26;i++) last[i]=st.length();
	dp[st.length()]=1;
	pre[st.length()]=st.length()+1;
	for (i=st.length();i>=0;i--)
	{
		last[st[i]-'a'+1]=i;
		mi=1;
		for (j=1;j<=26;j++) 
		{
			if (dp[last[j]+1]<dp[last[mi]+1])
			{
				mi=j;
			}
		}
		ans[i]=mi+'a'-1;
		dp[i]=dp[last[mi]+1]+1;
		pre[i]=last[mi];
	}
	print(0);
	return 0;
}

Measured memory_bytes: 2564
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	int A, B;
	cin >> A >> B;
	int diff = B - A;
	cout << diff * (diff+1) / 2 - B << endl;
}

Measured memory_bytes: 3612
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
if n>=m:
  print(0)
  exit()
d=[]
for i in range(1,m):
  d.append(abs(x[i]-x[i-1]))
d.sort()
print(sum(d[:m-n]))



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

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        String s[]=bu.readLine().split(" ");
        int n=Integer.parseInt(s[0]),k=Integer.parseInt(s[1]),i,a[]=new int[n];
        s=bu.readLine().split(" ");
        for(i=0;i<n;i++)
            a[i]=Integer.parseInt(s[i]);
        Arrays.sort(a);
        long sum=0;
        for(i=0;i<k;i++)
            sum+=a[i];
        System.out.print(sum);
    }
}


Measured memory_bytes: 32780
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  string x;
  ll ans = 0;
  cin >> x;
  ll s = 0, t = 0;
  REP(i, x.size()) {
    if (x[i] == 'S')
      s++;
    else if (s > 0)
      s--;
    else
      ans++;
  }
  ans += s;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3760
#include<iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  if(N<10){
    cout<<"Yes";
    return 0;
  }
  if(N>81){
    cout << "No";
    return 0;
  }
  for(int i=2;i<=9;i++){
    if(N%i==0 && N/i<10){
      cout << "Yes";
      return 0;
    }
  }
  cout << "No";
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int cnt[4];
int main()
{
	int n;
	string s;
	cin>>n;
	while (n--)
	{
		cin>>s;
		if (s=="AC")   cnt[0]++;
		if (s=="WA")   cnt[1]++;
		if (s=="TLE")   cnt[2]++;
		if (s=="RE")   cnt[3]++;
	}
	printf("AC x %d\n",cnt[0]);
	printf("WA x %d\n",cnt[1]);
	printf("TLE x %d\n",cnt[2]);
	printf("RE x %d\n",cnt[3]);
	return 0;
}

Measured memory_bytes: 3720
// ITP1_7_B
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
int calc(int n,int x){
    int ans=0;
    for(int i=1;i<=n-2;i++){
        for(int j=i+1;j<=n-1;j++){
            int num=x-(i+j);
            if(j+1<=num and num<=n)ans+=1;
        }
    }
    return ans;
}


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

    int n,x;
    cin>>n>>x;
    while(n!=0 or x!=0){
        cout<<calc(n,x)<<endl;
        cin>>n>>x;    
    }
    return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

#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 each(i, mp) for(auto& i:mp)

int main() {
  string s;
  cin >> s;
  string t;
  cin >> t;
  int counter = 0;
  rep(i, s.size()){
    if (s[i] == t[i]) counter++;
  }
  if (counter == s.size()) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3592
import java.util.Scanner;


public class Main {

	class Dice {
		int UP, LOW, BACK, FRONT, RIGHT, LEFT;
		public Dice() {
			UP = 1; LOW = 6; BACK = 2; FRONT = 5; RIGHT = 3; LEFT = 4;
		}
		public int moveNorth() {
			int temp = UP;
			UP = BACK; BACK = LOW; LOW = FRONT; FRONT = temp;
			return UP;
		}
		public int moveSouth() {
			int temp = UP;
			UP = FRONT; FRONT = LOW; LOW = BACK; BACK = temp;
			return UP;
		}
		public int moveEast() {
			int temp = UP;
			UP = LEFT; LEFT = LOW; LOW = RIGHT; RIGHT = temp;
			return UP;
		}
		public int moveWest() {
			int temp = UP;
			UP = RIGHT; RIGHT = LOW; LOW = LEFT; LEFT = temp;
			return UP;
		}
		public int rotateRight() {
			int temp = BACK;
			BACK = RIGHT; RIGHT = FRONT; FRONT = LEFT; LEFT = temp;
			return UP;
		}
		public int rotateLeft() {
			int temp = BACK;
			BACK = LEFT; LEFT = FRONT; FRONT = RIGHT; RIGHT = temp;
			return UP;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);


		int N = 0;
		while ((N = sc.nextInt()) != 0) {
			Dice dice = (new Main()).new Dice();
			sc.nextLine();
			long score = 1;
			for (int i = 0 ; i < N ; i++) {
				String com = sc.nextLine();
				if (com.equals("North")) score += dice.moveNorth();
				else if (com.equals("East")) score += dice.moveEast();
				else if (com.equals("West")) score += dice.moveWest();
				else if (com.equals("South")) score += dice.moveSouth();
				else if (com.equals("Right")) score += dice.rotateRight();
				else score += dice.rotateLeft();
			}
			System.out.println(score);
		}
	}
}

Measured memory_bytes: 36504
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 2e9;
 
unsigned int randxor() {
  static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned int t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
 
 
 
 
int main() {
  int D;
  cin >> D;
  vector<int> c(26);
  rep(i,26) cin >> c[i];
  vector<vector<int>> s(D + 1, vector<int>(26, 0));
  vector<vector<int>> last_day(D + 1, vector<int>(26, 0));
  vector<int> t(D);
  rep(i,D) rep(j,26) cin >> s[i + 1][j];
 
 
  int score = 0;
  auto Scoring = [&](int d, int id, int oid) {
    score += s[d][id];
  
    if (oid != -1) {
      t[d - 1] = id;
      score -= s[d][oid];
      for (int i = d; i <= D; i++) {
        if (last_day[i][oid] != d) break;
        last_day[i][oid] = last_day[i - 1][oid];
        score += c[oid] * (i - d);
        score -= c[oid] * (i - last_day[i][oid]);
      }
 
      for (int i = d; i <= D; i++) {
        if (last_day[i][id] == i) break;
        score += c[id] * (i - last_day[i][id]);
        last_day[i][id] = d;
        score -= c[id] * (i - last_day[i][id]);
      }
    } else {
      last_day[d][id] = d;
      for (int i = 0; i < 26; i++) {
        if (i != id) last_day[d][i] = last_day[d - 1][i];
        score -= c[i] * (d - last_day[d][i]); 
      }
    }
  };
 
  auto init = [&](){
    for (int i = 0; i < D; i++) {
      t[i] = i % 26;
    }
 
  };
  
  //初期解生成 
  init();
  
  rep(p, 5000000) {
 
    int d = randxor() % D;
    int change_q = randxor() % 26;    
    int old_q = t[d];
    int old_score = score;
    Scoring(d + 1, change_q, old_q);
    if (score < old_score) {
      Scoring(d + 1, old_q, change_q);
    }
  }
  
  rep(i,D) cout << t[i] + 1 << endl;
  return 0;
} 

Measured memory_bytes: 3748
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
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;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

/*constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;*/

using xy_t = complex<long double>;
using poly=vector<xy_t>;
 
poly dft(poly f, int n, int sgn){
    int bit_num = 0;
    while(1 << bit_num < n) ++bit_num;
    rep(i, n){
        int j = 0;
        rep(k, bit_num) j |= (i >> k & 1) << (bit_num - k - 1);
        if(i < j) swap(f[i], f[j]);
    }
 
    for(int k=1; k<n; k*=2){
        xy_t z_i = xy_t(1.0);
        xy_t z = polar(1.0, sgn * 2*M_PI / (2*k));
        rep(i, k){
            for(int j=0; j<n; j+=k*2){
                xy_t s = f[i+j];
                xy_t t = f[i+j+k] * z_i;
                f[i+j] = s + t;
                f[i+j+k] = s - t;
            }
            z_i *= z;
        }
    }
 
    return f;
}
 
poly idft(poly f, int n){
    f = dft(f, n, -1);
    rep(i, n) f[i] /= n;
    return f;
}
 
poly conv(poly g, poly h){
    int sz = g.size() + h.size() - 1;
    int n = 1;
    while(n < sz) n *= 2;
    g.resize(n);
    h.resize(n);
 
    g = dft(g, n, 1);
    h = dft(h, n, 1);
 
    poly f(n);
    rep(i, n) f[i] = g[i] * h[i];
    f = idft(f, n);
    return f;
}

lint powmod(lint x, lint n, lint mod){
    lint ret = 1;
    while(n){
        if(n & 1) (ret *= x) %= mod, --n;
        else (x *= x) %= mod, n >>= 1;
    }
    return ret;
}

int main(){
    int mod = 200003;
    int table[mod], pow_table[mod];
    table[0] = mod;
    for(int tmp=1, i=0; i<mod-1; ++i, (tmp *= 2) %= mod){
        table[tmp] = i;
        pow_table[i] = tmp;
    }

    int n;
    scanf("%d", &n);
    int a[n];
    poly x(mod, 0);
    rep(i, n){
        scanf("%d", &a[i]);
        x[table[a[i]]] += 1;
    }
    auto z = conv(x, x);

    lint ans = 0;
    rep(i, z.size()){
        lint t = (lint)(z[i].real()+0.5);
        if(t == 0) continue;
        ans += powmod(2, i, mod) * t;
    }
    rep(i, n) ans -= (lint)a[i] * a[i] % mod;
    printf("%lld\n", ans / 2);
}

Measured memory_bytes: 94152
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy, copy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

N, L = MAP()
S = [input() for _ in range(N)]
S.sort()
print("".join(S))

Measured memory_bytes: 5204
#include<bits/stdc++.h>
using namespace std;
typedef double db;
const db inf =1e9;
const int N=1e5+10;
struct Point{
    db x,y;
    void input(){scanf("%lf%lf",&x,&y);}
    db dis(Point p){return sqrt((p.x-x)*(p.x-x)+(p.y-y)*(p.y-y));}
}A[N];
bool cmp2(Point a,Point b){return a.y<b.y;}
db Closest(int l,int r){
    if(l==r)return inf;
    if(r==l+1)return A[l].dis(A[r]);
    int mid=(l+r)/2;
    db ans=min(Closest(l,mid-1),Closest(mid+1,r));
    vector<Point> V;V.push_back(A[mid]);
    int now=mid-1;while(now>=l&&A[mid].x-A[now].x<=ans)V.push_back(A[now]),--now;
    now=mid+1;while(now<=r&&A[now].x-A[mid].x<=ans)V.push_back(A[now]),++now;
    sort(V.begin(),V.end(),cmp2);
    now=0;
    for(int i=0;i<V.size();++i){
        while(now<V.size()&&V[now].y-V[i].y<=ans)++now;
        for(int j=i;j<now;++j)for(int k=j+1;k<now;++k)ans=min(ans,V[j].dis(V[k]));
    }
    return ans;
}
bool cmp(Point a,Point b){return a.x<b.x;}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;++i)A[i].input();
    sort(A+1,A+1+n,cmp);
    printf("%.10lf\n",Closest(1,n));
}


Measured memory_bytes: 7564
from math import ceil, floor

n = int(input())
ls = list(map(int, input().split()))
sqsm = 0
for i in range(n):
    sqsm += ls[i] * ls[i]
sm = sum(ls)
x1 = floor(sm / n)
x2 = ceil(sm / n)
print(min(sqsm + n * x1 * x1 - 2 * sm * x1, sqsm + n * x2 * x2 - 2 * sm * x2))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int N,M;
  cin>>N>>M;
  int ans=1;
  for(int i=1;i*i<=M;i++){
    int r=M/i;
    if(M%i!=0){continue;}
    if((int64_t)i*N<=M){ans=max(ans,i);}
    if((int64_t)r*N<=M){ans=max(ans,r);}
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3632
def f(n):
    if n%2 == 0:
        return n//2
    else:
        return 3*n + 1

L = [int(input())]

for i in range(10**10):
    L.append(f(L[i]))

    if L[i+1] in L[:i]:
        print(i+2)
        break


Measured memory_bytes: 2940
//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pb push_back
#define in insert
#define er erase
#define ct count
#define ep empty
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf = LLONG_MAX;
const int MOD = 1e9+7;
const double eps = 1e-6;
const double pi = acos(-1.0);
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; }return ans; }
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    ll X=x;
    x=y; y=X-a/b*y;
}
ll inv(ll x, int mod = MOD) { return qpow(x, mod - 2,mod); }
ll m_m(ll a){ return (a%MOD+MOD)%MOD; }


ll x[1005],y[1005],r[1005];
double c[1005][1005];
double lc[1005];
int vis[1005];
void dij(int n,int s){
    _for(i,0,n){
        lc[i]=inf;
        vis[i]=0;
    }
    lc[s]=0;
    _for(i,0,n){
        int k=-1;
        double mi=inf;
        _for(j,0,n){
            if(!vis[j]&&lc[j]<mi){
                mi=lc[j];
                k=j;
            }
        }
        if(k==-1)break;
        vis[k]=1;
        _for(j,0,n){
            if(!vis[j]&&lc[k]+c[k][j]<lc[j]){
                lc[j]=lc[k]+c[k][j];
            }
        }
    }
}
signed main() {
    //ifstream cin("E:\\acm dream\\in.in");
	//ofstream cout("E:\\acm dream\\out.out");
	FIO;
    #ifdef err
	double be = clock();
    #endif

    int sx,sy,ex,ey;cin>>sx>>sy>>ex>>ey;
    int n;cin>>n;
    x[0]=sx,y[0]=sy,r[0]=0,x[n+1]=ex,y[n+1]=ey,r[n+1]=0;
    _for(i,1,n+1){
        cin>>x[i]>>y[i]>>r[i];
    }
    n++;
    _for(i,0,n+1){
        _for(j,i+1,n+1){
            c[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-(r[i]+r[j]);
            if(c[i][j]<0)c[i][j]=0;
            c[j][i]=c[i][j];
        }
    }
    dij(n+1,n);
    cout<<fixed<<setprecision(9)<<lc[0];

    #ifdef err
	double en = clock();
    cout<<"time: "<<fixed<<setprecision(8)<<en-be;
    #endif
	return 0;
}

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

int main(){
int a, b, d, r;
double f;
cin >> a >> b;

d = a/b;
r = a%b;
f = (double)a/b;

cout << fixed << setprecision(15);
cout << d << " " << r << " " << f << endl;

return 0;
}



Measured memory_bytes: 3268
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <tuple>
#include <cassert>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

int main ()
{
    ll M; cin >> M;
    deque<ll> que;

    ll ans = 0;
    for (ll kai = 0LL; kai < M; kai++) {
        ll d,c;
        cin >> d >> c;
        c--;
        ll minus = (c / 9LL);
        ans += minus * (10LL + d - 1LL);
        c -= minus * 9LL;
        c++;
        for (ll j = 0; j < c; j++) {
            que.push_back(d);
        }
    }

    while (que.size() > 1LL) {
        ll a = que.front(); que.pop_front();
        ll b = que.front(); que.pop_front();
        ll c = a + b;
        ans++;
        if (c < 10) {
            que.push_front(c);
        } else {
            que.push_front(c % 10LL);
            que.push_front(c / 10LL);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 8464
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD 1000000007


int main (){
  long long X;
  cin>>X;
  for(long long i=-200;i<=200;i++){
    for(long long j=-200;j<=200;j++){
      if(pow(i,5)-pow(j,5)==X){
        cout<<i<<" "<<j;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 4012
#include<bits/stdc++.h>
using ll=long long;
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int k;
  cin>>k;
  for(int i =0;i<k;i++){
    if(a>=b)b=b*2;
    else if(b>=c)c=c*2;

  }
  if(a<b&&b<c)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


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

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

using namespace std;

int main(){
  string s;cin>>s;
  regex re("(.*keyence|k.*eyence|ke.*yence|key.*ence|keye.*nce|keyence|keyen.*ce|keyenc.*e|keyence.*)");
  smatch match;
  if( regex_match(s, match, re) ) cout<<"YES";
  else cout<<"NO";

  return 0;
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	ll N=in<ll>(),K=in<ll>();
	auto A=vecin<ll>(N);

	ll OK=accumulate(ALL(A),0LL)+1,NG=(*max_element(ALL(A)))-1;
	while(abs(NG-OK)>1){
		ll mid = (OK+NG)/2LL;
		
		ll num=0,sum=0;
		REP(i,N){
			if(sum+A[i]<=mid){
				sum += A[i];
			}
			else{
				sum = A[i];
				num++;
			}
		}
		if(num<K){
			OK = mid;
		}
		else{
			NG = mid;
		}
	}
	out(OK);
	return 0;
}



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

typedef long long int ll;

int main(){
  ll n,a,b,c,d; cin >> n >> a >> b >> c >> d;
  bool flag = false;
  for(long long int i=0;i<=n-1;i++){
  	if(a + (i*c) + (n-1-i)*(-d) <= b && b <= a + (i*d) + (n-1-i)*(-c)) flag = true;
  }
  if(flag) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
x = list(map(int, input().split()))

ans = float("inf")
for i in range(0, n-(k-1)):
    lr = abs(x[i]) + abs(x[i+k-1]-x[i])
    rl = abs(x[i+k-1]) + abs(x[i+k-1]-x[i])
    ans = min(lr, rl, ans)
print(ans)


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

using namespace std;

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

int main() {

  int N, M, A, B; cin >> N >> M >> A >> B;
  vector<int> D(N);
  rep(i, N) {
    cin >> D[i];
  }

  vector<int> box;
  rep(i, N) {
    if(D[i] >= A) {
      box.push_back(i);
    }
    else {
      break;
    }
  }

//  cout << box.size() << endl;

  vector<bool> not_use(box.size());

  if(D.size() - box.size() < M) {
    for(int i=box.size()-1; i>=0; i--) {
      if(D[box[i]] <= B) {
        not_use[i] = 1;
      }
      else {
        break;
      }
    }
  }

  int ans = 0;
  for(int i=0; i<not_use.size(); i++) {
    ans += not_use[i] == 0;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3148
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
// ?¨??????\???????????????????????????????????????
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int n = sc.nextInt();
        int[] values = new int[w];
        for (int i = 0; i < values.length; i++) {
            values[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            String[] ab = str.split(",");
            int a = Integer.parseInt(ab[0]) - 1;
            int b = Integer.parseInt(ab[1]) - 1;
            int temp=0;
            temp=values[a];
            values[a]=values[b];
            values[b]=temp;

        }
        for (int i = 0; i < values.length; i++) {
            System.out.println(values[i]);
        }


    }

}

Measured memory_bytes: 26152
from bisect import bisect
mod = 10**9+7
N,K = map(int,input().split())

c = []
for i in range(1,int(N**0.5)+1):
    c.append(i)
    c.append(int(N/i))
c = list(set(c))
c.sort()

k = []
for i in c:
    if int(N/i) != int(N/(i+1)):
        k.append(i)

dp = [[0]*len(k) for _ in range(K)]
for i in range(len(k)):
    dp[0][i]=k[i]

inv = [0]*(len(k)-1)
for i in range(len(k)-1):
    inv[i] = pow(k[i+1]-k[i],mod-2,mod)

index = [0]*len(k)
for i in range(len(k)):
    m = int(N/(k[i]+1))
    index[i] = bisect(k,m)

for i in range(K-1):
    dp[i+1][0] = dp[i][-1]
    for j in range(len(k)-1):
        m = int(N/(k[j]+1))
        l = index[j]
        S = dp[i][l-1]+(dp[i][l]-dp[i][l-1])*(m-k[l-1])*inv[l-1]
        dp[i+1][j+1] = dp[i+1][j]+(k[j+1]-k[j])*S
        dp[i+1][j+1] %= mod

print(dp[-1][-1])

Measured memory_bytes: 95412
# ABC091C - 2D Plane 2N Points (ARC092C)
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = sorted(
        [tuple(map(int, input().split())) for _ in range(N)],
        key=lambda x: x[1],
        reverse=1,
    )
    B = sorted([tuple(map(int, input().split())) for _ in range(N)])
    ans, memo = 0, set()
    for bx, by in B:
        for i, (ax, ay) in enumerate(A):
            if i not in memo and ax < bx and ay < by:
                ans += 1
                memo |= {i}
                break
    print(ans)


if __name__ == "__main__":
    main()


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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

constexpr ll MOD = 1e9 + 7;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N; cin >> N;
  ll K; cin >> K;
  vector<int> A(N); rep(i, N) cin >> A[i];
  ll ans = 0;
  rep(i, N) rep(j, i) if (A[j] > A[i]) ans++;
  ans *= K;
  ans %= MOD;
  rep(i, N) {
    ll c = 0;
    rep(j, N) if (A[j] > A[i]) c++;
    ans += c*(K*(K-1)/2 % MOD);
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

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

    int abcd;
    cin >> abcd;
    vector<int> a(4);
    for (int i = 0; i < 4; i++) {
        a[3 - i] = abcd % 10;
        abcd /= 10;
    }

    int i;
    for (i = 0; i <= 0b111; i++) {
        int sum = a[0];
        for (int j = 0; j < 3; j++) {
            sum += (i & 1 << j ? -a[j + 1] : a[j + 1]);
        }

        if (sum == 7) break;
    }

    cout << a[0];
    for (int j = 0; j < 3; j++) {
        cout << (i & 1 << j ? "-" : "+");
        cout << a[j + 1];
    }
    cout << "=7" << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

  int N;
  cin >> N;
  int a;
  int num_target = 0; // 3200 <=
  int bucket[8] = {0};

#define ADD(start, end, bid) \
  if ((start) <= a && a <= (end)) bucket[(bid)]++

  for (int i = 0; i < N; ++i) {
    cin >> a;

    ADD(1, 399, 0); // 灰
    ADD(400, 799, 1); // 茶
    ADD(800, 1199, 2); // 緑
    ADD(1200, 1599, 3); // 水
    ADD(1600, 1999, 4); // 青
    ADD(2000, 2399, 5); // 黄
    ADD(2400, 2799, 6); // 橙
    ADD(2800, 3199, 7); // 赤

    if (3200 <= a) {
      ++num_target;
    }
  }

  int num_colors = 0;
  for (int i = 0; i < 8; ++i) {
    if (bucket[i] > 0) ++num_colors;
  }

  const int min_colors = num_colors == 0 ? 1 : num_colors;
  const int max_colors = num_colors + num_target;

  cout << min_colors << " " << max_colors << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
using namespace std;
using i64 = long long;

i64 a,b,c;
int main(){
  cin >> a >> b >> c;
  i64 cnt = 0;
  if(c == 0){
    cnt = a;
  }
  else{
    cnt += max(0LL,(a - c)) * 2;
  }
  cout << fixed << setprecision(10) << 1.0 * (b - 1) * cnt / a / a << endl;
}


Measured memory_bytes: 256
import sys

N = int(input())
Cards = list(map(int, input().split()))
if N==2:
    print(abs(Cards[0] - Cards[1]))
    sys.exit()
B = sum(Cards) - Cards[0]
A = Cards[0]

del Cards[0]
del Cards[-1]
answer = 100000000

if N==2:
    print(abs(Cards[0] - Cards[1]))
    sys.exit()
for number in Cards:
    A += number
    B -= number
    if abs(A-B) < answer:
        answer = abs(A-B)

print(answer)

Measured memory_bytes: 23792
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)
#define EPS 10e-8

using namespace std;
typedef pair<llong, llong> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }


vector<ipair> split_sections(llong *arr, int length) {
    vector<ipair> res;
    llong cnt = 0;
    for(int i = 0; i < length; ++i)
        if(i == 0 || arr[i] == arr[i - 1])
            ++cnt;
        else {
            res.push_back(make_pair(arr[i - 1], cnt));
            cnt = 1;
        }
    res.push_back(make_pair(arr[length - 1], cnt));
    return res;
}

int N;
string S;
llong ch[100000];
int main(int argc, char **argv) {
    cin >> N >> S;
    for(int i = 0; i < N; ++i)
        ch[i] = S[i];

    vector<ipair> res = split_sections(ch, N);
    cout << res.size() << endl;
}

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 90000;

int h, w, d, a, q, l ,r;
pair<int, int> coord[MX];

int cost[MX];

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
    cin >> h >> w >> d;
    for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a; --a;
			coord[a] = {i, j};
		}
	}
	
	for (int i = 0; i < h * w; i++) {
		if (i < d) {
			cost[i] = 0;
		} else {
			int last = i - d;
			cost[i] = cost[last] + abs(coord[i].first - coord[last].first) + abs(coord[i].second - coord[last].second); 
			// cout << i <<  " " << cost[last] << " " << cost[i] << "\n";
		}
	}
    
    cin >> q;
    while(q--) {
		cin >> l >> r;
		--l; --r;
		cout << cost[r] - cost[l] << "\n";
	}
    return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(1e5) + 5;
constexpr double EPS = 1e-8;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()


int main() {
    ll n, m, dp[MAX_N]{};
    bool ng[MAX_N]{};
    cin >> n >> m;
    REP(i,m){
        int a;
        cin >> a;
        ng[a] = true;
    }
    dp[0] = 1;
    REP(i,n){
        if(ng[i])continue;
        dp[i+1] += dp[i];
        dp[i+1] %= MOD;
        dp[i+2] += dp[i];
        dp[i+2] %= MOD;
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 1152
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N],b[N],res;int q[N],n,s,id,t;
int main(){
	scanf("%d%d",&n,&s);
	fp(i,1,n){
		scanf("%lld%lld",&a[i],&b[i]);
		if(a[i]<s)id=i;
	}
	R int cnt=0,l=1,r=n;
	while((l<=id)!=(r<=id))
		b[l]>=b[r]?(b[l]+=b[r],q[++t]=a[r--]):(b[r]+=b[l],q[++t]=a[l++]);
	if(r<=id)fp(i,l,r)q[++t]=a[i];
	else fd(i,r,l)q[++t]=a[i];
	q[t+1]=s;
	fp(i,1,t)res+=abs(q[i]-q[i+1]);
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t,n,i,m=0;
	cin>>t>>n;
	int a[n],b[n];
	for(i=0;i<n;++i)cin>>a[i];
	for(i=0;i<n-1;++i)b[i]=a[i+1]-a[i];
	b[n-1]=t-a[n-1]+a[0];
	for(i=0;i<n;++i)m=max(m,b[i]);
	cout<<t-m;
	return 0;
}

Measured memory_bytes: 1792
"""
python3 c.py < input.txt
"""
import math
import itertools as it
import heapq

N,K=map(int, input().split())
S=input()
T=[S[0]]
U=[1]
for c in S[1:]:
    if c==T[-1]:
        U[-1]=U[-1]+1
    else:
        T.append(c)
        U.append(1) 
M=len(U)
V=[U[0]]
for i in range(1,M):
    V.append(V[-1]+U[i])

X=[]
for l in range(M):
    if T[l]=="0":
        ll=max(0, l-1)
        r=max(l, min(M-1, l+2*(K-1)+1))
        X.append((ll, r))
    else:
        X.append((0,0))
V=[0]+V
#print(T)
#print(U)
#print(V)
#print(X)
#print([([0]+V)[r+1]-([0]+V)[l] for (l,r) in X])
print(max([V[r+1]-V[l] for (l,r) in X]))

Measured memory_bytes: 18400
n_a, n_b, n_m = map(int, input().split())

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

price = [min(a) + min(b)]

for i in range(n_m):
    x, y, c = map(int, input().split())
    price.append(a[x-1]+b[y-1]-c)

print(min(price))

Measured memory_bytes: 73324
//#include <algorithm>
//#include <cstdio>
//#include <functional>
#include <iostream>
//#include <cfloat>
//#include <climits>
//#include <cstdlib>
//#include <cstring>
//#include <cmath>
//#include <map>
//#include <queue>
//#include <set>
//#include <sstream>
//#include <stack>
//#include <string>
//#include <time.h>
//#include <vector>
//#include <random>
//#include <unordered_set>
//#include <complex>
#define WAIT system ("pause")
#define rt0 return 0
using namespace std;
int main()
{
    int x,a,b,c,d;
    cin>>x;
    d=x%10;
    c=x/10%10;
    b=x/100%10;
    a=x/1000%10;
    if((a+b+c+d)==7) {cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7";WAIT;rt0;}
    if((a+b+c-d)==7) {cout<<a<<"+"<<b<<"+"<<c<<"-"<<d<<"=7";WAIT;rt0;}
    if((a+b-c+d)==7) {cout<<a<<"+"<<b<<"-"<<c<<"+"<<d<<"=7";WAIT;rt0;}
    if((a+b-c-d)==7) {cout<<a<<"+"<<b<<"-"<<c<<"-"<<d<<"=7";WAIT;rt0;}
    if((a-b+c+d)==7) {cout<<a<<"-"<<b<<"+"<<c<<"+"<<d<<"=7";WAIT;rt0;}
    if((a-b+c-d)==7) {cout<<a<<"-"<<b<<"+"<<c<<"-"<<d<<"=7";WAIT;rt0;}
    if((a-b-c+d)==7) {cout<<a<<"-"<<b<<"-"<<c<<"+"<<d<<"=7";WAIT;rt0;}
    if((a-b-c-d)==7) {cout<<a<<"-"<<b<<"-"<<c<<"-"<<d<<"=7";WAIT;rt0;}
    WAIT;
    rt0;
}

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

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB emplace_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n) cin >> a[i];
    ll max1 = -1, max2 = -1;
    REP(i, n){
        if(max1 <= a[i]){
            max2 = max1;
            max1 = a[i];
        }
        else if(max2 < a[i]) max2 = a[i];
    }
    REP(i, n){
        if(max1 != a[i]) cout << max1 << endl;
        else cout << max2 << endl;
    }
    return 0;
}

Measured memory_bytes: 4752
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <bitset>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};

int main(void){
    ll h, w;
    cin >> h >> w;
    ll n;
    cin >> n;
    ll b[n];
    for(ll i = 0; i < n; i++)
        cin >> b[i];
    vector<p> a;
    for(ll i = 0; i < h; i++){
        for(ll j = 0; j < w; j++){
            if(i%2==0)
                a.push_back(p(i, j));
            if(i%2!=0)
                a.push_back(p(i, w-j-1));
        }
    }
    vector<vector<ll>> ans(h, vector<ll>(w, 0));
    ll c = 0;
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < b[i]; j++){
            ll x = a[c].first, y = a[c].second;
            ans[x][y] = i+1;
            c++;
        }
    }
    for(ll i = 0; i < h; i++){
        for(ll j = 0; j < w; j++){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}


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

int main()
{
    int a,b,c;
    int goukei = 0;
    
    cin >> a >> b >> c;
    
    for(int i = a; i <= b; i++)
        if(c % i == 0) goukei++;
    
    cout << goukei << endl;
    
    return 0;
}


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

#define vec                vector<int>
#define vecll              vector<ll>
#define vecd               vector<double>
#define vecst              vector<string>
#define vecb               vector<bool>
#define vec2(var, n, m)    vector<vector<int>> var(n, vector<int>(m, 0))
#define vecll2(var, n, m)  vector<vector<ll>> var(n, vector<ll>(m, 0))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define f_sum(var)       accumulate(all(var), 0)
#define f_sumll(var)     accumulate(all(var), 0LL)
#define chmin(v1, v2)    v1 = min(v1, v2)
#define chmax(v1, v2)    v1 = max(v1, v2)
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
void prtok(bool ok){prt(ok ? "Yes" : "No");}
//----------------------------------------------------------------

int main(void) {
  int n, m;
  cin >> n >> m;
  arr(c,m);

  vec dp(n+1, 10000000);
  dp[0] = 0;
  rep(i,n){
    rep(j,m){
      if(i+1-c[j]>=0){
        dp[i+1] = min(dp[i+1], dp[i+1-c[j]] + 1);
      }
    }
  }

  prt(dp[n]);
}



Measured memory_bytes: 3176