akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> l(n+1, 0), r(n+1, 0);
    for(int i=0;i<n;i++){
    	cin >> l[i] >> r[i];
    }
    sort(be(l));
    reverse(be(l));
    sort(be(r));
    ll ans = 0, sum = 0;
    for(int i=0;i<=n;i++){
    	sum += (l[i] - r[i]) * 2;
    	ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}


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

string solve() {
  int N;
  cin >> N;
  vector<vector<int>> G(N);
  for(auto i=0; i<N; ++i) {
    int p;
    cin >> p;
    G[p-1].emplace_back(i);
  }

  vector<int> Grundy(N, -1);

  function<int(int, int)> dfs = [&](auto u, auto d) {
    if(Grundy[u]!=-1) return Grundy[u];
    Grundy[u] = N;
    set<int> S;
    for(auto v: G[u]) S.emplace(dfs(v, d));
    for(auto i=0; i<N; ++i) if(!S.count(i)) if(!S.count(N) || d--==0) return Grundy[u] = i;
    assert(false);
  };

  auto check = [&]() {
    for(auto u=0; u<N; ++u) {
      set<int> S;
      for(auto v: G[u]) {
        if(Grundy[u]==Grundy[v]) return false;
        S.emplace(Grundy[v]);
      }
      for(auto i=0; i<Grundy[u]; ++i) if(!S.count(i)) return false;
    }
    return true;
  };

  for(auto d: {0, 1}) {
    Grundy.assign(N, -1);
    for(auto v=0; v<N; ++v) dfs(v, d);
    if(check()) return "POSSIBLE";
  }
  return "IMPOSSIBLE";
}

int main() {
  cout << solve() << endl;
}


Measured memory_bytes: 29696
#include <stdio.h>

