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

int main() {

  int N; 
  cin >> N;
  
  // 配列
  vector<int> A(N); // int型の配列変数vecを宣言
  
  for (int i = 0; i < N; i++) {
    	cin >> A.at(i) ;
  	}
  vector<int> B(N);
  int ians = 1;
  string ans = "DENIED";
  for (int j = 0; j < N; j++) {
    if (A.at(j) % 2 == 1){
        B.at(j) = 1;
    }
    if (A.at(j) % 2 == 0 && A.at(j) % 3 == 0){
       B.at(j) = 1;
    }
    if (A.at(j) % 2 == 0 && A.at(j) % 5 == 0){
        B.at(j) = 1;
    }
  	ians = ians * B.at(j);
  }
	if (ians == 1){
      ans = "APPROVED";
    }
  cout << ans << endl;

}

Measured memory_bytes: 256
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    ss = [''.join(sorted(stdin.readline().rstrip())) for _ in range(N)]
    spam = {}
    ans = 0
    for s in ss:
        if s in spam:
            ans += spam[s]
            spam[s] += 1
        else:
            spam[s] = 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 19400
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <algorithm> 
using namespace std;

int gcd(int a,int b) {
    return b>0 ? gcd(b,a%b):a;
}
int main()
{   
    int n;
    cin >> n;
    long long  num = 0;
    for(int i = 1; i <=n; i++){
        for(int j = 1; j<=n; j++){
            for(int k = 1; k <= n ; k++ ){
                    int tmp = gcd(k,i);
                    num += gcd(tmp,j);
            }
        }
    }
    cout << num <<endl;
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i];

  vector<Int> dp(n+1,-n-n);
  dp[0]=0;
  for(Int a:as) dp[a]=dp[a-1]+1;

  Int ans=n-*max_element(dp.begin(),dp.end());
  if(ans==n) ans=-1;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3328
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
typedef long long ll;
class Solver{
public:
    int ans[110][110];
    int H,W,N;
    void solve(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>H>>W>>N;
        vector<pair<int,int>>a;
        for(int u=1;u<=N;u++){
            int v;
            cin>>v;
            a.push_back({v,u});
        }
        sort(a.begin(),a.end());
        reverse(a.begin(),a.end());
        int r=1,c=1,d=1;
        for(auto p:a){
            int t=p.first,i=p.second;
            while(r<=H&&t>0){
                if(d==1){
                    while(c<=W&&t>0){
                        ans[r][c]=i;
                        t--;
                        c++;
                    }
                    if(c>W){
                        d=0;
                        r++;
                        c=W;
                    }
                }
                if(d==0){
                    while(c>0&&t>0){
                        ans[r][c]=i;
                        t--;
                        c--;
                    }
                    if(c==0){
                        d=1;
                        r++;
                        c=1;
                    }
                }
            }
        }
        for(int r=1;r<=H;r++){
            for(int c=1;c<=W;c++){
                cout<<ans[r][c]<<" ";
            }
            cout<<"\n";
        }
    }
};
int main()
{
    // freopen("in.txt","r",stdin);
    (new Solver())->solve();
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
    A[i]--;
  }
  vector<int> B(N);
  for (int i = 0; i < N; i++){
    cin >> B[i];
    B[i]--;
  }
  vector<int> cntA(N, 0);
  for (int i = 0; i < N; i++){
    cntA[A[i]]++;
  }
  vector<int> cntB(N, 0);
  for (int i = 0; i < N; i++){
    cntB[B[i]]++;
  }
  bool ok = true;
  for (int i = 0; i < N; i++){
    if (cntA[i] + cntB[i] > N){
      ok = false;
    }
  }
  if (!ok){
    cout << "No" << endl;
  } else {
    vector<int> C;
    for (int i = 0; i < N; i++){
      for (int j = 0; j < max(cntA[i], cntB[i]); j++){
        C.push_back(i);
      }
    }
    int M = C.size();
    vector<int> D;
    for (int i = M / 2; i < M; i++){
      D.push_back(C[i]);
    }
    for (int i = 0; i < M / 2; i++){
      D.push_back(C[i]);
    }
    vector<int> ans;
    for (int x : D){
      if (cntB[x] > 0){
        ans.push_back(x);
        cntB[x]--;
      }
    }
    cout << "Yes" << endl;
    for (int i = 0; i < N; i++){
      cout << ans[i] + 1;
      if (i < N - 1){
        cout << ' ';
      }
    }
    cout << endl;
  }
}

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

using namespace std;

int n, a, b;
vector<long long> v;

long long dp[51][51];

