akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


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

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

#define REP(i, n) for(ll i = 0; i < n; i++)
















int main(){
    ll a[3][3];
    REP(i, 3){
        REP(j, 3){
            cin >> a[i][j];
        }
    }
    ll n;
    cin >> n;
    bool ok[3][3] = {};
    REP(i, n){
        ll b;
        cin >> b;
        REP(j, 3){
            REP(k, 3){
                if(a[j][k] == b){
                    ok[j][k] = true;
                }
            }
        }
    }
    bool ok2 = false;
    REP(i, 3){
        bool f = true;
        REP(j, 3){
            if(!ok[i][j]){
                f = false;
            }
        }
        if(f){
            ok2 = true;
        }
    }
    REP(j, 3){
        bool f = true;
        REP(i, 3){
            if(!ok[i][j]){
                f = false;
            }
        }
        if(f){
            ok2 = true;
        }
    }
    bool f1 = true;
    REP(i, 3){
        if(!ok[i][i]){
            f1 = false;
        }
    }
    bool f2 = true;
    REP(i, 3){
        if(!ok[i][2 - i]){
            f2 = false;
        }
    }
    if(f1 || f2){
        ok2 = true;
    }
    if(ok2){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int gcd(int a,int b){
	while(a){
		b%=a;
		int c=a;
		a=b;
		b=c;
	}
	return b ;
}
int main(){
	int a;
	scanf("%d",&a);
	while(a--){
		int b,c;
		scanf("%d%d",&b,&c);
		int d=b*b+c*c;
		bool ok=false;
		for(int i=2;i*i<=d;i++){
			if(d%i==0){
				for(int k=0;k*k<=i;k++){
					int m=(int)(sqrt(i-k*k)+0.0000001);
					if(m*m+k*k!=i)continue;
					//printf("%d %d %d\n",m*b+k*c,m*c-k*b,m*m+k*k);
					if(gcd(m*b+k*c,m*c-k*b)%(m*m+k*k)==0)ok=true;
				}
			}
		}
		if(ok)printf("C\n");
		else printf("P\n");
	}
}

Measured memory_bytes: 1012
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner((System.in));
		String n = sc.next();
		String ans = "Yes";
		int sum = 0;

		for (int i = 0; i < n.length(); i++) {
			sum += Integer.valueOf(n.substring(i, i + 1));
		}
		
		if (Integer.valueOf(n) % sum != 0) {
			ans = "No";
		}
		
		
		System.out.println(ans);

		sc.close();
	}
}


Measured memory_bytes: 23764
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>

/* template start */

using i64 = std::int_fast64_t;
using u64 = std::uint_fast64_t;

#define rep(i, a, b) for (i64 i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()

#ifdef LOCAL
#define debug(...)                                                    \
  std::cerr << "LINE: " << __LINE__ << "  [" << #__VA_ARGS__ << "]:", \
      debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << std::endl; }

template <typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
  std::cerr << " " << h;
  if (sizeof...(t) > 0) std::cout << " :";
  debug_out(t...);
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)
    os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename Num>
constexpr Num mypow(Num a, u64 b, Num id = 1) {
  if (b == 0) return id;
  Num x = id;
  while (b > 0) {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

/* template end */

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

  i64 n;
  std::cin >> n;

  if (n == 0) {
    std::cout << 0 << "\n";
    return 0;
  }

  i64 cnt = 1;
  std::string ans;

  while (true) {
    debug(n);
    if (n == 0) break;
    i64 pow = 1ll << cnt;
    if (((n % pow + pow) % pow) != 0) {
      ans.push_back('1');
      if (cnt % 2)
        n -= pow / 2;
      else
        n += pow / 2;
    } else {
      ans.push_back('0');
    }
    cnt++;
  }

  std::reverse(all(ans));

  std::cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 3632
#include<cstdio>

#define reps(i,f,n) for(int i = f; i < int(n); i++)
#define rep(i,n) reps(i,0,n)
using namespace std;

int main(void){
	int x, ans = 0;
	
	rep(i,10){
		scanf("%d", &x);
		ans+=x;
	}
	
	printf("%d\n",ans);
	
	return 0;
}

Measured memory_bytes: 1028
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
const double TL = 1.5 * CLOCKS_PER_SEC;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define clr(x, y) memset(x, y, sizeof(x))
#define forn(i, n) for (int i = 0; i < n; i++)
#define LL long long
const double pi = acos(-1.0);

char g[1005][1005];
int d[1005][1005];
int n, m;
int xx1, yy1, xx2, yy2;
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};


int main() {
#ifdef LOCAL
  auto start_clock = clock();
  freopen("in", "r", stdin);
#endif

  scanf("%d%d", &n, &m);
  scanf("%d%d%d%d", &xx1, &yy1, &xx2, &yy2);
  xx1--;yy1--;xx2--;yy2--;
  for (int i = 0; i < n; i++) {
    scanf("%s", g[i]);
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      d[i][j] = 1e9;
    }
  }
  

  queue<pair<int, int>> q;
  d[xx1][yy1] = 0;
  q.push({xx1, yy1});

  while (q.size() > 0) {
    queue<pair<int, int>> h;
    while (q.size() > 0) {
      auto p = q.front();
      h.push(p);
      q.pop();
      for (int i = 0; i < 4; i++) {
        int nx = p.first + dx[i], ny = p.second + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == '.' && d[nx][ny] > d[p.first][p.second]) {
          d[nx][ny] = d[p.first][p.second];
          q.push({nx, ny});
        }
      }
    }
    while (h.size() > 0) {
      auto p = h.front();
      h.pop();
      int x = p.first, y = p.second;
      for (int i = -2; i <= 2; i++) {
        for (int j = -2; j <= 2; j++) {
          int nx = x + i, ny = y + j;
          if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == '.' && d[nx][ny] > d[x][y] + 1) {
            d[nx][ny] = d[x][y] + 1;
            q.push({nx, ny});
          }
        }
      }
    }
  }
  
  if (d[xx2][yy2] == 1e9) puts("-1");
  else printf("%d\n", d[xx2][yy2]);

