akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

N, M = map(int, input().split())
p = list(map(int, input().split()))
union_find = UnionFind(N)

for _ in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    union_find.unite(x, y)

set_list = [set() for _ in range(N)]

for i in range(N):
    root = union_find.find_root(i)
    set_list[root].add(p[i])

ans = 0
for i in range(N):
    if (i+1) in set_list[union_find.find_root(i)]:
        ans += 1

print(ans)


Measured memory_bytes: 40420
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        long a = stdin.nextLong();
        long b = stdin.nextLong();

        long x = Math.min(a, b);
        long y = Math.max(a, b);
        Set<Long> cms = new HashSet<>();
        for (long i = 1; i * i <= y; i++) {
            if (y % i != 0) continue;

            long j = y / i;
            if (x % i == 0) cms.add(i);
            if (x % j == 0) cms.add(j);
        }

        long ans = 1;
        for (long cm : cms) {
            if (isPrime(cm)) ans++;
        }

        System.out.println(ans);
    }

    private static boolean isPrime(long x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (long i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }
}


Measured memory_bytes: 23544
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int gcd(int a, int b) {
    if (a < b) return gcd(b, a);
    if(!b) return a;
    return gcd(b, a % b);
}

signed main() {
    int a, b;
    cin >> a >> b;
    int d = __gcd(a, b);
    int _d = d;
    int result = 1;
    for(int i = 2; i * i <= _d; ++i) {
        if (d % i == 0) {
            result++;
            while (d % i == 0)
                d /= i;
        }
    }
    if (d != 1) result++;
    cout << result << "\n";
}


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

using namespace std;

using ll = long long;