void hawawa()
{
	cin >> n >> a >> b;
	v.resize(n);
	for (auto&& i : v) {
		cin >> i;
	}
	sort(rbegin(v), rend(v));
	double d = 0;
	for (int i = 0; i < a; i++) {
		d += v[i];
	}
	for (int i = 0; i <= 50; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) dp[i][j] = 1LL;
			else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
		}
	}
	cout << fixed << d / a << "\n";
	long long ans = 0;
	int cnt = count(begin(v), end(v), v[a - 1]);
	int p = n - (upper_bound(rbegin(v), rend(v), v[a - 1]) - rbegin(v));

	for (int i = a - p; i <= b - p; i++) {
		ans += dp[cnt][i];
		if (v[0] != v[a - 1]) break;
	}
	cout << ans << "\n";
}

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


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Security.Cryptography;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var A = new int[3][];
        A[0] = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        A[1] = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        A[2] = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var N = int.Parse(ReadLine());

        for (int i = 0; i < N; i++)
        {
            var b = int.Parse(ReadLine());

            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 3; k++)
                {
                    if (A[j][k] == b)
                        A[j][k] = 0;
                }
            }
        }

        var ok = false;
        var drOk = true;
        var dlOk = true;
        for (int i = 0; i < 3; i++)
        {
            var hOk = true;
            var vOk = true;

            for (int j = 0; j < 3; j++)
            {
                if (A[i][j] != 0)
                    hOk = false;

                if (A[j][i] != 0)
                    vOk = false;
            }

            if (hOk || vOk)
                ok = true;

            if (A[i][i] != 0)
                drOk = false;

            if (A[i][2 - i] != 0)
                dlOk = false;
        }

        if (drOk || dlOk)
            ok = true;

        if (ok)
            WriteLine("Yes");
        else
            WriteLine("No");
    }
}


Measured memory_bytes: 28180
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define INF 1 << 30

using namespace std;
typedef long long ll;
typedef pair<int, int> pp;

int main(void) {
	int num, i, x, l, ans = 1;
	cin >> num;
	vector<pp> d(num);
	rep(i, num) {
		cin >> x >> l;
		d[i] = make_pair(x + l, x - l);
	}
	sort(d.begin(), d.end());
	for (x = 0, i = 1; i < num; i++) {
		if (d[i].second >= d[x].first) {
			ans++;
			x = i;
		}
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 1024
X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif D<X and K*D<X:
    ans=X-K*D
else:
    ans=X%D
    if (X-ans)%2!=K%2:
        ans=D-ans
print(ans)

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define fo(i,n) for(ll i=0;i<n;i++)
#define fok(i,k,n) for(ll i=k;i<n;i++)
#define ci(x) cin>>x
#define ci2(x,y) cin>>x>>y
#define co(x) cout<<x<<"\n"
#define co2(x,y) cout<<x<<" "<<y<<"\n"
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
const int mod = 1000000007;
const int INF =1e9;


int main(){
	int a,b;
	ci2(a,b);
	for(int i=b-a+1;i>=(-1000000) && i<=b;i++){
		cout<<i<<" ";
	}
	for(int i=b+1;i<b+a && i<=(1000000);i++){
		cout<<i<<" ";
	}
}


Measured memory_bytes: 256
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	A, B = getlist()
	print(A * B)

if __name__ == '__main__':
	main()

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

int main(){
	int N;
	cin >> N;
	double p[N+1];
	for (int i=1; i<=N; i++) {
		cin >> p[i];
	}

	double dp[N+1][N+1];
	for (int i=0; i<=N; i++) {
		for (int j=0; j<=N; j++) {
			if (i == 0 && j == 0) {
				dp[i][j] = 1.0;
			} else if (i == 0) {
				dp[i][j] = 0.0;
			} else if (j == 0) {
				dp[i][j] = dp[i-1][j]*(1-p[i]);
			} else {
				dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
			}
		}
	}
	double res = 0.0;
	for (int i=N/2+1; i<=N; i++) {
		res += dp[N][i];
	}
	cout  << setprecision (15) << res << "\n";
}


Measured memory_bytes: 70528
import javax.management.MBeanRegistration;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.sql.SQLSyntaxErrorException;
import java.util.StringTokenizer;
import java.util.Scanner;
import java.lang.*;
import java.io.*;
import java.util.*;
import java.lang.Integer;
import java.util.HashMap;

public class Main {
    // driver function to test the above functions
    public static void main(String args[]) throws IOException {

        Reader.init(System.in);

        int a = Reader.nextInt();
        int b = Reader.nextInt();

        System.out.println(a*b);





    }

}

class Node_compare implements Comparator<Node>
{
    // Used for sorting in ascending order of
    // roll number
    public int compare(Node n1, Node n2)
    {
        if (n1.a.length()>n2.a.length()){
            return 1;
        }
        else if (n1.a.length()==n2.a.length()) {
            return n2.ind-n1.ind;
        }
        else {
            return -1;
        }

    }
}

class Node{
    String a;
    int ind;


}



class solu{

    int bin (int[][] arr, int l, int r, int val){
        while(r-l>1){
            int m = l+((r-l)/2);
            if (arr[m][0]>=val){
                r=m;
            }
            else {
                l=m;
            }
        }
        return r;
    }

}

/** Class for buffered reading int and double values */
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

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

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

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }

    static String line() throws IOException {
        return reader.readLine();
    }
}

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

int n;

bool binary_search(vector<int> &a ,int k){
    int x , y , z;
    x = 0;
    z = n - 1;
    while( x <= z ){
        y = (x + z) / 2;
        if(k == a[y]) return true;
        else if(k < a[y]) z = y - 1;
        else x = y + 1;
    }
    return false;
}

