akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MAX = 1010000;
const int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;

typedef pair<int, int>P;

int A[100010];
vector<int>mn;
signed main() {
	int N; cin >> N;
	int cnt = 0;
	REP(i, N) {
		cin >> A[i];
		mn.pb(abs(A[i]));
		if (A[i] <= 0) {
			cnt++;
			
		}
	}
	int ans = 0;
	if (cnt % 2 == 0) {
		REP(i, N) {
			ans += abs(A[i]);
		}
	}
	if (cnt % 2 == 1) {
		REP(i, N) {
			ans += abs(A[i]);
		}
		VSORT(mn);
		//VREVERSE(mn);
		//print(mn[0]);
		ans -= 2*mn[0];
	}
	print(ans);
}


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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#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 SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//conversion
//------------------------------------------
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();}

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

typedef long long LL;
const LL mod=1000000007;
#define MAX 10000
#define NIL -1
const double PI  = acos(-1.0);
const int INF = 1e9 + 7;
//-------------------------------------------

int n;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;

    if( n > 999)cout <<"ABD"<< endl;
    else { cout <<"ABC"<< endl;}

    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>
#include <cstdint>
#define _USE_CMATH_DEFINES

const long INF = (1l << 30);
const long LINF = (1l << 60); //1.15*10^18

long n, m;

int main(){
    scanf("%ld%ld", &n, &m);
    long ans = 0;
    if(n > 0){
        ans += n * (n-1) / 2;
    }
    if(m > 0){
        ans += m * (m-1) / 2;
    }
    printf("%ld\n", ans);
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int A = sc.nextInt();
		if (N % 500 <= A)
			System.out.println("Yes");
		else
			System.out.println("No");

	}
	//以下、自作ライブラリ

	//最大公約数
	public static long gcd(long a, long b) {
		if (a < b)
			return gcd(b, a);
		long c = 0;
		c = a % b;
		if (c == 0)
			return b;
		return gcd(b, c);
	}

	//最小公倍数
	public static long lcm(long m, long n) {
		return m * n / gcd(m, n);
	}

	//素数判定
	public static boolean isPrime(int n) {
		if (n < 2)
			return false;
		if (n == 2)
			return true;
		if (n % 2 == 0)
			return false;

		for (int i = 3; i * i <= n; i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}
}

//以下、高速スキャナークラス
class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 21332
tree = [ [] for _ in range(4) ]

for i in range(3):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    tree[a].append(b)
    tree[b].append(a)

for i in range(4):
    visited = [ False for _ in range(4) ]
    cur = i
    visited[cur] = True
    for j in range(3):
        for v in tree[cur]:
            if not visited[v]:
                next_v = v
                break
        visited[next_v] = True
        cur = next_v

print ( "YES" if all(visited) else "NO" )


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

using ll = long long;