template<typename T>
bool is_prime(T n) {
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (T i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return n != 1;
}

template<typename T>
vector<T> divisor(T n) {
    vector<T> res;
    for (T i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    return res;
}

template<typename T>
map<T, int> prime_factor(T n) {
    map<T, int> res;
    for (T i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

template<typename T>
vector<T> sieve(T n) {
    vector<T> res;
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for (T i = 2; i <= n; i++) {
        if (!is_prime[i]) continue;
        res.emplace_back(i);
        for (T j = 2 * i; j <= n; j += i) is_prime[j] = false;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int x;
    cin >> x;
    for (int i = x; ; ++i) {
        if (is_prime(i)) {
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ld long double
#define ll long long
#define st first
#define nd second
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int l, r, d;
	cin>>l>>r>>d;
	int ans = 0;
	for(int i=d; i<=r; i+=d) {
		if(i >= l) ans++;
	}
	cout<<ans;
}


Measured memory_bytes: 3608
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    lis = list(map(int, input().split()))
    su = []
    for i in range(m - 1):
        su.append(lis[i + 1] - lis[i])
    ou = lis[0] - lis[-1] + n
    print(sum(su) + ou - max(ou, max(su)))

if __name__ == '__main__':
    main()


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


int main() {

    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int s; cin >> s;
        sum += s;
        a[i] = s;
    }
    sort(a.begin(), a.end());
    if (sum % 10 == 0) {
        for (int i = 0; i < n; ++i) {
            if (a[i] % 10 != 0) {
                sum -= a[i];
                break;
            }
        }
    }
    if (sum % 10 == 0) sum = 0;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int main(void){
    cin >> n;
    int sum = 0;
    while(n>0){
        sum += n % 10;
        n /= 10;
    }
    if(sum == 1){
        cout<<10<<endl;
    }else{
        cout<<sum;
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//ライブラリ張り付け
		int furui[] = new int[100010];//篩を作成

		for(int i = 2; i <= 100005; i++) {
			furui[i]=i;//篩に2~nまでの値を入れる
		}
		for(int i = 2; i <= Math.sqrt(100010); i++) {
			for(int j = i+i; j <= 100000; j+=i) {//iの倍数は篩落とす
				furui[j]=0;
			}
		}
		//
		int st, en;
		int[] ruisekiWA = new int[100000];
		for(int i = 3; i < 100000; i++) {
			ruisekiWA[i] = ruisekiWA[i-1];
			if(i%2==1&&furui[i]!=0&&furui[(i+1)/2]!=0) {
				ruisekiWA[i]++;
			}
		}
		for(int i = 0; i < n; i++) {
			st=sc.nextInt();
			en=sc.nextInt();
			System.out.println(ruisekiWA[en]-ruisekiWA[st-1]);
		}
	}
}

Measured memory_bytes: 75920
S=input()
T=input()

ans=[]
if T in S:
    print(S.replace("?","a"))
else:
    for i in range(len(S)-len(T)+1):
        flag=True
        for j in range(i,i+len(T)):
            if S[j]==T[j-i] or S[j]=="?":
                continue
            else:
                flag=False
                break
        if flag==True:
            s=S
            s=s[:i]+T+s[i+len(T):]
            ans.append(s.replace("?","a"))
    if len(ans)==0:
        print("UNRESTORABLE")
    else:
        ans.sort()
        print(ans[0])

Measured memory_bytes: 3064
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <queue>
# define MOD 1000000000+7
# define INF 1000000000
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
using namespace std;
long double a = 0, b = 0, c = 0, d = 0, e = 0, ans = 0, x = 0, y = 0, z = 0, N = 0, m = 0, maxy = 0, mini = 9999, counter = 0, endp = 0, checker = 0;
long double zahyo[100][100];
std::vector <char> vec{}, vecsec{}, vecth{};
long long int iremono[100010], koware[100001];
long long  int iremono2[100001], check[100001], xpo[10000001], ypo[10000001], hei[1000001];
std::vector<std::string>kinds{}, kaku{};
char maze[1000];
int sx, sy;
int gx, gy;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
bool okada = false, okada2 = false;
long long int dp[4][100003] ,ire[4][100003];
std::string input[103],one,two,three;
char re;

int H, W;//はんい
bool qw = false, er = false, ty = false, ui = false;
std::string code;
int main() {
	cin >> a >> b;
	rep(i, a){
		rep(j, b) {
			cin >> zahyo[i+1][j+1];
	}
	}
	rep(i, a) {//一個目の点
		for (int j = i; j < a; j++) {
			counter = 0;
			x = 1;
			rep(k, b) {
				counter += (zahyo[i + 1][k + 1] - zahyo[j + 1][k + 1])*(zahyo[i + 1][k + 1] - zahyo[j + 1][k + 1]);
			}
		
			while (x*x <= counter) {
				if (counter == x*x) {
					z++;
				}
				x++;
			}
		}
	}
	cout << z << endl;
}



Measured memory_bytes: 2304
using System;

namespace B___Coins
{
    class Program
    {
        static void Main(string[] args)
        {
            var A = int.Parse(Console.ReadLine());
            var B = int.Parse(Console.ReadLine());
            var C = int.Parse(Console.ReadLine());
            var X = int.Parse(Console.ReadLine());
            int cnt = 0;

            for (int a = 0; a <= A; a++)
            {
                for (int b = 0; b <= B; b++)
                {
                    for (int c = 0; c <= C; c++)
                    {
                        if (500 * a + 100 * b + 50 * c == X)
                        {
                            cnt++;
                        }
                    }
                }
            }
            Console.WriteLine(cnt);
        }
    }
}


Measured memory_bytes: 11092
#include <stdio.h>
int main(void){
    int a,b;
    
    scanf("%d",&a);
    scanf("%d",&b);
    
    if(a-1>b) printf("%d",2*a-1);
    else if(b-1>a) printf("%d",2*b-1);
    else printf("%d",a+b);
    
    
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>
int abs(int n){
    if(n>0)return n;
    return -n;
}
int main(){
    int n,x[100],y[100];
    double a=0,b=0,c=0,d=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&x[i]);
    }
    for(int i=0;i<n;i++){
        scanf("%d",&y[i]);
        if(abs(x[i]-y[i])>d)d=abs(x[i]-y[i]);
        a+=abs(x[i]-y[i]);
        b+=(x[i]-y[i])*(x[i]-y[i]);
        c+=abs(x[i]-y[i])*(x[i]-y[i])*(x[i]-y[i]);
    }
     
    printf("%lf\n%lf\n%lf\n%lf\n",a,sqrt(b),pow(c,0.33333333333),d);
}


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

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
#define test cout<<"test"<<endl;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
void debug(vector<vector<ll>>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j]<<" ";cout<<endl;}};
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}
//m.emplace(x,0).fi->second++;

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll a,b,c;cin>>a>>b>>c;
  if((a*b*c)%2==0)cout<<0<<endl;
  else{
    cout<<min({a*b,b*c,c*a})<<endl;
  }

  return 0;
}

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

using namespace std;
using ll = long long;
#define endl '\n'
#define all(v) v.begin(), v.end()

int main() {
    string s, t;
    cin >> s >> t;
    t.pop_back();
    if (s == t) cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 3596
INF = 100000000
N, M, R = gets.chomp.split(' ').map(&:to_i)
r = gets.chomp.split(' ').map(&:to_i)

cost = Array.new(N+1) {Array.new(N+1, INF)}

M.times do
  a, b, c = gets.chomp.split(' ').map(&:to_i)
  cost[a][b] = c
  cost[b][a] = c
end

(1..N).each do |k|
  (1..N).each do |i|
    (1..N).each do |j|
      path = cost[i][k] + cost[k][j]
      cost[i][j] = path if path < cost[i][j]
    end
  end
end

ans = INF
r.permutation do |rr|
  temp = 0
  (1..(rr.length-1)).each do |i|
    temp += cost[rr[i-1]][rr[i]]
  end
  ans = [ans, temp].min
end

puts ans

Measured memory_bytes: 2172
from collections import Counter
N, = map(int, raw_input().split())
A = map(int, raw_input().split())
c = Counter(A)
ks = c.keys()
ks.sort()
r = 0
for i in ks[::-1]:
  for j in xrange(60):
    p = 1<<j
    if i<=p:
      break
  if p==i:
    r += c[i]//2
  else:
    q = p-i
    x = min(c[i], c[q])
    r += x
    c[i] -= x
    c[q] -= x
print r

Measured memory_bytes: 53052
#include<bits/stdc++.h>
using namespace std;
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const int INF = 0x3f3f3f3f;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int maxn = 2e5 + 10; 

int main()
{
	fastIO;
	int n,m;
	cin >> n >> m;
	int ans = 0;
	if(n) ans += (n - 1) * n / 2;
	if(m) ans += (m - 1) * m / 2;
	cout << ans << endl;	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {


	int N;
	cin >> N;
	vector<int> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec[i];
	}

	vector<int> maxMap;
	vector<int> maxIdx;
	int maxMax = 0; int tmpId = 0;

	for (int i = vec.size() - 1; i >= 0;i--) {

		if (vec[i] > maxMax) {
			maxMax = vec[i];
			tmpId =  i ;
		}
		maxMap.push_back(maxMax);
		maxIdx.push_back(tmpId );
	}
	reverse(maxMap.begin(), maxMap.end());
	reverse(maxIdx.begin(), maxIdx.end());
	

	int ans = vec[1] - vec[0];
	int min = vec[0];
	for (int i = 0; i < vec.size();i++) {
		if (vec[i] < min) {
			min = vec[i];
		}
		if (maxMap[i] - min > ans && maxIdx[i] > i) {
			ans = maxMap[i] - min;
		}

	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 5488
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vii vector<vi>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
	 //cin.tie(0);
	//ios::sync_with_stdio(false);
	//std::cout << std::fixed;
	//std::cout << std::setprecision(12);
	//std::cout << std::defaultfloat;
	int n;
	cin>>n;
	vector<LL> a(n);
	vector<LL> ans(n,0);
	LL sm=0;
	FOR(i,0,n){
		cin>>a[i];
		sm+=a[i];
	}
	sm/=2;
	if(n==3){
		ans[0]=(sm-a[1])*2;
		ans[1]=(sm-a[2])*2;
		ans[2]=(sm-a[0])*2;

	}else{
		cerr<<sm<<endl;
		LL rst=sm;
		FOR(i,0,n-1){
			rst-=a[i];
			i++;
		}
		cerr<<rst<<endl;
		ans[n-1]=rst*2;
		ans[0]=(a[n-1]-rst)*2;
		FOR(i,1,n-1){
			ans[i]=(a[i-1]-ans[i-1]/2)*2;
		}

	}


	FOR(i,0,n){
		cout<<ans[i]<<" ";
	}

	return 0;
}


Measured memory_bytes: 2816
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    int K_MAX = (N-1) * (N-2) / 2;
    if (K > K_MAX){
        cout << -1 << endl;
        return 0;
    }
    int D = K_MAX - K;
    int M = N - 1 + D;
    cout << M << endl;
    for (int i = 2; i <= N; i++) cout << 1 << ' ' << i << endl;
    
    int u = 2, v = 3;
    while (D > 0){
        cout << u << ' ' << v << endl;
        if (v == N){
            u++;
            v = u + 1;
        }
        else v++;
        D--;
    }
}

Measured memory_bytes: 504
#include <cstdlib>
#include <iostream>
#include <vector>


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

  int n;
  std::cin >> n;
  std::vector<int> as(n);
  for (auto&& a : as) {
    std::cin >> a;
    a--;
  }

  int cnt = 0;
  int idx = 0;
  for (decltype(as)::size_type i = 0, j; i < as.size(); i++) {
    idx = as[idx];
    cnt++;
    if (idx == 1) {
      std::cout << cnt << std::endl;
      return EXIT_SUCCESS;
    }
  }
  std::cout << -1 << std::endl;

  return EXIT_SUCCESS;
}


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

int main() {
	// your code goes here
	long long int n,w;
	cin>>n>>w;
	long long int dp[n+1][w+1];
	memset(dp,0,sizeof(dp));
	for(long long int i=0;i<=w;i++)
	{
	    dp[0][i]=0;
	}
	for(long long int i=0;i<=n;i++)
	{
	    dp[i][0]=0;
	}
	pair<long long int,long long int> a[n];
	long long int c,b;
	for(long long int i=0;i<n;i++)
	{
	    cin>>c>>b;
	    a[i].first=c;
	    a[i].second=b;
	}
	//sort(a,a+n);
	for(long long int i=1;i<=n;i++)
	{
	    for(long long int j=1;j<=w;j++)
	    {
	        if(a[i-1].first<=j)
	        {
	            dp[i][j]=max(dp[i-1][j],a[i-1].second+dp[i-1][j-a[i-1].first]);
	        }
	        else dp[i][j]=dp[i-1][j];
	    }
	}
	cout<<dp[n][w]<<endl;
	return 0;
}


Measured memory_bytes: 79104
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
A = []
for _ in range(M):
    A.append(int(input()))
A.append(0)

prev = 1
prev_prev = 0
m = 0
for i in range(1,N+1):
    if A[m] == i:
        prev, prev_prev = 0, prev
        m += 1
    else:
        prev, prev_prev = (prev + prev_prev) % MOD, prev
print(prev)

Measured memory_bytes: 49240
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m,a,b,c;
    cin>>n>>m;
    vector<int>dp(1<<n,1000000000);
    dp[0]=0;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        int bit=0;
        for(int j=0;j<b;j++){cin>>c;bit|=1<<(c-1);}
        for(int j=0;j<1<<n;j++)dp[j|bit]=min(dp[j|bit],dp[j]+a);
    }
    cout<<(dp.back()==1000000000?-1:dp.back())<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

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

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

void	solve()
{
	int n;
	cin >> n;
	if (n == 1)
		cout << "Hello World" << endl;
	else {
		int a, b;
		cin >> a >> b;
		cout << a + b << endl;
	}
}

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

	solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define vll vector<ll>
#define pii pair<ll,ll>
#define sz(v) (v).size()
#define srt(v) sort(v.begin(),v.end())
#define ull unsigned long long
#define tell(a) cout<<a<<" "
#define el cout<<endl;
#define rev(v) reverse(v.begin(),v.end())
#define rep(i,a,n) for(int i=a;i<n;i++)
#define M 1000000007
ll power(ll x, ll y, ll p){ll res = 1;x = x % p;while (y > 0){   if (y & 1)res = (res*x) % p;y = y>>1;
x = (x*x) % p;}return res;}



int main()
{
	IOS;
	int n;
	cin>>n;
	vll v(n);
	rep(i,0,n)cin>>v[i];
	ll dp[n+1][61];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<60;j++)
		{
			dp[i+1][j]=dp[i][j];
			if(v[i]&((ll)1<<j))
			dp[i+1][j]+=1;
		}
	}
	ll ans=0;