int main(){
  int i,n,fl=0,ng=0;
  
  for(i=0;i<4 && ng==0;i++){
  scanf("%d",&n);
    switch(n){
      case 1:
        fl += 1000;
        break;
      case 9:
        fl += 100;
        break;      
      case 7:
        fl += 10;
        break;      
      case 4:
        fl += 1;
        break;
      default:
        ng = 1;
        break;
    }
  }
  
  if(fl == 1111){
    printf("YES\n");
  }
  else{
    printf("NO\n");
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

const int max_n = 10, INF = 100000000;
struct edge{ int to, cost; };
typedef pair<int, int> P;

int n;
vector<edge> g[max_n];
int d[max_n];
bool exi[max_n];

void dijkstra(int s){
	//priority_que
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d + max_n, INF);
	d[s] = 0;
	que.push(P(0, s));//コスト、ノードの順
	
	while(!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;//もともと入っていたやつの方が低コスト
		for(int i = 0; i < g[v].size(); i++){
			edge e = g[v][i];
			if(d[e.to] > p.first + e.cost){
				d[e.to] = p.first + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main(){
	int res, ans, pos;
	
	while(true){
		scanf("%d", &n);
		if(n == 0) return 0;
		fill(exi, exi + max_n, false);
		for(int i = 0; i < max_n; i++){
			g[i].clear();
		}
		for(int i = 0; i < n; i++){
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			edge p1, p2;
			p1.to = b; p1.cost = c;
			p2.to = a; p2.cost = c;
			g[a].push_back(p1);
			g[b].push_back(p2);
			exi[a] = true; exi[b] = true;
		}
		
		ans = INF;
		pos = 0;
		for(int i = 0; i < 10; i++){
			if(!exi[i]) continue;
			res = 0;
			dijkstra(i);
			for(int j = 0; j < 10; j++){
				if(d[j] != INF){
					res += d[j];
				}
			}
			if(ans > res){
				pos = i;
				ans = res;
			}
		}
		
		printf("%d %d\n", pos, ans);
	}
}

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

int main()
{
	int64_t n;
	cin >> n;
	vector<int64_t> as(n);
	for (auto &&a : as)
	{
		cin >> a;

		if (a == 0)
		{
			cout << 0 << endl;

			return 0;
		}
	}

	__int128_t ans = 1;
	for (__int128_t &&a : as)
	{
		if (1'000'000'000'000'000'000LL < ans * a)
		{
			cout << -1 << endl;

			return 0;
		}

		ans *= a;
	}

	string s = "";
	while (ans)
	{
		s += char('0' + ans % 10);
		ans /= 10;
	}
	reverse(s.begin(), s.end());

	cout << s << endl;

	return 0;
}

Measured memory_bytes: 4052
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

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

        for (int i = 0; i < N; i++)
            A[i] = ReadLine().Split(' ').Select(s => int.Parse(s)).Skip(1).ToArray(); ;
        
        var foods = new int[M];
        foreach (var subA in A)
            foreach (var a in subA)
                foods[a - 1]++;

        var ans = foods.Count(x => x == N);

        WriteLine(ans);
    }
}


Measured memory_bytes: 28276
N=int(input())
##c=list(map(int, input().split()))
 
a = [list(map(int, input().split())) for _ in range(N)]
 
k=0
for i in range(N):
    for j in range(N):
        if(i!=j):
            k=k+((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]))**0.5
 
print(k/N)
 


Measured memory_bytes: 9368
package main

import (
  "fmt"
  "sort"
)
  
func main() {
  var a, b, c int
  fmt.Scan(&a, &b, &c)
  
  slice := []int{a, b, c}
  sort.Sort(sort.Reverse(sort.IntSlice(slice)))
  
  fmt.Println(slice[0] * 10 + slice[1] + slice[2])
}

Measured memory_bytes: 512
let id x = x
let (n,a,b) = Scanf.scanf "%d %d %d\n" (fun n a b -> (n,a,b))
 
let array = Array.init n (fun _ -> Scanf.scanf "%d\n" id)
let () = Array.sort compare array
let l = Array.length array

let max = (array.(l-1) / b) + 1

let rec func1 tmid i m =
  if i = l then m else
    let x = array.(i) - b*tmid in
    if x < 0 then func1 tmid (i+1) m
    else if x mod (a-b) = 0 then func1 tmid (i+1) (m + x/(a-b))
    else func1 tmid (i+1) (m + 1+x/(a-b))

let rec func tmin tmax =
  if tmin = tmax then tmin else
  let tmid = (tmax + tmin) / 2 in
  let tsuika = func1 tmid 0 0 in
  if tsuika <= tmid then func tmin tmid
  else (if tmax - tmin = 1 then tmax else func tmid tmax)

let ans = func 1 max

let () =
  Printf.printf "%d\n" ans


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

int main()
{
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    char c1 = s1[0] - 32;
    char c2 = s2[0] - 32;
    char c3 = s3[0] - 32;
    cout << c1 << c2 << c3 << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Scanner;
public class Main {
    private static final PrintStream ps = System.out;
    private static final Scanner     sc = new Scanner(System.in);

    public static void main(String[] args) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        long k = sc.nextLong();
            
        ps.println((k % 2 == 0) ? a-b : b-a);
    }
}

Measured memory_bytes: 21844
#include<stdio.h>
int main(void)
{
	int S,h,m,s;
	do{
		scanf("%d",&S);
		}while(0>S||S>86400);
	h=S/3600;
	m=S%3600/60;
	s=S%3600%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

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

typedef long long int lli;
typedef long int li;

void solve(){
    int x;
    cin >> x;
    cout << (360 / __gcd(360, x)) << '\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

/*
  check for corner cases.
  When using log check for zeros.
  Use queues and stacks if they are helping.

    (___)
    . . )____________
   _|__/\           |\
  (o_o_) \__________| \
           /|     ||   )
          < |     ||
*/


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,c=0,f=0;
  cin>>n;
  int a[n],b[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i]>>b[i];
}
    for(int i=0;i<=n-3;i++)
    {
    	c=0;
    	for(int j=i;j<i+3;j++)
    	{
    		if(a[j]==b[j])
    		c++;
		}
   if(c==3)
   {
   f=1;
   break;
}
   else
   continue;
     // cout<<"YES"<<endl;
  }
  if(f==1)
  cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
	return 0;
}


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

int main() {

    vector<int> x(5);
    int N = 5;

    rep(i, N) cin >> x[i];

    rep(i, N) {
        if (x[i] == 0) {
            cout << i+1 << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

string s[100];

int main() {
	string ans;
	rep(i, 3) {
		cin >> s[i];
		ans += s[i][i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
#define rep(i,n) for(ll i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define d_5 100000
#define d9_7 1000000007
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define pf push_front
#define ld long double
#define ll long long
#define ull unsigned long long

ll digitpower(ll a,ull b){//aのb乗を計算
  if(b==1){
    return a;
  }else if(b==0){
    return 1;
  }
  static int modmode=0;//%d9_7するのかどうか
  if(b%2==1){
    ll tmp = digitpower(a,(b-1)/2);
    if(modmode==1){
      tmp%=d9_7;
    }
    tmp*=tmp;
    if(modmode==1){
      tmp%=d9_7;
    }
    tmp*=a;
    if(modmode==1){
     return (tmp)%d9_7;
    }else{
      return tmp;
    }
  }else{
    ll tmp = digitpower(a,(b)/2);
    if(modmode==1){
      tmp%=d9_7;
    }
    tmp*=tmp;
    if(modmode==1){
      tmp%=d9_7;
    }
    if(modmode==1){
      return (tmp)%d9_7;
    }
    return tmp;
  }
}
template<class T>
class SegmentTree{
  public:
   int n;
   vector<T> nodes;
    //constructor
    SegmentTree(int size,T init){
      initialize(size,init);
    }
    //関数を定義(minなのかmaxなのかとか)
    T thisoperator(T a, T b){
      return min(a,b);
    }
    void update(int x,T a){//xがindex
      x+=n-1;
      nodes[x]=a;
      while(x>0){
        x=(x-1)/2;
        nodes[x]=thisoperator(nodes[2*x+1],nodes[2*x+2]);
      }
    }
   void initialize(int inputn,T init){
      int k=0;
      while(inputn>digitpower(2,k)){
        k++;
      }
      n=digitpower(2,k);
      nodes=vector<T> (digitpower(2,k)*2-1,init);
   }
   T sec_get(int reql,int reqr,int nowindex=0,int nowl=0,int nowr=-1){
     // 最初に呼び出されたときの対象区間は [0, n)
    if(nowr < 0) nowr = n;

    // 要求区間と対象区間が交わらない -> 適当に返す
    if(nowr <= reql || reqr <= nowl) return llMAX;

    // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
    if(reql <= nowl && nowr <= reqr) return nodes[nowindex];
    // 要求区間が対象区間の一部を被覆 -> 子について探索を行う
    // 左側の子を vl ・ 右側の子を vr としている
    // 新しい対象区間は、現在の対象区間を半分に割ったもの
    T val1 = sec_get(reql, reqr, 2*nowindex+1, nowl, (nowl+nowr)/2);
    T val2 = sec_get(reql, reqr, 2*nowindex+2, (nowl+nowr)/2, nowr);
    return thisoperator(val1, val2);
   }
   void Printn(){
     cout<<"Printvector"<<endl;
     rep(i,n){
       cout<<nodes[i+n-1]<<" ";
     }
     cout<<endl;
   }
};

int main(void){
  int n,q;
  cin>>n>>q;
  SegmentTree<ll> seg(n,digitpower(2,31)-1);
  vl c1(q),c2(q),c3(q);
  rep(i,q){
    cin>>c1[i]>>c2[i]>>c3[i];
  }
  rep(i,q){
    ll com=c1[i],x=c2[i],y=c3[i];
    if(com==0){
     // x--;
      seg.update(x,y);
    }else{
      //x--;y--;
      cout<<seg.sec_get(x,y+1)<<endl;
    }
    //seg.Printn();
  }
  return 0;
}



Measured memory_bytes: 7200
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  string s;
  cin >> s;
  string t;
  rep (i, s.size() / 2) t += "hi";
  cout << (s == t ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int n; cin >> n;
	string s; cin >> s;
	int ans = 0;
	int widx = 0;
	int ridx = n - 1;

	while (true) {
		//cout << widx << " " << ridx << " " << s[widx] << " " << s[ridx] << endl;
		while (widx < n && s[widx] == 'R') widx++;
		while (0 <= ridx && s[ridx] == 'W') ridx--;

		if (ridx < widx) break;
		if (widx == n) break;
		if (ridx == -1) break;

		ans++;
		swap(s[ridx], s[widx]);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3772
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N,C;
int S,T,C1;
int main() {
	cin>>N>>C;

	int D[31][100001]={};
	for(int i=0;i<N;i++){
		cin>>S>>T>>C1;
		for(int j=S-1;j<T;j++){
			D[C1][j]=1;
		}
	}

	int k;
	int total=0;
	for(int i=0;i<100001;i++){
		k=0;
		for(int j=1;j<31;j++){
			if(D[j][i]==1)k+=1;
		}
		total=max(total,k);
	}

	cout<<total<<endl;

	return 0;
}


Measured memory_bytes: 12416
#include<bits/stdc++.h>
#define int long long
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
	x = 0;char c = getchar();bool f = 0;
	for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
	for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
	if(f) x = -x;
}
const int base = 2010, mod = 1e9 + 7;
int n, f[base * 2 + 10][base * 2 + 10], fac[10010], inv[10010], fac_inv[10010];
int x[200100], y[200100];
int ans = 0 ;
main() {
	fac[0] = 1;for(int i = 1; i <= base * 4; i ++) fac[i] = (fac[i - 1] * i) % mod ;
	inv[1] = 1;for(int i = 2; i <= base * 4; i ++) inv[i] = (mod - inv[mod % i] * (mod / i) % mod) % mod;
	fac_inv[1] = 1;for(int i = 2; i <= base * 4; i ++) fac_inv[i] = fac_inv[i - 1] * inv[i] % mod; 
//	for(int i = 1; i <= 10; i ++) cerr << fac[i] << ' '<< inv[i] << ' '<< fac_inv[i] <<"\n";
	cin >> n;
	memset(f, 0, sizeof(f));
	for(int i = 1; i <= n; i ++) {
		read(x[i]), read(y[i]);
		f[base - x[i]][base - y[i]] ++; 
	}
	for(int i = 1; i < base * 2; i ++) {
		for(int j = 1; j < base * 2;j ++) {
			(f[i][j] += (f[i - 1][j] + f[i][j - 1]) % mod) %= mod;
//			if(f[i][j]) cout << i << ' ' << j << "\n";
		}
	}
	for(int i = 1; i <= n; i ++) {
		(ans += f[base + x[i]][base + y[i]]) %= mod;
//		cout << f[base + x[i]][base + y[i]] << "\n"; 
	}
	for(int i = -2; i <= 2; i ++) {
		for(int j = -2; j <= 2; j ++) {
//			cerr << f[base + i][base + j] << ' ';
		}
//		putchar('\n');
	}
//	cout << ans << "\n";
	for(int i = 1; i <= n; i ++) (ans += mod - (fac[(x[i] + y[i]) << 1] * fac_inv[x[i] + x[i]] % mod * fac_inv[y[i] + y[i]]) % mod ) %= mod;
//	cout << ans << "\n";
	cout << (ans * inv[2]) % mod<< "\n"; 
}

Measured memory_bytes: 130432
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MOD=1e9+7;
ll a[N];
//ll sum;
//ll ans[N];
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin >>n;
    for(int i=1;i<=n;i++){
        cin >>a[i];
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ans=max(ans,abs(a[i]-a[j]));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef map<int, int> mi;
typedef set<int> si;
#define VV(T) vector<vector< T > >
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define invrep(i, n) for(int i = (n)-1; i >= 0; i--)        // n-1, n-2, ..., 0
#define invREP(i, x, n) for(int i = (n)-1; i >= (x; i--)    // n-1, n-2, ..., x
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define PB push_back

#define COUT(x) cout << (x) << endl
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECCOUT(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    // 頂点数sz_だけ初期化をする
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    // xの属する根の検索を行う
    ll root(ll x) { 
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    // xとyをくっ付ける。小さい方を大きい方にくっ付ける。
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }
    // xとyが連結をしているか判定を行う。
    bool issame(ll x, ll y) { 
        return root(x) == root(y);
    }
    // 頂点xが属する素集合のサイズを求める。
    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, M; cin >> N >> M;
    UnionFind uf(N);
    vector<pi> vec(M);
    rep(i, M){
        int a, b; cin >> a >> b;
        a--; b--;
        vec[i].first = a;
        vec[i].second = b;
    }

    int ans = 0;
    rep(i, M){
        uf.init(N);
        rep(j, M){
            if (j == i) continue;
            uf.merge(vec[j].first, vec[j].second);
        }
        if (uf.size(0) < N) ans++;
    }
    COUT(ans);
}

Measured memory_bytes: 256
#include <stdio.h>

int
main(int argc, char *argv[])
{
  int n; char s[400000] = {}; int k = -1; int b[400000];
  scanf("%d%s", &n, s); int j = 0;
  for(int i = 0; i < n; i++){
    if(s[i] == '#'){
      b[j] = i;
      j++;
    }
  }

  int black = j;
  int m = j;
  if(j != 0){
  for(int i = 0; i <= black - 1; i++){
    if(i + n - black - (b[i] - i) < m){
      m = i + n - black - (b[i] - i);
    }
  }
  }
  else{
    m = 0;
  }

  printf("%d\n", m);
  return 0;
}



Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <utility>

using namespace std;

const int MAXN = 200005;

pair<int, int> X[MAXN];

int B[MAXN];

int n;

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> X[i].first, X[i].second = i;
	sort(X + 1, X + n + 1);
	int m = n / 2;
	for (int i = 1; i <= m; i++)
		B[X[i].second] = X[m + 1].first;
	for (int i = m + 1; i <= n; i++)
		B[X[i].second] = X[m].first;
	for (int i = 1; i <= n; i++)
		cout << B[i] << endl;
	return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <deque>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 1<<30;
typedef pair<int, int> P;

int main() {
  int n, k; cin >> n >> k;
  string s; cin >> s;
  int res = 0;
  for(int i = 1; i < n; i++) {
    if(s[i] == s[i-1]) res++;
  }
  cout << min(res+2*k, n-1) << endl;

  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;
typedef long long ll;

int main() {

    ll A;
    ll b[2];
    scanf("%lld %lld.%lld", &A, &b[0], &b[1]);
    ll B = b[0] * 100 + b[1];
    cout << (A * B / 100) << endl;
    
    return 0;
}

Measured memory_bytes: 3644
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	printf("%d\n", (1900*m + 100*(n-m))*(1<<m));
	return 0;
}



Measured memory_bytes: 3820
n=int(input())
#n,m=map(int,input().split())
pl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
mn=pl[0]
ans=0
for i in range(n):
    mn=min(pl[i],mn)
    if pl[i]<=mn:
        ans+=1
print(ans)


Measured memory_bytes: 24744
def z_algo(s):
    res = [0] * len(s)
    res[0] = len(s)
    i = 1
    j = 0
    while i < len(s):
        while i + j < len(s) and s[j] == s[i + j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res


n = int(input())
s = input()

ans = 0
for i in range(n):
    res = z_algo(s[i:])
    for i, lcp in enumerate(res):
        ans = max(ans, min(lcp, i))
print(ans)


Measured memory_bytes: 75428
class Rectangle
    attr_accessor :x,:y
    def initialize(x,y)
        self.x = x
        self.y = y
    end
    def calculate_area
        return self.x*self.y
    end
    def calculate_parameter
        return 2*self.x+2*self.y
    end
end

nums = gets.split.map(&:to_i)
rec = Rectangle.new(*nums)
puts("#{rec.calculate_area} #{rec.calculate_parameter}")


Measured memory_bytes: 6844
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<list>

#define endl "\n"
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;

int main(){
    int x;
    cin>>x;
    
    int dmax=0;
    for(int i=1;i<=x;i++){
        dmax += i;
        if(dmax >= x){
            cout<<i<<endl;
            return 0;
        }   
    }
}

Measured memory_bytes: 256
import Text.Printf

ans ([n,t]:xx) =
  let n' = ceiling n :: Int
      g = maximum $ map (\[x,h] -> t * h / x) $ take n' xx
  in
    g
    
main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Double]]
      o = ans i
  printf "%.6f\n" o



Measured memory_bytes: 5100
#include "bits/stdc++.h"
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
	stack<int> s;
	int a;
	while(cin>>a){
		if(a!=0){
		s.push(a);
		}else{
			cout<<s.top()<<endl;
			s.pop();
		}
	}
}

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

using namespace std;
using ll = long long;

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


class Eratosthenes {
public:
    vector<bool> prime;

    Eratosthenes(ll size) {
        size = max((int) sqrt(size) + 1, 101010);
        prime.resize(size, 1);
        prime[0] = 0;
        prime[1] = 0;
        for (size_t i = 2; i * i <= size; ++i)
            if (prime[i]) {
                for (size_t j = 2; i * j <= size; ++j)prime[i * j] = false;
            }
    }
};


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

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

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


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

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

ll N, Q;
string s;

int main() {
    cin >> N >> Q;
    cin >> s;
    vector<int> T(s.size() + 1);
    REP(i, s.size() - 1) {
        if (s[i] == 'A' && s[i + 1] == 'C')T[i + 1] = T[i] + 1;
        else T[i + 1] = T[i];
    }
    REP(i, Q) {
        int l, r;
        cin >> l >> r;
        cout << T[r-1] - T[l-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1408
S=input()
A=S.count('a')
B=S.count('b')
C=S.count('c')
if A==B and B==C:
    print('YES')
elif A==B:
    if C==A-1 or C==A+1:
        print ('YES')
    else:
        print('NO')
elif B==C:
    if A==B-1 or A==B+1:
        print('YES')
    else:
        print('NO')
elif C==A:
    if B==A-1 or B==A+1:
        print('YES')
    else:
        print('NO')
else:
     print('NO')

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  map<string, int> mp;
  int maxv = 0;
  rep(i, n) {
    string tmp;
    cin >> tmp;
    mp[tmp]++;
    maxv = max(maxv, mp[tmp]);
  }

  for(auto a : mp){
    string k = a.first;
    int v = a.second;
    if(v == maxv) cout << k << endl;
  }
}


Measured memory_bytes: 23808
#include <vector>
#include <algorithm>
using namespace std;
template<class T> class PriorityQueue {
private:
	size_t size_; vector<T> heap;
public:
	PriorityQueue() : size_(1), heap(vector<T>(1, 0)) {};
	PriorityQueue(PriorityQueue& que) : size_(que.size_), heap(que.heap) {};
	size_t size() { return size_ - 1; }
	inline void insert(int x) {
		unsigned ptr = size_++; heap.push_back(x);
		while (ptr > 1) {
			if (heap[ptr >> 1] < heap[ptr]) swap(heap[ptr], heap[ptr >> 1]);
			ptr >>= 1;
		}
	}
	inline int extract() {
		int ret = heap[1]; unsigned ptr = 1;
		while ((ptr << 1) + 1 < size_) {
			ptr <<= 1;
			if (heap[ptr] > heap[ptr + 1]) swap(heap[ptr >> 1], heap[ptr]);
			else swap(heap[ptr + 1], heap[ptr >> 1]), ptr++;
		}
		heap[ptr] = heap[--size_], heap[size_] = 0;
		while (ptr > 1) {
			if (heap[ptr >> 1] < heap[ptr]) swap(heap[ptr], heap[ptr >> 1]);
			ptr >>= 1;
		}
		heap.pop_back();
		return ret;
	}
};
char c[9]; int v;
int main() {
    PriorityQueue<int> que;
    while(scanf("%s", c), c[3]) {
        if(*c == 'i') scanf("%d", &v), que.insert(v);
        else printf("%d\n", que.extract());
    }
}

Measured memory_bytes: 6516
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <cstdlib>
#include <queue>
#include <vector>
#include <set>
#include <stdio.h>
#include <cstdio>
#include <cmath>
#include <complex> 
using namespace std;
typedef complex<double> xy_t;
xy_t P[2];
int N;
double x,y,z,w;
const double eps = 1e-11;
int main() {
cin >> N;
for( int j = 0;j < N ;j++) {
for(int i = 0;i < 2;i++) {
	cin >> x >> y >> z >> w;
	P[i] = xy_t(z-x,w-y);
}
	double s =  (P[0].real()*P[1].imag()-P[0].imag()*P[1].real())/2;
bool p;
if (abs(s) < eps) p = true;
else p = false;
cout << (p ? "YES" : "NO") << endl;
}
}

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

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

  vector<int> a(N);

  for(int i = 0; i < N; i++){
    a.at(i) = L + i;
  }

  int ans = 0;

  if(a.at(0) >= 0){
    for(int i = 1; i < N; i++){
      ans += a.at(i);
    }
  }
  else if(a.at(N - 1) <= 0){
    for(int i = 0; i < N - 1; i++){
      ans += a.at(i);
    }
  }
  else{
    for(int i = 0; i < N; i++){
      ans += a.at(i);
    }
  }

  

  cout << ans << endl;

  
}

Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int N;

int main(){
	scanf("%d", &N);

	for (int i = 0; i < N; i++){
		int x, y, b, p;
		scanf("%d %d %d %d", &x, &y, &b, &p);

		if (b >= 5 && p >= 2){
			printf("%d\n", (int)((x*b + y*p)*0.8));
		}
		else {
			int tb = b;
			int tp = p;
			int test = 0;
			int ans = x*b + y*p;

			if (5 > b)tb = tb + 5 - b;
			if (2 > p)tp = tp + 2 - p;

			test = (int)((tb*x + tp*y)*0.8);

			if (test > ans)
				printf("%d\n", ans);
			else
				printf("%d\n", test);
		}
	}
}

Measured memory_bytes: 1032
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    set<ll> s;
    ll cnt = 0;
    for (ll i = 0; i < n; i++)
    {
        ll temp;
        cin >> temp;
        if (temp >= 3200)
            cnt++;
        else
        {
            s.insert(temp / 400);
        }
    }
    if(s.size() == 0)
    {
        cout << 1 << " " << cnt << endl;
    }
    else
        cout << s.size() << " " << cnt + s.size() << endl;
}

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

int count_lighting_bulb(int M, const vector<int> &p_vec, 
        const vector<bitset<10>> &connected, const bitset<10> &switches)
{
    int cnt = 0;
    for (int i = 0; i < M; ++i) {
        int num_valid_switches = (connected.at(i) & switches).count();
        if (num_valid_switches % 2 == p_vec.at(i))
            ++cnt;
    }
    return cnt;
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> p_vec(M);
    vector<bitset<10>> connected(M, 0);
    int k, s;
    for (int i = 0; i < M; ++i) {
        cin >> k;
        for (int j = 0; j < k; ++j) {
            cin >> s;
            --s;
            connected.at(i).set(s);
        }
    }
    for (int i = 0; i < M; ++i)
        cin >> p_vec.at(i);
    int cnt = 0;
    for (int i = 0; i < (1 << N); ++i) {
        bitset<10> switches(i);
        int num = count_lighting_bulb(M, p_vec, connected, switches);
        if (num == M)
            ++cnt;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define endl "\n";
typedef  long long int lli;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inf (1000*1000*1000+5)
const int NODE =1e4+9;

const int mod=1e9+7;
const lli num=1e5+5;

void init(){

}


int main()
{
   boost;
   int t=1;
   //cin>>t;
   init();
   while(t--){
      int n,m;
      cin>>n>>m;
      char a[n][m];
      for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];
      int dp[n][m];
      memset(dp,0,sizeof(dp));
      dp[0][0]=1;
      for(int i=0;i<n;i++){
         for(int j=0;j<m;j++){
            if(a[i][j]=='#'){
               dp[i][j]=0;
               continue;
            }
            if(i==0&&j==0)continue;
            if(i==0)dp[i][j]=dp[i][j-1];
            else if(j==0)dp[i][j]=dp[i-1][j];
            else dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i][j-1])%mod;
         }
      }
      cout<<dp[n-1][m-1]<<endl;
   }
   return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
typedef long long ll;
#define INF 1000000000
using namespace std;
int main(void){
    ll a=INF,b=-INF;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        ll tmp;
        cin>>tmp;
        if(tmp<a){
            a=tmp;
        }
        if(b<tmp){
            b=tmp;
        }
    }
    cout<<b-a<<endl;
}

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

int main() {
  string n;
  char a;
  cin >> n;
  a = n[0];
  for(int i=1;i<n.size();i++){
    if(a!=n[i]){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 価値の少ないものは貢献度を低くする。そのために、最初に混ぜる
N = ir()
V = np.array(lr())
V.sort()
coef = [.5 ** x for x in range(1, N+1)]
coef.reverse()
coef[0] = coef[1]
coef = np.array(coef)
answer = (V * coef).sum()
print('{:.10f}'.format(answer))



Measured memory_bytes: 12440
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		Deque<Integer> q = new LinkedList<Integer>();
		for (int i = 0; i < n; i++) {
			String line = br.readLine();

			if (line.startsWith("insert")) {
				q.offerFirst(Integer.parseInt(line.substring(line.indexOf(" ") + 1)));
			} else if (line.equals("deleteFirst")) {
				q.pollFirst();
			} else if (line.equals("deleteLast")) {
				q.pollLast();
			} else {
				q.remove(Integer.parseInt(line.substring(line.indexOf(" ") + 1)));
			}
		}

		StringBuilder sb = new StringBuilder();
		sb.append(q.poll());
		for (Integer s : q) {
			sb.append(" ").append(s);
		}
		System.out.println(sb.toString());

		if (br != null) {
			br.close();
			br = null;
		}
	}
}

Measured memory_bytes: 135084
n = int(input())

output = ""
for i in range(1,n+1):
    if i % 3 == 0:
        output += " %s" % (i,)
        continue
    elif i % 10 == 3:
        output += " %s" % (i,)
        continue
    x = i
    while x > 1:
      x = int(x/10)
      if x % 10 == 3:
        output += " %s" % (i,)
        break
print(output)

Measured memory_bytes: 7688
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define I64d_OJ

//#ifdef I64d_OJ
//#define LL __int64
//#endif // I64d_OJ
#ifdef I64d_OJ
#define LL long long
#endif // I64d_OJ

typedef unsigned LL ULL;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;
typedef vector<int> vi;

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

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define MID(a,b) (((LL)(a)+(LL)(b))>>1)
#define absx(a) ((a)<0?-(a):(a))
#define MK(a,b) make_pair(a,b)
#define PB(a) push_back(a)
#define lowbit(x) ((x)&-(x))

#define lc c[x][0]
#define rc c[x][1]

template< typename T >
inline void Max(T &a,T &b){if(a<b) a=b;}
template< typename T>
inline void Min(T &a,T &b){if(a>b) a=b;}

const double pi=(double)acos(-1.0);
const double eps=(double)1e-8;
const int INF = (int) 0x3f3f3f3f;
const int MOD = (int) 1e9+7;
const int MAXN =(int) 1e5+10;
const int MAXM = (int) 3e6+10;

///--------------------START-------------------------
int N,K;
LL s[MAXN];

LL power(LL x,LL y){
    LL ret=1;
    for(;y;x=x*x%MOD,y>>=1)if(y&1){
        ret=ret*x%MOD;
    }
    return ret;
}

void work(){
    scanf("%d%d",&N,&K);
    for(int i=K;i>=1;i--){
        s[i]=power((LL)K/i,(LL)N);
//        printf("%d %lld\n",i,s[i]);
    }
//    for(int i=1;i<=K;i++) printf("%lld ",s[i]);
//    printf("\n");
    LL ans=0;
    for(int i=K;i>=1;i--){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                int k=i/j;
                if(k!=i) s[k]-=s[i];
                if(j!=k) s[j]-=s[i];
            }
        }
    }
//    for(int i=1;i<=K;i++) printf("%lld ",s[i]);
//    printf("\n");
    for(int i=1;i<=K;i++){
        ans=(ans+i*s[i]%MOD)%MOD;
    }
    printf("%lld\n",ans);
}

///--------------------END-------------------------
int main(){
#ifdef NNever
//freopen("data.in","r",stdin);
///freopen("out.txt","w",stdout);
#endif // NNever
    work();
    return 0;
}







Measured memory_bytes: 4624
n, k = gets.split.map(&:to_i)
a = [0] + gets.split.map(&:to_i)
visited = Array.new(n + 1, nil)
now = 1
visited[1] = 0
isfirst = true
i = 1
while i <= k
	now = a[now]
	if visited[now] && isfirst
		i = i + (k - i) / (i - visited[now]) * (i - visited[now])
		isfirst = false
	else
		visited[now] = i
	end
	i += 1
end
		
puts now

Measured memory_bytes: 30448
n=int(raw_input(''))
a,b=raw_input('').split()
a=int(a)
b=int(b)
p=map(int,raw_input('').split())
ac=0
bc=0
cc=0

for i in p:
    if i<=a:
        ac+=1
    elif i>=a+1 and i<=b:
        bc+=1
    elif i>=b+1:
        cc+=1

print(min(ac,min(bc,cc)))

Measured memory_bytes: 2568
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"

#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
typedef long long ll;
using namespace std;

int n, m, a, b, c;
ll mem;
pair<ll, bool>g[1000];
vector<pair<int, int>>gp[1000];

/*
ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	ll g = gcd(x, y);
	return x / g * y;
}*/



int main(){
	cin >> n >> m;
	lp(m) {
		cin >> a >> b >> c;
		gp[a - 1].push_back(make_pair(b - 1, c));
	}
	lp(n)
		g[i].second = false;
	g[0] = make_pair(0, true);
	LP(n, h) {
		lp(n) {
			if (g[i].second) {
				LP(gp[i].size(), j) {
					if (g[gp[i][j].first].second)
						g[gp[i][j].first].first = max(g[gp[i][j].first].first, g[i].first + gp[i][j].second);
					else {
						g[gp[i][j].first].first = g[i].first + gp[i][j].second;
						g[gp[i][j].first].second = true;
					}
				}
			}
		}
	}
	mem = g[n - 1].first;
	LP(n, h) {
		lp(n) {
			if (g[i].second) {
				LP(gp[i].size(), j) {
					if (g[gp[i][j].first].second)
						g[gp[i][j].first].first = max(g[gp[i][j].first].first, g[i].first + gp[i][j].second);
					else {
						g[gp[i][j].first].first = g[i].first + gp[i][j].second;
						g[gp[i][j].first].second = true;
					}
				}
			}
		}
	}
	if (mem == g[n - 1].first)cout << mem << endl;
	else cout << "inf" << endl;
	return 0;
}

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

using namespace std;

int day(const string& s)
{
    if (s == "SUN") { return 0; }
    else if (s == "MON") { return 1; }
    else if (s == "TUE") { return 2; }
    else if (s == "WED") { return 3; }
    else if (s == "THU") { return 4; }
    else if (s == "FRI") { return 5; }
    else if (s == "SAT") { return 6; }
    throw runtime_error("unknown day");
}

int main()
{
    string s;
    cin >> s;
    
    cout << (7 - day(s)) << endl;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N,0);
  
  for(int i=0; i<N; i++) {
    cin >> A[i];
  }
  
  sort(A.begin(), A.end());
  
  int min_diff = 1e9+10;
  for(int i=0; i<N-K+1; i++) {
    int tmp = A[i+K-1] - A[i];
    if(tmp<min_diff) {
      min_diff = tmp;
    }
  }
  
  cout << min_diff << endl;
  
  return 0;
}

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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

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

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

char a[]={'y','u','i','o','p','h','j','k','l','n','m'};

inline bool isright(char in){
	rep(i,11) if(in==a[i]) return true;
	return false;
}

int solve(string in){
	int n=in.size();
	bool flag=isright(in[0]);
	int ans=0;
	for(int i=1;i<n;++i){
		bool next=isright(in[i]);
		if(flag^next)
			ans++;
		flag=next;
	}
	return ans;
}

int main(void){
	string in;
	while(cin >> in){
		if(in=="#")
			break;
		int ans=solve(in);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1188
#include<iostream>
#include<cmath>
#define MAX 1299710
using namespace std;

bool isPrime[1299710];

void prime(){
  isPrime[0]=isPrime[1]=true;
  for(int i=2;i<sqrt(MAX);i++){
    for(int j=2*i;j<MAX;j+=i)isPrime[j]=true;
  }
}

int main(){
  prime();
  int n;
  while(cin>>n,n){
    int forward,back;
    forward=back=n;
    while(isPrime[forward]==true)forward++;
    while(isPrime[back]==true)back--;
    cout << forward-back << endl;
  }
  return 0;
}

Measured memory_bytes: 2428
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#else
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 119 << 23 | 1;
class {
 public:
  void solve() {
    string s;
    cin >> s;
    if (s == "ABC")
      cout << "ARC\n";
    else
      cout << "ABC\n";
  }
} NSPACE;
int main() {
  FPEN;
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  NSPACE.solve();
}

Measured memory_bytes: 3576
def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = [[M] * 26 for i in range(M + 1)]
    for i in range(M - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(S[i]) - ord('a')] = i
    ans = 0
    i = 0
    for c in T:
        pos = ord(c) - ord('a')
        if nxt[i][pos] == M:
            return -1
        ans += nxt[i][pos] - i + 1
        i = (nxt[i][pos] + 1) % N
    return ans

print(solve())


Measured memory_bytes: 72108
n, a, b = map(int, input().split())
s = input()
ab = a + b
cnt = 0
cnt_b = 0
for i in range(n):
    p = s[i]
    if p == 'a':
        if cnt < ab:
            print('Yes')
            cnt += 1
        else:
            print('No')
    elif p == 'b':
        if cnt < ab and cnt_b < b:
            print('Yes')
            cnt += 1
            cnt_b += 1
        else:
            print('No')
    else:
        print('No')

Measured memory_bytes: 4016
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 1<<29
#define LLINF 1LL<<60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modpow(ll a, ll n){ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}

ll N;
ll fact[100010];
ll ifact[100010];

ll modcomb(ll n, ll k){
    if(k < 0 || k > n) return 0;
    ll ans = fact[n];
    ans = ans * ifact[k] % MOD;
    ans = ans * ifact[n-k] % MOD;
    return ans;
}

int main() {
    scanf("%llu", &N);
    vector<ll> cnt(N+1, -1);
    ll a, d1, d2;
    REP(i, N) {
        scanf("%llu", &a);
        if(cnt[a] != -1) {
            d1 = min(cnt[a], ll(i));
            d2 = max(cnt[a], ll(i));
            break;
        }
        cnt[a] = i;
    }
    fact[0] = 1;
    ifact[0] = 1;
    FOR(i, 1, N+2) {
        fact[i] = fact[i-1] * i % MOD;
        ifact[i] = modpow(fact[i], MOD-2);
    }
    ll ans;
    printf("%lld\n", N);
    FOR(k, 2, N) {
        ans = modcomb(N-1, k) % MOD;
        ans = (ans + 2 * modcomb(N-1, k-1)) % MOD;        
        ans = (ans - modcomb(N-(d2-d1), k-1) + MOD) % MOD;
        ans = (ans + modcomb(N-1, k-2)) % MOD;
        printf("%llu\n", ans);
    }
    printf("1\n");
 	return 0;
}


Measured memory_bytes: 3584