akhauriyash/Code-Regression huggingface dataset:
#include <numeric>
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
using namespace std;
#define int long long
#define inf 1000000007
#define rep(i,j,n) for(int i=j;i<n;i++)
typedef pair<int,int>  P;
double pi = 3.141592653589793;
//使うやつはここから下に置こうな
int a[214514]={};
signed main() {
    int n;cin>>n;//iがあるのは何番メカを格納
    rep(i,0,n){
        int b;cin>>b;
        a[b-1]=i;
    }
    int maxi=0;
    int count=1;
    rep(i,1,n){
        if(a[i]>a[i-1]){
            count++;
        }
        else {
            if(!maxi)maxi=count;
            else maxi=max(maxi,count);
            count=1;
        }
    }
    int ansf=0;
    count=inf;
    rep(i,0,n){
        if(count==inf)count=a[i];
        else if(count>a[i]){
            ansf=n-i;
            break;
        }
        else count=a[i];
    }
    count=inf;
    int ansb=0;
    for(int i=n-1;i>=0;i--){
        if(count==inf)count=a[i];
        else if(count<a[i]){
            ansb=i+1;
            break;
        }
        else count=a[i];
    }
    cout<<min({ansf,ansb,n-maxi})<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, N) for (ll i = 0; i < (N); ++i)

ll N, Q, L, R;
vector<ll> A;
vector<tuple<ll, ll, ll, ll>> query;

const ll INF = (ll)1e9 + 7;