//	for(int i=0;i<=n;i++)
//	{
//		for(int j=0;j<60;j++)
//		cout<<dp[i][j]<<" ";
//		el;
//	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<60;j++)
		{
			if(!(v[i]&((ll)1<<j)))
			{
			 	ans=(ans+(dp[n][j]-dp[i+1][j])*power(2,j,M))%M;
			}
			else
			ans=(ans+(((n-i-1)-dp[n][j]+dp[i+1][j])*power(2,j,M)))%M;
		}
	}
	cout<<ans;el;
}

Measured memory_bytes: 145536
N = str(input())
K = int(input())

dp = [[[0]*2 for _ in range(K+1)] for _ in range(len(N)+1)]
dp[0][0][0] = 1

for i in range(len(N)):
  n = int(N[i])
  for j in range(K+1):
    for k in range(2): # smaller(未満なら1)
      for l in range(10): 
        nj, nk = j, 0
        if k == 0 and l == n:
          nk = 0
        elif k == 0 and l < n:
          nk = 1
        elif k == 0 and l > n:
          continue
        
        if k == 1:
          nk = 1
        
        if l != 0:
          if j < K:
            nj += 1
          else:
            continue
        
        dp[i+1][nj][nk] += dp[i][j][k]

print(dp[-1][K][0] + dp[-1][K][1])


        


