akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define pa pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
using namespace std;

int a[5005];
ll dp[5005];
int main()
{   
    ll n,A,B; scanf("%lld%lld%lld",&n,&A,&B);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    a[n+1]=n+1;
  for(int i=1;i<=n+1;++i)
  {
     dp[i]=1e18;
     int big=0;
     for(int j=i-1;j>=0;j--) 
     {
       if(a[i]<a[j]) big++;
       else dp[i]=min(dp[i],dp[j]+A*big+B*(i-1-j-big));
     }
  }
  printf("%lld\n",dp[n+1]);
return 0;
}
/*
*/

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(auto it= (o).begin(); it != (o).end(); ++ it)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define inrep(t) int t;cin>>t; while(t--)
#define pb push_back
#define mp make_pair 
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi; 
typedef pair<int,int> pii;
typedef vector<pii > vpii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll > vpll; 
typedef vector<string> vs;
typedef long double ld;


int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL); 
	int n; cin>>n; 
	int a[2][n]; 
	reu(i,0,2){
		reu(j,0,n) {
			cin>>a[i][j]; 
			if(j>0) { a[i][j]+=a[i][j-1]; }
		}
	}
	int ans=-1; 
	reu(i,0,n){
		int temp=a[0][i]+((i==0)? a[1][n-1]: (a[1][n-1]-a[1][i-1])); 
		ans=max(ans,temp); 
	}
	cout<<ans; 
}

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

ll MOD = 1e9 + 7;
ll MAXN = MOD + 6;

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        res %= MOD;
        a = a * a;
        a %= MOD;
        b >>= 1;
    }
    return res;
}

ll inverse(ll n) {
    return binpow(n, MOD-2);
}

ll fact (ll n) {
	ll res = 1;
	FOR(i, 1, n+1) {
		res *= i;
		res %= MOD;
	}
	return res;
}

ll choose(ll n, ll k) {
	ll res = 1;
	FOR(i, n-k+1, n+1) {
		res *= i;
		res %= MOD;
	}
    return res * inverse(fact(k)) % MOD;
}

int main() {
	ll N, A, B; cin >> N >> A >> B;
	print((binpow(2, N) - choose(N, A) - choose(N, B) - 1 + 2 * MOD) % MOD);
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;

namespace ABC127 {
  class ProblemB {
    static void Main(string[] args) {
      int[] input = Input.nums, input2;
      int[] l = new int[input[1]], r = new int[input[1]];
      int[] pass = new int[input[0] + 1];
      
      for (int i = 0; i < input[1]; i++) {
        input2 = Input.nums;
        l[i] = input2[0]; r[i] = input2[1];
      }
      for (int i = 0; i < input[1]; i++) {
        pass[l[i] - 1]++;
        pass[r[i]]--;
      }
      for (int i = 0; i < input[0]; i++) {
        if (i > 0) pass[i] += pass[i - 1];
      }
      int cnt = 0;
      for (int i = 0; i < input[0]; i++) {
        if (pass[i] == input[1]) cnt++;
      }
      System.Console.WriteLine(cnt);
    }
  }
  public class Input {
    public static string str => System.Console.ReadLine();
    public static string[] strs => str.Split(' ');
    public static char[] charArr => str.ToCharArray();
    public static int num => int.Parse(str);
    public static int[] nums => Array.ConvertAll(strs, int.Parse);
    public static long numL => long.Parse(str);
    public static long[] numLs => Array.ConvertAll(strs, long.Parse);
  }
}

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

int main() { /* ここに書く */
  
  long long A,B,C,K,N;
  cin >> A >> B >> C >> K;
  N = 0;
  
  if(K<A){
    N = N + K;
    K = 0;}
  else{
    N = N + A;
    K = K-A;}
  
  if(K<B){
    K = 0;
  }
  else{
    K = K-B;}

    N = N - K;
  
  cout << N <<endl;
  
}



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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){ cerr << "\n"; } template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }



int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, k;
	cin >>n >>k;
	VI a(n);
	rep(i, n) cin >>a[i];
	
	ll sm = accumulate(all(a), 0LL);
	VI dv;
	for(ll i=1; i*i <=sm; i++){
		if(sm % i ==0){
			dv.push_back(i);
			if(i*i != sm)dv.push_back(sm/i);
		}
	}
	sort(dv.rbegin(), dv.rend());

	for(auto cn: dv){
		VI b =a, c(n);
		rep(i, n) b[i] = b[i]%cn;
		sort(all(b));
		rep(i, n) c[i] = (cn - b[i])%cn;

		VI bp(n+1), cp(n+1);
		rep(i, n) bp[i+1] = bp[i] + b[i];
		repr(i, n-1, 0) cp[i] = cp[i+1] + c[i];
		//for(auto x :bp) printf("%3d", x); dbg(" cn",cn);
		//for(auto x :cp) printf("%3d", x); dbg(" cn",cn);
	
		rep(i, n){
			if(bp[i] == cp[i] && cp[i] <= k){
				cout << cn <<"\n";
				return 0;
			}
		}
	
	}
	
	
	return 0;
	
}


Measured memory_bytes: 384
n,m = map(int,input().split())
lr = []
for i in range(m):
    LR = list(map(int,input().split()))
    lr.append(LR)
min,max = 1,n
for i in range(m):
    if lr[i][0] > min:
        min = lr[i][0]
    if lr[i][1] < max:
        max = lr[i][1]