#ifdef LOCAL
 auto end_clock = clock();
 cout << "Time:" << (end_clock - start_clock) * 1.0 / CLOCKS_PER_SEC << endl;
#endif
  return 0;
}

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

const int hell = 1e9+7;

int32_t main(){
	int n,k;
	cin>>n>>k;
	vector<int>dp(k+1,0);
	dp[0] = 1;
	for(int i=0;i<n;i++){
		int candies;
		cin>>candies;
		vector<int>prefix(k+1,0);
		for(int j=k-1;j>=0;j--){
			int l = j+1;
			int r = min(k,candies+j);
			if(r+1<=k) (prefix[r+1] += hell - dp[j])%=hell;
			( prefix[l] += dp[j] )%= hell;	
		}
		int prefix_sum = 0;
		for(int j=0;j<=k;j++){
			( prefix_sum += prefix[j] )%=hell;
			( dp[j] += prefix_sum )%= hell;
		}
	}
	cout<<dp[k]<<endl;
	return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		scan.close();
		for(int i = 0; i <= 25; i++) {
			for(int j = 0; j <= 14; j++) {
				int t = 4 * i + 7 * j;
				if(t == N) {
					System.out.println("Yes");
					System.exit(0);
				}
				if(t > 100) {
					break;
				}
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N, M, A[1 << 17], B[1 << 17], pre[1 << 17], low[1 << 17], cnts;
vector<int> G[1 << 17]; vector<pair<int, int>> E;

void dfs(int pos, int prevs) {
	cnts++; pre[pos] = cnts; low[pos] = cnts;

	for (int i = 0; i < G[pos].size(); i++) {
		if (pre[G[pos][i]] == 0) {
			dfs(G[pos][i], pos);
			if (low[G[pos][i]] == pre[G[pos][i]]) {
				int u1 = pos, u2 = G[pos][i]; if (u1 > u2) swap(u1, u2);
				E.push_back(make_pair(u1, u2));
			}
			low[pos] = min(low[pos], low[G[pos][i]]);
		}
		else {
			if (G[pos][i] != prevs) low[pos] = min(low[pos], low[G[pos][i]]);
		}
	}
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d", &A[i], &B[i]);
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	dfs(1, 0);
	sort(E.begin(), E.end());
	for (int i = 0; i < E.size(); i++) printf("%d %d\n", E[i].first, E[i].second);
	return 0;
}


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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#include <set>
#define all(x) (x).begin(),(x).end()

const int MOD = 1e9 + 7;

void solve(){

}
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << min(b/a,c) << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		int temp = 0;
		Scanner s = new Scanner(System.in);
		int sort[] = new int[3];
		int num1 = s.nextInt();
		int num2 = s.nextInt();
		int num3 = s.nextInt();
		s.nextLine();
		sort[0] = num1;
		sort[1] = num2;
		sort[2] = num3;
		if ((num1 >= 1 && num1 <= 10000) && (num2 >= 1 && num2 <= 10000) && (num3 >= 1 && num3 <= 10000)) {
			for (int i = 0; i < sort.length; i++) {
				for (int j = i + 1; j < sort.length; j++) {
					if (sort[i] > sort[j]) {
						temp = sort[i];
						sort[i] = sort[j];
						sort[j] = temp;

					}
				}

			}
			System.out.print(sort[0]);
			System.out.print(" ");
			System.out.print(sort[1]);
			System.out.print(" ");
			System.out.println(sort[2]);
			

		}

	}

}

Measured memory_bytes: 26112
n,m=map(int, input().split())
x_list=[int(i) for i in input().split()]

x_list.sort()

differ_list=[]

for i in range(m-1):
    differ_list.append(x_list[i+1]-x_list[i])
    
if n>=m:
    ans=0
else:
    differ_list.sort(reverse=True)
    ans=sum(differ_list[n-1:])
    
print(ans)

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

int main()
{
    int n,sum=0,i,j,k,r,m;
    cin>>n;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            for(k=1;k<=n;k++){
            r=__gcd(i,j);
            m=__gcd(r,k);
            sum=sum+m;
            }
        }
    }
    cout<<sum<<" ";
}