int main(){
    bool ans = true;
    cin >> n;
    vector<int> a(n);
    rep(i ,n) cin >> a[i];
    int m; cin >> m;
    vector<int> b(m);
    rep(i ,m) cin >> b[i];
    rep(i , m){
        if(!binary_search(a,b[i])) {
            ans = false; break;
        } 
    }
    cout << ( ans ? 1 : 0) << endl;
}



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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int ans = 700;
  for(int i = 0; i < 3; i++) {
    if(S[i] == 'o') ans += 100;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
# t=int(input())
# for _ in range(t):
#     n,m=map(int,stdin.readline().split())
k=int(stdin.readline())
s=input()
if(len(s)<=k):
    print(s)
else:
    print(s[:k]+'...')

Measured memory_bytes: 9484
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
	string x,y;
	cin >> x >> y;
	if(x == y) cout << "=" <<endl;
	else cout << ((x < y) ? "<" : ">") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;
#define _GLIBCXX_DEBUG

 // 深さ優先探索
vector<bool> seen;
int dfs(const Graph &G, ll v) {
    seen[v] = true; // v を訪問済にする
    int score = 0; 

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー

        // 負荷さ優先探索中の処理



        dfs(G, next_v); // 再帰的に探索, 毎回mat渡してええの？
    }
    return score;
} 

/*
//桁数の計算
ll keta(ll num){
  ll ans= 0 ;
  ll rem;

  for (ll i = 4; i >= 0 ; i--){
    rem = pow(10,i);
    ans += (num / rem); 
    num = num % rem;
  }
  return ans;
}
*/


int main() {
  ll A, B, C;
  cin >> A >> B >> C;
  bool flag = false;

  for (ll i = 1; i <= A; i++){
    if((i * B + C) % A == 0){
      flag = true;
      break;
    }    
  }

  if(flag) cout << "YES" << endl;
  else cout << "NO" << endl; 

  return 0;
}

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

int main(){
	int h,w;
  	cin >> h >>w;
  	vector<string> vec(h);
  	for (int i=0;i<h;i++){
    	cin >>vec[i];
      	cout << vec[i] << endl << vec[i]<< endl;
    }
}

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