Measured memory_bytes: 68352
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << (x) << endl
using namespace std;

using ull = unsigned long long;
using ll = long long;

using Int = int;
using Double = double;

using P = pair<Int, Int>;
using V = vector<Int>;
using M = vector<V>;

const Double PI  = 3.141592653589793238463;
const Int MOD = 1000000007;
const Int INF = numeric_limits<Int>::max() / 3;

template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec){
        is >> x;
    }
    return is;
}

Int solve(Int n, string& s){
    Int m = 0;
    char x = 'X';
    for(char c: s){
        if(c != x){
            x = c;
            m++;
        }
    }
    return m;
}

int main(int argc, char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    Int n;
    string s;
    cin >> n >> s;
    cout << solve(n, s) << "\n";

    return 0;
}


Measured memory_bytes: 512
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9 + 7

ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + pow(i + 1, MOD - 2, MOD)

ans = 0
for i in range(n):
    ans += a[i] * (ruiseki[n - i] + ruiseki[i + 1] - ruiseki[1])
    ans %= MOD

for i in range(n):
    ans *= (i + 1)
    ans %= MOD

print(ans)

Measured memory_bytes: 62576
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
StringBuilder sb=new StringBuilder("");
		int H=sc.nextInt(),W=sc.nextInt();
		while (H!=0 || W!=0){
			for (int m=1;m<=W;m++){
			sb.append("#");}
		for (int n=1;n<=H;n++){System.out.println(sb);}
			System.out.println();
			sb.delete(0,W);
			H=sc.nextInt();W=sc.nextInt();
				}}}

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