//constant
const double EPS = 1e-10;
ll MOD = 1000000007;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// view vector
template<typename T> void view(T e) { std::cout << e << std::endl; }
template<typename T> void view(const std::vector<T>& v) { for (const auto& e : v) { std::cout << e << " "; } std::cout << std::endl; }
template<typename T> void view(const std::vector<std::vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

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

// ***************************************

const ll inf = 1LL << 60;

struct Mint {
    ll v;
    ll _mod;
    Mint() : v(0), _mod(_mod) {}
    Mint(signed v, ll _mod = MOD) : v(v), _mod(_mod) {}
    Mint(ll t, ll _mod = MOD) : _mod(_mod) {
        v = t % _mod;
        if (v < 0)
            v += _mod;
    }

    Mint pow(ll k) {
        Mint res(1, _mod), tmp(v, _mod);
        while (k) {
            if (k & 1)
                res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    } 
    static Mint add_identity(ll mod = MOD) { return Mint(0, mod); }
    static Mint mul_identity(ll mod = MOD) { return Mint(1, mod); }
    Mint inv() { return pow(_mod - 2); }

    Mint& operator+=(Mint a) {
        v += a.v;
        if (v >= _mod)
            v -= _mod;
        return *this;
    }
    Mint& operator-=(Mint a) {
        v += _mod - a.v;
        if (v >= _mod)
            v -= _mod;
        return *this;
    }
    Mint& operator*=(Mint a) {
        v = v * a.v % _mod;
        return *this;
    }
    Mint& operator/=(Mint a) { return (*this) *= a.inv(); }

    Mint operator+(Mint a) const { return Mint(v, _mod) += a; };
    Mint operator-(Mint a) const { return Mint(v, _mod) -= a; };
    Mint operator*(Mint a) const { return Mint(v, _mod) *= a; };
    Mint operator/(Mint a) const { return Mint(v, _mod) /= a; };

    Mint operator-() const { return v ? Mint(_mod - v, _mod) : Mint(v, _mod); }

    bool operator==(const Mint a) const { return v == a.v; }
    bool operator!=(const Mint a) const { return v != a.v; }
    bool operator<(const Mint a) const { return v < a.v; }
};
ostream& operator<<(ostream& os, Mint m) { return os << m.v; }


int main(void) {
	ll N, P;
	string S;
	
	cin >> N >> P >> S;

	vector<ll> md(P, 0);

	ll ans = 0;
	if (P == 2 || P == 5) {
		REP(i, N) {
			if ((S[i] - '0') % P == 0) {
				ans += i + 1;
			}
		}
	}
    else {
        md[0]++;
		Mint num(0, P);
		REP(i, N) {
            num += Mint(S[N - i - 1] - '0', P)* Mint(10, P).pow(i);
			md[num.v]++;
		}

        for (auto& x : md) {
            ans += (x * (x - 1) / 2);
        }
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
module Main where
import Data.Char
int = read :: String -> Int
getWord :: IO String
getWord = do
  c <- getChar
  if isSpace c
  then
    return []
  else do
    ws <- getWord
    return (c:ws)
getInt = fmap int getWord
replace pred a = map (\x -> if pred x then a else x)

main = interact $ printer . solver . parser
parser = int
printer = unlines . (:[]) . show

solver = flip div 3


Measured memory_bytes: 508
#include <bits/stdc++.h>
#include <boost/range.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>
using namespace std;
constexpr char nl = '\n';
using ll = long long;
using boost::irange;
namespace rng { using namespace boost; using namespace boost::range; }
namespace adp { using namespace boost::adaptors; }

struct init_ { init_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } init_;

template<class C> auto operator>>(istream& in, C& c) -> typename enable_if<!is_void<decltype(c.begin())>::value && !is_same<C, string>::value, istream&>::type {
    for (auto& v : c) { in >> v; } return in; }
template<class C> auto operator<<(ostream& out, const C& c) -> typename enable_if<!is_void<decltype(c.begin())>::value && !is_same<C, string>::value, ostream&>::type {
    int i = 0; for (const auto& v : c) { if (i++) { out << ' '; } out << v; } return out; }
template<size_t N, class T, class R> using when_last = typename enable_if<N == tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N, class T, class R> using when_init = typename enable_if<N != tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_last<N, T, istream&> { return in >> get<N>(t); }
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_init<N, T, istream&> { return operator>><N + 1>(in >> get<N>(t), forward<T>(t)); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_last<N, T, ostream&> { return out << get<N>(t); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_init<N, T, ostream&> { return operator<<<N + 1>(out << get<N>(t) << ' ', t); }

#ifdef LOCAL
constexpr auto color_s_ = "\033[2m\033[33m", color_e_ = "\033[0m";
template<class T> void trace_(const T& v) { cerr << v; }
template<class T> void trace_(const vector<vector<T>>& m) { cerr << "\n"; for (const auto& v : m) { trace_(v); cerr << "\n"; } }
template<class T> void trace_(const char* s, const T& v) { cerr << color_s_ << s << "="; trace_(v); cerr << color_e_ << "\n"; cerr.flush(); }
template<class T, class... Ts> void trace_(const char* s, const T& v, const Ts&... vs) { cerr << color_s_; for (; *s != ','; ++s) { cerr << *s; } cerr << "="; trace_(v); cerr << ","; trace_(++s, vs...); }
#define TRACE(...) trace_(#__VA_ARGS__, __VA_ARGS__)
#else
#define TRACE(...)
#endif

int main() {
    ll x;
    cin >> x;
    map<ll, ll> fs;
    ll i = 0;
    for (;;) {
        ll f = i * i * i * i * i;
        if (f > (1ll<<60)) {
            break;
        }
        fs.emplace(f, i);
        i++;
    }
    TRACE(fs.size());
    for (auto [fa, a] : fs) {
        auto it = fs.find(x - fa);
        if (it != fs.end()) {
            cout << a << " " << -(it->second) << nl;
            return 0;
        }
        it = fs.find(x + fa);
        if (it != fs.end()) {
            cout << it->second << " " << a << nl;
            return 0;
        }
    }
}


Measured memory_bytes: 3900
#include<stdio.h>

int arr[500000];

int main(){
    int N,i,j,n;
    while(~scanf("%d",&N)){
        for(i = 0; i < N; i++)
            arr[i] = 0;
        for(i = j = 0; i < N; i++){
            scanf("%d",&n);
            arr[n-1] = i+1;
            for(;j < N && arr[j];j++)
                printf("%d ",arr[j]);
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 1152
n, m = map(int, input().split())
mod = 10 ** 9 + 7


def n_factorial_mod(n, mod):
    ret = 1
    while n != 1:
        ret = ret * n % mod
        n -= 1
    return ret


if abs(n - m) > 1:
    print(0)
elif abs(n - m) == 1:
    print(n_factorial_mod(n, mod) * n_factorial_mod(m, mod) % mod)
else:
    print(2 * n_factorial_mod(n, mod) * n_factorial_mod(m, mod) % mod)

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

int main(){
    int N, Y; cin >> N >> Y;
    int judge = 1;
    for(int x = 0; 10000*x <= Y; ++x){
        for(int y = 0; 10000*x +5000*y <= Y; ++y){
            if(10000*x + 5000*y + 1000*(N-x-y) == Y){
                cout << x << " " << y << " " << N - x - y << endl;
                judge = 0;
                break;
            }
        }
        if(judge == 0) break;
    }
    if(judge) cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
txt = input()
N = txt.split("RL")
#print(N)
for i in range(len(N)):
  for j in range(len(N[i])):
    if i == len(N)-1 and j == len(N[i])-1:
      print("0")
    else:
      print("0",end=" ")
  if i < len(N)-1:
    print(1+N[i].count("R")//2+N[i+1].count("L")//2+N[i+1].count("L")%2,end=" ")
    print(1+N[i].count("R")//2+N[i].count("R")%2+N[i+1].count("L")//2,end=" ")

Measured memory_bytes: 57048
using System;

namespace _0588
{
    class Program
    {
        static void Main(string[] args)
        {
            int output = int.Parse(Console.ReadLine());
            while (true)
            {
                string now = Console.ReadLine();
                if (now == "+")
                {
                    output += int.Parse(Console.ReadLine());
                }
                else if (now == "-")
                {
                    output -= int.Parse(Console.ReadLine());
                }
                else if (now == "*")
                {
                    output *= int.Parse(Console.ReadLine());
                }
                else if (now == "/")
                {
                    output /= int.Parse(Console.ReadLine());
                }
                else if (now == "=")
                {
                    Console.WriteLine(output);
                    break;
                }
            }
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 9080
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		String str = s.next();

		for (int i = 0; i < str.length(); i++) {
			int count = 0;
			for (int j = 0; j < str.length(); j++) {
				if (str.charAt(i) == str.charAt(j)) {
					count++;
				}
			}
			if (count % 2 != 0) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}
}

Measured memory_bytes: 9420
#include <cstdio>
#include <utility>
#include <queue>
using namespace std;
int i,N,L,t,tr[100002],s,u;
int main(){
	typedef pair<int,int>pii;
	priority_queue<pii> qu;
	
	scanf("%d%d",&N,&L);
	for(;i++<N;)scanf("%d",tr+i);

	for(i=0;i++<N;)
		if(tr[i]>tr[i-1]&tr[i]>tr[i+1]){
			qu.push(pii(tr[i]-L,i));
			tr[i]=L;
		}

	while(!qu.empty()){
		pii p=qu.top();
		qu.pop();
		
		t=p.first;
		tr[s=p.second]=0;
		
		u=tr[s-1];
		if(u&&u!=L&&u>tr[s-2]){
			qu.push(pii(t-L+u,s-1));
			tr[s-1]=L;
		}
		u = tr[s+1];
		if(u&&u!=L&&u>tr[s+2]){
			qu.push(pii(t-L+u,s+1));
			tr[s+1]=L;
		}
	}
	printf("%d\n",-t);
}

Measured memory_bytes: 0
def main():
    n = int(input())
    a = list(map(int, input().split()))

    for i in range(n):
        for j in range(i + 1, n):
            b = [k for k in a]
            b[i], b[j] = b[j], b[i]
            if b == [k for k in range(1, n + 1)]:
                print("YES")
                return

    print("YES" if a == [k for k in range(1, n + 1)] else "NO")

main()

Measured memory_bytes: 3060
import java.util.Scanner;

//Pi is Three
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			double R = sc.nextDouble();
			if(R==0)break;
			int n = 1, d = 1;
			double min = 1<<29;
			int an = 0, ad = 1<<29;
			while(d<=ad){
				double r = Math.PI-n*1.0/d;
				double e = Math.abs(r);
				if(e<=R&&e<min){
					min = e; an = n; ad = d;
				}
				if(r<0)d++;
				else n++;
			}
			System.out.println(an+"/"+ad);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
import java.util.Scanner;

public class Main {
    public static void main(String[] args){

        Scanner sc =new Scanner(System.in);

        int K = sc.nextInt();
        int N =0;
          for (int i =0; i<K; i++){
            for (int j=0; j<K; j++){
              if ((i % 2 ==0 && j % 2 !=0)  || (j % 2 == 0 && i % 2 != 0)){
                N += 1;
              }
            }
          }
            System.out.println(N / 2);

    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define MAX_V 2050
#define int long long
int MOD=1000000007;
int V;
vector<int> G[MAX_V],rG[MAX_V],nG[MAX_V],vs,kv[MAX_V];
bool used[MAX_V];
int cmp[MAX_V];
void add_edge(int from,int to){
  G[from].push_back(to);
  rG[to].push_back(from);
}
void dfs(int v){
  used[v]=1;
  for(int i=0;i<(int)G[v].size();i++){
    if(!used[G[v][i]]) dfs(G[v][i]);
  }
  vs.push_back(v);
}
void rdfs(int v,int k){
  used[v]=1;
  cmp[v]=k;
  kv[k].push_back(v);
  for(int i=0;i<(int)rG[v].size();i++){
    if(!used[rG[v][i]]) rdfs(rG[v][i],k);
  }
}
int dfs2(int v,int f){
  int res=0,tmp=1;
  if(!f){
    for(int i=0;i<(int)nG[v].size();i++) tmp=(tmp*dfs2(nG[v][i],0))%MOD;
    res=tmp;tmp=1;
  }
  for(int i=0;i<(int)nG[v].size();i++) tmp=(tmp*dfs2(nG[v][i],1))%MOD;
  //cout<<v<<":"<<f<<"/"<<res+tmp<<endl;
  return (res+tmp)%MOD;
}
int scc(){
  memset(used,0,sizeof(used));
  vs.clear();
  for(int v=0;v<V;v++){
    if(!used[v]) dfs(v);
  }
  memset(used,0,sizeof(used));
  int k=0;
  for(int i=vs.size()-1;i>=0;i--){
    if(!used[vs[i]]) rdfs(vs[i],k++);
  }
  memset(used,0,sizeof(used));
  int ans=1;
  for(int i=0;i<k;i++){
    for(int j=0;j<(int)kv[i].size();j++){
      for(int l=0;l<(int)rG[kv[i][j]].size();l++){
	if(i!=cmp[rG[kv[i][j]][l]]){
	  nG[i].push_back(cmp[rG[kv[i][j]][l]]);
	  used[cmp[rG[kv[i][j]][l]]]=1;
	}
      }
    }
  }
  for(int i=0;i<V;i++){
    if(used[cmp[i]]) continue;
    //cout<<i<<":"<<ans<<endl;
    used[cmp[i]]=1;
    ans=(ans*dfs2(cmp[i],0))%MOD;
  }
  return ans;
}
signed main(){
  int n,m;
  cin>>n>>m;
  V=n;
  for(int i=0;i<m;i++){
    int s,d;
    cin>>s>>d;
    add_edge(s-1,d-1);
  }
  cout<<scc()<<endl;
  return 0;
}

Measured memory_bytes: 3492
#include <bits/stdc++.h>
using namespace std;
int main(){
    int i,n,ABC=0;
    cin>>n;
    char s[n];
    for(i=0;i<n;i++)cin>>s[i];
    for(i=0;i<n-2;i++){
    	if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C')ABC++;
	}
	cout<<ABC;
	return 0;
}

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

int main(){
    int n, t, m = 0;
    int a[100] = {};
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    int flag = 1;

    while(flag){
        flag = 0;
        for (int j = n-1; j > 0; j--){
            if (a[j] < a[j-1]){
                t = a[j];
                a[j] = a[j-1];
                a[j-1] = t;
                flag = 1;
                m++;
            }
        }
    }
    for (int k = 0; k < n; k++){
        cout << a[k];
        if (k != n-1) cout << " "; 
    }
    cout << "\n";
    cout << m << endl;
    return 0;

}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    int n;
    cin >> n;
    ll tmp = 1;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        if (a % 2 == 0)
            tmp *= 2;
        else
            tmp *= 1;
    }
    ll ans = pow(3, n) - tmp;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <cstdarg>
#include <cstdlib>
#include <string>

#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

int main(int argc, char const *argv[]) {
    int N, W;
    cin >> N >> W;
    int v[N], w[N];
    for (int i = 0; i < N; i ++) {
        cin >> v[i] >> w[i];
    }

    int dp[N + 1][W + 1];
    memset(dp[0], 0, sizeof(dp[0]));
    for (int i = 0; i < N; i ++) {
        for (int j = 0; j <= W; j ++) {
            if (j < w[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = max(
                    dp[i][j],
                    dp[i + 1][j-w[i]] + v[i]
                );
            }
        }
    }
    cout << dp[N][W] << endl;
    return 0;
}


Measured memory_bytes: 7020
n = int(input())
A = list(map(int, input().split()))

MOD = 10**9 + 7

dig = 60
Abn = [[0]*dig for _ in range(n)]

b0 = [0]*dig
b1 = [0]*dig
for i in range(n):
  for j in range(dig):
    if A[i]>>j&1:
      b1[j] += 1
    else:
      b0[j] += 1
      
pow2 = [pow(2, i, MOD) for i in range(dig)]

ans = 0
for i in range(dig):
  ans += b1[i]*b0[i]*pow2[i]%MOD
  
print(ans%MOD)

Measured memory_bytes: 202572
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 

def main():
    n,m = inpm()
    x = inpl()
    y = inpl()
    X = 0
    Y = 0
    cntX, cntY = n-1, m-1
    for i in range(n-1,-1,-1):
        X += x[i]*cntX
        X %= mod
        cntX -= 2
    for i in range(m-1,-1,-1):
        Y += y[i]*cntY
        Y %= mod
        cntY -= 2
    print((X*Y)%mod)


    
if __name__ == "__main__":
    main()

Measured memory_bytes: 81512
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define repi(i,n,init) for(ll i=init;i<(n);i++)

int main()
{
    int a,p;
    cin >> a >> p;
    cout <<( a * 3 + p )/ 2 << endl;
    return 0;
}

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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
	int n;
	cin >> n;
	int deck[2*n];
	REP(i, 2*n) deck[i] = i+1;
	int m;
	cin >> m;
	REP(i, m){
		int k;
		cin >> k;
		int newdeck[2*n];
		if(k == 0){
			REP(i, n) newdeck[2*i] = deck[i];
			REP(i, n) newdeck[2*i+1] = deck[i+n];
		}
		else{
			REP(i, 2*n-k) newdeck[i] = deck[k+i];
			REP(i, k) newdeck[2*n-k+i] = deck[i];
		}
		REP(i, 2*n) deck[i] = newdeck[i];
	}
	REP(i, 2*n) cout << deck[i] << endl;
	return 0;
} 


Measured memory_bytes: 3100
#include"bits/stdc++.h"
using namespace std;

int main() {
	char b;
	cin >> b;
	if (b == 'A') {
		putchar('T');
	}
	else if (b == 'T') {
		putchar('A');
	}
	else if (b == 'C') {
		putchar('G');
	}
	else {
		putchar('C');
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int main(){
    int N;cin>>N;
    vector<bool> b(10,false);
    int a,free=0;
    for(int i=0;i<N;i++){
        cin>>a;
        if(1<=a && a<400)    b[0]=true;
        if(400<=a && a<800)  b[1]=true;
        if(800<=a && a<1200) b[2]=true;
        if(1200<=a && a<1600)b[3]=true;
        if(1600<=a && a<2000)b[4]=true;
        if(2000<=a && a<2400)b[5]=true;
        if(2400<=a && a<2800)b[6]=true;
        if(2800<=a && a<3200)b[7]=true;
        if(3200<=a)          free++;
    }
    int B=0;
    for(int i=0;i<=7;i++)if(b[i])B++;
    cout<<max(B,1)<<" "<<B+free<<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())

a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

dpa = [0] * N
dpb = [0] * N
dpc = [0] * N

dpa[0] = a[0]
dpb[0] = b[0]
dpc[0] = c[0]
for i in range(1, N):
    dpa[i] = a[i] + max(dpb[i - 1], dpc[i - 1])
    dpb[i] = b[i] + max(dpc[i - 1], dpa[i - 1])
    dpc[i] = c[i] + max(dpa[i - 1], dpb[i - 1])
print(max(dpa[N - 1], dpb[N - 1], dpc[N - 1]))

Measured memory_bytes: 26740
while True:
    h, w = map(int, input().split())

    if h == 0 and w == 0:
        break
    for i in range(h):
        for j in range(w):
            if ((i % 2 == 0 and j % 2 == 0) or (i % 2 == 1 and j % 2 == 1)):
                print('#', end='')
            else:
                print('.', end='')
        print()
    print()





Measured memory_bytes: 7008
#if _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#ifndef ONLINE_JUDGE 
const bool DEBUG = true;
#else
const bool DEBUG = false;
#endif

// Reads a 1D vector
template <class T>
void read1d(vector<T> & arg) {
	const int l = arg.size();
	for (int i = 0; i < l; ++i) cin >> arg[i];
}

void read() {}
// Reads arbitrary values
template <class T1, class... T2>
void read(T1& var1, T2&... var2) { cin >> var1; read(var2...); }



void pln() { cout << (DEBUG ? "]\n" : "\n"); }
template <class T1, class... T2>
void pln(const T1& var1, const T2& ... var2) { cout << var1 << " "; pln(var2...); }

// Prints arbitrary values and goes to next line
template <class T1, class... T2>
constexpr void print(const T1& var1, const T2& ... var2) { cout << (DEBUG ? " [ " : ""); pln(var1, var2...); }

// Prints arbitrary values and goes to next line ONLY IF IN DEBUG MODE
template <class T1, class... T2>
constexpr void debug(const T1& var1, const T2& ... var2) { if (!DEBUG) return;  cout << " debug : [ "; pln(var1, var2...); }





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


#define all(x) begin(x), end(x)

const bool MULTIPLE_TEST_CASES = 0;


void exec() 
{
	int n;
	cin >> n;

	int ans = 0;
	for (int i = 1; i < n; ++i) {
		int x = n / i;
		if (n % i == 0) --x;
		ans += x;
	}

	cout << ans;
}

















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

	if (!MULTIPLE_TEST_CASES)
		exec();
	else {
		int n;
		cin >> n;

		while (n--)
			exec();
	}

    return 0;
}

Measured memory_bytes: 3668
#include "bits/stdc++.h"
using namespace std;

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 1e18 * 4;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	int n, x, i;
	cin >> n >> x;
	if (n == 1) {
		cout << 1 << endl << 1 << endl;
		return 0;
	}
	if (x == 1 || x == 2 * n - 1) {
		cout << "No" << endl;
		return 0;
	}
	else {
		cout << "Yes" << endl;
	}
	if (n == 2) {
		cout << 1 << endl << 2 << endl << 3 << endl;
		return 0;
	}
	if (x == 2 * n - 2) {
		for (i = 1; i <= n - 2; i++) {
			cout << i << endl;
		}
		cout << x - 1 << endl;
		cout << x << endl;
		cout << x + 1 << endl;
		cout << x - 2 << endl;
		for (i = n - 1; i < 2 * n - 4; i++) {
			cout << i << endl;
		}
	}
	else {
		vi a(2 * n - 1);
		for (i = 0; i < 2 * n - 1; i++) {
			a[i] = i + 1;
		}
		//DEBUG_VEC(a);
		for (i = 0; i < 4; i++) {
			a.erase(a.begin() + x - 2);
		}
		a.resize(2 * n - 5);
		//DEBUG_VEC(a);
		for (i = 0; i < n - 2; i++) {
			cout << a[i] << endl;
		}
		cout << x + 1 << endl << x << endl << x - 1 << endl << x + 2 << endl;
		for (i = n - 2; i < a.size(); i++) {
			cout << a[i] << endl;
		}
		
	}
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

int binpow(int a, int b) {
    if (b == 0)
    {
        return 1;
    }
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
    {
        return res * a;
    }
    return res;
}

ll gcd(ll a,ll b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}
string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    if (a==b&&b==c)
    {
        cout<<"No";return 0;
    }
    if (a==b||b==c||a==c)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}

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

int main() {
    ll k, a, b;
    cin >> k >> a >> b;
    if(b-a<=2 || k-1<a){
        cout << k+1 << endl;
    }
    else{
        ll ans = 0;
        k -= a-1;
        ans += (b-a)*(k/2)+a;
        ans += k%2;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#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;

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<int, int> pi;
#define oset tree<pi, null_type,greater<pi>, rb_tree_tag,tree_order_statistics_node_update>

#define N 105
vector<string> gr;
int dp[N][N];

int main()
{
    int h, w;
    cin >> h >> w;
    for(int i=0; i<h; i++){
        string s;
        cin >> s;
        gr.push_back(s);
    }
    if(gr[0][0] == '#') dp[0][0] = 1;

    for(int i=1; i<w; i++){
        if(gr[0][i] == '#' && gr[0][i-1] == '.'){
            dp[0][i] = dp[0][i-1]+1;
        }
        else{
            dp[0][i] = dp[0][i-1];
        }
    }
    for(int i=1; i<h; i++){
        if(gr[i][0] == '#' && gr[i-1][0] == '.'){
            dp[i][0] = dp[i-1][0]+1;
        }
        else{
            dp[i][0] = dp[i-1][0];
        }
    }
    for(int i=1; i<h; i++){
        for(int j=1; j<w; j++){
            if(gr[i][j] == '#'){
                if(gr[i-1][j] == '.' && gr[i][j-1] == '.'){
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1;
                }
                else if(gr[i-1][j] == '.'){
                    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]);
                }
                else if(gr[i][j-1] == '.'){
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]+1);
                }
                else{
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
                }
            }
            else {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << dp[h-1][w-1] << "\n";

    return 0;
}


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i=a;i<b;i++)
#define REP(i, n) FOR(i, 0, n)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((b)=max((a),(b)))

void next(int &y, int &m, int &d){
	if(m==12 && d==31){
		y++;
		m=d=1;
		return;
	}else if(m==2){
		if(y%4==0 && y%100!=0 || y%400==0){
			if(d==29){
				m++;
				d=1;
				return;
			}
		}else{
			if(d==28){
				m++;
				d=1;
				return;
			}
		}
	}else if(m==4 || m==6 || m==9 || m==11){
		if(d==30){
			m++;
			d=1;
			return;
		}
	}else{
		if(d==31){
			m++;
			d=1;
			return;
		}
	}
	d++;
}
int pls(int bm, int bd, int y, int m, int d){
	if(bm==2 && bd==29){
		if(y%4==0 && y%100!=0 || y%400==0){
		}else{
			if(m==3 && d==1) return 1;
		}
	}
	if(bm==m && bd==d) return 1;
	else return 0;
}
int main(){
	int a,b,c,d,e,f;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
	int p,q,r,x,y;
aaa:
	p=a; q=b; r=c;
	x=0; y=0;
	while(p!=d || q!=e || r!=f){
		if(p>d){
			swap(a,d);
			swap(b,e);
			swap(c,f);
			goto aaa;
		}
		next(p,q,r);
		x+=pls(b,c,p,q,r);
	}
	int ans=0;
	REP(i, 10000){
		next(p,q,r);
		x+=pls(b,c,p,q,r);
		y+=pls(e,f,p,q,r);
		LAR(ans,x-y);
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 3220
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val D = sc.nextInt()
    val r = D match {
      case 25 => "Christmas"
      case 24 => "Christmas Eve"
      case 23 => "Christmas Eve Eve"
      case 22 => "Christmas Eve Eve Eve"
    }
    println(r)
  }

}



Measured memory_bytes: 25380
#include <iostream>

using namespace std;

int main() {
    size_t r, d, x;
    cin >> r >> d >> x;
    size_t xs[11];
    xs[0] = x;
    for (size_t i = 1; i < 11; ++i)
        xs[i] = r * xs[i - 1] - d;
    for (size_t i = 1; i < 11; ++i)
        cout << xs[i] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n,pr[3000],cnt,ans;ll a[maxn];
map<ll,ll> A,B;bool mk[3000];
void sieve(int n){
    memset(mk,1,sizeof(mk));mk[1]=0;
    rep(i,2,n){
        if(mk[i]) pr[++cnt]=i;
        for(int j=1;j<=cnt&&i*pr[j]<=n;++j){
            mk[i*pr[j]]=0;
            if(i%pr[j]==0) break;
        }
    }
}
int main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%lld",&a[i]);
    sieve(2200);
    rep(i,1,n){
        ll t1=1,t2=1;
        rep(j,1,cnt) if(a[i]%pr[j]==0){
            int dsy=0;
            while(a[i]%pr[j]==0) a[i]/=pr[j],++dsy;
            dsy%=3;
            rep(i,1,dsy) t1*=pr[j];
            rep(i,1,(3-dsy)%3) t2*=pr[j];
        }
        ll o=(ll)sqrt(a[i]+0.5);
        if(o*o==a[i]) t1*=o*o,t2*=o;
        else t1*=a[i],t2*=a[i]*a[i];
        ++A[t1];B[t1]=t2;
        //printf("%lld %lld\n",t1,t2);
    }
    for(auto x:A){
        if(x.fi==1) A.erase(1),ans++;
        else ans+=max(x.se,A[B[x.fi]]),A.erase(B[x.fi]),A.erase(x.fi);
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 13568
#include<stdio.h>
int main()
{
    double n,sum=0;
    int N,i;
    scanf("%d",&N);
    for(i=1;i<=N;i++)
    {
        scanf("%lf",&n);
         sum=sum+(1.0/n);
    }

    printf("%lf\n",1/sum);
    return 0;
}


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

typedef long long ll;
 string convertToTitle(ll n) {

    string res;

    char tmp;

    while(n){

        n -= 1;

        tmp = 'a' + n % 26;

        res = tmp + res;

        n /= 26;

    }

    return res;

}
int main() {
	ll n;
	cin >> n;
	cout << convertToTitle(n) << endl;

	return 0;
}

Measured memory_bytes: 3600
from math import gcd

k = int(input())
l = [[[0] * (k + 1) for i in range(k + 1)] for j in range(k + 1)]
ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            mn, mx = min(a, b, c), max(a, b, c)
            mi = a + b + c - mn - mx
            if l[a][b][c]:
                ans += l[a][b][c]
                continue
            else:
                ans += gcd(gcd(a, b), c)
print(ans)

Measured memory_bytes: 140988
import bisect
N = int(input())
l = list(map(int, input().split()))
ans = 0
tmp = 0
l.sort()
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        tmp = bisect.bisect_left(l, l[i] + l[j])
        ans += tmp - j - 1

print(ans)


Measured memory_bytes: 42972
#include <stdio.h>

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

    int v[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = i; j >= 0; j--) {
            if (v[j] < v[j - 1]) {
                int tmp = v[j];
                v[j] = v[j - 1];
                v[j - 1] = tmp;
            } else {
                continue;
            }
        }
    }

    float nv = v[0] / 1.0;
    for (int i = 1; i < n; i++){
        nv = (nv + v[i]) / 2;
    }

    printf("%f\n", nv);

    return 0;
}

Measured memory_bytes: 128
import itertools
N = int(input())
e = [0]*(N+1)
for i in range(2,N+1):
  cur = i
  for j in range(2,i+1):
    while cur%j==0:
      e[j] += 1
      cur = cur//j

ans = 0
for x in e :
  if x>=74:
    ans +=1
for i in range(N+1):
  for j in range(i+1,N+1):
    for k in range(j+1,N+1):
        for a, b, c in [[4, 4, 2], [4, 2, 4], [2, 4, 4]]:
          if e[i] >= a and e[j] >= b and e[k] >= c:
            ans += 1
for (x, y) in itertools.combinations(e, 2):
  #print(x, y)
  for a, b in [(24, 2), (14, 4), (4, 14), (2, 24)]:
    if x >= a and y >= b:
      ans += 1

print(ans)

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

int main() {
  char ctmp;
  vector<int> S;
  while (cin >> ctmp) {
    if (ctmp == 'B')
      S.push_back(1);
    else
      S.push_back(0);
  }
  int last = S.size() - 1;
  long long nr_of_zero = 0;
  long long answer = 0;
  for (int i = last; i >= 0; --i) {
    if (S[i] == 0) {
      ++nr_of_zero;
    } else {
      answer += nr_of_zero;
    }
  }
  cout << answer << endl;
  return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LLMAX (1ll << 60) - 1
#define INTMAX (1 << 30) - 1
#define MOD 1000000007 
#define NMAX 1000*100+1

#define numberOfSetBits(S) __builtin_popcount(S) // __builtin_popcountl(S) __builtin_popcountll(S)
#define MSET(x,y) memset(x,y,sizeof(x))
#define gcd(a,b) __gcd(a,b)
#define all(x)  x.begin(),x.end()
#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define print(x)    for(auto it=x.begin();it!=x.end();it++) cout<<*it<<' '; cout<<endl;
#define printii(x)  for(auto it=x.begin();it!=x.end();it++) cout<<*it.F<<' '<<*it.S<<'\t';  cout<<endl;
#define in(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}

#define vi vector<ll>
#define vvi vector<vi>
#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vii vector<ii>
#define viii vector<pair<ii,ll>>
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define mc(a,b,c) mp(mp(a,b),c)
vi ans;

ll power(ll x, unsigned ll y, unsigned ll m=MOD) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
  
    return (y%2 == 0)? p : (x * p) % m; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,x,t,m,k;
    cin>>n>>k;
    ans.resize(k+1);
    for(ll i=k;i>=1;i--){
    	ans[i] = power(k/i, n);
        for(int j=2*i;j<=k;j+=i){
            ans[i]-=ans[j];
            ans[i]%=MOD;
        }
    }
    ll s = 0;
    for(ll i=1;i<=k;i++){
        s+=(ans[i]*i)%MOD;
        s%=MOD;
    }
    if(s<0){
    	s+=MOD;
    }
    cout<<s;
    
    

    return 0;
}







Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int k, q;
    cin >> k >> q;
    vi d(k);
    cin >> d;
    rep(qi, q) {
        int n, x, m;
        cin >> n >> x >> m;
        ll eq = 0, last = x;
        rep(i, k) {
            ll num = (n - 1 - i + k - 1) / k;
            last += (d[i] % m) * num;
            if (d[i] % m == 0) eq += num;
        }
        ll ans = (n - 1) - (last / m - x / m) - eq;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define W 100010
using namespace std;
typedef long long ll;
ll w,mp[W];
ll l[W],r[W];
 
int main(){
  cin>>w;
   
  for(int i=0;i<w+2;i++)l[i]=r[i]=-10000000;
  l[0]=0;
  r[w+1]=0;
 
  for(int i=1;i<=w;i++) {
    cin>>mp[i];
    if(mp[i]<0) l[i]=r[i]=mp[i];
    if(mp[i]==0)l[i]=r[i]=-10000000;
  }
  w+=2;
   
  for(int i=1;i<w;i++){
    int j=w-i-1;
    if(mp[i]!=0)l[i]=max(l[i],l[i-1]+1);
    if(mp[j]!=0)r[j]=max(r[j],r[j+1]+1);
  }
 
  ll ans=0;
  for(int i=0;i<=w;i++){
    if(mp[i]<=0)continue;
    ll a=l[i]<0? min(mp[i],abs(l[i])):0;  
    ll b=r[i]<0? min(mp[i],abs(r[i])):0;   
    ans+=max(0LL,max(a,b));
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 5444
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#include <iostream>
#include <vector>

using namespace std;

struct UnionFind
{
    vector<int> par;

    void init(int N) { par.assign(N, -1); }

    int root(int x)
    {
        if (par[x] < 0) { return x; }              // x が根
        else { return par[x] = root(par[x]); }     // 経路短縮
    }

    bool same(int x, int y) { return (root(x) == root(y)); }

    void unite(int x, int y)
    {
        int xx = root(x);
        int yy = root(y);

        if (xx == yy) { return; }

        if (par[xx] < par[yy])
        {
            par[xx] += par[yy];
            par[yy] = xx;
        }
        else
        {
            par[yy] += par[xx];
            par[xx] = yy;
        }
    }

    int size(int x)
    {
        return -par[root(x)];
    }
};


int main()
{
    int N, M;
    UnionFind uf;

    cin >> N >> M;
    uf.init(N);
    for (int i = 0; i < M; ++i) 
    { 
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        uf.unite(a, b);
    }

    cout << (-*min_element(uf.par.begin(), uf.par.end())) << endl;


    return 0;
}


Measured memory_bytes: 3996
#include <iostream>
#include <vector>
#include <functional>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)

template<typename T>struct SegTree {
  private:
    using F = function<T(T,T)>;
    int n;
    vector<T> node;
    const F f;
    const T init;
  public:
    SegTree(int size, T init, const F f) : init(init), f(f) {
      n = 1;
      while (n < size) n *= 2;
      node.resize(2*n-1, init);
    }
    void update(int index, T value) {
      index = n - 1 + index;
      node[index] = value;
      while (index != 0) {
        index = (index-1) / 2;
        node[index] = f(node[2*index+1], node[2*index+2]);
      }
    }
    T query(int left, int right, int k = 0, int l = 0, int r = -1) {
      if (r < 0) r = n;
      if (r <= left || right <= l) return init;
      if (left <= l && r <= right) return node[k];
      return f(query(left, right, 2*k+1, l, (l+r)/2), query(left, right, 2*k+2, (l+r)/2, r));
    }
};

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

  SegTree<int> T(N, 0, [](int a, int b){return a | b;});

  rep(i, N) {
    char s; cin >> s;
    T.update(i, 1 << ((int)(s - 'a')));
  }
  int Q; cin >> Q;


  rep(i, Q) {
    int q; cin >> q;
    if (q == 1) {
      int n; char c;
      cin >> n >> c;
      --n;
      T.update(n, 1 << (c - 'a'));
    } else {
      int l, r;
      cin >> l >> r;
      --l, --r;
      cout << __builtin_popcount(T.query(l, r +1)) << endl;
    }
  }

  return 0;
}


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

int main(){
  string s;
  cin >> s;
  //cout << s <<endl;
  int tmp=0;
  int ans=0;
  
  for(int i=0;i<s.size();i++){
    if(s.at(i) == 'A'||s.at(i) == 'C'||s.at(i) == 'G'||s.at(i) == 'T'){
      ans++;
    }else{
      if(ans > tmp){
      tmp = ans;
      }
      ans = 0;
    }
  }
  
  cout << max(tmp,ans) << endl;

}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll add(ll a, ll b){return(a+b)%mod;}
int n,m,dp[100005];
set<int> s;

int main(void){
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int b;
        cin >> b;
        s.insert(b);
    }
    dp[0]=1;
    for(int i=0;i<n;i++){
        if(s.count(i+1)==0) dp[i+1]=add(dp[i],dp[i+1]);
        if(s.count(i+2)==0) dp[i+2]=add(dp[i],dp[i+2]);
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 4992