int main()
{
    rep(i,5) {
        int a;
        cin >> a;
        if (a == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}


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

using namespace std;

#define inf 1<<30
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> P;


int main(){
	llong N;
	cin >> N;
	llong A, B;
	for(llong i = 1; i*i <= N; i++){
		if(N%i == 0)
			A = i, B = N/i;
	}

	int cnt = -1;
	while(cnt++, B)
		B /= 10;

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int n, i, k;

	scanf("%d", &n);
	k = 0;
	for (i = 0; i < n; i++) {
		int a;

		scanf("%d", &a);
		if (a == k + 1)
			k++;
	}
	printf("%d\n", k > 0 ? n - k : -1);
	return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
 
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
 
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
 
#define int         long long
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define mp          make_pair
#define all(a)      (a).begin(),(a).end()
#define FF           first
#define SS           second
#define sz(x)       (int)x.size()
#define endl        '\n'
//#define hell          1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
// mp::cpp_int
 
const int hell=1000000007;
 
 
int pw(int a,int b)
{
  int x=a;
  rep(i,1,b){a=a*x;
    a%=10000000000LL;}
  return a;
}
 
 ll power(ll a,ll b)
{
  if(b==0)return 1;
  if(b==1)return a%hell;
  ll t=power(a,b/2);
  t*=t;
  t%=hell;
   if(b&1)
   {
       t*=a;
       t%=hell;
   }
   return t;
 
}

int inverse(int a)
{
  return power(a,hell-2);
}
 
int gcd(int a,int b)
{   
  
  if(b==0)return a;
  return gcd(b-a%b,a%b);
}
 
bool cmp(pii a,pii b)
{
  return a.SS<b.SS;
}
 
 
int sum(int a,int b )
{
   int ans=a-a/b; 
   return ans;
}


 
int solve()
{  
 
  int n,a,b;
  cin>>n>>a>>b;
  cout<<min(n*a,b);


 return 0;
}
 
 
signed main()
{  int t=1;
//pri();
 ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
  
   cin.exceptions(cin.failbit);                                                                    
 
 
  

  clock_t time_req;
 
    // Without ung pow function
                                                                                                                   
 //cin>>t;
 
    int k=1;
     
   while(t--)
     {
      //cout<<"Case #"<<k<<":"<<" ";k++;
      solve();
     }
        exit(0);
 
         time_req = clock() - time_req;
    cout <<endl<< "Processor time taken is "
      << (double)time_req/CLOCKS_PER_SEC << " seconds" << endl;
 
 
    return 0;
}

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

int main() {
    int N, A, B, C; cin >> N >> A >> B >> C;
    vector<int> take(N); for (int i = 0; i < N; i++) cin >> take[i];
    vector<int> powl(N+1); powl[0] = 1;
    int ans = 1e9;
    for (int i = 1; i <= N; i++) powl[i] = powl[i-1] * 4;
    for (int i = 0; i < powl[N]; i++) {
        vector<vector<int>> res(4);
        for (int j = 0; j < N; j++) {
            int k = (i / powl[j]) % 4;
            res[k].push_back(take[j]);
        }
        int t = 0;
        if (res[1].size() != 0 && res[2].size() != 0 && res[3].size() != 0) {
            t += abs(A - accumulate(res[1].begin(), res[1].end(), 0)) + 10 * (res[1].size() - 1);
            t += abs(B - accumulate(res[2].begin(), res[2].end(), 0)) + 10 * (res[2].size() - 1);
            t += abs(C - accumulate(res[3].begin(), res[3].end(), 0)) + 10 * (res[3].size() - 1);
            ans = min(ans, t);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}

var mod int

func main() {
	mod = 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := intScanner()
	a := intSliceScanner(n)
	ans := 1
	list := []int{0, 0, 0}
	for _, v := range a {
		idxs := search(v, list)
		ans *= len(idxs)
		ans %= mod
		if idxs[0] == -1 {
			ans = 0
			break
		}
		list[idxs[0]]++
	}
	fmt.Println(ans)
}
func search(n int, a []int) []int {
	ret := make([]int, 0, 3)
	for i, v := range a {
		if v == n {
			ret = append(ret, i)
		}
	}
	if len(ret) == 0 {
		ret = append(ret, -1)
	}
	return ret
}


Measured memory_bytes: 5120
import sys
input = sys.stdin.readline
import itertools
def print_ans(N, ar):
    """Test Case
    >>> print_ans(5, [1, 1, 2, 2])
    2
    2
    0
    0
    0
    >>> print_ans(10, [1,1,1,1,1,1,1,1,1])
    9
    0
    0
    0
    0
    0
    0
    0
    0
    0
    >>> print_ans(7, [1,2,3,4,5,6])
    1
    1
    1
    1
    1
    1
    0
    """
    ans_list = [0] * N
    gr = itertools.groupby(sorted(ar))
    for key, group in gr:
        ans_list[key-1] = (len(list(group)))
    for ans in ans_list:
        print(ans)
    
    



    
    

if __name__ == '__main__':
    N = int(input().rstrip())
    ar = list(map(int, input().rstrip().split()))
    print_ans(N, ar)




Measured memory_bytes: 32340
//a.c
#include <stdio.h>
#include <string.h>
int main(){
    char s[50] = {0};
    scanf("%s",s);
    int n = strlen(s);
    int i;
    for(i=0;i<n-8;i++){
        printf("%c",s[i]);
    }
    printf("\n");
    return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    int Q;
    cin >> Q;
    vector<int> M(Q);
    for (int i = 0; i < Q; ++i) cin >> M[i];
    vector<bool> res(Q, false);
    for (int bit = 0; bit < (1<<N); ++bit) {
        int sum = 0;
        for (int j = 0; j < N; ++j) if (bit & (1<<j)) sum += A[j];
        for (int j = 0; j < Q; ++j) if (M[j] == sum) res[j] = true;
    }
    for (auto&& r : res) if (r) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}


Measured memory_bytes: 3080
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
#define free  freopen ("input.txt", "r", stdin);freopen ("output.txt", "w", stdout);
#define Fast  ios::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second

bool vowel(char che)
{
    if (che == 'A' || che == 'E' || che == 'I' || che == 'O' || che == 'U' || che == 'Y')
        return true;
    else
        return false;
}

const int N = 2e7+5;
const int mod = 1e9+7;
int a[N], b[N], c, d, dp, dis = 0;
pair <int, int> p[N];
char o;
bool mark[N], h;
//string s, s1;
//stack <int> st;
//set <ll> st1, st2;
//deque <int> dq;
vector <int> vt[N];
//int a1[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

void dfs(ll v)
{
    dis++;
    mark[v] = true;
    for (int i = 0; i < vt[v].size(); i++){
        if (!mark[vt[v][i]]){
            dfs(vt[v][i]);
        }
    }
}
int main()
{
    Fast
    ll t, n, m, k = 0, f = 0, sum = 0, ans = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> p[i].F >> p[i].S;
        if (p[i].F > p[i].S)
            swap(p[i].F, p[i].S);
    }
    sort (p, p+m);
    for (int i = 1; i <= m; i++){
        if (p[i].F != p[i-1].F || p[i].S != p[i-1].S){
            vt[p[i-1].F].pb(p[i-1].S);
            vt[p[i-1].S].pb(p[i-1].F);
        }
    }
    int mx = 0;
    for (int i = 1; i <= n; i++){
        if (!mark[i]){
            dis = 0;
            dfs(i);
        }
        mx = max(mx, dis);
    }
    cout << mx;
}


Measured memory_bytes: 486612
import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int a = sc.nextInt();
		if( x >= a ) {
			System.out.println("10");
		}else {
			System.out.println("0");
		}
	}
}

Measured memory_bytes: 21844
from math import gcd


class SegmentTree:
    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)

    def __getitem__(self, key):
        return self._data[self._offset + key]

    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result


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

st = SegmentTree(N, gcd, 0)
st.build(A)

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, st.query(0, N - 1))
print(result)


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

#define lint long long

const lint INF = 1E9;
// #define P pair<lint, int>