signed main() {

    cin >> N >> Q >> L >> R;

    A.resize(N + 1);
    A[0] = -INF;
    REP(i, N) cin >> A[i + 1];

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

    // REP(i, N) cerr << A[i] << endl;

    REP(i, Q) {
        ll q, x, s, t;
        cin >> q >> x >> s >> t;
        query.emplace_back(make_tuple(q, x, s, t));
    }

    function<bool(ll, ll)> check = [&](ll m, ll MAX) {
        if (m == -INF) return true;
        REP(i, Q) {
            ll q, x, s, t;
            tie(q, x, s, t) = query[i];
            if (q == 1) {
                if (m >= x) {
                    m = t * (m + s);
                }
            } else {
                if (m <= x) {
                    m = (m - s) / t;
                }
            }
        }
        return (m <= MAX);
    };

    ll l = 0, r = 0;

    {
        ll ok = 0, ng = N + 1;
        while (abs(ok - ng) > 1) {
            ll mid = (ok + ng) / 2;
            if (check(A[mid], R)) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        r = ok;
    }

    {
        ll ok = 0, ng = N + 1;
        while (abs(ok - ng) > 1) {
            ll mid = (ok + ng) / 2;
            if (check(A[mid], L - 1)) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        l = ok;
    }

    cout << max<ll>(0, r - l) << endl;

    // cerr << l << ' ' << r << endl;

}


Measured memory_bytes: 12752
import sys
input = sys.stdin.readline
from collections import deque
import math

def main():
    def pre(n,MOD):
        a=1
        for i in range(1,n+1):
            a=(a*i)%MOD
        an=a
        b=pow(a,MOD-2,MOD)
        bs=[1]*(n+1)
        bs[n]=b
        for i in range(n,1,-1):
            b=b*i%MOD
            bs[i-1]=b
        return an,bs
    
    x,y=map(int,input().split())
    d=(x+y)//3
    MOD=10**9+7
    if (x+y)%3!=0 or x<d or y<d:
        print(0)
    else:
        a,b=pre(d,MOD)
        a=a*b[y-d]*b[2*d-y]%MOD
        print(a)

if __name__ == '__main__':
    main()

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

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

const int mod = 1e9 + 7;
const int mN = 1e9;

int n, k;

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

  cin>>n>>k;
  vector<int> arr(n);
  for(int &v : arr) cin>>v;

  vector<int> dp(n, 1e9);

  dp[0] = 0;
  for(int i = 0; i < n; ++i){
    for(int j = 1; j <= k; ++j){
      if(i + j < n) dp[i + j] = min(dp[i + j], dp[i] + abs(arr[i + j] - arr[i]));
    }
  }
  // for(int i : dp) cout<<i<<" ";
  cout<<dp[n - 1]<<"\n";
}


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

void test_case(){
    
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    string s;
    cin >> s;
    int a[2] = {};
    int cnt = 0;
    for( int i = 0 ; i< 3; i++)
        a[s[i]-'A'] = 1;
    rng( i, 0, 2)
        cnt += a[i];
    
    if( cnt > 1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
        
	return 0;
}






Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <string>
#include <stack>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <time.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;
typedef long long ll;

vector<ll> primeFactors(ll a)
{
	vector<ll> ans;
	if (a % 2 == 0)
	{
		ans.push_back(2);
		while (a % 2 == 0)
			a /= 2;
	}
	for (ll i = 3; i <= sqrt(a); i++)
	{
		if (a % i == 0)
		{
			ans.push_back(i);
			while (a % i == 0)
				a /= i;
		}
	}
	if (a > 2)
		ans.push_back(a);
	return ans;
}
int main() {
	FAST_IO;
	/*int t, a, b, c;
	cin >> t;
	while (t--)
	{
		cin >> a >> b >> c;
		int m1 = min(a, b / 2);
		int m2 = min(b, c / 2);
		int ans = 0;
		if (m1 > m2)
		{
			a -= m1;
			b -= m1 * 2;
			ans += m1 * 3;
		}
		else
		{
			b -= m2;
			c -= m2 * 2;
			ans += m2 * 3;
		}
		ans += max(min(a, b / 2), min(b, c / 2)) * 3;
		cout << ans << "\n";
			
	}*/
	ll a, b;
	cin >> a >> b;
	vector<ll> p1 = primeFactors(a);
	vector<ll> p2 = primeFactors(b);
	map<ll, bool> m;
	for (auto x : p1)
		m[x] = true;
	ll cnt = 0;
	for (auto x : p2)
	{
		if (m[x] == true)
			cnt++;
	}
	cout << cnt + 1;
	
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include<stdlib.h>
#include <math.h>
using namespace std;
int main() {
        int R;
        cin >> R;
        if(R <1200){
            cout << "ABC";
        }
        else {if(R<2800){
            cout <<"ARC";

        }else{
            cout <<"AGC";
        }}
        return 0;
}

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

int64_t gyaku(int64_t a, int64_t mod){
  int64_t s = 1, tmp = a, t = mod - 2;
  while(t > 0){
    if(t % 2 == 1){
      s *= tmp;
      s %= mod;
    }
    t /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  return s;
}

int main() {
  int64_t mod = 1000000007, n, a, b, s = 1, p = 1, q = 1, t, tmp = 2;
  cin >> n >> a >> b;
  t = n;
  while(t > 0){
    if(t % 2 == 1){
      s *= tmp;
      s %= mod;
    }
    t /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  --s;
  rep(i, a){
    p *= n-i;
    p %= mod;
    p *= gyaku(i+1, mod);
    p %= mod;
  }
  rep(i, b){
    q *= n-i;
    q %= mod;
    q *= gyaku(i+1, mod);
    q %= mod;
  }
  s += 2 * mod;
  s -= p;
  s -= q;
  s %= mod;
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const int inf = 1 << 20;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
using namespace std;


int main()
{
    ll s;
    cin >> s;
    ll x1 = 1e9,y1;
    ll x2 = 1,y2;

    ll m = s % 1000000000;
    if(m == 0){
        y1 = 0;
    }else{
        y1 = 1000000000 - m;
    }

    y2 = (s+y1) / 1000000000;

    cout << 0 << ' ' << 0 << ' ' << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
}


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

int main(){
  int n, d;
  double x, y;
  int cnt = 0;
  cin >> n >> d;
  for (int i = 0; i < n; i++){
    double a;
    double b;
    cin >> x >> y;
    a = pow(x, 2.0);
    b = pow(y, 2.0);
    if (sqrt(a+b) <= d){
      cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3840
using Yorukatsu018.Questions;
using Yorukatsu018.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Yorukatsu018.Questions
{
    /// <summary>
    /// ABC069 A
    /// </summary>
    public class QuestionA : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var nm = inputStream.ReadIntArray();
            yield return (nm[0] - 1) * (nm[1] - 1);
        }
    }
}


namespace Yorukatsu018
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionA();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace Yorukatsu018.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace Yorukatsu018.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

Measured memory_bytes: 13396
def do_solve(n, k, c, s):
    dp = [0 for i in xrange(n)]
    for i in xrange(n):
        dp[i] = 1 if s[i] == 'o' else 0
        if i - c - 1 >= 0:
            dp[i] = max(dp[i], dp[i - c - 1] + 1 if s[i] == 'o' else 0)
        if i - 1 >= 0:
            dp[i] = max(dp[i], dp[i - 1])
    return dp

def solve(n, k, c, s):
    dp1 = do_solve(n, k, c, s)
    dp2 = do_solve(n, k, c, s[::-1])[::-1]

    # print dp1
    # print dp2

    res = []
    for i in xrange(n):
        if s[i] == 'x':
            continue
        l = dp1[i - 1] if i - 1 >= 0 else 0
        r = dp2[i + 1] if i + 1 < n else 0

        # print i, l, r

        if l + r == k - 1:
            res.append(i + 1)
    # print res
    return res

assert solve(16, 4, 3, 'ooxxoxoxxxoxoxxo') == [11, 16]
assert solve(11, 3, 2, 'ooxxxoxxxoo') == [6]
assert solve(5, 1, 0, 'ooooo') == []
assert solve(5, 2, 3, 'ooxoo') == [1, 5]

(n, k, c) = map(int, raw_input().split())
s = raw_input().strip()

for num in solve(n, k, c, s):
    print num



Measured memory_bytes: 21956
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
List = [[] for k in range(K)]
for n in range(N):
    List[n % K].append(T[n])

point = {'r': P, 's': R, 'p': S}

score = 0
for k in range(K):
    L = List[k]
    count = 1
    length = len(L)
    for i in range(length):
        try:
            if L[i] == L[i+1]:
                count += 1
            else:
                score += point[L[i]]*((count+1)//2)
                count = 1
        except:
            score += point[L[i]]*((count+1)//2)
print(score)

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

int main(){
char s;
cin>>s;
if(s=='A'){
        cout<<'T'<<endl;

}
if(s=='T'){
    cout<<'A'<<endl;
}
if(s=='C'){
    cout<<'G'<<endl;
}
if(s=='G'){
    cout<<'C'<<endl;
}

return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VVI vector<VI>
#define VL vector<LL>
#define VVL vector<VL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
#define mset(a,v) memset(a,v,sizeof(a))
#define setp(x) cout<<fixed<<setprecision(x)
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(LL i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 1e7 + 9;
const LL INF = 1e9;

void print_a(VI v)
{
    if(v.size()) cout<<v[0];
    loop(i,1,v.size()) cout<<' '<<v[i];
    cout<<'\n';
}

VVI init_vvi(int n, int m, int val)
{
    return VVI(n,VI(m,val));
}

VVL init_vvl(int n, int m, LL val)
{
    return VVL(n,VL(m,val));
}

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

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

    loop(i,1,n+1)
    {
        LL n1 = n/i;
        ans += (i * ((n1 * (n1 + 1))/2));
    }

    cout<<ans<<'\n';

    /*
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int a[n];
        loop(i,0,n) cin>>a[i];
    }
    */

    /*
    int n;
    cin>>n;
    int a[n];
    loop(i,0,n) cin>>a[i];
    */

    /*
    cout<<ans<<'\n';

    if(f) cout<<"YES\n";
    else cout<<"NO\n";

    if(f) cout<<"Yes\n";
    else cout<<"No\n";
    */

    return 0;
}


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


int main(){
	int n,a,b,cnt=0,cnt2=0;
	string s;
	cin >> n >> a >> b >> s;
	
	for(int i=0;i<n;i++){
		bool ok=false;
		if(s[i]=='b'){
			if(cnt2<b){
				cnt2++;
				if(cnt+cnt2<=a+b) ok=true;
			}
		}
		else if(s[i]=='a'){
			cnt++;
			if(cnt+cnt2<=a+b) ok=true;
		}
		
		if(ok) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
typedef long double ld;
using namespace std;

int main(){
    ld a, b, c;
    cin >> a >> b >> c;
    if(a != b){
        if(a + b + 2*pow(a*b, 0.5) < c){
            cout << "Yes" << endl;
            return 0;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }else{
        if(2*a +2*b < c){
            cout << "Yes" << endl;
            return 0;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 384
A, B, C = map(int, input().split())
count=0

if A == B == C ==1:
    print(0)

elif A == B == C:
    print(-1)

else:
    while A%2==0 and B%2==0 and C%2==0:
        a = A
        b = B
        c = C
        A = b/2 + c/2
        B = a/2 + c/2
        C = a/2 + b/2
        count += 1

    print(count)


Measured memory_bytes: 3060
#define George_Plover
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define EPS (1e-9)
#define MAXN 600001
#define MOD 998244353
#define ull unsigned long long
#define LL long long
using namespace std;
int n;
int L[20];
int main()
{
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>L[i];
    }
    sort(L+1,L+n+1);
    int sum=0;
    for(int i=1;i<n;i++)
        sum+=L[i];
    if(sum>L[n])
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}




Measured memory_bytes: 3500
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define ll long long

int main() {
    vector<int>a(3);
  int p=1000000;
  for(int i=0;i<3;i++)
  {
    cin>>a.at(i);
  }
  sort(a.begin(),a.end());
  cout<<abs(a.at(1)-a.at(0))+abs(a.at(2)-a.at(1));
}
  
  
  
  

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

int r[4000], g[4000];

int abs(int a, int b) {
  return a > b? a-b: b-a;
}

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int rnum = 0, gnum = 0, bnum = 0;
  rep(i, n) {
    if (s[i] == 'R') {r[rnum] = i; rnum++;}
    else if (s[i] == 'G') {g[gnum] = i; gnum++;}
    else if (s[i] == 'B') bnum++;
  }
  ll sum = 0;
  if ((bnum == 0) || (rnum == 0) || (gnum == 0)) {
    cout << 0 << endl; return 0;
  }
  rep(i, rnum) rep(j, gnum) {
    sum += bnum;
    int o1 = 2*r[i] - g[j];
    if ((o1 >= 0) && (s[o1] == 'B')) sum--;
    int o2 = 2*g[j] - r[i];
    if ((o2 >= 0) && (s[o2] == 'B')) sum--;
    int in = abs(r[i], g[j]);
    if (in % 2 == 0) {
      if ((r[i] < g[j]) && (s[g[j] - in/2] == 'B')) sum--;
      else if ((r[i] > g[j]) && (s[r[i] - in/2] == 'B')) sum--;
    }
  }
  cout << sum << endl;
  return 0;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

// Returns Run Length Enconding of an input vector.
// Verified: AGC040A
template<typename T> vector<pair<T, int>> RLE(vector<T> xs) {
  vector<pair<T, int>> es;

  T current = xs[0];
  int current_count = 1;
  for (int i = 1; i < xs.size(); i++) {
    if (xs[i] == current) {
      current_count++;
    } else {
      es.push_back(make_pair(current, current_count));
      current = xs[i];
      current_count = 1;
    }
  }
  es.push_back(make_pair(current, current_count));
  return es;
}

constexpr int64 P = 1000000007;

struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 x) : x(x) {
    if (x > P || x < 0) { cerr << "Invalied FiniteField!" << endl; exit(1); }
  }
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) const {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) const {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

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

  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<char> cs(s.begin(), s.end());
  auto es = RLE(cs);
  FiniteField ans = 1;
  if (es[0].second == 2) {
    ans *= 6;
  } else {
    ans *= 3;
  }
  for (int i = 1; i < es.size(); i++) {
    int x1 = es[i - 1].second;
    int x2 = es[i].second;
    if (x1 == 2) {
      if (x2 == 2) {
        ans *= 3;
      } else {
        ans *= 1;
      }
    } else {
      if (x2 == 2) {
        ans *= 2;
      } else {
        ans *= 2;
      }
    }
  }
  cout << ans.Value() << endl;
}

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

#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

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

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

void unq(auto &a){
  sort(all(a));
  a.resize(unique(all(a))-a.begin());
}

const int N=200005;

vector<int>fc,inv;

int nCr(int n,int r){
  if(n<r){
    return 0;
  }
  return mul(mul(fc[n],inv[r]),inv[n-r]);
}

void prec(int n){
  fc.resize(n);
  inv.resize(n);
  fc[0]=1;
  for(int i=1;i<n;i++){
    fc[i]=mul(fc[i-1],i);
  }
  inv[n-1]=powz(fc[n-1],mod-2);
  for(int i=n-2;i>=0;i--){
    inv[i]=mul(inv[i+1],i+1);
  }
}

int dp[500005];

void solve(){
  prec(500005);
  int n,k;
  cin>>n>>k;
  int ans=0;
  for(int i=k;i>=1;i--){
    int cr=k/i;
    dp[i]=powz(cr,n);
    for(int j=i+i;j<=k;j+=i){
      dp[i]=sub(dp[i],dp[j]);
    }
    add(ans,mul(i,dp[i]));
  }
  debug(dp[1],dp[2]);
  cout<<ans;
  
  
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //cin>>tc;
  for(int _=0;_<tc;_++){
    //cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}



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

int main()
{
    stack<char>s;
    char c[111111];
    scanf("%s",c);
    int sum=0,n=strlen(c);
    for(int i=0;i<n;i++)
    {
        if(s.size()==0)
            s.push(c[i]);
        else
        {
            if(c[i]!=s.top())
            {
                s.pop();
                sum+=2;
            }
            else
                s.push(c[i]);
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int a[5][4][11];
int main() {
	int n; cin >> n; int b, c, d,e;
	for (int i = 0; i < n; i++) {
		cin >> b >> c >> d >> e;
		a[b][c][d] += e;
	}
	for (int i = 1; i < 5; i++) {
		for (int j = 1; j < 4; j++) {
			for (int k = 1; k < 11; k++) {
				cout << " " << a[i][j][k];
			}
			cout << endl;
		}
		if (i != 4) {
			cout << "####################" << endl;
		}
	}
}


Measured memory_bytes: 3096
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>
#include<deque>




using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const ll INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;



void solve() {
    int m, n;
    cin >> m >> n;
    vector<string> a(m);
    for (int i = 0; i < m; ++i)
        cin >> a[i];
    vector<int> r(m, 0), c(n, 0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (a[i][j] == '#') {
                ++r[i];
                ++c[j];
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        if (r[i] == 0)
            continue;
        for (int j = 0; j < n; ++j) {
            if (c[j] == 0)
                continue;
            cout << a[i][j];
        }
        cout << endl;
    }
}


//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();



#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


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

int main() {
    string s, t;
    cin >> s >> t;

    int size = s.size(), count = 0;
    map<char, int> char_map;
    for (int i = 0; i < size; i++) {
        if (s.at(i) != t.at(i)) count++;
    }

    cout << count << endl;
}

Measured memory_bytes: 3920
#include<bits/stdc++.h>
using namespace std;
int n,a;
set<int> s;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a);
		if(s.find(a)!=s.end()) {
			cout<<"NO";
			return 0;
		}
		s.insert(a);
	}
	cout<<"YES";
	return 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define ll                      long long
#define pb                      push_back
#define rep(i,a,b,c)            for(ll i=(a);i<=(b);i+=(c))
#define repb(i,a,b,c)           for(ll i=(a);i>=(b);i-=(c))
#define MOD                     1000000007
#define inf                     3e18
#define ld                      long double
#define mp                      make_pair
#define vpll                    vector<pair<ll,ll> >
#define vll                     vector<ll>
#define vld                     vector<ld>
#define vvll                    vector<vector<ll>>
#define vvld                    vector<vector<ld>>
#define pll                     pair<ll,ll>
#define vvpll                   vector<vector<pair<ll,ll>>>
#define pqll                    priority_queue<ll>
#define mll                     map<ll,ll>
#define mlc                     map<ll,char>
#define um                      unordered_map
#define umll                    um<ll,ll>
#define umlc                    um<ll,char>
#define all(x)                  x.begin(),x.end()
#define fi                      first
#define se                      second
#define ln                      cout<<"\n";
#define endl                    "\n"
#define test                    ll T;cin>>T;while(T--)
#define isvowel(a)              (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define show(w,size)            for(ll i=0;i<size;i++) cout<<w[i]<<" ";
#define prll(a)                 cout<<a<<"\n";
#define mset(dp,no)             memset(dp,no,sizeof(dp))
#define input(a,n)              rep(i,0,n-1,1) cin>>a[i];
#define countbit                __builtin_popcount                                           //Number of setbits in decimal notation
#define lb(v,cur)               lower_bound(all(v),cur)-v.begin()
#define ub(v,cur)               upper_bound(all(v),cur)-v.begin()
long long pows(long long a, long long b) {
  long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
ll powm(ll x,ll y,ll m=MOD){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
ll modInverse(ll a, ll m=MOD){if(m == 1)return 0;ll m0=m,y=0,x=1;while(a>1){ll q=a/m,t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0) x+=m0;return x;}
int main()
{
fastIO
ll n,m,i,j=0,k,x,y,z,t,e,f,p,q,g,l,r,w,h,count1=0,prod=1,a,b,c,d,index,x1,x2,y1,y2,diff,ans=0,sum=0,sum1=0,sum2=0,flag=0,flag1=0,flag2=0;
string s,s1,s2;
cin>>n;
ll ar[n+1];
for(i=1;i<=n;i++)
{
  cin>>ar[i];
  if(i%2==1&&ar[i]%2==1)
  {
    ans++;
  }
}
cout<<ans;
}


Measured memory_bytes: 3616
class Dice:
    """サイコロを操作するクラス"""
    def __init__(self, num):
        self.num = num
    def roll_north(self):
        tmp = self.num[:]
        self.num[0] = tmp[1]
        self.num[1] = tmp[5]
        self.num[4] = tmp[0]
        self.num[5] = tmp[4]
    def roll_south(self):
        tmp = self.num[:]
        self.num[0] = tmp[4]
        self.num[1] = tmp[0]
        self.num[4] = tmp[5]
        self.num[5] = tmp[1]
    def roll_east(self):
        tmp = self.num[:]
        self.num[0] = tmp[3]
        self.num[2] = tmp[0]
        self.num[3] = tmp[5]
        self.num[5] = tmp[2]
    def roll_west(self):
        tmp = self.num[:]
        self.num[0] = tmp[2]
        self.num[2] = tmp[5]
        self.num[3] = tmp[0]
        self.num[5] = tmp[3]
    def roll_right(self):
        tmp = self.num[:]
        self.num[1] = tmp[3]
        self.num[2] = tmp[1]
        self.num[3] = tmp[4]
        self.num[4] = tmp[2]
    def print_dice(self):
        print(self.num)
    def print_top(self):
        print(self.num[0])

num = list(map(int, input().split()))
dice = Dice(num)
for i in range(int(input())):
    top, front = map(int, input().split())
    while not(top == dice.num[0] or front == dice.num[1]):
        dice.roll_north()
    while top != dice.num[0]:
        dice.roll_east()
    while front != dice.num[1]:
        dice.roll_right()
    print(dice.num[2])


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

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

    ll n,a,b;
    cin >> n >> a >> b;

    if(b > a) swap(a,b);
    if((a-b) % 2 == 0) cout << (a-b) / 2 << endl;
    else {
        ll x = min(a - 1, n - b);
        ll y = min(b + (a - b - 1) / 2, (n - a + 1) + ((n - (b + (n - a + 1))) / 2));
        cout << min(x,y) << endl;
    }
}


Measured memory_bytes: 256
//g++でビルド

#include "bits/stdc++.h"

using namespace std;

int h, w;
int dp[1001][1001];
char area[1001][1001];

int main(){
    cin >> h >> w;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> area[i][j];
        }
    }

    for(int i = 0; i <= h; i++){
        for(int j = 0; j <= w; j++){
            dp[i][j] = 0;
        }
    }


    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(area[i-1][j-1] == '.'){
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
            }
            if(i == 1 && j == 1) dp[1][1] = 1;
        }
    }

    int result = dp[h][w];


    cout << result << endl;
    return 0;
}

Measured memory_bytes: 5120
#include <cassert>
#include <chrono>
#include <cmath>
#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main(){
    int N;
    int count = 0;
    cin >> N;
    char S[N];
    cin >> S;
    for (int i =0; i < N - 2 ; i ++ ){
        if(S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C')   count ++;
    }
    cout << count << endl;
}


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

int main() {
  int n,m;
  cin >> n >> m;
  vector<int> a(n),b(n),c(m),d(m);
  for(int i=0; i<n; i++) {
    cin >> a[i] >> b[i];
  }
  for(int i=0; i<m; i++) {
    cin >> c[i] >> d[i];
  }
  for(int i=0; i<n; i++) {
    int min=abs(a[i]-c[0])+abs(b[i]-d[0]);
    int cnt=1;
    for(int j=1; j<m; j++) {
      int x=abs(a[i]-c[j])+abs(b[i]-d[j]);
      if(min>x) {
        cnt=j+1;
        min=x;
      }
    }
    cout << cnt << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;
typedef pair<ll, ll> pint;


void yesno(bool b) {
    if (b) {
        cout << "Yes" << endl;
    }     else {
        cout << "No" << endl;
    }

}

int main() {
    int N;
    string S;
    cin >> N;
    cin >> S;
    int R[N+1];
    int G[N+1];
    int B[N+1];
    R[0] = 0; G[0] = 0; B[0] = 0;
    rep(i, N) {
        R[i+1] = R[i];
        G[i+1] = G[i];
        B[i+1] = B[i];
        if (S[i] == 'R') R[i+1]++;
        if (S[i] == 'G') G[i+1]++;
        if (S[i] == 'B') B[i+1]++;
    }
    ll ans = 0;
    rep(i, N) {
        REP(j, i+1, N) {
            if (S[i] != S[j]) {
                if (S[i] == 'R' && S[j] == 'G' || S[i] == 'G' && S[j] == 'R' ) {
                    ans += B[N] - B[j+1];
                    if (j - i + j < N && S[j - i + j] == 'B') {
                        ans--;
                    }
                } else if (S[i] == 'B' && S[j] == 'G' || S[i] == 'G' && S[j] == 'B' ) {
                    ans += R[N] - R[j+1];
                    if (j - i + j < N && S[j - i + j] == 'R') {
                        ans--;
                    }
                } else {
                    ans += G[N] - G[j+1];
                    if (j - i + j < N && S[j - i + j] == 'G') {
                        ans--;
                    }
                }

            }
        }
    }

    cout << ans << endl;



}


Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	const double eps=1e-11;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var a=new int[n+1][];
		var h=new int[n+1];
		var d=new int[n+1];
		var qu=new Queue<(int,int,int d)>();
		int p=0,ans=0;
		a[0]=new int[1];
		for(int i = 1;i<=n;i++) {
			a[i]=sc.Ia3(0);
			if(a[i][0]<i&&a[a[i][0]][h[a[i][0]]]==i){qu.Enqueue((a[i][0],i,1));}
		}
		while(qu.Count>0){
			var e=qu.Dequeue();
			h[e.Item1]++;
			h[e.Item2]++;
			d[e.Item1]=d[e.Item2]=e.d;
			ans=Max(ans,e.d);
			int c=a[e.Item1][h[e.Item1]];
			if(a[c][h[c]]==e.Item1){qu.Enqueue((e.Item1,c,Max(d[e.Item1],d[c])+1));}
			c=a[e.Item2][h[e.Item2]];
			if(a[c][h[c]]==e.Item2){qu.Enqueue((e.Item2,c,Max(d[e.Item2],d[c])+1));}
			p++;
		}
		Console.WriteLine("{0}",p==n*(n-1)/2?ans:-1);
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),int.Parse);}
	public int[] Ia3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),long.Parse);}
	public long[] La3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 49468
#include <iostream>
#include <algorithm>
#define AC ios_base::sync_with_stdio(0),cin.tie(0);
using namespace std;
int main(int argc, char** argv)
{
    //AC
    int limit;
    cin>>limit;
    int* arr = new int[limit];
    int* dp = new int[limit];
    for(int i=0;i<limit;i++)
        cin>>arr[i];
    dp[0] = 0, dp[1] = abs(arr[0]-arr[1]);
    for(int i=2;i<limit;i++)
        dp[i] = min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i]-arr[i-1]));
    cout<<dp[limit-1]<<'\n';
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;

class Main{
    int w,h,sx,sy;
    char[][] tile;
    ArrayList<Point> p;
    int[][] dist,d,dp;
    int INF = 100000000;

    class Point{
	int x,y;
	public Point(int x, int y){
	    this.x = x;
	    this.y = y;
	}
    }

    void solve(){
	Scanner sc = new Scanner(System.in);
	while(true){
	    w = sc.nextInt();
	    h = sc.nextInt();
	    if(w==0 && h==0)break;

	    tile = new char[h][w];
	    p = new ArrayList<Point>();
	    for(int i=0; i<h; i++){
		String line = sc.next();
		for(int j=0; j<w; j++){
		    tile[i][j] = line.charAt(j);
		    if(tile[i][j]=='o'){sx = j; sy = i;}
		    if(tile[i][j]=='*')	p.add(new Point(j,i));
		}
	    }
	    p.add(new Point(sx,sy));

	    //距離行列作成
	    d = new int[p.size()][p.size()];
	    for(int i=0; i<p.size(); i++) Arrays.fill(d[i],INF);
	    for(int i=0; i<p.size(); i++){
		dist = new int[h][w];
		for(int j=0; j<h; j++) Arrays.fill(dist[j],INF);
		bfs(i);
		for(int j=0; j<p.size(); j++){
		    d[i][j] = dist[p.get(j).y][p.get(j).x];
		}
	    }

	    //TSP
	    dp = new int[1 << p.size()][p.size()];
	    for(int i=0; i<1<<p.size(); i++)Arrays.fill(dp[i],-1);
	    int ans = tsp(0,p.size()-1);
	    System.out.println(ans==INF ? -1:ans);
	}
    }

    void bfs(int s){
	int[] dx = {0,0,1,-1};
	int[] dy = {1,-1,0,0};

	LinkedList<Point> q = new LinkedList<Point>();
	q.add(new Point(p.get(s).x,p.get(s).y));
	dist[p.get(s).y][p.get(s).x] = 0;

	while(q.size()>0){
	    Point point = q.poll();
	    for(int i=0; i<4; i++){
		int nx = point.x+dx[i];
		int ny = point.y+dy[i];
		if(nx>=0 && nx<w && ny>=0 && ny<h && tile[ny][nx]!='x' && dist[ny][nx]==INF){
		    q.add(new Point(nx,ny));
		    dist[ny][nx] = dist[point.y][point.x]+1;
		}
	    }
	}
    }

    int tsp(int S, int v){
	if(dp[S][v]>=0) return dp[S][v];

	if(S==(1<<p.size())-1) return dp[S][v] = 0;

	int res = INF;
	for(int i=0; i<p.size(); i++){
	    if((S>>i&1)==0){
		res = Math.min(res,tsp(S|1<<i,i)+d[v][i]);
	    }
	}

	return dp[S][v] = res;
    }

    public static void main(String[] args){
	new Main().solve();
    }
}

Measured memory_bytes: 12000
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

void solveSingleCase(int caseNo)
{
    int N;
    cin >> N;
    VEC(int) A(N);
    READVEC(A);
    sort(ALL(A));

    Pii ret(0, 0);
    FOR(i, 1, N) {
        int x = A[i];
        VEC(int) y;
        y.PB(A[i - 1]);
        // choose one closest to x / 2 or (x + 1) / 2
        FOR(j, 0, 2) {
            int t = lower_bound(ALL(A), (x + j) / 2) - BEGIN(A);
            if (t < SZ(A)) {
                y.PB(A[t]);
            }
            if (t - 1 >= 0) {
                y.PB(A[t - 1]);
            }
        }
        
        int mindiff = 1 << 30, besty = -1;
        int x1 = x / 2, x2 = (x + 1) / 2;
        for (int yc : y) {
            if (min(abs(x1 - yc), abs(x2 - yc)) < mindiff) {
                besty = yc;
                mindiff = min(abs(x1 - yc), abs(x2 - yc));
            }
        }

        // x and besty.
        ret = Pii(x, besty);
    }

    cout << ret << endl;
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    // cin >> T;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


Measured memory_bytes: 640
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  int x, a, b;
  scanf("%d", &x);
  scanf("%d", &a);
  scanf("%d", &b);
  printf("%d\n", (x-a)%b);
  return 0;
}


Measured memory_bytes: 128
import java.io.*;

public class Main {

  static long k, ans;

  public static long gcd(long a, long b){
    if(b > a) return gcd(b, a);
    if(b == 0L) return a;

    return gcd(b, a % b);
  }

  public static long gcd(long a, long b, long c){
    return gcd(a, gcd(b, c));
  }

  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    String[] in = br.readLine().split(" ");
    k = Long.parseLong(in[0]);

    br.close();

    ans = 0;

    for(long i = 1; i <= k; i++){
      for(long j = 1; j <= k; j++){
        for(long l = 1; l <= k; l++){
          ans += gcd(i, j, l);
        }
      }
    }

    System.out.println(ans);

  }
}

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

int H, W;
int board[10][10];
string s;

void input() {
	H = W = 0;
	int i = 0, j = 0;
	for(auto c : s) {
		if(c == 'b') {
			board[i][j] = 1;
			j++;
		}
		else if(c == '/') {
			i++;
			W = j;
			j = 0;
		}
		else {
			for(int k = 0; k < c - '0'; k++) {
				board[i][j] = 0;
				j++;
			}
		}
	}
	H = i + 1;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a--, b--, c--, d--;
	board[a][b] = 0;
	board[c][d] = 1;
}

void output() {
	for(int i = 0; i < H; i++) {
		int s = 0;
		for(int j = 0; j < W; j++) {
			if(board[i][j]) {
				if(s != 0) {
					cout << s;
					s = 0;
				}
				cout << 'b';
			}
			else {
				s++;
			}
		}
		if(s != 0) cout << s;
		if(i != H - 1) cout << '/';
	}
	cout << endl;
}

void solve() {
	input();
	output();
}

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

	while(cin >> s, s != "#") solve();
}

Measured memory_bytes: 3224
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*) array, (T*) (array + N), val);
}
pii Dir[8] = { //?§????
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};


signed main() {
	int w, h;
	scanf("%d %d", &w, &h);
	vector<vector<int>> m(h+2, vector<int>(w+2)),al(h + 2, vector<int>(w + 2));
	REP(i, h) {
		REP(j, w) {
			scnaf("%d", &m[i+1][j+1]);
		}
	}

	queue<pii> que;
	int ans = 0;
	que.push({0,0});
	while (que.size()) {
		pii cur = que.front();
		que.pop();
		if (!RANGE(cur.first, 0, h + 1) || !RANGE(cur.second, 0, w + 1))
			continue;
		if (m[cur.first][cur.second]) {
			ans++;
			continue;
		}
		if (al[cur.first][cur.second])
			continue;

		al[cur.first][cur.second] = 1;
		que.push({ cur.first + 1,cur.second });
		que.push({ cur.first ,cur.second + 1 });
		que.push({ cur.first - 1,cur.second });
		que.push({ cur.first ,cur.second - 1 });
		if (cur.first % 2) {
			que.push({ cur.first + 1,cur.second + 1 });
			que.push({ cur.first - 1,cur.second + 1 });
		}
		else {
			que.push({ cur.first + 1,cur.second - 1 });
			que.push({ cur.first - 1,cur.second - 1 });
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3372
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
 
 
public class Main {

	static long MOD = 1_000_000_007;
	static int INF = 1_000_000_007;
	//二項係数関連ここから-----
	static boolean isPreprocessing = false;	//二項係数を計算するための前処理を行っているかどうかのフラグ
	static int MAX = 260;				//MAXまで階乗やそれらの逆元のテーブルを保持する。
	static long[] fac;	//fac[i] := i! % MOD
	static long[] inv;	//inv[i] := mod. MODにおける i の逆元
	static long[] finv;	//finv[i] := mod. MODにおける i! の逆元(invの累積"積")
	//二項係数関連おわり------
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		//int N = Integer.parseInt(sc.next());
		//long L = Long.parseLong(sc.next());
		//char[] A = sc.next().toCharArray();
		
		int N = Integer.parseInt(sc.next());
		System.out.println(3*N*N);
		
		
	}
	
	//aとbの最小公倍数を返す
	static long lcm (long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return (c/b);
	}
	
	//二項係数用の前処理
	static void COMinit(){
		//二項係数演算用前処理
		fac = new long[MAX+1];
		fac[0] = 1L;
		fac[1] = 1L;
		inv = new long[MAX+1];
		inv[1] = 1L;
		finv = new long[MAX+1];
		finv[0] = 1L;
		finv[1] = 1L;
		for(int i=2;i<MAX;i++){
			fac[i] = fac[i-1] * i % MOD;
			inv[i] = MOD - inv[(int)(MOD%i)] * (MOD/i) % MOD;
			finv[i] = finv[i-1] * inv[i] % MOD;
		}
		isPreprocessing = true;
	}
	
	//二項係数i_C_jをMODで割った余りを返す
	static long COM(int i, int j){
		if(i<j)return 0;
		if(i<0 || j<0)return 0;
		if(!isPreprocessing)COMinit();
		return fac[i] * (finv[j] * finv[i-j] % MOD) % MOD;
	}
	
}



Measured memory_bytes: 25428