if min > max:
    print("0")
else:
    print(max - min + 1)

Measured memory_bytes: 27276
# アルファベットをずらす数
SHIFT_COUNT = int(input())
# 暗号化する文字列
encryptionStr = input()
# 暗号化から除外する文字列
excludeStr = "{}_"
# 暗号化した文字列の結果を格納
result = ""

for c in encryptionStr :
    # 除外する文字列ならば変換せず、そのままにする
    if excludeStr.find(c) != -1 :
        result = result + c
        continue

    # 暗号化する処理
    if ord('a') <= ord(c) <= ord('z') :
        result = result + chr(abs(((ord(c) + SHIFT_COUNT - ord('a')) % 26)) + ord('a'))
    else :
        result = result + chr(abs(((ord(c) + SHIFT_COUNT - ord('A')) % 26)) + ord('A'))

print (result)

Measured memory_bytes: 3064
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	int ar[n],i,j=0,pr[n];
	for(i=0;i<n;i++){
		cin>>ar[i];
		pr[i]=ar[i];
	}
	sort(ar,ar+n);
	for(i=0;i<n;i++){
		if(ar[i]!=pr[i]){
			j++;
		}
	}
	if(j==0 || j==2){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
        int n, m, k, ans = 2e9;
        cin >> n >> m >> k;
        for(int i = 0; i <= m; ++i)
                for(int j = 0; j <= n; ++j)
                        if(i * n + j * m - i * j >= k) ans = min(ans, i + j);
        cout << ans;
        return 0;
}


Measured memory_bytes: 3592
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
#include<iomanip>
#include<functional>
using namespace std;

#define ll long long
using vt = ll; //ここで数値の型を変えられる
#define rep(i, n) for (vt i = 0; i < (vt)(n); i++)
#define reps(i, s, n) for(vt i = (vt) (s); i < (vt) (n); i++) 
#define all(v) v.begin(), v.end()
#define P pair<int, int>
const ll  MOD = 1000000007;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (b + c < a) cout << 0;
	else cout << c + b - a;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define fs first
#define sc second

const int nmax = 100;
int t = 1;
int n;
string s, st;

void INPUT()
{
     cin >> n;
     cin >> s;
}

void INIT()
{
     st = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
}

void SOLVE()
{
     for(int i = 0; i < s.size(); i++) {
          int tmp = s[i] - 'A';
          s[i] = st[tmp + n];
     }
     cout << s;
}