Measured memory_bytes: 3596
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }


int main(){
    double a, b, x;
    cin >> a >> b >> x;
    x /= a;
    if(x >= a*b*0.5){
        cout << setprecision(16) << atan2((a*b-x)*2 / a, a) * 180 / M_PI << endl;
    }else{
        cout << setprecision(16) << atan2(b, x*2 / b) * 180 / M_PI << endl;
    }
    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int A1 = scan.nextInt();
		int A2 = scan.nextInt();
		int A3 = scan.nextInt();
		scan.close();
		
		int max = 0;
		int mid = 0;
		int min = 0;
		if (A1 > A2) {
			max = A1;
			min = A2;
		} else {
			max = A2;
			min = A1;
		}
		
		if (max < A3) {
			max = A3;
			mid = max;
		} else {
			mid = A3;
		}
		
		if (mid < min) {
			int tmp = mid;
			mid = min;
			min = tmp;
		}
		
		int ans1 = 0;
		ans1 = mid - max;
		if (ans1 < 0) {
			ans1 = ans1 * -1;
		}
		
		int ans2 = 0;
		ans2 = min - mid;
		if (ans2 < 0) {
			ans2 = ans2 * -1;
		}
		System.out.print(ans1 + ans2); 
	}
}


Measured memory_bytes: 22612
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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 (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll n, a, b, c, d;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>a>>b>>c>>d;
    if(d*(n-1)<abs(a-b)){
            return NO,0;
    }
    ll sa=d-c;
    ll centers=2*c;
    ll atumi=1;
    ll block=1;
    for(int i=0;i<n-1;i++){
        if(i!=0){
        centers-=sa;
        }
        atumi+=sa;
        block++;
    }
    if(centers<=0){
        return YES,0;
    }
    //cout<<atumi<<" "<<centers<<"\n";
    ll le=abs(a-b);
    ll kyori;
    ll tani=centers+atumi-1;
    if(n%2){
        kyori=atumi/2;
        if(le<=kyori){
            return YES,0;
        }
        ll amari=(le-kyori)%tani;
        if(amari==0){
            return YES,0;
        }
        if(amari<centers){
            return NO,0;
        }
        return YES,0;
    }
    else{
        kyori=centers/2;
        if(le<kyori){
            return NO,0;
        }
        ll amari=(le-kyori)%tani;
        if(amari<atumi){
            return YES,0;
        }
        return NO,0;
    }
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
using static Func;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	uint[] GU => Strs.Select(uint.Parse).ToArray();
	decimal[] GD => Strs.Select(decimal.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	static T[] ConstantArray<T>(int n, T val) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = val; return a; }
	static T[] MakeArray<T>(int n, Func<int, T> f) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = f(i); return a; }
	static T[] Recurse<T>(int n, T a0, Func<int, T, T> f) { var a = new T[n]; a[0] = a0; for (var i = 1; i < n; i++) a[i] = f(i, a[i - 1]); return a; }
	static T[] Accumulate<T>(IList<T> a, T zero, Func<T, T, T> f) { var s = new T[a.Count + 1]; s[0] = zero; for (var i = 0; i < a.Count; i++) s[i + 1] = f(s[i], a[i]); return s; }
	static ulong One(int k) => 1ul << k;
	static ulong All(int k) => One(k) - 1;
	static bool Has(ulong s, int k) => (s & One(k)) != 0;
	const int MOD = 1000000007;
	public K()
	{
		//SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var I = G;
		WriteLine((I[1] + I[0] * 3) / 2);
	}
}
static class Func { }


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

using namespace std;

int main()
{
  int N, M, X; cin >> N >> M >> X;
  vector<int> cost(N+1, 0);
  for (int i = 0; i < M; ++i) {
    int x; cin >> x;
    cost[x]++;
  }


  cout << min(accumulate(cost.begin() + X, cost.end(), 0),
              accumulate(cost.begin(), cost.begin() + X, 0));

}

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

int main(){
  int64_t K;
  cin >> K;
  int64_t x = 100;
  int y = 0;
  
  while(x < K){
    x += x / 100;
    y++;
  }
  
  cout << y << endl;
  
  return 0;
  
}

Measured memory_bytes: 3632
#include <bits/stdc++.h> 
using namespace std; 
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,n) for (int i = 0; i < (n); ++i)

