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

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

int main() {
  string S;
  cin >> S;
  if ((S[0] == S[1] && S[2] == S[3] && S[0] != S[2]) || (S[0] == S[2] && S[1] == S[3] && S[0] != S[1]) || (S[0] == S[3] && S[1] == S[2] && S[0] != S[1])) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
};


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

int main()
{
  int x;

  cin >> x;

  int maxi=1;
  
  for(int b=2;b <= x;b++){
    int sum = b*b;
    while(sum <= x){ 
      maxi = max(maxi,sum);
      sum *= b;
    }
  }
  cout << maxi << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		long d = Integer.parseInt(sc.next());
		long[] x = new long[n];
		long[] y = new long[n];
		for(int i = 0; i < n; i++) {
			x[i]  = Integer.parseInt(sc.next());
			y[i]  = Integer.parseInt(sc.next());
		}
		int sum = 0;
		for(int i =  0; i < n; i++) {
			if(d*d >= x[i]*x[i] + y[i]*y[i]) {
				sum++;
			}
		}
		System.out.println(sum);
	}

	
	
}



Measured memory_bytes: 54672
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;

signed main(){
  int k;cin>>k;
  int array[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout<<array[k-1]<<endl;
  return 0;
}


Measured memory_bytes: 256
package main

import (
        "fmt"
)

func main() {
        var n, h, mh, cnt int
        fmt.Scanf("%d", &n)

        for i := 0; i < n; i++ {
                fmt.Scanf("%d", &h)
                if mh <= h {
                        cnt++
                        mh = h
                }
        }
        fmt.Println(cnt)
}


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

typedef long long ll;
#define SZ(a) (int)a.size()
#define PB push_back
//#define cerr if(false)cerr
#define print(x) cerr<<"\n" << (#x) << " is " << (x) << endl;



int32_t main(){
	int n;
	cin >> n;
	vector<int> v(n);
	for(auto &i : v)
		cin >> i;
	bool f = true;
	for(auto x : v){
		if(x % 2) continue;
		if((x % 3 == 0) || (x % 5 == 0)) continue;
		f = false;
		break;
	}
	if(f) cout << "APPROVED" << endl;
	else cout << "DENIED" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <random>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
long H[100000];
void Calc(){
	int N = rei();
	for(int i=0;i<N;i++){
		H[i] = rei();
	}
	bool OK = true;;
	for(int i=N-2;i>=0;i--){
		if(H[i] > H[i+1]){
			if(H[i] > H[i+1]+1){
				OK = false;
				break;
			}
			H[i]--;
		}
	}
	if(OK){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

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

int main()
{
  vector<i64> e(12);
  for (i64 i = 0; i < 12; i++)
    cin >> e[i];
  sort(e.begin(), e.end());
  bool ok = true;
  for (i64 i = 0; i < 3; i++)
    for (i64 j = 0; j < 4; j++)
      if (e[i * 4] != e[i * 4 + j])
        ok = false;
  if (ok)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
  return 0;
}



Measured memory_bytes: 3144
N = int(input())
r0, r1 = int(input()), int(input())
if r0 < r1:
    mint = r0
else:
    mint = r1
d = r1 - r0
for c in range(N-2):
    rj = int(input())
    dj = rj - mint
    if dj > d:
        d = dj
    if rj < mint:
        mint = rj
print(d)


Measured memory_bytes: 5620
n = int(input())
s = list(map(int, input().split()))
s.sort()

A = max(s)
dp = [0] * (A + 5)

for ss in s:
    dp[ss] += 1

pairwise = True
setwise = True

for i in range(2, A + 1):
    cnt = 0
    for j in range(i, A + 1, i):
        cnt += dp[j]
    if cnt > 1:
        pairwise = False
    if cnt >= n:
        setwise = False
        break

if pairwise:
    print("pairwise coprime")
elif setwise:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 194948
#include <cstdio>
#include <utility>
using namespace std;

using i64 = long long;

#define REP(i, stop) for (int i = 0, i##_len = stop; i < i##_len; ++i)

i64 D[2][13];
const i64 M = 1000000007;
signed main() {
	D[0][0] = 1;
	int p = 0;
	while(true) {
		char c = getchar_unlocked();
		if (c == '\n') {
			break;
		} else if (c == '?') {
			REP(r, 13) {
				i64 s = 0;
				REP(j, 10) {
					s += D[p][(j - r + 13) * 9 % 13];
				}
				D[p ^ 1][r] = s % M;
			}
		} else {
			i64 d = c - '0';
			REP(r, 13) {
				D[p ^ 1][r] = D[p][(d - r + 13) * 9 % 13];
			}
		}
		p ^= 1;
	}
	printf("%d", D[p][5]);
}


Measured memory_bytes: 128
s = input()
res = 1
i = 1
while i < len(s)-2:
  if s[i] == s[i-1]:
    i += 3
    res += 2
  else:
    res += 1
    i += 1
if i == len(s):
  print(res)
elif i == len(s)-1:
  if s[-1] == s[-2]:
    print(res)
  else:
    print(res+1)
elif i == len(s)-2:
  if s[-1] == s[-2]:
    print(res+1)
  else:
    if s[-1]==s[-2] or s[-2] == s[-3]:
      print(res+1)
    else:
      print(res+2)

Measured memory_bytes: 3500
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}


int main() {
	int n;
	cin >> n;
	vector<double> a(n);
	rep(i, n) cin >> a[i];
	vector<vector<double>> dp(n+1, vector<double>(n+1, 0));
	dp[0][0] = 1;
	rep(i,n){
		rep(j,i+2){
			if(j){
				dp[i + 1][j] = dp[i][j - 1] * a[i] + dp[i][j] * (1 - a[i]);
			}
			else
				dp[i + 1][j] = dp[i][j] * (1 - a[i]);
		}
	}
	double ans = 0;
	rep2(i,n/2+1,n+1){
		ans += dp[n][i];
	}

	cout << fixed << setprecision(10) << ans << endl;

	return 0;
}

Measured memory_bytes: 70784
N, K = map(int, input().split())
tree = list(map(int, input().split()))
left = 0
right = max(tree)

while right - left > 1:
    cnt = 0
    mid = (right + left) // 2
    for i in tree:
        cnt += i // mid
        if i % mid == 0:
            cnt -= 1  # ちょうどに切れるときは切り口が1減る
    if K >= cnt:
        right = mid
    else:
        left = mid

print(right)


Measured memory_bytes: 30856
n = int(input())
3 <= n <= 10000
for i in range(n) :
    if (i + 1) % 3 == 0 :
        print(" " + str(i + 1), end = "")
    else :
        x = i + 1
        while (x) :
            if x % 10 == 3 :
                print(" " + str(i + 1), end = "")
                break
            x //= 10
print()


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

int main(void)
{
	int red = 0, blue = 0, mini = 0;
	string s;
	cin >> s;
	size_t size = s.length();
	for (int i = 0; i < size; i++)
	{
		if (s[i] == '0') { red += 1; }
		else { blue += 1; }
	}
	cout << min(red, blue) * 2 << endl;

	return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<pair<ll, ll> > vec;
  for (int i = 1; i <= N; i++) {
    int a, b;
    cin >> a >> b;
    vec.push_back(make_pair(b, a));
  }
  sort(vec.begin(), vec.end(), greater<pair<ll, ll> >());

  priority_queue<ll> pq;
  set<ll> s;
  ll sum = 0;
  for (int i = 0; i < K; i++) {
    sum += vec[i].first;
    if (s.count(vec[i].second)) {
      pq.push(-vec[i].first);
    } else {
      s.insert(vec[i].second);
    }
  }

  ll ans = sum + s.size() * s.size();
  for (int i = K; i < N && !pq.empty(); i++) {
    if (s.count(vec[i].second)) {
      continue;
    }
    sum += pq.top();
    pq.pop();
    sum += vec[i].first;
    s.insert(vec[i].second);
    ll tmp = sum + s.size() * s.size();
    ans = max(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5232
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>

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

int main() {
  ll N, t;
  cin >> N;
  vector<ll> a(N);
  rep(i, N){
    cin >> t;
    a[i] = t - i - 1;
  }
  sort(a.begin(), a.end());
  // 中央値を求める
  ll mid;
  if (N % 2 == 0) mid = (a[N/2]+a[N/2-1])/2;
  else mid = a[N/2];

  // 合計を求める
  ll ans = 0;
  rep(i, N){
    ans += abs(a[i] - mid);
  }
  cout << ans << endl;

}


Measured memory_bytes: 1792
N = int(input())
p_list = list(map(int, input().split()))

swap = 0
result = True
for i in range(1, N + 1):
    if p_list[i - 1] != i:
        swap += 1
    if swap > 2:
        result = False
        break

if result:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define all(v) v.begin(), v.end()

const ll mod=1000000007;

int countBits(int in){
  int res=0;
  for(int i=0;i<10;i++){
    int msk=1<<i;
    if((in&msk)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

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);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string outputYesNo(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  char a,b;cin>>a>>b;
  char ans;
  if(a==b){
    ans='H';
  }else{
    ans='D';
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    int n;
    cin>>n;
    vector<int> b(n,0);
    rep(i,n){
        cin>>b[i];
    }
    vector<int> res(n,0);
    int cnt=n-1;
    while(true){
        if(b.empty()){break;}
        int cur=b.size()-1;
        while(cur>=0&&b[cur]-1!=cur){
            cur--;
        }
        if(cur<0){break;}
        res[cnt]=b[cur];
        b.erase(b.begin()+cur);
        cnt--;
    }
    if(!b.empty()){cout << -1 << endl;}
    else{
        rep(i,n){
            cout << res[i] <<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    abc084b()
}

fun abc084b() {
    val (a, b) = readLine()!!.split(" ").map { it.toInt() }
    val s = readLine()!!

    val pre = s.substring(0 until a)
    val mid = s.substring(a until a + 1)
    val aft = s.substring(a + 1 until s.length)

    val answer = if (pre.all { it in '0'..'9' } && mid == "-" && aft.all { it in '0'..'9' }) {
        "Yes"
    } else {
        "No"
    }

    println(answer)
}


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

using namespace std;
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) reverse((a).begin(), (a).end())
#define rep(i, a, b) for (int64_t i = (a); i < (b); ++i)
const int MOD = 1e9 + 7;
typedef long long ll;
// const long long INF = 1LL << 60;
const int INF = 1000000000;
using Graph = vector<vector<int>>;
// typedef pair<int, int> pair;

int main() {
  ll n, k, s;
  cin >> n >> k >> s;
  for (int i = 0; i < k; i++) {
    cout << s << " ";
  }
  if (k == 1 && n == 1000000000) {
    for (int i = 0; i < n - k - 1; i++) cout << 1 << " ";
    cout << 2 << endl;
  } else if (s == 1000000000) {
    for (int i = 0; i < n - k; i++) cout << 1 << " ";
  } else {
    for (int i = 0; i < n - k; i++) cout << 1000000000 << " ";
  }
  cout << endl;
}


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

const int N = 505;

pair <int, int> b[N];
int cnt[N];
int a[N * N];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> b[i].first;
		b[i].second = i;
		a[b[i].first] = i;
	}
	sort(b + 1, b + n + 1);
	int t = 1, p = 1;
	for (int i = 1; i <= n * n; i++) {
		if (a[i]) {
			cnt[a[i]]++;
			if (cnt[a[i]] != a[i]) {
				cout << "No";
				return 0;
			}
			continue;
		}
		while (t <= n && cnt[b[t].second] >= b[t].second - 1) {
			t++;
		}		
		if (t <= n) {
			a[i] = b[t].second;
			cnt[a[i]]++;
		}
		else {
			while (cnt[b[p].second] == n) {
				p++;
			}
			a[i] = b[p].second;
			cnt[b[p].second]++;
		}
	}
	cout << "Yes" << endl;
	for (int i = 1; i <= n * n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}


Measured memory_bytes: 2176
#include <iostream>
#include <array>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <cmath>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
	mint operator+(const mint a) const { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= a; }
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint& operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
} comb(2000005);

mint g(int r, int c) {
	return comb(r + c + 2, r + 1) - 1;
}

int main()
{
	int a1, a2, a3;
	cin >> a1 >> a2 >> a3;
	cout << ((a1 + a2 + a3 >= 22) ? "bust" : "win");
}


Measured memory_bytes: 31488
from sys import stdin
import sys
import math
import random
from decimal import Decimal
import itertools as it

N = int(input())
# for i in range(1,N+1):
f = [0 for i in range(N)]
# print(f)
for x in range(1, 101):
    x2 = x**2
    for y in range(1, 101):
        y2 = y**2
        for z in range(1, 101):
            a = x2+y2+z**2+x*y+y*z+x*z
            if a <= N:
                f[a-1] += 1
            else:
                break
for i in f:
    print(i)


Measured memory_bytes: 10424
#include<iostream>
using namespace std;
int main(void){
    int a[100],list[4] ={0,0,0,0},i,j;
    for(i = 1; i <= 10; i++){
        cin >> a[i];
        if(list[1] < a[i]){
            list[3] = list[2];
            list[2] = list[1];
            list[1] = a[i];
        }
        else if(list[2] < a[i]){
            list[3] = list[2];
            list[2] = a[i];
        }
        else if(list[3] < a[i]){
            list[3] = a[i];
        }
    }
    for(j = 1; j <= 3; j++){
        cout << list[j] << endl;
    }
}


Measured memory_bytes: 3068
n,y = map(int,input().split())
flag = 0
yuki = 0
while True:
  if yuki * 10000 > y:
    break
  ichi = 0
  while True:
    h = (y - yuki * 10000 - ichi * 5000) // 1000
    if h < 0:
      break
    if h == n - yuki - ichi:
      print(str(yuki) + ' ' + str(ichi) + ' ' + str(h))
      flag = 1
      break
    ichi += 1
  yuki += 1
  if flag == 1:
    break
if flag == 0:
  print('-1 -1 -1')

Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
//#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

ll l,a,b,MOD;

//aは正方行列
vector<vector<ll>> matpow(vector<vector<ll>> a, ll b){
	vector<vector<ll>> ret;
	rep(i,a.size()){
		ret.push_back(vector<ll>());
		rep(j,a.size()){
			ret[i].push_back(0);
		}
	}
	if(b == 0){
		rep(i,a.size()){
			ret[i][i] = 1;
		}
	}else if(b%2==0){
		vector<vector<ll>> memo = matpow(a, b/2);
		rep(i,a.size()){
			rep(j,a.size()){
				rep(h,a.size()){
					ret[i][j] += memo[i][h] * memo[h][j] % MOD;
					ret[i][j] %= MOD;
				}
				
			}
		}
	}else{
		vector<vector<ll>> memo = matpow(a, b - 1);
		rep(i,a.size()){
			rep(j,a.size()){
				rep(h,a.size()){
					ret[i][j] += a[i][h] * memo[h][j] % MOD;
					ret[i][j] %= MOD;
				}
			}
		}
	}

	return ret;
}

vector<ll> matmulti(vector<vector<ll>> A, vector<ll> b){// A * b
	vector<ll> ret;
	//返すベクトルの次元数 = Aの行数
	rep(i,A.size()){
		ret.push_back(0);
	}
	rep(i,A.size()){
		rep(h,b.size()){
			ret[i] += A[i][h] * b[h] % MOD;
			ret[i] %= MOD;
		}
	}
	return ret;
}

ll howketa(ll x){
	ll ret = 0;
	ll x_ = a + b*x;
	//cout<<x_<<"hoge"<<endl;
	while(true){
		x_ /= 10;
		ret++;
		if(x_ == 0) break;
	}
	return ret;
}

ll ketabegin(ll keta){
	ll start = -1;
	ll end = l;
	while(end - start >= 2){
		ll aida = (start + end) / 2;
		if(howketa(aida) >= keta){
			end = aida;
		}else{
			start = aida;
		}
	}
	//cout<<end<<endl;
	return end;
}

ll ketaend(ll keta){
	ll start = -1;
	ll end = l;
	while(end-start >= 2){
		ll aida = (start + end) / 2;
		if(howketa(aida) <= keta){
			start = aida;
		}else{
			end = aida;
		}
	}
	//cout<<start<<endl;
	return start;
}

int main(void){
	
	cin>>l>>a>>b>>MOD;
	vector<ll> vec;
	vec.push_back(0);
	vec.push_back(a%MOD);
	vec.push_back(a%MOD);
	vec.push_back(b%MOD);
	vector<vector<ll>> F;
	F.push_back(vector<ll>{1,0,0,1});
	F.push_back(vector<ll>{1,10,1,1});
	F.push_back(vector<ll>{0,0,1,0});
	F.push_back(vector<ll>{0,0,0,1});
	ll start,end;
	bool first = true;
	reps(i,18){
		start = ketabegin(i);
		end = ketaend(i);
		if(howketa(0) > i || howketa(l-1) < i) continue;
		if(first){
			start++;
			first = false;
		}

		F[1][1] = (ll)pow((ll)10, i)%MOD;

		vector<vector<ll>> F2 = matpow(F,end-start+1);
		vec = matmulti(F2, vec);

	}
	cout<<vec[1]<<endl;
	return 0;
}


Measured memory_bytes: 892
N, W = map(int, raw_input().split())
v = [0]*N
w = [0]*N
for i in xrange(N):
    v[i], w[i] = map(int, raw_input().split())
dp = [0] * (W+1)
for i in xrange(N):
    for j in xrange(W, w[i]-1, -1):
        dp[j] = max(dp[j-w[i]] + v[i], dp[j])
print dp[W]

Measured memory_bytes: 6572
#include <iostream>
#include <vector>

/*動的計画法で解く*/
int main(){
	int a, b;
	while(std::cin >> a >> b){
		if(a == 0 && b == 0){
			break;
		}
		int n;
		std::cin >> n;
		std::vector<std::vector<int> > dp(a, std::vector<int>(b, 1));
		//工事中の点に0をいれる
		int x, y;
		for(int i = 0; i < n; ++i){
			std::cin >> x >> y;
			//端が工事中になればその北と東を全て0にする
			if(y == 1){
				for(int i = x - 1; i < a; ++i){
					dp[i][y - 1] = 0;
				}
			}
			else if(x == 1){
				for(int i = y - 1; i < b; ++i){
					dp[x - 1][i] = 0;
				}
			}
			//端じゃないときはその点だけ0にする
			else{
				dp[x - 1][y - 1] = 0;
			}
		}
		//(2,2)から処理する
		for(int i = 1; i < a; ++i){
			for(int j = 1; j < b; ++j){
				if(dp[i][j] != 0){
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
			}
		}
		std::cout << dp[a - 1][b - 1] << std::endl;
	}
}

Measured memory_bytes: 1216
//                             ¯\_(ツ)_/¯   
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mma,ava,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define ll long long
 
 
void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
 
const int N=2e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;
std::vector<int> c(26);
int D;
std::vector<int>last(26);
std::vector<vector<int>>s;
int go(int indx,int S,int depth){
	if(indx == D || depth == 2)return S;
	
	for(int j=0;j<26;j++){
		S-=c[j]*(indx-last[j]);
	}
	int mx = 0;
	for(int j=0;j<26;j++){
		int takeback = s[indx][j] + c[j]*(indx-last[j]);
		mx = max(mx,go(indx+1,S+takeback,depth+1));
	}
	return mx;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();
	scanf("%d",&D);
	
	for(int i=0;i<26;i++)scanf("%d",&c[i]);
	s = vector<vector<int>>(D,vector<int>(26));
	for(int i = 0;i<D;i++){
		for(int j=0;j<26;j++){
			scanf("%d",&s[i][j]);
		}
	}
	int S = 0;
	
	for(int i=0;i<D;i++){
		for(int j=0;j<26;j++){
			S-=c[j]*(i-last[j]);
		}
		int who = 1;
		int mx = 0;
		int take = 0;
		for(int j=0;j<26;j++){
			int takeback = s[i][j] + c[j]*(i-last[j]);
			int wa = go(i+1,S+takeback,0);
			if(mx < wa){
				mx = wa;
				take = takeback;
				who = j+1;
			}
		}
		last[who-1] = i;
		S+= take;
		printf("%d\n",who );
	}
}

Measured memory_bytes: 3812
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)


int main(void){
    char a[1000],b[1000];

    scanf("%s%s",a,b);

    if(strlen(a) > strlen(b)){
        printf("GREATER\n");
    }else if(strlen(a) < strlen(b)){
        printf("LESS\n");

    }else{
        int i;
        for(i = 0;i < strlen(a);i++){
            if(a[i] > b[i]){
                printf("GREATER\n");break;
            }else if(a[i] < b[i]){
                printf("LESS\n");break;
            }
        }
        if(i == strlen(a))
            printf("EQUAL\n");
    }
    return 0;
}

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

int main(){
  int N, i;

  cin >> N >> i;

  cout << N - i + 1 << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define cout16 cout << setprecision(16) 
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
#define REV(A) reverse(A.begin(),A.end())
typedef long long int ll;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vll = std::vector<ll>;
using vvll = std::vector<std::vector<ll>>;
using P = std::pair<int,int>;
using vp = std::vector<P>;
using namespace std;
#define INF 1001001001
#define LL_INF 1001001001001001001
#define fi first
#define se second

int main(void) {
	int n; cin >> n;
	vi a(n); rep(i,n) cin >> a[i];
	vi dp(n,0);
	int m = 0;
	vi boxidx;
	for(int i=n-1; i>=0; i--){
		int sum = 0;
		for(int j=i+(i+1); j<n; j+=i+1){
			sum += dp[j];
		}
		sum %= 2;
		int c = a[i]^sum;
		dp[i] = c;
		if(c){
			m++;
			boxidx.push_back(i+1);
		}
	}
	REV(boxidx);
	cout << m << endl;
	rep(i,m) cout << boxidx[i] << endl;
}




Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double max=0;
        double min=99999999;
        while(sc.hasNext()){
        	double h=sc.nextDouble();
        	if(h>max)max=h;
        	if(min>h)min=h;
        }
        System.out.println(max-min);
    }
}

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

int main() {

	int N;
	cin >> N;

	string  S;
	cin >> S;
	int c;
	cin >> c;
	char C;

	C = S.at(c - 1);
	

	for (int i = 0; i < N; i++) {
		if (S.at(i) != C) {
			S.at(i) = '*';
		}
	}
	cout << S << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main() {
    ll A[6];
    rep(i,3){
        cin >> A[i];
    }
    sort(A,A+3);
    cout << (A[0]+A[1]==A[2] ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define tcase int _; cin >> _; while(_--)
const int MOD = 1e9+7;
const int MAX = 1e6;

string s;

void solve() {
	cin >> s;
	cout << s;
	if(s.back() == 's') cout << "es\n";
	else cout << "s\n";	
}	

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

 	solve();

  	return 0;
}



Measured memory_bytes: 3648
#include<stdio.h>
#define LEN 2000010
#define ALEN 10000

int n, C[LEN+1];

void Counting(int A[],int B[] ,int k){
  int i,j;
  for(i=0;i<=k;i++) C[i] = 0;

  for(j=1;j<=n;j++) C[A[j]]++;

  for(i=1;i<=k;i++) C[i] = C[i] + C[i-1];

  for(j=n;j>0;j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
}


int main(){
  int A[LEN],B[LEN];
  int i,k=0;
  scanf("%d",&n);
  for(i=1;i<n+1;i++) scanf("%d",&A[i]);
  for(i=1;i<n+1;i++){
    if(k<A[i]) k=A[i];
  }
  Counting(A,B,k);

  for(i=1;i<n+1;i++){
    if(i!=1) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");

  return 0;
}



Measured memory_bytes: 17360
function syukusyou(yx){
   var cnt=0;
   yx=yx.filter(v=>{
      var flag = v.every(val=> val==".");
      if(!flag){
         cnt=0;
         return true;
      }else if(flag && cnt==0){
         cnt++;
         return true;
      }else {
         return false;
      }
   });
   return yx;
}

function kaiten(yx){
   return  yx[0].map((a, i) => yx.map(b => b[i]));
}

function saikiY(y,x,d){
   if(yx[y][x] != ".")return yx[y][x];
   else if(y+d!=-1 && y+d!=h)return saikiY(y+d,x,d);
   else return ".";
}

function saikiX(y,x,d){
   if(yx[y][x]!=".")return yx[y][x];
   else if(x+d!=-1 && x+d!=w)return saikiX(y,x+d,d);
   else return ".";
}

function kesu(y,x){
   var arr= [saikiY(y,x,1),saikiY(y,x,-1),saikiX(y,x,1),saikiX(y,x,-1)];
   var a = arr.filter(function (x, i, self) {
      if(x==".")return false;
      return self.indexOf(x) === i && i !== self.lastIndexOf(x);
   });
   a.forEach(v=> replaceFn(y,x,v));
   return a.length*2;
}

function replaceFn(y,x,s){
   for(var i=0;i<h;i++){
      if(yx[i][x]==s)yx[i][x]=".";
   }
   for(var i=0;i<w;i++){
      if(yx[y][i]==s)yx[y][i]=".";
   }
}

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
var yx = arr.slice(1).map(v=> v.split(""));
yx=syukusyou(yx);
yx=kaiten(yx);
yx=syukusyou(yx);
var h=yx.length;
var w=yx[0].length;
var sum=0;
while(true){
   var flag=false;
   yx.forEach((ary,y)=>{
      ary.forEach((v,x)=>{
         if(v=="."){
            var add = kesu(y,x);
            if(add != 0)flag=true;
            sum += add;
         }
      });
   });
   if(!flag)break;
}
console.log(sum);


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

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int64_t> v(n);
	int64_t sum = 0;
	int64_t minn = 1e9 + 7;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		sum += abs(v[i]);
		minn = min(minn, abs(v[i]));
	}
	int neg = 0;
	for (int i = 0; i < n; ++i) {
		if (v[i] < 0) {
			neg = (neg == 0);
		}
	}
	if (neg) {
		cout << sum - 2 * minn;
	}else {
		cout << sum;
	}
}


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

using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<int> num(N + 1);
  priority_queue<pair<int,int>> que;
  for (int i = 0; i < Q; ++i) {
    int a, v;
    cin >> a >> v;
    num[a] += v;
    que.emplace(num[a], -a);
    while (num[-que.top().second] != que.top().first) que.pop();
    cout << -que.top().second << " " << que.top().first << endl;
  }
  return 0;
}

Measured memory_bytes: 7688
n = int(input())
li = []
for _ in range(n):
    li.append(list(map(int, input().split())))

ans = 'Yes'
t0, x0, y0 = 0, 0, 0
for t, x, y in li:
    d = abs(x - x0) + abs(y - y0)
    if d > t - t0 or d % 2 != (t - t0) % 2:
        ans = 'No'
        break
    t0, x0, y0 = t, x, y

print(ans)

Measured memory_bytes: 27380
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int Q;
    static int H;
    static int S;
    static int D;
    static int N;

    public static void main(String[] args) {
        FastScanner fc = new FastScanner(System.in);
        Q = fc.nextInt();
        H = fc.nextInt();
        S = fc.nextInt();
        D = fc.nextInt();
        N = fc.nextInt();
        System.out.println(solve());
    }

    static long solve() {
        int DQ = Q * 8;
        int DH = H * 4;
        int DS = S * 2;
        int DD = D;

        int cheap = Math.min(Math.min(Math.min(DQ, DH), DS), DD);
        if( DQ == cheap ) {
            return (long)N * 4 * Q;
        } else if( DH == cheap ) {
            return (long)N * 2 * H;
        } else if( DS == cheap ) {
            return (long)N * S;

        } else {
            if( N % 2 == 0 ) {
                return (long)N / 2 * D;

            } else {
                long ans = (long)N / 2 * D;
                int cheap2 = Math.min(Math.min(DQ, DH), DS);
                if( DQ == cheap2 ) {
                    return ans + 4 * Q;
                } else if( DH == cheap2 ) {
                    return ans + 2 * H;
                } else {
                    return ans + S;
                }
            }
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 22612
N = int(input())
A, B = map(int, input().split())
P = list(map(int, input().split()))

low, middle, high = 0, 0, 0
for i in range(N):
    if P[i] <= A:
        low += 1
    elif P[i] <= B:
        middle += 1
    else:
        high += 1
print(min(low, middle, high))


Measured memory_bytes: 3060
int main()
{
    int N,a,b;
    scanf("%d",&N);
    if(10<=N && N<=99)
    {
    b=abs(N%10);
    a=abs(N/10);
    if(9 == a || 9 == b){
        printf("\nYes\n");
    }
    else printf("\nNo\n");
    }
return 0;
}

Measured memory_bytes: 1660
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<set>
#include <valarray>
#include<stack>
#include<sstream>
#include<math.h>
 
using namespace std;
 
void Solution()
{
    string n;
   
    
    while(cin>>n)
    {
        int sum = 0;
       
        if(n == "0") break;
        
        for(int i = 0; i < (int)n.size(); i++)
        {
            sum += n[i] - '0';
        }
        cout<<sum<<endl;   
    }
    
}
 
int main()
{
    Solution();
    return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;


int main(){;
    int N;
    // vector<int> H;
    cin >> N;
    int ans = 0;
    int data;
    int Max = 0;

    for(int i = 0; i < N; i++){
        cin >> data;
        if(data >= Max){
            ans++;
            Max = data;
        }
    }

    cout << ans << endl;

}


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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

using namespace std;
using ll = double;
using pii = pair<int, int>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<int> a(n);
    ll pro = 1;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        pro *= a[i];
    }
    ll sum = 0;
    for(int i = 0; i < n; ++i){
        sum += pro / a[i];
    }
    cout << (double)pro / sum << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

int64 calc(int64 *x,int *v,int n,int64 c){
  int64 max=0;
  int64 sum=0;
  int i;
  for(i=0;i<n;i++){
    sum+=v[i];
    max=MAX(max,sum-x[i]);
  }
  int64 *y=(int64 *)calloc(n,sizeof(int64));
  y[0]=v[0]-x[0];
  sum=v[0];
  for(i=1;i<n;i++){
    sum+=v[i];
    y[i]=MAX(y[i-1],sum-x[i]);
  }
  sum=0;
  for(i=n-1;i>0;i--){
    sum+=v[i];
    max=MAX(max,sum-2*(c-x[i])+y[i-1]);
  }
  free(y);
  return max;
}

void run(void){
  int n;
  int64 c;
  scanf("%d%lld",&n,&c);
  int64 *x=(int64 *)calloc(n,sizeof(int64));
  int *v=(int *)calloc(n,sizeof(int));
  int i;
  for(i=0;i<n;i++) scanf("%lld%d",x+i,v+i);
  int64 a=calc(x,v,n,c);
  for(i=0;i<n-1-i;i++){
    int64 t=c-x[i];
    x[i]=c-x[n-1-i];
    x[n-1-i]=t;
    t=v[i];
    v[i]=v[n-1-i];
    v[n-1-i]=(int)t;
  }
  int64 b=calc(x,v,n,c);
  printf("%lld\n",MAX(a,b));
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 2176
n = list(input())
h = ["2", "4", "5", "7", "9"]
p = ["0", "1", "6", "8"]
b = ["3"]
if n[-1] in h:
    print("hon")
elif n[-1] in b:
    print("bon")
elif n[-1] in p:
    print("pon")

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

typedef long long int LL;
typedef long long int LLint;

//Faster Program
#define endl "\n"

//Faster Coding
#define ED return
#define GET(a) int a;cin >> a
#define DGET(a) double a;cin >> a
#define SGET(a) string a;cin >> a
#define CGET(a) char a;cin >> a
#define PRINT(a) cout << a << "\n"
#define ANS(a,b) int a;cin >> a;cout << b << "\n"
#define FOR(n) for(int i = 0;i < n;i++)
#define SORT(vec) sort(vec.begin(),vec.end())
#define REV(vec) reverse(vec.begin(),vec.end())

//As Function
#define UP(a,b) ((a+(b-1))/b)
#define ipow(x,y) LL(pow(x,y))

//Debug
#define TEST cout << "OK\n"

const double PI = M_PI;
const long long INF = int(999999999);
const long long MOD = int(1000000007);

//Settings
const bool DO_BENCHMARK = false;
const int DOUBLE_ACCURACY = 15;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(DOUBLE_ACCURACY);
    void solve();
    if(DO_BENCHMARK){
        clock_t clock_start = clock();
        solve();
        clock_t clock_end = clock();
        const double time = static_cast<double>(clock_end-clock_start)/CLOCKS_PER_SEC*1000.0;
        cout << "\n" << time << "[ms]\n";
    }
    else solve();
}

void solve(){
    int H, W, D;
    cin >> H >> W >> D;
    vector<vector<int>> input_grid (H,vector<int>(W));
    for(int i = 0;i < H;i++){
        for(int j = 0;j < W;j++){
            cin >> input_grid[i][j];
        }
    }
    vector<pair<int,int>> grid (H*W);
    for(int i = 0;i < H;i++){
        for(int j = 0;j < W;j++){
            grid[input_grid[i][j]-1].first = i;
            grid[input_grid[i][j]-1].second = j;
        }
    }

    vector<int> memo (H*W);
    for(int i = 1;i <= D;i++){
        int count = i;
        memo[i-1] = 0;
        count += D;
        while(count <= H*W){
            memo[count-1] = memo[count-D-1]+abs(grid[count-1].first-grid[count-D-1].first)+abs(grid[count-1].second-grid[count-D-1].second);
            count += D;
        }
    }

//    for(int i = 0;i < H*W;i++){
//        cout << "memo[" << i << "] " << memo[i] << endl;
//    }

    int Q;
    cin >> Q;
    for(int i = 0;i < Q;i++){
        int L, R;
        cin >> L >> R;
        cout << memo[R-1]-memo[L-1] << endl;
    }
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main(void){
  
  int n,m;
  int i,j,score=0,score_j;
  
  cin>>n;
  vector<string> s(n,"");
  for(i=0;i<n;i++) cin>>s.at(i);

  cin>>m;
  vector<string> t(m,"");
  for(i=0;i<m;i++) cin>>t.at(i);
  
  for(j=0;j<n;j++){
    score_j=0;
    for(i=0;i<n;i++)if(s.at(j)==s.at(i))score_j++;
    for(i=0;i<m;i++)if(s.at(j)==t.at(i))score_j--;
    if(score<score_j)score=score_j;
  }
  cout<<score;

}

Measured memory_bytes: 256
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>	tree_set;
typedef long long ll;
typedef long double ld;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

ll mod=1e9 + 7;

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

    cout<<3*n*n;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

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

    cout <<  800 * N - 200 * (N/15) << endl;

    return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.HashMap;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        GreenBin solver = new GreenBin();
        solver.solve(1, in, out);
        out.close();
    }

    static class GreenBin {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            HashMap<String, Long> set = new HashMap<>();
            for (int i = 0; i < n; i++) {
                char[] chars = in.next().toCharArray();
                Arrays.sort(chars);
                StringBuilder sb = new StringBuilder();
                sb.append(chars);
                set.put(Arrays.toString(chars), set.getOrDefault(Arrays.toString(chars), 0L) + 1);
            }

            long result = 0;
            for (String key : set.keySet()) {
                Long a = set.get(key);
                if (a > 1L) {
                    result += a * (a - 1) / 2;
                }
            }
            out.println(result);
        }

    }
}



Measured memory_bytes: 70868
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 1000000007;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

int main() {
  string s;
  cin >> s;
  ll n = s.size();
  mint dp[n + 1][4] = {};
  dp[0][0] = 1;
  vi v = {2, 3, 5};
  rep(i, n) {
    int k;
    if(s[i] == '?')
      k = 30;
    else
      k = v[s[i] - 'A'];
    if(k % 5 == 0) {
      dp[i + 1][3] += dp[i][2];
      rep(j, 4) dp[i + 1][j] += dp[i][j];
    }
    if(k % 3 == 0) {
      dp[i + 1][2] += dp[i][1];
      rep(j, 4) dp[i + 1][j] += dp[i][j];
    }
    if(k % 2 == 0) {
      dp[i + 1][1] += dp[i][0];
      rep(j, 4) dp[i + 1][j] += dp[i][j];
    }
  }
  cout << dp[n][3] << endl;
}

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

int main()
{
 int n,k;
 cin>> n >> k ;
 int p[n] ;
 for (int i=0 ; i<n ; i++)
    cin >> p[i];
 sort (p , p+n) ;
 int sum = 0 ;
 for (int i=0 ; i<k ; i++)
    sum+= p[i];
  cout << sum << endl ;
  
  return 0 ;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using Pt = pair<int, int>;

void ABC129D()
{
	int H, W;
	cin >> H >> W;
	vvi S(H, vi(W));
	for (int i = 0; i < H; ++i)
	{
		string X;
		cin >> X;
		for (int j = 0; j < W; ++j)
		{
			S[i][j] = X[j] == '#' ? 1 : 0;
		}
	}
	vvi C1(H, vi(W));
	for (int i = 0; i < H; ++i)
	{
		int c = 0;
		int start = 0;
		for (int j = 0; j < W; ++j)
		{
			if (S[i][j] == 1)
			{
				int d = j - start;
				for (int k = start; k < j; ++k)
				{
					C1[i][k] = d;
				}
				start = j + 1;
			}
		}
		int d = W - start;
		for(int k = start; k < W; ++k)
		{
			C1[i][k] = d;
		}
	}
	vvi C2(H, vi(W));
	for (int j = 0; j < W; ++j)
	{
		int c = 0;
		int start = 0;
		for (int i = 0; i < H; ++i)
		{
			if (S[i][j] == 1)
			{
				int d = i - start;
				for (int k = start; k < i; ++k)
				{
					C2[k][j] = d;
				}
				start = i + 1;
			}
		}
		int d = H - start;
		for (int k = start; k < H; ++k)
		{
			C2[k][j] = d;
		}
	}

	int ret = 0;
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			ret = max(ret, C1[i][j] + C2[i][j] - 1);
		}
	}
	cout << ret << endl;
}
int main()
{
	ABC129D();
	return 0;
}


Measured memory_bytes: 47488
#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
  int N, x = 0, max = 0;
  char c;
  cin >> N;
  cin.get (c); // skip new line
  for (int n = 0; n < N; n++) {
    cin.get (c);
    if (c == 'I') x++;
    else x--;
    if (x > max) max = x;
  }

  cout << max << endl;
  return 0;
}


Measured memory_bytes: 256