int main()
{
    //freopen("test.inp","r",stdin);
    INPUT();
    INIT();
    while (t--) SOLVE();
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  string s;
  cin>>s;
  for(int i=1;i<s.length();i++) {
    if(s[i-1]=='A'&&s[i]=='C'){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
}

Measured memory_bytes: 256
N, K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7

count_1 = 0
count_2 = 0

for i in range(N):
    for j in range(N):
        if(A[i] > A[j]):
            count_2 += 1
            if i < j:
                count_1 += 1

k = (K-1)*K//2
B = count_1 * K + count_2 * k

print(B%mod)




# mod=10**9+7
# n,k=map(int,input().split())
# arr=list(map(int,input().split()))
#
# cnt1=[0]*n
# cnt2=[0]*n
#
# for i in range(n):
#   for j in range(n):
#     if arr[i]>arr[j]:
#       cnt2[i]+=1
#       if i<j:
#         cnt1[i]+=1
#
# ans=0
# for val in cnt1:
#   ans+=val*k
#   ans%=mod
# for val in cnt2:
#   ans+=val*(k*(k-1)//2)
#   ans%=mod
# print(ans)



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

using pll = pair<long, long>;
constexpr long MOD = 1000000007;

int main() {
	string s, t; cin >> s >> t;
	long ans = LONG_MAX;
	for (long i = 0; i < s.size() - t.size() + 1; i++) {
		long tmp = 0;
		for (long j = 0; j < t.size(); j++) {
			if (s[i + j] != t[j]) tmp++;
		}
		ans = min(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3152
#include<iostream>
using namespace std;
int main()
{
    int N;
    cin >> N;
    int D[N][2];
    for(int i = 0; i < N; i++){
        cin >> D[i][0] >> D[i][1];
    }
    for(int i = 0; i < N-2; i++){
        if(D[i][0] == D[i][1] && D[i+1][0] == D[i+1][1] && D[i+2][0] == D[i+2][1]){
            cout << "Yes";
            goto Exit;
        }
    }
    cout << "No";
    Exit: ;
}

Measured memory_bytes: 3632
#include<stdio.h>
 
int main(){
  int n,i;
  int s;
  int cnt=0;
 
  scanf("%d\n",&n);
  while((s=getchar())!='\n'){
   if(s=='R') cnt++;
  }

  if(cnt>n/2) printf("Yes");
  else	printf("No");
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>

int main(){
   int N;
   std::cin >> N;
   int P;
   int min = N;
   int ans = 0;
   for(int i=0; i<N; ++i){
      std::cin >> P;
      if(P<=min){
	 min = P;
	 ++ans;
      }
   }
   std::cout << ans << std::endl;
   return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int A,B,C,D,K;

signed main(){
	cin>>A>>B>>C>>D>>K;
	cout<<(C*60+D)-(A*60+B)-K<<endl;
	return 0;
}


Measured memory_bytes: 3636
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n,sum;
		
		while(true){
			n = sc.nextInt() / 4;
			if(n == 0)break;
			sum = 0;
			
			for(int i = 0; i < n; i++)
				sum += sc.nextInt();
			
			System.out.println(sum);
		}
		sc.close();
	}
}

Measured memory_bytes: 18164
#include <iostream>

using namespace std;

int main()
{
    int N, K;
    string S;
    cin >> N >> S >> K;
    const char kthChar = S[K-1];
    string result = "";
    for(const char &ch : S){
        if(ch == kthChar){
            result += ch;
        }
        else{
            result += '*';
        }
    }
    cout << result;
}

Measured memory_bytes: 256
//written by libra9z
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,n) for (int i=0;i<(n);i++)
#define repit(it,a) for (__typeof(a.begin()) it=a.begin();it!=a.end();++it)
#define RET(p,x) return p<<x<<endl,0
#define all(a) (a).begin(),(a).end()
#define reunique(v) v.erase(unique(all(v)),v.end())
#define sz(a) (int)a.size()
#define sqr(x) ((x)*(x))
const int inf=1e9;
const ll lnf=1e18;
const int mod=1e9+7;
const int Maxn=2e5+5;
int n,sum;
int a[Maxn],b[Maxn];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie();cout.tie();
	cout<<setprecision(15);
	cin>>n;
	for (int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
	sort(a+1,a+n+1);
	int k=(n+1)/2;
	for (int i=1;i<=n;++i)
	{
		if (b[i]<=a[k])
		{
			cout<<a[k+1]<<endl;
		}
		else cout<<a[k]<<endl;
	}
	return 0;
}

Measured memory_bytes: 3712
#include<stdio.h>

int main(void)
{
	int a, b, answer;
	char op;

	while (1){
		scanf("%d %c %d", &a, &op, &b);
		if (op == '?')
			break;
		switch (op){
		case '+':
			answer = a + b;
			break;
		case '-':
			answer = a - b;
			break;
		case '*':
			answer = a * b;
			break;
		case '/':
			answer = a / b;
			break;
		}
		printf("%d\n", answer);
	}
	return 0;
}

Measured memory_bytes: 1028
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long a[1000 + 100][2], b[10 + 100][100000+100] = { 0 };
long long sol(int n, int i, int j)
{
	if (i == n - 1)
	{
		long long m = -8;
		for(int t = 0; t < 3; t++)
		{
			if (t != j)
				m = max(m, a[i][t]);
			
		}
		return m;
	}
	long long m = -8,s=0;
	for (int t = 0; t < 3; t++)
	{
		if (t != j)
		{
			if (m < a[i][t])
				s = t;
			m = max(m, a[i][t]);

		}

	}
	if(b[i][s]==-1)
	b[i][s]= m + sol(n, i + 1, s);
	return b[i][s];
}
int main()
{
	
	int n,w;
	cin >> n>>w;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 2; j++)
		{
			cin >> a[i][j];
			
		}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			if (j - a[i][0] > -1)
			{
				b[i][j] = max(a[i][1] + b[i-1][j - a[i][0]],b[i-1][j]);
			}
			else b[i][j] = b[i - 1][j];
			
		}
		
	}
	cout << b[n][w]<<endl;
	return 0;
}

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

#define Need_For_Speed ios_base::sync_with_stdio;cin.tie(NULL);cout.tie(NULL);

#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define sz size()
#define fi first
#define se second

#define batr ONLINE_JUDGE
#define all(x) (x).begin(),(x).end()
#define skip continue

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e6 + 17, maxN = 4 * N, darr = 1e3 + 17, mod = 1e9 + 7;

int n;

int sum (int n) {
	int res = 0;
	while (n) {
		res += (n % 10);
		n /= 10;
	}
	return res;
}

int main () {
	Need_For_Speed;
	cin >> n;
	int mn = darr;
	for (int i = 1; i + i <= n; i++) {
		mn = min(mn, sum(i) + sum(n - i));
	}
	cout << mn;
	return 0;
}

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

int a,b,c;

int main(void){
	scanf("%d %d", &a, &b);
	if(b == b%10)	c=10*a+b;
	else if(b==b%100)	c=100*a+b;
	else	c=1000*a+b;

	if(floor(sqrt(c)) == sqrt(c))	printf("Yes");
	else	printf("No");

	return 0;
}

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

int main()
{
	int n;
	cin >> n;
	string s;
	int k;
	vector<tsii> v;
	rep(i, n)
	{
		cin >> s >> k;
		tsii t(s, 100 - k, i+1);
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	for (auto x : v)
		cout << get<2>(x) << endl;
}


Measured memory_bytes: 3600
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define pi acos(-1.0)
#define maxd 1000000007
typedef long long ll;
int n,dp[1001000],xo[1001000],cnt[1001000],ans=0,w[1001000];

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

int main()
{
	n=read();memset(w,0,sizeof(w));int i,j;
	for (i=1;i<n;i++) 
	{
		int u=read(),v=read(),w1=read();
		w[u]^=w1;w[v]^=w1;
	}
	for (i=0;i<n;i++) cnt[w[i]]++;
	int ans=0,now=0;
	for (i=1;i<=15;i++)
	{
		ans+=cnt[i]/2;now|=(cnt[i]&1)<<(i-1);
	}
	int all=(1<<15)-1;
	for (i=1;i<=all;i++) dp[i]=dp[i>>1]+(i&1);
	for (i=1;i<=all;i++) dp[i]--;
	for (i=0;i<=all;i++)
	{
		xo[i]=0;
		for (j=1;j<=15;j++)
		{
			if ((i>>(j-1))&1) xo[i]^=j;
		}
	}
	for (i=1;i<=all;i++)
	{
	    if (xo[i]) continue;
		for (j=i;j;j=(j-1)&i)
		{
		    if (!xo[j]) dp[i]=min(dp[i],dp[j]+dp[j^i]);
		}
	}
	ans+=dp[now];
	printf("%d",ans);
	return 0;
}



Measured memory_bytes: 8576
use std::cmp::Reverse;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();

    let mut positive = vec![];
    let mut negative = vec![];
    for _ in 0..n {
        let s = sc.chars();
        let (left, right) = compile(s);

        if left - right > 0 {
            positive.push((left, right));
        } else {
            negative.push((left, right));
        }
    }

    positive.sort_by_key(|&(_, right)| right);

    let mut left_stack = 0;
    for (left, right) in positive.into_iter() {
        if left_stack < right {
            println!("No");
            return;
        }
        left_stack -= right;
        left_stack += left;
    }

    negative.sort_by_key(|&(left, _)| left);
    let mut right_stack = 0;
    for (left, right) in negative.into_iter() {
        if right_stack < left {
            println!("No");
            return;
        }
        right_stack -= left;
        right_stack += right;
    }

    if left_stack == right_stack {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn compile(s: Vec<char>) -> (i64, i64) {
    let mut left = 0;
    let mut right = 0;
    for c in s.into_iter() {
        match c {
            '(' => {
                left += 1;
            }
            ')' => {
                if left > 0 {
                    left -= 1;
                } else {
                    right += 1;
                }
            }
            _ => unimplemented!(),
        }
    }
    (left, right)
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 17848
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int K = scan.nextInt();
        long[] A = new long[N];
        for (int i = 0; i < N; i++) {
            A[i] = scan.nextLong();
        }
        long[] sum = new long[N + 1];
        for (int i = 0; i < N; i++) {
            sum[i + 1] = sum[i] + A[i];
        }
        Map<Long, Long> map = new HashMap<>();
        for (int i = 0; i <= Math.min(K-1, N); i++) {
            long m = (sum[i] - i + K) % K;
            if (!map.containsKey(m)) {
                map.put(m, 0L);
            }
            long c = map.get(m);
            map.put(m, c + 1);
        }
        long answer = 0;
        for (int i = 0; i <= N; i++) {
            long m = (sum[i] - i + K) % K;
            long x = map.get(m);
            answer += x - 1;
            map.put(m, x - 1);
            if (i + K <= N) {
                long n = (sum[i + K] - (i + K) + K) % K;
                if (!map.containsKey(n)) {
                    map.put(n, 0L);
                }
                long c = map.get(n);
                map.put(n, c+1);
            }
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 103796
n = int(input())
s = input()
o = int()
s = list(s)
for i, youso in enumerate(s):
    o = ord(youso)
    if o+n>90:
        s[i] = chr(64 + n-(90-o))
    else:
        s[i] = chr(o + n)
print("".join(s))

Measured memory_bytes: 3064
import numpy as np
 
N, K = [int(i) for i in input().split()]
ab = np.array(
  [[int(i) for i in input().split()] for _ in range(N)])
 
idx_ab = np.argsort(ab[:, 0])
ab = ab[idx_ab, :]

k_sum = 0
 
for record in ab:
  a = record[0]
  b = record[1]
  
  k_sum += b
  if k_sum >= K:
    print(a)
    break

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

using namespace std;

#define rep(i,n) for (decay_t <decltype (n)> i = 0, i ## __len = (n); i < i ## __len; ++ i)

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

  size_t n;
  cin >> n;

  vector <tuple <int, string, int>> rs;

  rep (i, n)
  {
    string s;
    int p;
    cin >> s >> p;

    rs.emplace_back (i + 1, s, p);
  }

  sort (rs.begin (), rs.end (), [&] (auto && r1, auto && r2) {
    string s1, s2;
    int p1, p2;
    tie (ignore, s1, p1) = r1;
    tie (ignore, s2, p2) = r2;
    return s1 == s2 ? p1 > p2 : s1 < s2;
  });

  for (auto && elem : rs)
  {
    int id;
    tie (id, ignore, ignore) = elem;
    cout << id << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] p = new int[M];
        String[] S = new String[M];
        boolean[] judge = new boolean[N + 1];
        int correct = 0;
        int[] penalty = new int[N + 1];

        for (int i = 0; i < M; i++) {
            p[i] = sc.nextInt();
            S[i] = sc.next();
            if (judge[p[i]] != true) {
                if (S[i].equals("AC")) {
                    judge[p[i]] = true;
                    correct++;
                } else {
                    penalty[p[i]]++;
                }             
            }
        }

        int penaltySum = 0;
        boolean[] plusJudge = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            if (judge[p[i]] == false) {
                penalty[p[i]] = 0;
            }
            if (plusJudge[p[i]] == true) {
                continue;
            }
            penaltySum += penalty[p[i]];
            plusJudge[p[i]] = true;
        }

        System.out.println(correct + " " + penaltySum);
        
        sc.close();
    }
}

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

long long gcd(long long a, long long b){
  if (a%b == 0){
    return(b);
  }else{
    return(gcd(b, a%b));
  }
}

long long lcm(long long a, long long b){
  return a / gcd(a, b) * b;
}

int main() {
  int N;
  cin >> N;
  vector<long long> T(N);
  long long lcm_tmp = 1;
  for(int i=0;i<N;i++){
    cin >> T.at(i);
    lcm_tmp = lcm(T.at(i),lcm_tmp);
  }
  cout << lcm_tmp << endl;

}

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

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
#define REP(i, n)  for(int i = 0; i < n; ++i)
#define FOR(i, t, n)  for(ll i = t; i <= (ll)n; ++i)
struct edge {
    int from, to;
    ll cost;
};


class Eratosthenes {
public:
    vector<bool> prime;

    Eratosthenes(int size) {
        prime.resize(size + 1, 1);
        prime[0] = 0;
        prime[1] = 0;
        FOR(i, 2, size) {
            if (prime[i]) {
                for (int j = 2 * i; j <= size; j += i) {
                    prime[j] = 0;
                }
            }
        }
    }

};


class Combination {
    vector<ll> fac; //n!(mod M)
    vector<ll> ifac; //k!^{M-2} (mod M)
public:
    Combination(ll size) {
        fac.resize(size);
        ifac.resize(size);
        fac[0] = 1;
        ifac[0] = 1;
        for (ll i = 0; i < size; i++) {
            fac[i + 1] = fac[i] * (i + 1) % MOD;
            ifac[i + 1] = ifac[i] * mpow(i + 1, MOD - 2) % MOD;
        }
    }

    ll mpow(ll x, ll n) {
        ll ans = 1;
        while (n != 0) {
            if (n & 1) ans = ans * x % MOD;
            x = x * x % MOD;
            n = n >> 1;
        }
        return ans;
    }

    ll comb(ll a, ll b) {
        if (a == 0 && b == 0)return 1;
        if (a < b || a < 0)return 0;
        ll tmp = ifac[a - b] * ifac[b] % MOD;
        return tmp * fac[a] % MOD;
    }
};


ll GCD(ll a, ll b) {
    if (b == 0)return a;
    return GCD(b, a % b);
}

ll LCM(ll a, ll b) {
    ll gcd = GCD(a, b);
    return a / gcd * b;
}

int N, C, K;

int main() {
    cin >> N;
    vector<int> A(3 * N);
    REP(i, 3 * N)cin >> A[i];
    sort(A.begin(), A.end());
    ll res = 0;
    int l = 0, r = 3 * N ;
    while (l < r) {
        l++;
        r -= 2;
        res += A[r];
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vec A(n);
    rep(i,n) cin>>A[i];
    rep(i,n) A[i]-=i+1;
    sort(all(A));
    ll ans=0;
    rep(i,n) ans+=abs(A[i]-A[n/2]);
    cout<<ans<<"\n";
}

Measured memory_bytes: 4740
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<int(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;

struct Edge{ int src, dest; };

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &g, int from, int to) {
  g[from].push_back((Edge){from, to});
}

int scc(Graph &graph, vector<int> &cmp) {
  int V = graph.size();
  vector<vector<int>> g(V), rg(V);
  vector<int> vs;
  vector<bool> used(V, false);
  cmp.resize(V);
  REP(i,V) {
    for (Edge e: graph[i]) {
      g[i].push_back(e.dest);
      rg[e.dest].push_back(i);
    }
  }
  function<void(int)> dfs = [&g, &vs, &used, &dfs](int v) {
    used[v] = true;
    for (int i: g[v]) if (!used[i]) dfs(i);
    vs.push_back(v);
  };
  function<void(int,int)> rdfs = [&rg, &cmp, &used, &rdfs](int v, int k) {
    used[v] = true; cmp[v] = k;
    for (int i: rg[v]) if (!used[i]) rdfs(i, k);
  };
  REP(v,V) if (!used[v]) dfs(v);
  used = vector<bool>(V, false);
  reverse(ALL(vs));
  int k = 0;
  for(int i: vs) if (!used[i]) rdfs(i, k++);
  return k;
}

vector<vector<int>> buildRevGraph(const Graph &g, const vector<int> &cmp, int K) {
  int V = g.size();
  vector<set<int>> s(K);
  vector<vector<int>> res(K);
  REP(i,V) for (Edge e: g[i]) s[cmp[i]].insert(cmp[e.dest]);
  REP(i,K) for (int j: s[i]) if (i != j) res[j].push_back(i);
  return res;
}

using ld = long double;

int main() {
  while(1) {
    int n;
    cin>>n;
    if(!n) break;
    Graph g(n);
    vector<ld> prob(n);
    REP(i,n) {
      int m;
      cin>>prob[i]>>m;
      REP(j,m) {
        int a;
        cin>>a;
        --a;
        add_edge(g, i, a);
      }
    }
    vector<int> cmp;
    int k = scc(g, cmp);
    auto dag = buildRevGraph(g, cmp, k);
    vector<ld> vp(k, 1.0); 
    REP(i,n) {
      vp[cmp[i]] *= prob[i];
    }
    ld res = 1.0;
    REP(i,k) if (dag[i].empty()) res *= 1.0 - vp[i];
    cout << fixed << setprecision(10) << res << endl;
  }
  return 0;
}

Measured memory_bytes: 3384
import math

def minus_one(n):
    return n - 1

N, K = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
A = list(map(minus_one, A))

doubling_table = [A]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K -= 2 ** i
        city = doubling_table[i][city]
        
print(city + 1)

Measured memory_bytes: 216792
N,K = map(int,input().split())

sunuke = [0]*N
okashi = []

for i in range(K):
    gomi = input()
    temp = input().split()
    okashi.append(temp)
    
    


for i in range(len(okashi)):
    for j in okashi[i]:
        sunuke[int(j) - 1] += 1
        

count = 0

for i in range(N):
    if sunuke[i] == 0:
        count += 1
        
print(count)

Measured memory_bytes: 9448
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n,a[100005];
	cin >> n;
	
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		sort(a, a + n );
		cout << a[(n / 2)] - a[(n / 2) - 1] << '\n';
}

Measured memory_bytes: 640
N = int(input())
Ali = list(map(int,input().split()))
bli = [0]*(N+1)
M = 0

for z in range(N):
  i = N-z
  #iの倍数の箱の和%2がAliと同じか調べる
  sb = 0
  for j in range(i*2,N+1,i):
    sb += bli[j]
  if sb%2 != Ali[i-1]:
    bli[i] = 1
    M += 1
    
print(M)

cnt = 0
for i in range(N+1):
  if bli[i] == 1:
    cnt += 1
    if cnt == M:
      print(i)
    else:
      print(i,end=" ")

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

bool check (string s){
  int n = s.length();
  if (n%2==1){
    return false;
  }
  else {
    return (s.substr(0,n/2-1)==s.substr(n/2));
  }
}

int choise_sort (int n, int a[]){
  int index;
  for (int i=0; i<n-1; i++){
    int min = a[i], num;
    for (int j=i; j<n-1; j++){
      if (a[j+1]<min){
        min = a[j+1];
        num = j+1;
      }
    }
    index = a[i];
    a[i] = min;
    a[num] = index;
  }
}

int main(){
  int h, w;
  cin >> h >> w;

  string board[50];

  for (int i=0; i<h; i++) cin >> board[i];

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

  for (int i=0; i<h; i++){
    for (int j=0; j<w; j++){
      if (board[i][j] == '#') continue;

      int num = 0;
      for (int d=0; d<8; d++){
        const int ni = i + dx[d];
        const int nj = j + dy[d];

        if (ni < 0 or h <= ni) continue;
        if (nj < 0 or w <= nj) continue;
        if (board[ni][nj] == '#') num++;
      }

      board[i][j] = char(num + '0');
    }
  }

  for (int i=0; i<h; i++) cout << board[i] << endl;

  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

int main() {

    int A,B,C;
    cin >> A >> B >> C;
    string out = "No";
    if((A == B && A != C) || (A != B && A == C) || (A != B && B == C)) out = "Yes";
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N = int(input().strip())
#-----

def get_divisor(n :int) -> dict:
    divisor_dic={}
    tmp_num = n

    for i in range(2, int(n**(1/2)+1) ):
        while tmp_num % i == 0:
            divisor_dic.setdefault(i,0)
            divisor_dic[i] += 1
            
            tmp_num //= i
    
    if (tmp_num != 1):
        divisor_dic[tmp_num] = 1
    
    return divisor_dic
#-----

div = get_divisor(N)
cnt =0

for num,pow in div.items():
    for p in range(1, pow+1):
        #if N % (num ** p) == 0:
        #    N /= (num ** p)
        #    cnt += 1
        
        if div[num] >= p:
            div[num] -= p
            cnt += 1


print(cnt)


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()
#define vprint(v) for(auto e:v){cout<<e<<" ";};cout<<endl;
#define vvprint(vv) for(auto v:vv)vprint(v);

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

    ll D, T, S;
    cin >> D >> T >> S;

    if(D<=T*S) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

int main(){
	int n; 
	while( cin >> n, n ){
		vector<int> s(n);
		for(int i=0 ; i < n ; i++ ){
			cin >> s[i];
		}
		sort( s.begin(), s.end() );
		int sum = 0;
		for(int i=1 ; i < s.size()-1 ; i++ ){
			sum += s[i];
		}
		cout << (sum / (s.size() - 2)) << endl;
	}
}

Measured memory_bytes: 0
#######################################################################################
import sys
from math import sqrt
 
 
def rec(state, v):
    if state == (1 << N) - 1:
        return cakes[v]
    if dp[state][v] != -1:
        return dp[state][v]
 
    ret = INF
    for u in range(N):
        if state == 0:
            ret = min(ret, rec(1 << u, u) + cakes[u])
        elif not (state >> u & 1):
            ret = min(ret, rec(state | 1 << u, u) + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - cakes[v], 2)))
    dp[state][v] = ret
    return ret
 
 
testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]
 
for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    dp = [[-1] * N for _ in range(1 << N)]
    print('OK' if rec(0, 0) <= box else 'NA')


Measured memory_bytes: 7644
#include<bits/stdc++.h>
//#define fori(a,n) for(int i=a,i<n;i++)
#define MX 1000007
using namespace std;

int main()
{
    int n,d,x,a,sum=0;

    cin>>n>>d>>x;

    int ara[n];

    for(int i=0;i<n;i++)
    {
        cin>>a;
        int test=1;
        sum++;

        for(int j=1;test<=d;j++)
        {
            test=(j*a+1);
            //cout<<test<<" ";
            if(test<=d)
                sum++;
        }
    }
    cout<<sum+x<<endl;

    return 0;
}


Measured memory_bytes: 256
//Code by ASIM FOIZE AIMON
//CSE'19;CUET
//avoid copy paste//Hit the frined button
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define precise cout.precision(10); cout << fixed;
#define endl "\n"
#define int int64_t
#define ll long long
#define yes printf("Yes\n")
#define no printf("No\n")

int32_t main()
{
    /*#ifndef ONLINE_JUDGE
        freopen("/media/AIMON/SSDVol/Progs/CodeForces/input.txt", "r", stdin);
        freopen("/media/AIMON/SSDVol/Progs/CodeForces/output.txt", "w", stdout);
    #endif*/
    int a[100001],b[100001],c,d,e,f,m,n,p,x,y,z,t,i,j,k;
       cin>>c>>d>>e;
       m=d*e;
       if(c<=m)
        yes;
       else
        no;
    }

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int c[34];

int main(void){
	int n,m,k,a,i,j,ans=0;
	fill(c,c+34,0);
	cin >> n >> m;
	for(i=0; i<n; ++i){
		cin >> k;
		for(j=0; j<k; ++j){
			cin >> a;
			--a;
			++c[a];
		}
	}
	for(i=0; i<m; ++i){
		if(c[i]==n){
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}


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

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree< int, null_type, less< int >, rb_tree_tag, tree_order_statistics_node_update> ost;
// name.find_by_order(x) or name.order_of_key(x)
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef vector<vector<int>> vvi;

void yes() {printf("YES\n");}
void no() {printf("NO\n");}

int dx4[] = {-1, 1, 0, 0};
int dy4[] = {0, 0, -1, 1};
int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

const int maxn = 2e5 + 5, maxv = 2e6 + 5;
int MOD = 1e9 + 7;

int mult(ll a, ll b) {return (a * b) % MOD;}
int pot(int n, int k) {
	int ret = 1, pot = n;
	for(;k > 0;k >>= 1, pot = mult(pot, pot)) 
		ret = mult(ret, (k & 1) ? pot : 1);
	return ret;
}
int divide(int a, int b) {return mult(a, pot(b, MOD - 2));}
int add(int a, int b) {a += b;if(a >= MOD) a -= MOD;return a;}
int sub(int a, int b) {a -= b;if(a < 0) a += MOD;return a;}

vector<int> fact;
void calc_fact(int n) {
	fact = vector<int>(n + 1, 1);
	for(int i = 1;i <= n;i++) fact[i] = mult(fact[i - 1], i);
}
int choose(int n, int k) {return divide(fact[n], mult(fact[n - k], fact[k]));}

bool prime(ll a) {
	if (a == 1) return 0;
	for(ll i = 2;i * i <= a;i++) 
		if (a % i == 0) return 0;
	return 1;
}

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

ll phi(ll x) {
	double ret = x;
	for(ll i = 2;i * i <= x;i++) {
		if (x % i) continue;
		ret *= (1.0 - 1.0 / (double)i);
		while (x % i == 0) x /= i;
	}
	if (x > 1) ret *= (1.0 - 1.0 / (double)x );
	return (ll)ret;
}

void solve() {
	ll n;
	int x, m;
	scanf("%lld %d %d", &n, &x, &m);
	MOD = m;
	vi vis(m, 0);
	vi v;
	int y = x, poc = -1;
	while(1) {
		if(vis[y]) {poc = y;break;}
		vis[y] = 1;
		v.pb(y);
		y = mult(y, y);
	}
	int pl = 0;
	for(int i = 0;i < (int)v.size();i++) if(v[i] == poc) pl = i;
	ll ans = 0;
	if(n < (int)v.size()) {
		for(int i = 0;i < n;i++) ans += (ll)v[i];
		printf("%lld\n", ans);
		return;
	}
	
	for(int i = 0;i < pl;i++) ans += (ll)v[i];
	ll cycle = 0;
	for(int i = pl;i < (int)v.size();i++) cycle += (ll)v[i];
	n -= pl;
	int sz = (int)v.size() - pl;
	ans += (ll)cycle * (n / sz);
	n %= sz;
	for(int i = pl;i < pl + n;i++) ans += (ll)v[i];
	printf("%lld\n", ans);
}

int main() {
	int t = 1;
	//scanf("%d", &t);
	while(t--) solve();
	return 0;
}


Measured memory_bytes: 4012
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    s = S()
    n = len(s)
    f = True
    for i in range(0,n,2):
        if s[i] == "L":
            f = False
            break
    for i in range(1,n,2):
        if s[i] == "R":
            f = False
    if f:
        return 'Yes'

    return "No"


print(main())





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

int A[200010];

int main() {
  int N; cin >> N;
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N-1; i++) {
    if (A[i] < 0) {
      A[i] *= -1; A[i+1] *= -1;
    }
  }
  if (A[N-1] > 0) {
    long sum = 0;
    for (int i = 0; i < N; i++) sum += A[i];
    cout << sum << endl;
  }
  else if (find(A, A+N, 0) != A+N) {
    long sum = 0;
    for (int i = 0; i < N; i++) sum += abs(A[i]);
    cout << sum << endl;
  }
  else {
    for (int i = 0; i < N; i++) A[i] = abs(A[i]);
    long sum = 0;
    for (int i = 0; i < N; i++) sum += A[i];
    sum -= 2 * *min_element(A, A+N);
    cout << sum << endl;
  }
}

Measured memory_bytes: 4020
from functools import reduce
A, B, C, D = map(int, input().split())
if C == 1 or D == 1:
  print(0)
  exit()

def gcd(*numbers):
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    return reduce(gcd, numbers)

def lcm(*numbers):
    def lcm(a, b):
        return (a * b) // gcd(a, b)
    return reduce(lcm, numbers, 1)

result = 0

if A%C == 0 or A%D == 0:
  A += 1

result += (B-A+1) - (B//C - A//C) - (B//D - A//D)
l = lcm(C, D)
result += (B//l - A//l)

print("{}".format(result))

Measured memory_bytes: 3572
from sys import stdin
N = int(input())

middle = 0
countB = 0
countA = 0
countBA = 0
sumcount = 0

for i in range(N):
    s = input()
    middle += s.count("AB")
    if s[0] == "B" and s[-1] == "A":
        countBA +=1
    elif s[0] == "B":
        countB +=1
    elif s[-1] == "A":
        countA +=1
if countBA > 0:
    sumcount += countBA -1
    if countA > 0:
        sumcount +=1
        countA -= 1
    if countB > 0:
        sumcount +=1
        countB -= 1

t = min(countA, countB)

print(sumcount+middle+t)


Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{

	public static void main(String[] args) throws Exception {
		// TODO ?????????????????????????????????????????????
		int[] arg =new int[100];
        int i=0,sum=0,n=0,m=0;
        int[] bibs=null;
        int[][] result=null;
        boolean first=true;

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String line;
            while ((line = br.readLine()) != null) {
            	if(first){
            		String[] str=line.split(" ");
            		n=Integer.parseInt(str[0]);
            		m=Integer.parseInt(str[1]);
            		bibs=new int[n+1];
            		i=0;
            		first=false;
            	}else{
            		i++;
            		bibs[i]=Integer.parseInt(line);
            		if(i==n){
            			for(int k=1;k<=m;k++){
            				for(int j=1;j<n;j++){
            					if(bibs[j]%k>bibs[j+1]%k){
            						int w=bibs[j];
            						bibs[j]=bibs[j+1];
            						bibs[j+1]=w;
            					}
                			}
            			}
            			for(int j=1;j<n+1;j++){
                			System.out.println(bibs[j]);
                		}
            			break;
            		}

            	}
            }
         }
	}

}

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

int main() {
	int N;
	cin >> N;
	string S;
	cin >> S;
	int ans = 0;
	char before = '@';
	rep(i,N){
		if(S[i] != before) ans++;
		before = S[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 512
N, M = map(int, input().split())
out = set()
for _ in range(M):
    out.add(int(input()))

check = [0] * (N + 1)
check[0] = 1

for i in range(1, N+1):
    if i not in out:
        if i == 1:
            check[i] = check[i-1]
        else:
            check[i] = check[i-2] + check[i-1]
    else:
        check[i] = 0

print(check[N] % 1000000007)

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

#define ll int
#define ull unsigned long long
#define pll pair<ll,ll>
#define MS(x, y) memset(x, y, sizeof(x))
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define INFL LLONG_MAX
#define pb push_back
#define FIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const ll N = 1e6 + 5;
const ll M = 5e2 + 5;
const ll mod = 1e9 + 7;
const ll m1 = 1e9 + 7;
const ll m2 = 1e9 + 9;
const ll p1 = 402653189;
const ll p2 = 1610612741;
const int LN = 32;

ll powermodm(ll x,ll n,ll M){ll result=1;while(n>0){if(n % 2 ==1)result=(result * x)%M;x=(x*x)%M;n=n/2;}return result;}
ll power(ll _a,ll _b){ll _r=1;while(_b){if(_b%2==1)_r=(_r*_a);_b/=2;_a=(_a*_a);}return _r;}
ll gcd(ll a,ll b){if(a==0)return b;return gcd(b%a,a);}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}

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

ll pw[LN],fact[N],invfact[N];

void pre()
{
    fact[0]=1;
    for(int i=0;i<LN;i++)pw[i]=power(2,i);
    for(int i=1;i<N;i++)fact[i]=(i*fact[i-1])%mod;
    for(int i=0;i<N;i++)invfact[i]=powermodm(fact[i],mod-2,mod);
}

int main()
{
    FIO;
    //pre();

    ll i,j;

    ll n;
    cin>>n;
    ll tmp = n;

    vector <pll> ans;

    if(n%2)
        n--;

    for(i=1;i<=n/2;i++)
    {
        for(j=i+1;j<=n/2;j++)
        {
            if(i==j)continue;
            ans.pb({i,j});
            ans.pb({i,n+1-j});
            ans.pb({n+1-i,j});
            ans.pb({n+1-i,n+1-j});
        }
    }
    if(tmp!=n)
    {
        for(i=1;i<=n;i++)
            ans.pb({tmp,i});
    }

    cout<<ans.size()<<"\n";
    for(i=0;i<ans.size();i++)
        cout<<ans[i].ff<<" "<<ans[i].ss<<"\n";

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int r;
  cin >> r;
  cout << fixed << setprecision(10) << M_PI * r * 2.0 << endl;
  return 0;
}

Measured memory_bytes: 3780