int main(void) {
    io;
    string a, t;
    cin >> a >> t;
    sort(a.begin(), a.end());
    sort(t.rbegin(), t.rend());
    cout << ((a < t)?"Yes":"No");
    return 0;
}



Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200200;
long long tr[maxn<<2], lazy[maxn<<2];
void push(int id, int l, int r){
  if(lazy[id]){
    tr[id] += lazy[id];
    if(l != r){
      lazy[id<<1] += lazy[id];
      lazy[id<<1|1] += lazy[id];
    }
    lazy[id] = 0;
  }
}
void add(int id, int l, int r, int x, int y, long long v){
  push(id, l, r);
  if(l > y || r < x) return;
  if(x <= l && r <= y) {
    lazy[id] += v;
    push(id, l, r);
    return;
  }
  int mid = (l + r)>>1;
  add(id<<1, l, mid, x, y, v);
  add(id<<1|1, mid + 1, r, x, y, v);
  tr[id] = max(tr[id<<1], tr[id<<1|1]);
}
long long sum(int id, int l, int r, int x, int y){
  push(id, l, r);
  if(l > y || r < x) return (-(1ll<<60));
  if(x <= l && r <= y) return tr[id];
  int mid = (l + r)>>1;
  return max(sum(id<<1, l, mid, x, y), sum(id<<1|1, mid + 1, r, x, y));
}
vector<pair<int,int> > upd[maxn];
int main(){
  int n, m; cin >> n >> m;
  vector<long long> psum(n + 2, 0);
  for(int i = 0; i < m; i++){
    int l, r, w; cin >> l >> r >> w;
    upd[l].push_back({r, -w});
    upd[r + 1].push_back({l, w});
    psum[l] += w;
    psum[r + 1] -= w;
  }
  for(int i = 2; i <= n; i++) psum[i] += psum[i - 1];
  long long ans = 0;
  for(int i = 1; i <= n; i++){
    for(auto j : upd[i]) add(1, 0, n, min(i, j.first), max(i - 1, j.first), j.second);
    long long now = sum(1, 0, n, 0, i - 1) + psum[i];
    ans = max(ans, now);
    add(1, 0, n, i, i, now);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 25216
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

int H, W, D, Q;
int A[301][301];
int dp[300 * 300 + 1];
int L[100000], R[100000];

int main(int argc, char* argv[]) {
  cin >> H >> W >> D;

  unordered_map<int, pair<int, int>> map;
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      cin >> A[i][j];
      map[A[i][j]] = make_pair(i, j);
    }
  }
  cin >> Q;
  for (int i = 0; i < Q; i++)
    cin >> L[i] >> R[i];

  for (int i = 1; i <= H * W; i++) {
    if (i <= D) {
      dp[i] = 0;
    } else {
      auto prev = map[i - D];
      auto present = map[i];
      dp[i] = dp[i - D] + abs(present.first - prev.first) +
              abs(present.second - prev.second);
    }
  }

  for (int i = 0; i < Q; i++)
    cout << dp[R[i]] - dp[L[i]] << endl;

  return 0;
}

Measured memory_bytes: 8340
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

template<typename T> bool chmin(T& a, const T& b) {
    if (a > b) return a = b, true; else return false;
}

template<typename T> bool chmax(T& a, const T& b) {
    if (a < b) return a = b, true; else return false;
}

// End of template.

int main() {
    cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cin.read(buf, sizeof buf); // 注意: ./a.out < in か pbp | ./a.out で入力すること

    int n;
    cin >> n;
    int64 ans = 0;

    rep(i, n + 1) {
        if (i % 3 != 0 && i % 5 != 0) ans += i;
    }

    print(ans);

    return 0;
}



Measured memory_bytes: 3640
/* be name khoda */

// #define stream_enable
#define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

#ifdef stream_enable
#define cin sss
#endif
#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

const ll MOD = 1000000007;
const long long BIG = 1446803456761533460;
const int Big = 336860180;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debugp(x) cout << #x << " -> " << "(" << (x).F << ", " << (x).S << ")" << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugap(x, n) cout << #x << " ->\n"; fori (i1_dap, n) { cout << "(" << (x)[i1_dap].F << ", " << (x)[i1_dap].S << ")\n"; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl
#define debugav(x, n) cout << #x << " ->\n"; fori (i1_dav, n) { fori (i2_dav, (x)[i1_dav].size()) { cout << (x)[i1_dav][i2_dav] << ' '; } cout << '\n'; } cout << endl
#define debugia(x, n) cout << #x << " ->\n"; fori (i1_dia, n) { cout << i1_dia << " : " << (x)[i1_dia] << '\n'; } cout << endl

#define forifrom(i, s, n) for(ll i = (s); i < (n); ++i)
#define forirto(i, n, e) for(ll i = (n) - 1; i >= (e); --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

stringstream sss;

// -----------------------------------------------------------------------

const ll maxn = 100010;