int main(void) {
    int h, w;
    while (1) {
        cin >> h >> w;
        if (h == 0 && w == 0) break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cout << '#';
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 1152
students = []
cnt = 0
while True:
    m, f, r = map(int, input().split())
    if (m, f, r) == (-1, -1, -1):
        break
    else:
        students.append((m, f, r))
        cnt += 1

for i in range(cnt):
    m, f, r = students[i]
    if m == -1 or f == -1 or m + f < 30:
        print('F')
    elif m + f >= 80:
        print('A')
    elif m + f >= 65:
        print('B')
    elif m + f >= 50 or r >= 50:
        print('C')
    else:
        print('D')



Measured memory_bytes: 5600
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
const int nax=57;
ll mod;

int n=50;

ll pot[nax][nax];

ll wyn;

int jeszrz[nax];
int jeszkol[nax];

void ff()
{
	fflush(stdout);
}

int pyt(int a, int b, int x, int y)
{
	printf("? %d %d %d %d\n", a, x, b, y);
	ff();
	int v;
	scanf("%d", &v);
	return v;
}

int los(int a, int b)
{
	return (rand()%(b-a+1))+a;
}

void szuk(int a, int b, int x, int y, int w)
{
	if (!w)
		return;
	if (!jeszrz[a])
	{
		szuk(a+1, b, x, y, w);
		return;
	}
	if (!jeszrz[b])
	{
		szuk(a, b-1, x, y, w);
		return;
	}
	if (!jeszkol[x])
	{
		szuk(a, b, x+1, y, w);
		return;
	}
	if (!jeszkol[y])
	{
		szuk(a, b, x, y-1, w);
		return;
	}
	if (w==(b-a+1)*(y-x+1))
	{
		for (int i=a; i<=b; i++)
		{
			for (int j=x; j<=y; j++)
			{
				wyn+=pot[i][j];
				jeszrz[i]--;
				jeszkol[j]--;
			}
		}
		return;
	}
	if (x==y || (a!=b && (rand()&1)))
	{
		int s=(a+b)>>1;
		//~ int s=los(a, b-1);
		int p=pyt(a, s, x, y);
		szuk(a, s, x, y, p);
		szuk(s+1, b, x, y, w-p);
	}
	else
	{
		int s=(x+y)>>1;
		//~ int s=los(x, y-1);
		int p=pyt(a, b, x, s);
		szuk(a, b, x, s, p);
		szuk(a, b, s+1, y, w-p);
	}
}

int main()
{
	int szit;
	scanf("%d%d%d%lld", &szit, &szit, &szit, &mod);
	ll trz=1;
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			pot[i][j]=trz;
			trz=(trz*2)%mod;
		}
	}
	for (int i=0; i<n; i++)
	{
		jeszrz[i]=pyt(i, i, 0, n-1);
		jeszkol[i]=pyt(0, n-1, i, i);
	}
	szuk(0, n-1, 0, n-1, 250);
	printf("! %lld\n", wyn%mod);
	ff();
	return 0;
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, ans = 0;
  cin >> n;
  vector<long long> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
  }
  sort(vec.begin(), vec.end());
  for (int i = 0; i < n; i++) {
    int cnt=0;
    while (vec[i] == vec[i+1]) {
      i++;
      cnt++;
    }
    if (cnt%2 == 0) {
      ans++;
    }
  }
  cout << ans << '\n';
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll N;
  std::cin >> N;
  std::cout << (N*(N-1))/2 << '\n';
  return 0;
}


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

int main(void){
  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=1;i<N;i++){
    cin>>A[i];
    A[i]--;
  }
  map<int,int> result;
  for(int i=1;i<N;i++){
    result[A[i]]++;
  }
  for(int i=0;i<N;i++){
    cout<<result[i]<<endl;
  }
  return 0;
}


Measured memory_bytes: 13556
namespace Test
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    public class Test
    {
        public static void Main(string[] args)
        {
            var t = new Test();
            var input = t.ConvertIntList(t.ReadInput());
            var ans = 0;
            var ans2 = 0;

            for (var i = input[0]; i > 0; i--)
            {
                ans += i - 1;
            }

            for (var i = input[1]; i > 0; i--)
            {
                ans2 += i - 1;
            }
            Console.WriteLine(ans + ans2);
        }

        public int Gcd(int a, int b)
        {
            for (var i = b; i > 1; i -= 1)
            {
                if (a % i == 0 && b % i == 0)
                {
                    return i;
                }
            }
            return 1;
        }

        public string[] ReadInput()
        {
            return Console.ReadLine().Split(' ');
        }

        public List<int> ConvertIntList(string[] x)
        {
            var convertedList = new List<int>(x.Length);
            for (var i = 0; i < x.Length; i++)
            {
                convertedList.Add(int.Parse(x[i]));
            }

            return convertedList;
        }

        public List<double> ConvertDoubleList(string[] x)
        {
            var convertedList = new List<double>(x.Length);
            for (var i = 0; i < x.Length; i++)
            {
                convertedList.Add(double.Parse(x[i]));
            }

            return convertedList;
        }

        public List<long> ConvertLongList(string[] x)
        {
            var convertedList = new List<long>(x.Length);
            for (var i = 0; i < x.Length; i++)
            {
                convertedList.Add(long.Parse(x[i]));
            }

            return convertedList;
        }

        public int CountContainWords(string source, string word)
        {
            var count = 0;
            var loopCount = source.Length - (word.Length - 1);
            for (var i = 0; i < loopCount; i++)
            {
                if (source.Substring(i, word.Length) == word)
                {
                    count++;
                }
            }
            return count;
        }
    }
}

Measured memory_bytes: 13140
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;


public class Main {
	static int N;
	static int[] R, W;
	