signed main() {
    int sx, sy, tx,ty;

    cin >> sx >> sy >> tx >> ty;

    int X = tx - sx;
    int Y = ty - sy;
    for(int i = 0; i < X; ++i){
        cout << 'R';
    }
    for(int i = 0; i < Y; ++i){
        cout << 'U';
    }

    for(int i = 0; i < X; ++i){
        cout << 'L';
    }
    for(int i = 0; i < Y; ++i){
        cout << 'D';
    }
    cout << 'D';

    for(int i = 0; i < X + 1; ++i){
        cout << 'R';
    }
    for(int i = 0; i < Y + 1; ++i){
        cout << 'U';
    }
    cout << "LU";

    for(int i = 0; i < X + 1; ++i){
        cout << 'L';
    }
    for(int i = 0; i < Y + 1; ++i){
        cout << 'D';
    }
    cout << 'R' << endl;

}


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

int PP(int a, int b) {
	int res = 1;
	for(int i = 1; i <= b; i++) {
		res *= a;
	}
	return res;
}

int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, sum = 0, len = 0; cin >> n; 
	string ans;
	int p = 1;
	for(int i = 1; true; i++) {
		p *= 26;
		if(sum + p >= n) {
			n -= sum;
			len = i;
			break;
		}
		sum += p;
	}

	for(int i = 1; i <= len; i++) {
		for(char ch = 'a'; ch <= 'z'; ++ch) {
			if(PP(26, len - i) >= n) {
				ans.push_back(ch);
				break;
			}
			n -= PP(26, len - i);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3612
<>;
/ /,++$_[$t=($t+$`)%86400],$t=($t+$')%86400for<>;
$%=$i+=$_ for@_[0..10800];
$i+=$_[$_%86400]-$_[($_-10801)%86400],$%+=$-=$i-$%for 10801..86399+10800;
print$%,$/


Measured memory_bytes: 17792
N,M,K = list(map(int,input().split()))

mod = 10**9 + 7

A = ((N**2)*(N-1))//2 - (N*(2*N-1)*(N-1))//6
A = A*(M**2)
A %= mod
B = 1
for i in range(1,K-1):
    B *= N*M-1-i
    B %= mod
    B *= pow(i,mod-2,mod)
    B %= mod
ans1 = A*B

N,M = M,N
A = ((N**2)*(N-1))//2 - (N*(2*N-1)*(N-1))//6
A = A*(M**2)
A %= mod
B = 1
for i in range(1,K-1):
    B *= N*M-1-i
    B %= mod
    B *= pow(i,mod-2,mod)
    B %= mod
ans2 = A*B

print((ans1+ans2)%mod)

Measured memory_bytes: 39152
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t a, b, c;
  cin >> a >> b >> c;
  if(4*a*b < (c-b-a)*(c-b-a) && c-b-a >= 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <cstdlib>
#define PI acos(-1.0)
#define ll long long int
#define db double
#define ull unsigned long long int
#define Fill(x,y) memset(x,y,sizeof(x))
#define bug printf("!!!!!!\n");
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sz(a) (int)(a).size()
using namespace std;
const db eps = 1e-6;
const int inf = 0x3f3f3f3f; //用这个可以直接mem
const ll INF = 1e18;
const int mod = 1e9+7;
const int maxn = 1e5+5;
const int maxm = 1e6+5;
int cas=1;
int cnt, head[maxn];
struct node
{
    int to, next, w;
    bool operator < (const node& a) const {
        return w > a.w;
    }
} e[maxm];

void add(int u, int v,int w) {
    e[cnt] = (node){v,head[u],w};
    head[u] = cnt++;
}

void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}

bool vis[maxn];
int dis[maxn];
int dij(int st,int ed)
{
    priority_queue<node> q;
    Fill(dis,inf); Fill(vis,0);
    dis[st] = 0;
    q.push((node){st, 0, 0});
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if(vis[u.to]) continue;
        vis[u.to] = 1;  //在堆优化的dij中vis标记的应该是起点而不是
        //经过的点,逻辑思路清晰点.

        for (int i = head[u.to]; ~i; i = e[i].next) {
            node k = e[i];
            if (dis[k.to] > dis[u.to] + k.w) {
                dis[k.to] = dis[u.to] + k.w;
                q.push((node){k.to, 0, dis[k.to]});
            }
        }
    }
    return dis[ed];
}
void solve()
{
    int k ; scanf("%d", &k);
    init();
    for (int i = 0 ; i <= k-1 ; i ++) {
        for (int j = 0 ; j <= 9 ; j ++) {
            add(i, (i*10+j)%k, j);
//            cout << i << ' ' << (i*10+j)%k << ' ' << j << endl;
        }
    }
    int ans = inf;
    for (int i = 1 ; i <= 9 ; i ++) {
        ans = min(ans, dij(i, 0) + i);
//        cout << dij(i, 0) << endl;
    }
    printf("%d\n", ans);
}
int main()
{
    //  freopen("in.txt","r",stdin);
    //  freopen("out.txt","w",stdout);
    int t = 1 ;
    //scanf("%d",&t);
    while(t--){
       // printf("Case %d: ", cas++);
        solve();
        //printf("\n");
    }
}









Measured memory_bytes: 18672
#include<bits/stdc++.h>
using namespace std;
int main(){
 int n;
 cin>>n;
 vector<string> s(n);
 for(int i=0; i<n; ++i){
   cin>>s.at(i);
 }
 int AC=0,WA=0,TLE=0,RE=0;
 for(int i=0; i<n; ++i){
   if(s.at(i)=="AC") AC++;
   if(s.at(i)=="WA") WA++;
   if(s.at(i)=="TLE") TLE++;
   if(s.at(i)=="RE") RE++;
 }
  cout<<"AC x "<<AC<<endl;
  cout<<"WA x "<<WA<<endl;
  cout<<"TLE x "<<TLE<<endl;
  cout<<"RE x "<<RE<<endl;

}


Measured memory_bytes: 6424
#include<cstdio>

const int MAX_N = 256;
int N,M;
int a[MAX_N - 1];

int c=0;
int ans=0;
int main(){
	scanf("%d %d",&N,&M);
	for(int i = 0;i < M;i++){
		scanf("%d",&a[i]);
	}
	
	c = N - M;
	
	ans = c -1;
	
	printf("%d\n",ans);
	
	return 0;
}

Measured memory_bytes: 2740
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long result = 0;
        int[] d = new int[N];
        for(int i = 0; i < N; i++){
            d[i] = sc.nextInt();
        }
        for(int i = 0; i < N; i++){
            for(int j = i + 1; j < N; j++){
                result += d[i] * d[j];
            }
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 24148
#include<iostream>
using namespace std;
typedef long long Int;

Int INF = (1LL<<31)-1;

Int seg[1 << 20];


void set_value(Int pos, Int val){
    pos += 1 << 19;
    seg[pos] = val;
    while((pos /= 2) > 0){
        seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
    }
}

Int get_min(int ql, int qr, int sl = 0, int sr = 1<<19, int pos = 1){
    //ちっとも被っていない
    if(qr <= sl || sr <= ql)return INF;
    //完全に包まれる
    if(ql <= sl && sr <= qr)return seg[pos];
    Int sm = (sl + sr) / 2;
    Int lmin = get_min(ql, qr, sl, sm, pos * 2);
    Int rmin = get_min(ql, qr, sm, sr, pos * 2 + 1);
    return min(lmin, rmin);
}

int main(){
    Int n, q, com, x, y;
    cin >> n >> q;
    for(int i = 0;i < n;i++){
        set_value(i, INF);
    }
    for(int i = 0;i < q;i++){
        cin >> com >> x >> y;
        if(com == 0){
            set_value(x, y);
        }
        else{
            cout << get_min(x, y+1) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4680
using System;

namespace ABC123
{
    class Program
    {
        static int Main(string[] args)
        {
            Program.ProblemB();
            return 0;
        }

        static void ProblemB()
        {
            int[] input = new int[5];
            string a = Console.ReadLine();
            string b = Console.ReadLine();
            string c = Console.ReadLine();
            string d = Console.ReadLine();
            string e = Console.ReadLine();
            input[0] = int.Parse(a);
            input[1] = int.Parse(b);
            input[2] = int.Parse(c);
            input[3] = int.Parse(d);
            input[4] = int.Parse(e);

            int[] mod = new int[5];

            for(int i=0;i<5; i++)
            {
                mod[i] = input[i] % 10;
                if(mod[i] == 0)
                {
                    mod[i] = 10;
                }
            }
            int min = 10;
            int index = 0;

            for(int i=0; i < 5; i++)
            {
                if(min > mod[i])
                {
                    min = mod[i];
                    index = i;
                }
            }

            int ans = 0;

            for(int i=0; i < 5; i++)
            {
                if (i == index)
                {
                    ans += input[i];
                }
                else
                {
                    if(mod[i] == 10)
                    {
                        ans += input[i];
                    }
                    else
                    {
                        ans += ((input[i] + 10) / 10) * 10;
                    }
                    
                }
            }

            Console.WriteLine(ans);
        }
    }
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n, m;
  cin >> n >> m;
  int a[31] = {};

  rep(i, 0, n) {
    int k;
    cin >> k;
    rep(j, 0, k) {
      int s;
      cin >> s;
      a[s]++;
    }
  }
  int sum = 0;
  rep(i, 0, m + 1) {
    if(a[i] == n) sum++;
  }

  cout << sum << endl;
}


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

#define rep(i, n) for(int i = 0; i < n; i ++)
#define ITER(c) __typeof((c).begin())
#define each(c, it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define ALL(c) c.begin(), c.end()
#define mp make_pair
#define pb push_back
#define MEMSET(v, h) memset((v), h, sizeof(v))
 
using namespace std; 

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

const int INF = 1 << 24;
const int N = 10;

int main(void){
    for(;;){
        vi l(N), v(2);
        double dis = 0; char c;
        rep(i, N){ if(i) cin >> c; if(!(cin >> l[i])) return 0; dis += l[i]; }
        rep(i, 2) cin >> c >> v[i];

        dis = v[0] * dis / (v[0] + v[1]);

        int res = 0; double cur = 0;
        rep(i, N){
            cur += l[i];
            if(dis <= cur){ res = i + 1; break; }
        }
        cout << res << endl;
    }
 
    return 0;
}

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

typedef long long ll;
#define rep(i,n) for( ll (i)=0; (i)<(n); ++(i) )
#define rpi(i,n) for( int (i)=0; (i)<(n); ++(i) )
#define rpv(d) for(auto& v:d)
#if __cplusplus < 201703L
  std::ostream& co_(){ return std::cout << std::endl; }
  std::istream& cn_(){ return std::cin; }
  template<class Head, class... Args>
  std::ostream& co_( Head&& head, Args&&... args ){ std::cout << head; return co_(std::forward<Args>(args)...); }
  template<class Head, class... Args>
  std::istream& cn_( Head&& head, Args&&... args ){ std::cin >> head; return cn_(std::forward<Args>(args)...); }
#else
  template<class... Args>
  std::ostream& co_( Args... args ){ return std::cout << ... << args << std::endl; }
  template<class... Args>
  std::istream& cn_( Args... args ){ return std::cin >> ... >> args; }
#endif
#define co(...) co_(__VA_ARGS__);
#define cn(...) cn_(__VA_ARGS__);
#define all(x) (x).begin(), (x).end()
#define rgt(x,i) (x).begin(), (x).begin()+(i)

int main(){
  int n;cn(n)
  vector<int> x(n);
  rpv(x){cn(v)}
  ll ans = 10000000;
  for( int i=1; i<=100; ++i ){
    ll t = 0;
    rep(j,n){
      t += (x[j]-i)*(x[j]-i);
    }
    ans = min(ans,t);
  }
  co(ans)
}

Measured memory_bytes: 256
n,m=map(int,input().split())
dp=[0]*(1+n)
dp[1]=1
b=[1]*(1+n)
for i in range(m):
    x,y=map(int,input().split())
    dp[y]=max(dp[x],dp[y])
    b[y]+=1
    b[x]-=1
    if b[x]==0:
        dp[x]=0
print(sum(dp))


Measured memory_bytes: 51416
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()


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

int main() {
  vector<int> A(9);
  vector<bool>a(9,false);
  for(int i=0;i<9;i++)
    cin>>A.at(i);
  int N;
  cin>>N;
  vector<int>b(N);
  for(int i=0;i<N;i++)
    cin>>b.at(i);
  for(int i=0;i<9;i++){
    for(int j=0;j<N;j++){
      if(A.at(i)==b.at(j)){
        a.at(i)=true;
        break;
      }
    }
  }
  if(a.at(0)&&a.at(1)&&a.at(2))
    cout<<"Yes"<<endl;
  else if(a.at(3)&&a.at(4)&&a.at(5))
    cout<<"Yes"<<endl;
  else if(a.at(6)&&a.at(7)&&a.at(8))
    cout<<"Yes"<<endl;
  else if(a.at(0)&&a.at(3)&&a.at(6))
    cout<<"Yes"<<endl;
  else if(a.at(1)&&a.at(4)&&a.at(7))
    cout<<"Yes"<<endl;
  else if(a.at(2)&&a.at(5)&&a.at(8))
    cout<<"Yes"<<endl;
  else if(a.at(0)&&a.at(4)&&a.at(8))
    cout<<"Yes"<<endl;
  else if(a.at(2)&&a.at(4)&&a.at(6))
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
a,b,c = map(int,input().split())#標準入力を行う
if (a == 5 or a== 7):
    if(b == 5 or b == 7):
        if(c == 5 or c == 7):
            if(a + b + c == 17):
                print("YES")
            else:
                print("NO")
        else:
            print("NO")
    else:
        print("NO")
else:
    print("NO")


Measured memory_bytes: 9036
#include <bits/stdc++.h>
#include <string.h>
#include <numeric>

using namespace std;

///////////////////////////////////////////
//const long long int INF = 1000000000000000000LL;
const long long int INF = 1000000;
using ll = long long int;
using vi = vector<int>;
using Vi = vector<long long int>;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
auto min(auto x,auto y){if(x>y){return y;}else{return x;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return 1; } return 0; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return 1; } return 0; }
template<class T>T sqar(T x){ return x*x; }
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(    v[0])>()) //降順でVをソート
///////////////////////////////////////////
ll ta=50000000000;
string s;
ll k;

int main(){
    cin>>s>>k;
    ll tak=10;
    char ans='1';
    rep(i,k){
        if(s[i]!='1'){
            ans=s[i];
            break;
        }else{
            tak*=10;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define  ll long long
#define MOD 1000000007
 
 
ll modpow(ll a,ll n)
{
	ll res = 1;
	while (n > 0)
	{
		if (n % 2 > 0)
			res = res * a % MOD;
		a = a * a % MOD;
		n /= 2;
	}
	return res;
}
 
#if 0
ll rui( ll a,ll b){
  if(a==1)return 1;
  else {ll c=1;
   for(;b!=0;b--){
     c=c*a%MOD;
   };     
   return c%MOD; 
  };
};  
#endif
int main(){
  ll n,k,d, ans=0;
  scanf("%lld %lld",&n,&k);
  ll  w[k+1];
  for(int a=k;a!=0;a--){
    d=k/a;
    //printf("%lld\n",d);
    w[a]=modpow(d,n);
    for(ll j=2;j*a<=k;j++){
      w[a]-=w[a*j];
    }; 
    if(w[a]>MOD)w[a]%=MOD;
    //printf("%lld ",w[a]);
    ans+=(w[a]*a)%MOD;
  };
  ans%=MOD;
  printf("%lld",ans);
};

Measured memory_bytes: 2504
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <int> p(n);
  vector <int> q(n);
  for (int& elem: p) cin >> elem;
  for (int& elem: q) cin >> elem;
  vector <int> perm(n);
  iota(all(perm), 1);
  int a = -1;
  int b = -1;
  int index = 1;
  do {
    if (perm == p) a = index;
    if (perm == q) b = index;
    index++;
  } while (next_permutation(all(perm)));
  cout << abs(a - b) << '\n';
  return (0);
}


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


def main():
    """Function."""
    h, w = map(int, input().split())

    sharp = ""
    for _ in range(w+2):
        sharp += "#"
    print(sharp)

    for _ in range(h):
        dum = "#"
        a = str(input())
        dum += a
        dum += "#"
        print(dum)

    print(sharp)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
from collections import defaultdict, Counter
import sys
import itertools
input = sys.stdin.readline

c = defaultdict(int)
H,W,N = map(int,input().split())
for _ in range(N):
  a,b = map(int,input().split())
  # そのセルを含む正方形の中心を記録
  for dx,dy in itertools.product([-1,0,1],repeat = 2):
    aa = a + dx
    bb = b + dy
    if 2 <= aa <= H-1 and 2 <= bb <= W-1:
	    c[(aa,bb)] += 1

result = Counter(c.values())
result[0] = (H-2)*(W-2) - sum(result.values())

for j in range(10):
  print(result[j])


Measured memory_bytes: 166892
#include <cstdio>
#define ll long long int
int main()
{
	ll n, now = 100, ans = 0;
	scanf("%lld", &n);
	while(now<n)
	{
		ans++;
		now = now+now/100;
		if(now>=n)
		{
			printf("%lld\n", ans);
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <deque>
#include <stdio.h>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
	string ans;
	int k;
	cin >> k;
	rep(i, k) {
		ans += "ACL";
	}

	cout << ans << endl;
}

Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<cmath>
#include<utility>
#include<cstdio>
using namespace std;
 
 
#define EPS 1e-10
#define INF 1e-10
 
double add(double a,double b){
if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;
return a+b;
}
struct P{
	double x,y;
	P(){}
	P(double x,double y):x(x),y(y){}
	P operator+(const P p) {return P(add(x,p.x),add(y,p.y));}
	P operator-(const P p) {return P(add(x,-p.x),add(y,-p.y));}
	P operator*(double d){return P(x*d,y*d);}
	double det(P p){return add(x*p.y,-y*p.x);}
};
 
 
P intersection(P p1,P p2, P q1, P q2){
	return p1+(p2-p1)*( (q2-q1).det(q1-p1)/(q2-q1).det(p2-p1) );
}
P line_symmetry(P p1,P p2,P q){
	double dx,dy;
	dx=p2.x-p1.x;
	dy=p2.y-p1.y;
	P inter=intersection(p1,p2,q,q+P(dy,-dx));
	return q+(inter-q)*2;
}
 
bool isline(pair<P,P> p){
	return p.second.x!=INF;
}
pair<P,P> f(string s){
	int lev=0;
	for(int i=s.size()-1;i>=0;i--){
		if(s[i]==')')lev++;
		else if(s[i]=='(')lev--;
		else if(s[i]=='@'&&lev==0){
			string s1,s2;
			pair<P,P> a,b;
			a=f(s.substr(0,i));
			b=f(s.substr(i+1));
			 
			if(isline(a)){
				if(isline(b)){
					return make_pair(intersection(a.first,a.second,b.first,b.second), P(INF,INF));
				}else{
					return make_pair(line_symmetry(a.first,a.second,b.first),P(INF,INF));
				}
			}else{
				if(isline(b)){
					return make_pair(line_symmetry(b.first,b.second,a.first),P(INF,INF));
				} else{
					return make_pair(a.first,b.first);
				}
			}
		}
	}
	if(s[0]=='('){return f(s.substr(1,s.size()-2));}
	else{
		//printf(" %s\n",s.c_str());
		int i=0,x=0,y=0;
		bool sign=false;
		if(s[i]=='-')sign=true,i++;
		for(;s[i]!=',';i++){
			x*=10;
			x+=(s[i]-'0');
		}
		if(sign)x*=-1;
		//printf("%c\n",s[i]);
		sign=false;
		i++;
		//printf("%c\n",s[i]);
		if(s[i]=='-')sign=true,i++;
		//printf("%c\n",s[i]);
		for(;i<s.size();i++){
			y*=10;
			y+=s[i]-'0';
		}
		if(sign)y*=-1;
		return make_pair(P(x,y),P(INF,INF));
	}
}
 
 
int main(){
	string line;
	while(cin>>line&&line!="#"){
		pair<P,P> a=f(line);
		printf("%.8f %.8f\n",a.first.x,a.first.y);
	}
	return 0;
}

Measured memory_bytes: 1260