ll N, T, E;
ll X[maxn];
ll dp[maxn], pmn[maxn];

void MAIN() {

    cin >> N >> E >> T;
    fori (i, N) cin >> X[i + 1];
    dp[N] = E - X[N];
    pmn[N] = dp[N] + X[N] * 3;
    pmn[N + 1] = BIG;
    ll ptr = N;
    forir (i, N) {
        while ((X[ptr] - X[i + 1]) * 2 > T) --ptr;
        dp[i] = T + dp[ptr] + X[ptr] - X[i + 1];
        smin(dp[i], pmn[ptr + 1] - X[i + 1] * 3);
        dp[i] += X[i + 1] - X[i];
        pmn[i] = min(pmn[i + 1], dp[i] + X[i] * 3);
    }
    cout << dp[0] << '\n';

}

// -----------------------------------------------------------------------

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(10);
    sss << R"(
5 100 1000
4 10 30 40 50

3 9 3
1 3 8
    )";
    MAIN();
    return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
#pragma warning(disable:4996)
int main() {
	char S[4];
	scanf("%s", S);
	if(S[0] == S[1] && S[1] != S[2] && S[2] == S[3]) printf("Yes");
	else if(S[0] != S[1] && S[1] == S[2] && S[0] == S[3]) printf("Yes");
	else if(S[1] == S[3] && S[0] == S[2] && S[0] != S[1]) printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define itn int
#define nibu(K,x) binary_search(K.begin(),K.end(),x)
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define out(x) cout<<x<<endl
#define put(x) out(x)
#define in(x) cin>>x
#define maxx(a,b,c) max(a,max(b,c))
#define minn(a,b,c) min(a,min(b,c))
using ll = long long;
using vl = vector<ll>;
using vs = vector<string>;
const double pi = 3.14159265358979;
const ll mod = 1000000007;

int main() {
 int A,B,C;
  in(A>>B>>C);
  int a = maxx(A,B,C);
  int c = minn(A,B,C);
  int b = (A+B+C)-a-c;
  int ans;
  if(c%2==b%2){
   ans = (b-c)/2+(a-b); 
  }
  else if(a%2 == c%2){
   ans = (a-c)/2 + (a-b+1)/2 +1; 
  }
  else if(b%2 == a%2){
   ans = (a-b)/2 + (a-c+1)/2  +1; 
  }
  out (ans);
}


Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

from itertools import permutations
l = []
for pp in permutations(range(1, n+1)):
    ll = []
    for _p in pp:
        ll.append(_p)
    l.append(str(ll))

a = l.index(str(p))
b = l.index(str(q))
print(abs(a - b))


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

using ll = long long;
#define mod 9

int main(){

	string s;
	cin >> s;
	int ans=0;
	for(int i=0;i<s.length();i++){
		ans=ans+(s[i]-'0');
		ans=ans%mod;
	}
	if(ans==0){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
}


Measured memory_bytes: 3724
#include <iostream>

using namespace std;

int main()
{
   int N,T;
   
   cin >> N >> T;
   int *c = new int[ N+1 ];
   int *t = new int[ N+1 ];
   c[0]=1001;
   t[0]=1001;
   
   for(int i=1 ; i<=N  ;i++){
       cin >> c[i] >> t[i];
       
       if(t[i]<=T && c[i]<c[0]){
           c[0]=c[i];
           t[0]=t[i];
           
       }
       
   }
   
   
   if(t[0]<1001){
       cout << c[0] << endl; 
       
   }
   else{
   
         cout << "TLE" << endl; 
       
   }
   
   
   
   delete[] c;
   delete[] t;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int a,b,c,d;
  cin >>a>>b>>c>>d;
  if(a+b>c+d){
   cout<<"Left"<<endl; 
  }else if (a+b==c+d){
   cout<<"Balanced"<<endl;
  }else{
    cout<<"Right"<<endl;
  }

}

Measured memory_bytes: 256
from collections import deque

n = int(input())
C = [[] for _ in range(n)]
for _ in range(n-1):
    s,t,w = map(int,input().split())
    C[s].append((t,w))
    C[t].append((s,w))

INF = 10000000000

def BFS(start):
    D = [INF]*n
    q = deque()
    visited = [False]*n
    q.append(start)
    visited[start] = True
    D[start] = 0
    while q:
        node = q.pop()
        visited[node] = True
        for adj,w in C[node]:
            if D[node] + w < D[adj]:
                D[adj] = D[node] + w
            if not visited[adj]:
                q.append(adj)
    return D

D = BFS(0)
max_ind1 = D.index(max(D))
D = BFS(max_ind1)
print(max(D))

        





Measured memory_bytes: 46260
#include <bits/stdc++.h>
using namespace std;
#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL);

int main() {
  FAST;
  string S;
  cin >> S;
  int len = S.size();
  for (int i = 0; i < len; i++) {
    cout << "x";
  }
  cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n,m,c=0;
cin>>n>>m;
if(n*2<=m){
c+=n;
m-=n*2;
c+=m/4;
}else{
c+=m/2;
}
cout<<c;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    string s;
    cin>>s;
    bool ok=true;
    rep(i,s.size()){
        if(i%2){
            ok&=(s[i]!='R');
        }
        else ok&=(s[i]!='L');
    }
    cout<<(ok?"Yes":"No")<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

void warshall_floyd(int n, vector<vector<int>> &dist){
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

int main(){
    while(1){
        int n; cin>>n;
        if(n == 0) return 0;
        vector<vector<int>> dist(20, vector<int>(20, 1e9));
        for(int i=0; i<20; i++){
            dist[i][i] = 0;
        }

        int town=0;
        for(int i=0; i<n; i++){
            int a, b, c; cin>>a>>b>>c;
            dist[a][b] = c;
            dist[b][a] = c;
            chmax(town, max(a, b));
        }

        warshall_floyd(10, dist);

        int ans=1e9;
        int ansid;
        for(int i=0; i<=town; i++){
            int sum=0;
            for(int j=0; j<=town; j++){
                sum += dist[i][j];
            }

            if(sum < ans){
                ans = sum;
                ansid = i;
            }
        }

        cout << ansid << " " << ans << endl;
    }
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(void){
  int h,w,i,j,di[4]={1,0,-1,0},dj[4]={0,1,0,-1};
  bool b[1010][1010]={false};
  string g[1010];
  queue<P> que;
  cin >> h >> w;
  for (i=0;i<h;i++) cin >> g[i];
  for (i=0;i<h;i++) for (j=0;j<w;j++){
    if (g[i][j]=='#'){
      que.push(P(i,j));
      b[i][j]=true;
    }
  }
  
  int qs,t=0,ni,nj;
  P y;
  while (!que.empty()){
    qs=que.size();
    for (i=0;i<qs;i++){
      y=que.front();
      que.pop();
      for (j=0;j<4;j++){
        ni=y.first+di[j];
        nj=y.second+dj[j];
        if (ni<0 || ni>=h || nj<0 || nj>=w) continue;
        if (!b[ni][nj]){
          b[ni][nj]=true;
          que.push(P(ni,nj));
        }
      }
    }
    t++;
  }
  cout << t-1 << endl;
  return 0;
}

Measured memory_bytes: 10512
#include<bits/stdc++.h>
#define fastio     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x)   cerr<<#x<<": "<<x<<endl;
#define all(x)     (x).begin() , (x).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl       '\n'
#define MAX        1000000
typedef long long int ll;
using namespace std;


const ll mod = 1e9+7;
const double eps = 1e-9;


vector<int>cost,value;
int h , n;
int dp[10001][1002]; 

int recur(int ind,int w) {
    if(ind==0&&w>0)return 1e9;
    else if(ind>=0&&w<=0)return 0;

    if(dp[w][ind]!=-1)return dp[w][ind];

    int first=recur(ind,w-cost[ind-1])+value[ind-1];
    int second=recur(ind-1,w);
    return dp[w][ind]=min(first,second);
}

void show(int a,int b){
    for(int i=0;i<=a;i++) {
        for(int j=0;j<=b;++j) {
            cout<<dp[i][j]<<"  ";
        }
        cout<<endl;
    }
}

void solve(){
    cin>>h>>n;
    cost.resize(n+1);
    value.resize(n+1);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++) {
        cin>>cost[i]>>value[i];
    }
    cout<<recur(n,h)<<endl;
}


void sec() {
    ll n,d,a;
    cin>>n>>d>>a;
    vector<pair<ll,ll>>arr(n);
    map<ll,ll>res;
    for(int i=0;i<n;i++) {
        cin>>arr[i].first>>arr[i].second;
    }
    sort(all(arr));
    int end=0;
    ll ans=0;
    for(int start=0;start<n;start++) {
        while(end<n&&arr[end].first<=arr[start].first+2*d){
            end++;
        }
        ll req=max((arr[start].second-res[start]*a+a-1)/a,0LL); 
        ans+=req;
        res[start]+=req;
        res[end]-=req;
        res[start+1]+=res[start];
    }
    cout<<ans;
}



int main(){
    fastio
    int test=1;
    while(test--)
        sec();
    return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
 
// headers {{{
using namespace std;
// using namespace rel_ops;
 
typedef long long int64;
typedef unsigned long long uint64;
const double pi=acos(-1.0);
const double eps=1e-11;
const int INF=0x7FFFFFFF;
template<class T> inline bool checkmin(T &a,T b){return b<a?a=b,1:0;}
template<class T> inline bool checkmax(T &a,T b){return b>a?a=b,1:0;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define mem(a,b) memset(a, b, sizeof(a))
#define clr(a) memset(a, 0, sizeof(a))
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ff first
#define ss second
#ifdef LOCAL
#define dbg(args...) printf(args); //##__VA_ARGS__
#define dout cout
#define out(x) (cout<<#x<<": "<<x<<endl)
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
#else
#define dbg(...)
#define dout if(true);else cout
#define out(...)
#define show(...)
#endif
// }}}

int main() {
    int a, b;
    while (cin >> a >> b) 
        cout << a*b<<endl;
    return 0;
}



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

int main(){
  int64_t A, B, K; cin >> A >> B >> K;
  if(A>=K){
    cout << A-K << " " << B << endl;
    return 0;
  }
  int64_t C=B-K+A;
  if(C<0){
    C=0;
  }
  cout << 0 << " " << C << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<list>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;

int main(){
	double D,A,x=0,y=0,r=0;
	while(scanf("%lf,%lf",&D,&A),D||A){
		x += D*sin(r/180*M_PI);
		y += D*cos(r/180*M_PI);
		r += A;
	}
	printf("%d\n%d\n",(int)x,(int)y);
}

Measured memory_bytes: 1216
#include<iostream>
using namespace std;
int main(){
  int n; cin >> n;
  int t[101];
  for(int i=0;i<n;i++) cin >> t[i+1];
  int m; cin >> m;
  for(int i=0;i<m;i++){
    int time=0;
    int p,x; cin >> p >> x;
    int tt = t[p];
    t[p] = x;
    for(int i=1;i<=n;i++) time += t[i];
    cout << time << endl;
    t[p] = tt;
  }
  return 0;
}

Measured memory_bytes: 768
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
// constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

//     int root(int x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

typedef vector<vector<ll>> Matrix;

ll MOD;

void matunit(Matrix &A) {
    for (int i=0;i<3;i++) A[i][i] = 1;
}

void matmul(Matrix &A, Matrix B) {
    Matrix C(vector<vector<ll>>(3,vector<ll>(3,0LL)));
    for (int i=0;i<3;i++) for (int j=0;j<3;j++) for (int k=0;k<3;k++) C[i][j] = (C[i][j] + (A[i][k]%MOD) * (B[k][j]%MOD) % MOD) % MOD;
    for (int i=0;i<3;i++) for (int j=0;j<3;j++) A[i][j] = C[i][j];
}

void matpow(Matrix &M, ll e) {
    Matrix B(vector<vector<ll>>(3,vector<ll>(3)));
    for (int i=0;i<3;i++) for (int j=0;j<3;j++) B[i][j] = M[i][j];
    Matrix C(vector<vector<ll>>(3,vector<ll>(3,0LL)));
    matunit(C);
    while (e) {
        if (e & 1) {
            matmul(C,B);
        }
        e >>= 1;
        matmul(B,B);
    }
    for (int i=0;i<3;i++) for (int j=0;j<3;j++) M[i][j] = C[i][j];
}

int digit(ll x) {
    int ans = 0;
    while (x) {
        x /= 10;
        ans++;
    }
    return ans;
}

int main(void) {
    ll L, A, B, M;
    cin >> L >> A >> B >> M;
    MOD = M;

    // 各桁数の要素数を求める
    vector<ll> N(20,0), F(20,0);
    ll base = 1, v = A, w = L;
    // v は各桁数の最小値, w は残り要素数
    for (int i=1;i<=19;i++) {
        base *= 10;
        if (v < base && w > 0) {
            N[i] = min(w,(base-v+B-1)/B);
            F[i] = v;
            v += B*N[i];
            w -= N[i];
        }
    }

    // 行列を累乗
    vector<Matrix> X(20,vector<vector<ll>>(3,vector<ll>(3)));
    base = 1;
    for (int i=1;i<=19;i++) {
        base *= 10;
        X[i][0][0] = base;
        X[i][0][1] = 1;
        X[i][1][1] = 1;
        X[i][1][2] = B%MOD;
        X[i][2][2] = 1;
        matpow(X[i],N[i]);
    }

    // 行列積
    Matrix E(vector<vector<ll>>(3,vector<ll>(3)));
    matunit(E);
    for (int i=19;i>0;i--) matmul(E,X[i]);
    // for (int i=0;i<3;i++) {
    //     for (int j=0;j<3;j++) cout << E[i][j] << " ";
    //     cout << endl;
    // }

    vector<ll> V(3,0LL);
    V[1] = A%MOD; V[2] = 1LL;
    ll ans = 0;
    for (int i=0;i<3;i++) ans = (ans + E[0][i] * V[i] % MOD) % MOD;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n,k;
	cin>>n>>k;
	ll s,p,r;
	cin>>s>>p>>r;
	string t;
	cin>>t;
	ll ans=0;
	for(ll i=0;i<n;i++){
		if(i<k){
			if(t[i]=='s'){
				ans+=s;
			}
			else if(t[i]=='p'){
				ans+=p;
			}
			else{
				ans+=r;
			}
		}
		else{
			if(t[i-k]==t[i]){
				t[i]='n';
				continue;
			}
			if(t[i]=='s'){
				ans+=s;
			}
			else if(t[i]=='p'){
				ans+=p;
			}
			else{
				ans+=r;
			}			
		}
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <vector>
#include <bits/stdc++.h>
#include <math.h>
#include <stack>
#define pb push_back
// #define pop pop_back
#define ll long long int
#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rep2(i, a, b) for (ll i = a; i <= b; i++)
#define repr(i, a, b) for (ll i = a; i >= b; i--)
#define I long_max
#define pii pair<int, int>
#define pll pair<long, long>
#define vpair vector<pair<int, int>>
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fir first
#define sec second
#define d (int)1e9 + 7
#define INF (int)2e9 + 1
#define el "\n"
#define fs fastscan

#define vrep(vec) for (const auto &value : vec)
#define arep(arrat) for (const auto &value : array)
using namespace std;

bool sortinrev(const pair<int, int> &a,
               const pair<int, int> &b)
{
    return (a.first > b.first);
}
void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//over

bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

int dfs(int n, vector<vector<int>> &adj, vector<bool> &check, vector<vector<ll>> &final1, int last)
{
    // if (n == target)
    // {
    //     check[target] = true;
    //     return final;
    // }
    for (int j = 0; j < adj[last].size(); j++)
    {
        if (adj[last][j] != 0 && !check[j])
        {
            check[j] = true;
            final1[n][j] = final1[n][last] + adj[last][j];
            dfs(n, adj, check, final1, j);
        }
        // if (check[target])
        // {
        //     return a;
        // }
    }
    return 0;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //use auto instead of data types
    // int t;
    // cin >> t;
    // while (t--)
    {
     int n;
     cin>>n;
     vector<int> a(n);
     rep(i,n){
         cin>>a[i];
     }
     vector<int> dp(n,0);
     for(int i = 1;i<n;i++){
        //  dp[i] = dp[0] + abs(a[i] - a[0]);
        if(i>=2){
         dp[i] = min(dp[i-1] + abs(a[i] - a[i-1]),dp[i-2] + abs(a[i] - a[i-2]));
        }
        else{
            dp[i] = dp[i-1] + abs(a[i] - a[i-1]);
        }
     }
     cout<<dp[n-1]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3940
let () =
  let h, w = Scanf.scanf "%d %d" (fun h w -> h, w) in
  let a = Array.init h (fun _ -> Scanf.scanf " %s" (fun s -> s)) in
  String.init (w+2) (fun _ -> '#') |> print_endline;
  Array.iter (Printf.printf "#%s#\n") a;
  String.init (w+2) (fun _ -> '#') |> print_endline


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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll ans = 0;
    rep(i, n) {
        cin >> a[i];
        ans += a[i]-1;
    }
    cout << ans << endl;
}


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

int main(){
    int w,h,x,y,r;
    cin >> w >> h >> x >> y >> r;
    bool ans = true;
    
    if(x + r > w || x - r < 0 || y + r > h || y - r < 0){
        ans = false;
    }
    
    if(ans == true){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    


}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll mod = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int main() {
  ll a, b, n;
  cin >> a >> b >> n;
  ll x = n;
  if (x >= b-1) x = b-1;
  ll ans = a*x/b - a*(x/b);
  cout << ans << endl;
  return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
	for(auto &a : A) cin >> a;

    ll ans = 0;
    ll left = 0, right = 0;
    ll xor_sum = 0, sum = 0;

	for(left=0;left<N;left++) {
		while(right < N) {
			if((sum + A[right]) == (xor_sum ^ A[right])) {
				sum += A[right];
				xor_sum ^= A[right];
				right++;
			} else {
				break;
			}
		}
		ans += (right - left);
		sum -= A[left];
		xor_sum -= A[left];
		if(left == right) right++;
	}

    cout << ans << endl;
}

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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

string str;
int N;
void no(){
	cout << "-1\n";
}
bool can(){
	forn(i,1,N){
		if(str[i-1] != str[N-i-1])return false;
	}
	return true;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> str;
	N = str.size();
	if(!can() || str[N-1] == '1' || str[0] == '0' || str[N-2] == '0'){
		no();
		return 0;
	}
	int mitad = (N&1) ? (N-1)/2 : N/2;
	int ant = 0;
	int ac = 0;
	int cnt = 1;
	forn(i,1,mitad+1){
		if(str[i-1] == '0')continue;
		int root = cnt;
		while(ac < i){
			cout << root << ' ' << cnt+1 << '\n';
			cnt++;
			ac++;
		}
	}
	int root = cnt; cnt++;
	while(1){
		if(cnt > N)break;
		cout << root << ' ' << cnt << '\n';
		cnt++;
	}
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


Measured memory_bytes: 1616