	// list内の要素を何個か足して、max以下の最大数を返す
	static private int calc(int[] list, int max)
	{
		Arrays.sort(list);
		
		int[][] dp = new int[1001][1001];
		for (int i = 0; i < 1001; i++) {
			for (int j = 0; j < 1001; j++) {
					dp[i][j] = 0;
			}
		}
		dp[0][0] = 1;
		
		for (int i = 0; i < list.length; i++) {
			for (int j = 0; j < 1001; j++) {
				if(dp[i][j] == 0) continue;
				
				dp[i+1][j] = 1;
				if(j + list[i] <= max) dp[i+1][j+list[i]] = 1;
			}
		}
		
		for (int i = max; i >= 0; i--) {
			if(dp[list.length][i] == 1) return i;
		}
		
		return 0;
	}
	
	static private void solve()
	{
		if(N == 1)
		{
			System.out.println(R[0]*2 + W[0]);
			return;
		}
		
		int maxread = 0;
		int maxindex = 0;
		int sumread = 0;
		int sumwrite = 0;
		for (int i = 0; i < N; i++) {
			if(maxread < R[i])
			{
				maxread = R[i];
				maxindex = i;
			}
			sumread += R[i];
			sumwrite += W[i];
		}
		
		if((sumread - maxread) >= maxread)
		{
			System.out.println(sumread + sumwrite);
			return;
		}
		
		int free = maxread - (sumread - maxread);
		
		int[] list = new int[N-1];
		for (int i = 0; i < N; i++) {
			if(i == maxindex) continue;
			
			if(i < maxindex)
				list[i] = W[i];
			else {
				list[i-1] = W[i];
			}
		}
		
		int totalwrite = calc(list, free);
		
		System.out.println(maxread*2+sumwrite-totalwrite);
	}
	
	static public void main(String[] args)
	{
		Scanner sca = new Scanner(System.in);
		
		while(true)
		{
			
			N = sca.nextInt();
			if(N == 0) break;
			
			R = new int[N];
			W = new int[N];
			for (int i = 0; i < N; i++) {
				R[i] = sca.nextInt();
				W[i] = sca.nextInt();
			}
			
			solve();
		}
	}
}

Measured memory_bytes: 88304
#include<cstdio>
int main(){for(int n,a,c,r,t;c=r=scanf("%d",&n),n;printf("%d\n",r))for(char d[]="123456",s[9];n--;r+=*d-48)scanf("%s",s),*s%6-4?a=*s%5+*s%2*2+c&3,t=*d,*d=d[a+=a/2?2-a%2*2:1],d[a]=d[5],d[5]=d[5-a],d[5-a]=t:c+=*s+3;}

Measured memory_bytes: 0
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    while(q--) {
        int k;
        cin >> k;
        vi::iterator itrl, itru;
        tie(itrl, itru) = equal_range(all(a), k);
        cout << itrl-a.begin() << ' ' << itru-a.begin() << '\n';
    }
}


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

/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
*/

using namespace std;

#if DEBUG && !ONLINE_JUDGE
    #include "debug.h"
#else
    #define debug(...)
#endif

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<vector<int> > vvi;
typedef vector<vector<ii> > vvii;

#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define fill(a,x) memset(a,x,sizeof(a))
#define ff first
#define ss second
#define trav(a, x) for(auto& a : x) 
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
const ll INF = 1e18;
const int mod =  1e9 + 7;
const int N = 1e6;
ll gcd(ll a,ll b){if (a==0) return b;return gcd(b%a,a);}
ll lcm(ll a,ll b){return a*(b/gcd(a,b));}
ll Abs(ll a){if(a>0)return a;return -a;}
ll Ceil(ll a,ll b){if(a%b==0)return a/b;else return a/b+1;}
double Abs(double a){if(a>0)return a;return -a;}

//*X.find_by_order(2) element at index=2
//X.order_of_key(1) how many elements strictly less than 1

/*
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
*/

inline int pow_(ll x, ll y,ll p){
  int r = 1; while(y){if(y & 1) r = r * x % p; y >>= 1; x = x * x % p;} return r;
}
inline int inv_(int x){return pow_(x, mod - 2, mod);}
inline int add(int a, int b){a += b; if(a >= mod) a -= mod; return a;}
inline int mul(int a, int b){return a * 1LL * b % mod;}
inline int sub(int a, int b){a -= b; if(a < 0) a += mod; return a;}

ll n,k;

void multiply(ll a[55][55] , ll b[55][55])
{
	ll mul[55][55]; 
    for (int i = 1; i <= n; i++) 
    { 
        for (int j = 1; j <= n; j++) 
        { 
            mul[i][j] = 0; 
            for (int k = 1; k <= n; k++) 
                mul[i][j] = (mul[i][j] + (a[i][k]*b[k][j])%mod)%mod; 
        } 
    } 

  	for (int i=1; i<=n; i++) 
    	for (int j=1; j<=n; j++) 
        	a[i][j] = mul[i][j]; 
}

ll matrix_expo(ll a[55][55],ll k)
{
	ll m[55][55] = {0};

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

	if(k==1)
	{
		ll ans = 0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				ans = (ans + a[i][j])%mod;
			}
		}

		return ans;
	}


	matrix_expo(a,k/2);

	multiply(a,a);

	if(k%2!=0)
		multiply(a,m);

	ll ans = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			ans = (ans + a[i][j])%mod;
		}
	}

	return ans;
}

int main()
{
	#ifdef LOCAL_TEST
    freopen("in.txt","r",stdin);
    //freopen("out.txt", "w", stdout);
    #else
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    #endif
	cin>>n>>k;
	ll a[55][55] = {0};
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}

	cout << matrix_expo(a,k) << "\n";
    return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <utility>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  set<long long int> S;
  multiset<long long int> MS;
  for (int i = 0; i < N; i++) {
    long long int t; cin >> t;
    S.insert(t); MS.insert(t);
  }
  long long int ans = 0;
  for (auto it = S.begin(); it != S.end(); ++it) {
    ans += (MS.count(*it)%2 == 1);
  }
  cout << ans << endl;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FT first
#define SC second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
const int INF = 1e9;
const double EPS = 1e-9;



int main()
{
  string s, t ;
  cin >> s >> t ;
  int count = 0 ;
  REP(i,3){
    if(s.at(i)==t.at(i)){
      count++ ;
    }
  }
  
  cout << count <<endl ;
    

  return 0 ;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;
ll n,k;
vector<ll> vec(100000);

bool jud(ll x){
  ll sum = 1;
  ll t1 = 0;
  rep(i,n){
    t1 += vec[i];
    if(t1 > x){
      sum++;
      t1 = vec[i];
    }
  }
  return sum <= k;
}

int main(){
  cin >> n >> k;
  ll ng = 0;
  rep(i,n){
    cin >> vec[i];
    chmax(ng,vec[i]);
  }
  ng--;
  ll ok = 1e15;
  while(abs(ok - ng) > 1){
    ll mid = (ok + ng) / 2;
    if(jud(mid)){
      ok = mid;
    }else{
      ng = mid;
    }
    //cout << ok << " " << ng << endl;
  }
  cout << ok << endl;
}


Measured memory_bytes: 3460
#include <bits/stdc++.h>
using namespace std;
#define   ll long long int
#define maxn 1000000
vector<ll> dp(maxn,0);
ll mod=998244353;

int main(){

ll n,x,m;
cin>>n>>x>>m;
ll sum=0;
ll last=x;
int tm=0;
int vis[m]={0};
int flag=0;
for(int i=0;i>=0;i++){
        if(vis[last]){
            tm=i;
            break;
        }
    vis[last]=1;
    sum+=last;
    last=last*last;
    last=last%m;
    //cout<<last<<endl;
}

ll tlast=x;
ll fans=0;
///cout<<last<<" "<<tlast<<endl;
for(int i=0;i>=0;i++){
    if(tlast==last || n==0 ){
        break;
    }
    fans+=tlast;
    sum-=tlast;
    tlast=tlast*tlast;
    tlast=tlast%m;
    tm--;
    n--;
}
//cout<<fans<<endl;
fans+= sum*(n/tm);
int lt=n%tm;
for(int i=0;i<lt;i++){
    fans+=last;
    last=(last*last)%m;
}
cout<<fans<<endl;



}


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

typedef long long ll;
constexpr ll MOD = ll(1e9+7);

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

int N, X, Y, Z;
ll dp[41][1<<17];  // dp[i][S] = i番目までみて直前の状態がSであるものでXYZを含まない個数

bool XYZ(int S){
    int sum = 0;
    for(int d=1; S>0 && sum<Z; S>>=1){
        if(S&1){
            sum += d;
            d = 1;
        }else{
            d++;
        }
    }
    if(sum != Z) return false;
    sum = 0;
    for(int d=1; S>0 && sum<Y; S>>=1){
        if(S&1){
            sum += d;
            d = 1;
        }else{
            d++;
        }
    }
    if(sum != Y) return false;
    sum = 0;
    for(int d=1; S>0 && sum<X; S>>=1){
        if(S&1){
            sum += d;
            d = 1;
        }else{
            d++;
        }
    }
    if(sum != X) return false;
    return true;
}

int main(){
    cin >> N >> X >> Y >> Z;
    int mask = (1<<(X+Y+Z))-1;
    dp[0][0] = 1;
    for(int i=0;i<N;i++){
        for(int S=0;S<=mask;S++){
            for(int d=1;d<=10;d++){
                int T = (((S<<1)+1)<<(d-1)) & mask;
                if(XYZ(T)) continue;
                dp[i+1][T] += dp[i][S];
                dp[i+1][T] %= MOD;
            }
        }
    }
    ll ans = 0;
    for(int S=0;S<=mask;S++){
        ans += dp[N][S];
        ans %= MOD;
    }
    ans = (power(10,N) - ans + MOD) % MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 41216
#include <iostream>
#include <ostream>
#include <fstream>
#include <set>
#include <queue>
#include <time.h>
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;
#define It(q) for (auto elem :q)
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define read(vec, n) for(int (i)=0;(i)<(int)(n);++(i)) cin >> vec[i];
#define print(q) for(auto it = (q).begin(); it != (q).end();++(it)) cout << *it << ' '; cout << endl;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
    int n, a, b;
    cin >> n >> a >> b;

    if (abs(a - b) % 2 == 0) {
        cout << "Alice";
    } else {
        cout << "Borys";
    }
    return 0;
}

Measured memory_bytes: 256
//
//AtCoder Beginner Contest 177
//D
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>
#include <bitset>
#include <numeric>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

const double PI = 3.14159265358979323846;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

int main()
{
    int n, m;
    cin >> n >> m;

    UnionFind uf(n);

    REP(i, m){
        int a, b;
        cin >> a >> b;
        a--;b--;
        uf.unite(a, b);
    }

    int ans = 0;
    REP(i,n) ans = max(ans, uf.size(i));
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N,K,sum=0;cin>>N>>K;
  for(int i=0;i<N;i++){int x;cin>>x;
  if(x<(K-x)){sum+=x*2;}else{sum+=(K-x)*2;}
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <cstdio>

int main(){
	int a[3][6];
	int b[3][3];
	
	for(int i=0; i<3; i++){
		scanf("%d %d %d %d %d %d", &a[i][1], &a[i][2], &a[i][3], &a[i][4], &a[i][5], &a[i][6]);
	}
	for(int i=0; i<3; i++){
		if(a[i][6] < a[i][3]){
			a[i][5]--;
			a[i][6] += 60;
			if(a[i][5] < a[i][2]){
				a[i][4]--;
				a[i][5] += 60;
			}
		}		
	}
	for(int i=0; i<3; i++){
		b[i][1] = a[i][4] - a[i][1];
		b[i][2] = a[i][5] - a[i][2];
		b[i][3] = a[i][6] - a[i][3];
		printf("%d %d %d\n", b[i][1], b[i][2], b[i][3]);
	}
	return 0;
}

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

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

    int q;
    cin >> q;

    bool flag = true;
    vector<char> sentou, matubi;
    rep(i, 0, q) {
        int t;
        cin >> t;

        if (t == 1) {
            if (flag) flag = false;
            else flag = true;

        } else {
            int f;
            char c;
            cin >> f >> c;

            if (f == 1) {
                if (flag) sentou.push_back(c);
                else matubi.push_back(c);
            } else {
                if (flag) matubi.push_back(c);
                else sentou.push_back(c);
            }
        }
    }
    
    if (flag) {
        for (int i = sentou.size() - 1; i >= 0; i--) cout << sentou[i];
        cout << s;
        rep(i, 0, matubi.size()) cout << matubi[i];
        cout << endl;
    } else {
        for (int i = matubi.size() - 1; i >= 0; i--) cout << matubi[i];
        for (int i = s.size() - 1; i >= 0; i--) cout << s[i];
        rep(i, 0, sentou.size()) cout << sentou[i];
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
const long long mod = 1e9 + 7;

int main(){
  int n, m;
  cin >> n >> m;
  vector<bool> oks(n + 1, true);
  rep(i,m){
    int a;
    cin >> a;
    oks[a] = false;
  }
  vector<ll> dp(n + 1);
  dp[0] = 1;
  for (int now = 0; now < n; now++){
    for (int next = now + 1; next <= min(n, now + 2); next++){
      if(oks[next]){
        dp[next] += dp[now];
        dp[next] %= mod;
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	// ?????????????????°???????????????????????°?????£?¨???????
	// ????????\????????????????????????????????????????????????????????¨
	void doIt( ) {
		Scanner sc = new Scanner(System.in);
		int race = 3,ninzu = 8;
		Person[][] playersArray =  new Person [race][ninzu];
		//??????????????\???
		for(int i = 0;i < race;i++){
			for(int k = 0;k < ninzu;k++){
				playersArray[i][k] = new Person(sc.nextInt(),sc.next());
			}
		}
		//System.out.println(Arrays.toString(playersArray[0]));
		//?????????????????????
		for(int i = 0;i < 3;i++)Arrays.sort(playersArray[i]);
		//System.out.println(Arrays.toString(playersArray[0]));

		//?????¬??????1???2????????????
		for(int i = 0;i < race;i++){
			for(int k = 0;k < 2;k++){
				System.out.println(playersArray[i][k]);
			}
		}
		//3?????\????????????
		Person[] ThreeArray =  new Person [3*2];
		for(int i = 0;i < race;i++){
			for(int k = 2;k < 4;k++){
				ThreeArray[i*2+k-2] = playersArray[i][k];
			}
		}
		//System.out.println(Arrays.toString(ThreeArray));
		Arrays.sort(ThreeArray);
		//3?????\????????????
		for(int i = 0;i < 2;i++)System.out.println(ThreeArray[i]);

	}
	public static void main(String [ ] args) {
		new Main( ) . doIt( );
	}
	class Person implements Comparable<Person>{
		int num;
		String time;
		Person(int num, String time) {
			this.num = num;
			this.time = time;
		}
		@Override
		public String toString() {
			return num + " " + time;
		}
		@Override
		public int compareTo(Person p) {
			return time.compareTo(p.time);
		}
	}
}

Measured memory_bytes: 26180