akhauriyash/Code-Regression huggingface dataset:
/*
ID: rchalam1
LANG: C++14
TASK:
*/
// For train.usaco.org, fill the template above.

// Competitive Coding Template

// GCC OPTIMIAZTION FLAGS
#ifdef ONLINE_JUDGE
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#endif

#include <bits/stdc++.h>

/*
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
*/
// All Includes for Competitive Coding Template

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

using vi = std::vector<int>;
using vll = std::vector<long long>;
using vull = std::vector<unsigned long long>;

#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (auto i = (a); i >= (b); --i)
#define R0F(i, a) ROF(i, a, 0)
#define ITR(a, x) for (auto& a: x)

#define FSRT(set) sort((set).begin(),(set).end())
#define RSRT(set) sort((set).rbegin(),(set).rend())
#define CSRT(set, function) sort((set).begin(),(set).end(), (function))
#define TRS(set) sort((set).begin(),(set).end(), greater<>())
#define REV(set) reverse((set).begin(),(set).end());

#define ALL(set) (set).begin(), (set).end()

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// For stdio, call setIO() or setIO("").
void setIO(std::ifstream &readFile, std::ofstream &writeFile, const std::string &name = "", bool stdIO = false)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	if(!name.empty() && !stdIO)
	{
		readFile.open(name + ".in");
		if(readFile.fail()) return;
		writeFile.open(name + ".out");
		std::cin.rdbuf(readFile.rdbuf());
		std::cout.rdbuf(writeFile.rdbuf());
	}
}

// To time program, create object Timer  to start timing, and call Timer.elapsed().
#include <chrono>

class Timer
{
	std::chrono::time_point<std::chrono::high_resolution_clock> m_beg;
public:
	Timer() : m_beg(std::chrono::high_resolution_clock::now())
	{}

	void reset()
	{ m_beg = std::chrono::high_resolution_clock::now(); }

	[[nodiscard]] long double elapsed() const
	{
		return std::chrono::duration_cast<std::chrono::duration<long double, std::ratio<1> >>(
				std::chrono::high_resolution_clock::now() - m_beg).count();
	}
};

// Defines datatype
using dt = int;
// Defines MAXN value
constexpr dt MAXN = 1e5 + 1;
// Defines Modulus
constexpr dt MOD = 1e9 + 7;
// Defines Floating Point Correction
constexpr long double EPS = 1e-9;

//*****
//START CODE BELOW
//*****

int main(int argc, char *argv[])
{
	static std::ifstream readFile;
	static std::ofstream writeFile;
	setIO(readFile, writeFile);
	string s, t;
	cin >> s >> t;
	for(int i = 0; i < s.size(); ++i)
	{
		string modified = s.substr(i, s.size() - i) + s.substr(0, i);
		if(modified == t) return cout << "Yes\n", 0;
	}
	cout << "No\n";
}

Measured memory_bytes: 3624
$n = gets.chomp.to_i
$ans = 0
$cur = 0
$n.times do |i|
  a = gets.split(" ")
  i0 = a[0].to_i
  i1 = a[1].to_i
  if i0 == i1 
    $cur += 1
  else
    if $cur > $ans 
      $ans = $cur 
    end
    $cur = 0
  end
end

if $cur > $ans 
  $ans = $cur 
end

if $ans > 2
  print "Yes"
else
  print "No"
end

Measured memory_bytes: 14372
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def string_to_number(a):
    return 1 << (ord(a) - 97)

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = string_to_number(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if not a & 1:
                res |= self.seg[a]
            if b & 1:
                res |= self.seg[b]
                b -= 2
            a >>= 1
            b -= 1
            b >>= 1
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    #print(seg.seg)

    Q = int(readline())
    q = map(str, read().split())
    for t, a, b in zip(*[iter(q)]*3):
        if t == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 47528
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int W[26]{};

int main() {
  string w;
  cin >> w;
  for (int i = 0; i < w.size(); ++i) {
    ++W[w[i] - 'a'];
  }
  for (int i = 0; i < 26; ++i) {
    if (W[i] % 2 != 0) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}

Measured memory_bytes: 3136
def answer(x, y):
    absX = abs(x)
    absY = abs(y)
    a = abs(absY - absX)
    # 0인 경우는 좀 다르게 취급된다
    if x == 0:
        if y > 0:
            return y
        else:
            return -y+1
    if y == 0:
        if x > 0:
            return 1+x
        else:
            return -x
        
    # 둘다 양수
    if (x > 0 and y > 0):
        if absX < absY:
            return y-x
        else:
            return 1+(x-y)+1
    if (x < 0 and y > 0):
        if absX < absY:
            return 1+(y+x)
        else:
            return -(x+y)+1
    if (x > 0 and y < 0):
        if absX < absY:
            return -(y+x)+1
        else:
            return 1+(x+y)
    if (x < 0 and y < 0):
        if absX < absY:
            return 1+(x-y)+1
        else:
            return y-x

x, y = map(int, input().split())
print(answer(x, y))

Measured memory_bytes: 3064
n,m = map(int,input().split())
if n == 1 and m == 1:
    ans = 1
elif n == 1 :
    ans = max(0,m - 2)
elif m == 1:
    ans = max(0,n - 2)
else:
    ans = (n - 2) * (m - 2)
print(ans)

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int n, m;
    cin >> n >> m;
    cout << (n - 1)*(m - 1) << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    
    int n;
    cin >> n;
    string ans = "No";
    for(int i=1;i<=9;i++){
        if(n %i == 0 && 1 <= n/i && n/i <= 9){
            ans = "Yes";
            // cout << i << endl;
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
void minimize(int * N, int digit, int min){
    int i;
    for(i = 0; i <= digit; i++){
        N[i] = min;
    }
}

void calc(int * N, int K, int * D, int digit, int digit_max, int * moveup, int min, int max){
    if(digit > 0 && N[digit] <= max) calc(N, K, D, digit-1, digit_max, moveup, min, max);
    N[digit] += *moveup;
    if(digit == digit_max && N[digit] == 0) return;
    if(N[digit] == 10) return;
    *moveup = 0;

    while(1){
        int D_loop = 0;
        for(; D_loop < K; D_loop++){
            if(N[digit] == D[D_loop]) break;
        }
        if(D_loop == K) return;
        
        N[digit]++;
        for(int i = 0; i < digit; i++){
            N[i] = min;
        }
        if(N[digit] == 10){
            *moveup = 1;
            N[digit] = min;
            return;
        }
    }
}


int main(void){
    int N_orig;
    int N_q = -1;
    int N[5] = {0, 0, 0, 0, 0};
    int K;
    int D[9] = {};
    int digit_max;
    int min = 0;
    int max = 9;
    int N_ans = 0;
    
    scanf("%d %d", &N_orig, &K);
    for(int i = 0; i < K; i++) scanf("%d", &D[i]);
    
    for(int i = 0; i < K; i++){
        if(D[i] == min) min++;
        if(D[K-(i+1)] == max) max--;
    }
    
    N_q = N_orig;
    for(digit_max = 0; N_q != 0; digit_max++){
        N[digit_max] = N_q % 10;
        N_q /= 10;
    }
    
    int moveup = 0;
    calc(N, K, D, digit_max, digit_max, &moveup, min, max);
    
    for(int i = 4; i >= 0; i--){
        N_ans *= 10;
        N_ans += N[i];
    }
    printf("%d", N_ans);
}


Measured memory_bytes: 128
N = int(input())
D, X = map(int, input().split())
A_list = [int(input()) for _ in range(N)]

count_chocolate_list = []

for i in range(N):
    k = 0
    chocolate_day_list = []

    while (k*A_list[i] + 1 <= D):
        chocolate_day_list.append(k*A_list[i] + 1)
        chocolate_count = len(chocolate_day_list)
        k += 1
        
    count_chocolate_list.append(chocolate_count)
        
    i += 1
    
ans = sum(count_chocolate_list) + X

print(ans)

Measured memory_bytes: 9112
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <map>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;


int main() {

    int N;
    cin >> N;
    if(N%10==3){
        cout << "bon" << endl;
    }else if(N%10==0||N%10==1||N%10==6||N%10==8){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }
    return 0;
}

Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);

vector<int> G[100005];
int ans,k,arr[100005];

int dfs(int u)
{
    int h=1;
    for(int v:G[u])
        h=max(h,dfs(v)+1);
    if(h>=k&&arr[u]!=1)
        ++ans,arr[u]=1,h=0;
    return h;
}

int main()
{
    IOS();
    int n;
    cin >> n >> k;
    for(int i=1;i<=n;++i)
        cin >> arr[i];
    if(arr[1]!=1) ++ans,arr[1]=1;
    for(int i=2;i<=n;++i)
        G[arr[i]].pb(i);
    dfs(1);
    cout << ans << "\n";
}

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

int main(){
	int shotoku[12];
	int l,m,n;
	int i,total;
	while(cin>>l,l){
		for(i=0;i<12;i++){
			cin>>m>>n;
			shotoku[i]=m-n;
		}
		total=0;
		for(i=0;i<12;i++){
			total+=shotoku[i];
			if(l<=total){
				cout<<i+1;
				break;
			}
		}
		if(i==12) cout<<"NA";
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1164
n,m = map(int,input().split())
drink = []
for i in range(n):
    a,b = map(int,input().split())
    drink.append((a,b))
drink.sort()
ans = 0
for i in range(n):
    if m == 0:
        break
    if m >= drink[i][1]:
        ans += drink[i][0] * drink[i][1]
        m -= drink[i][1]
    else:
        ans += m*drink[i][0]
        m = 0
print(ans)


Measured memory_bytes: 83220
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int idou = 0;
  int ans = 0;
  vector<int> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H.at(i);
  }
  for (int i = 0; i < N - 1; i++) {
    if (H.at(i) >= H.at(i + 1)) {
      idou++;
    }
    if (H.at(i) < H.at(i + 1)) {
      idou = 0;
    }
    if (ans < idou) {
      ans = idou;
    }
  }
  cout << ans << endl;
}

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

using namespace std;

int main(){
	typedef long long ll;
	ll n, k;
	cin>>n>>k;
	ll a[n];
	for(ll i = 0; i < n; i++){
		cin>>a[i];
	}
	sort(a, a+n);
	ll sum = 0;
	for(ll i = 0; i < n - k; i++){
		sum += a[i];
	}

	cout<<sum<<endl;

	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;cin>>N;
  int ans = INF;
  repeat(i,N){
    int A;cin>>A;
    int cnt=0;
    while(!(A&1)){
      cnt++;
      A>>=1;
    }
    ans = min(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)
func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

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

const mod = 1000000007

func main() {
	var s string
	fmt.Scan(&s)

	dp := make([][]int, len(s)+1)
	for i := 0; i < len(s)+1; i++ {
		dp[i] = make([]int, 13)
	}

	dp[0][0] = 1
	for i := 0; i < len(s); i++ {
		if string(s[i]) != "?" {
			digit,_ := strconv.Atoi(string(s[i]))
			for j := 0; j < 13; j++ {
				dp[i+1][(digit+j*10)%13] = dp[i][j]
			}
		} else {
			for d := 0; d < 10; d++ {
				for j := 0; j < 13; j++ {
					dp[i+1][(d+j*10)%13] += dp[i][j]
					dp[i+1][(d+j*10)%13] %= mod
				}
			}
		}
	}

	fmt.Println(dp[len(s)][5])
	
}


Measured memory_bytes: 14976
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;

int main(){
  ll n;
  cin >> n;
  ll a;
  ll b[60] = {0};
  rep(i,n){
    cin >> a;
    rep(j,60){
      if(a>>j  & 1) b[j]++;
    }
  }
  ll ans = 0;
  ll digit = 1;
  rep(i,60){
    // printf("%lld\n",b[i]);
    b[i] = b[i]*(n-b[i])%mod;
    digit %= mod;
    // printf("%lld %lld\n",b[i],digit );
    ans += digit*b[i]%mod;
    ans %= mod;
    digit *= 2;
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30);
const ll INFL = (1LL<<62);
const int MOD = 1000000007;
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> ll mod_pow(ll a, ll n, T mod) { mod=(ll)mod; ll res=1, p=a%mod; while(n){ if(n&1) res=res*p%mod; p=p*p%mod; n>>=1; } return res; }

int main() {
    double r;
    cin >> r;
    cout << fixed << setprecision(10);
    cout << r*r*M_PI << " " << 2*r*M_PI << endl;

    return 0;
}


Measured memory_bytes: 3276
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rep2(i,n) for(int i=1; i<=(n); ++i)
#define Sort(x) sort((x).begin(),(x).end())
#define Sort2(x) sort((x).begin(),(x).end(), greater<int>())
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main()
{
    int a; cin >> a;
    cout << a*a << endl;
}

/*
Ctrl+@ でコンソールを開け、以下で実行。
g++ code.cpp
./a.out

サンプルのダウンロードは oj d URL
テストは oj t
*/

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<fstream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<map>
#include<iomanip>
#include<cassert>
#include<complex>
#include<functional>
#include<list>
#include<cmath>
#include<stack>
#include<assert.h>
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define F first
#define S second
using namespace std;
LL h[100010];
int main(){
  int n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++)
    cin>>h[i];
  sort(h,h+n);
  LL ans=1000000007;
  for(int i=0;i<=n-k;i++)
    ans=min(ans,h[i+k-1]-h[i]);
  cout<<ans;
  return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

template <typename QvQ> inline QvQ Min(QvQ a,QvQ b){if(a<b) return a;return b;}
template <typename QvQ> inline QvQ Max(QvQ a,QvQ b){if(a>b) return a;return b;}

#define inf 2147483647
#define dinf 0x3f3f3f3f
#define llinf 0x7f7f7f7f7f7f7f7f

#define ll long long
#define rei register int
#define inv inline void
#define ull unsigned long long
#define il inline

#define bl putchar(' ')
#define ed putchar('\n')
#define test cout<<"this:" 

#define read2(a,b) read(a),read(b)
#define write2(a,b) write(a),bl,write(b)
#define read3(a,b,c) read(a),read(b),read(c)
#define write3(a,b,c) write(a),bl,write(b),bl,write(c)

template <typename QvQ>inv read(QvQ &x){
    x=0;int f=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=x*f;
}
template <typename QvQ>inv write(QvQ x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+48);
}
#define maxn 250005
#define int ll
struct  edge{
    int to,next;
    edge(){}
    edge(const int &_to,const int &_next){ to=_to,next=_next; }
}e[maxn];
int head[maxn],k;

int stack[maxn],top;
bool vis[maxn],instack[maxn],inloop[maxn];
int n,m;

inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
inline void add(const int &u,const int &v){
    e[k]=edge(v,head[u]);
    head[u]=k++;
}
int ans[100005],cnt;
int maxx=100005,b[100005];
void dfs(int u)
{
    vis[u]=instack[u]=true,stack[++top]=u;
    for(register int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].to;
        if(!vis[v]) dfs(v);
        else if(instack[v])
        {
            int w,t=top;
            do
            {
                w=stack[t--],instack[w]=false,inloop[w]=true;
                ans[++cnt]=w;
            }while(w!=v);
            if(maxx>cnt)
            {
                maxx=cnt;
                for( int i=1;i<=cnt;++i) b[i]=ans[i];
            }
            cnt=0;
//            std::cout<<cnt<<std::endl;
//            for(int i=1;i<=cnt;++i) std::cout<<ans[i]<<std::endl;
          //  exit(0);
        }
    }
    instack[u]=false,top--;
}
signed main()
{
    memset(head,-1,sizeof head);
    n=read(),m=read();
    for(register int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        add(u,v);
    }
    for(register int i=1;i<=n;i++) if(!vis[i]) dfs(i);
    if(maxx==100005) puts("-1");
    else
    {
        std::cout<<maxx<<std::endl;
        for( int i=1;i<=maxx;++i) std::cout<<b[i]<<std::endl;
    }
    return 0;
}

Measured memory_bytes: 6400
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using i128 = boost::multiprecision::int128_t;
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using VVV = vector<VV>;
using VVVll = vector<VVll>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const ld PI    = acos(-1.0);
const int MOD  = int(1e9)+7;
// const int MOD  = 998244353;


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

  V ans(m+2);
  rep(i, n) {
    int l, r; cin >> l >> r;
    --l;
    if (l == 0) {
      ++ans[1];
      --ans[r+1];
      continue;
    }

    int a = INF;
    rep2(d, 1, l+1) {
      int b = l/d;
      if (b >= a-1) break;
      a = b;
      int x = l/(a+1) + 1;
      int y = r/(a+1);
      if (a > 0) chmin(y, l/a);
      ++ans[x];
      --ans[y+1];
    }
    --a;
    for (; a>=0; --a) {
      int x = l/(a+1) + 1;
      int y = r/(a+1);
      if (a > 0) chmin(y, l/a);
      ++ans[x];
      --ans[y+1];
    }
  }

  rep(i, m+1) ans[i+1] += ans[i];
  rep(i, m) cout << ans[i+1] << "\n";
  return 0;
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
using namespace std;
struct point{
	int v,w;
}a[105];
int dp[105][10005];
int main(){
	int n,w;cin>>n>>w;
	for(int i=1;i<=n;i++)cin>>a[i].v>>a[i].w;
	for(int i=1;i<=n;i++){
		for(int j=w;j>=a[i].w;j--)
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].w]+a[i].v);
		for(int j=a[i].w-1;j>=0;j--)
			dp[i][j]=dp[i-1][j];
	}
	cout<<dp[n][w]<<endl;
	return 0;
}


Measured memory_bytes: 7020
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <utility>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <cstdlib>
#include <set>
#include <chrono> 

#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define mp make_pair
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define repf(i,st,end,inc) for(int i = st; i < end; i += inc)
#define repb(i,st,end,dec) for(int i = st; i >= end; i -= dec) 

#define MOD 1000000007

#define trace1(a) cout << a << endl;
#define trace2(a,b) cout << a << " | " << b << endl;
#define trace3(a,b,c) cout << a << " | " << b << " | " << c << endl;
#define trace4(a,b,c,d) cout << a << " | " << b << " | " << c << " | "<< d << endl;

using namespace std;
using namespace std::chrono;


int main(){
	fast;
	auto start = high_resolution_clock::now(); 

	int n, a, b;
	cin >> n >> a >> b;

	int temp = n-a-b;

	cout << min(a,b) << " " << max(a+b-n, 0);
	
	auto stop = high_resolution_clock::now(); 
	auto duration = duration_cast<microseconds>(stop - start);	
	// cout << endl;
	// cout << double(duration.count()) / 1000000 << endl; 

	return 0;
}



Measured memory_bytes: 256
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
typedef pair<int,int> P;
int h,w,dist[1005][1005]={},ans=-inf,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char c[1005][1005]={};
queue<P> q;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> h >> w;
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      dist[i][j]=inf;
    }
  }
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      cin >> c[i][j];
      if(c[i][j]=='#') {
        dist[i][j]=0,q.push({i,j});
      }
    }
  }
  while(q.size()) {
    P p=q.front();
    q.pop();
    for(int i=0; i<4; i++) {
      for(int j=0; j<4; j++) {
        int nx=p.first+dx[i],ny=p.second+dy[i];
        if(0<=nx&&nx<h&&0<=ny&&ny<w) {
          if(dist[nx][ny]>dist[p.first][p.second]+1) {
            dist[nx][ny]=dist[p.first][p.second]+1;
            q.push({nx,ny});
          }
        }
      }
    }
  }
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      ans=max(ans,dist[i][j]);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 13328
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int A = sc.nextInt();
		int B = sc.nextInt();

		if (A <= 8 && B <= 8){
			System.out.println("Yay!");
		} else {
			System.out.println(":(");
		}
	}
}


Measured memory_bytes: 22228
#include "bits/stdc++.h"
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target ("avx,avx2")

using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
	ll sum = 0;
	string s; cin >> s;
	for(int i{}; i<(int)s.size(); ++i){
		sum+=(s[i]-'0')%9;
	}
	if(sum%9==0){
		cout << "Yes";
	}else{
		cout << "No";
	}


}


Measured memory_bytes: 3784
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<int(n);++i)
using namespace std;
template<class A>void pr(A a){cout << a << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;p(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;p(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;p(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for(int j=0;j<N;++j) {}

int main(void) {
  int N,M;cin>>N>>M;
  int a[N+10]={0};
  int n;
  REP(i,M) {
    cin>>n;
    a[n]=1;
  }
  ll dp[100010];
  dp[0]=1;
  dp[1]=1;
  for(int j=0;j<N+1;++j) {
    if(a[j]) {
      dp[j]=0;
    } else if(j==0||j==1)  {
      dp[j]=1;
    } else {
      dp[j]=(dp[j-1]+dp[j-2])%1000000007;
    }
  }
  pr(dp[N]%1000000007);
  return 0;
}


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

#define int long long
#define endl '\n'
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vpi vector<pi>

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int MX = 3e5 + 5;
const ld PI = 4 * atan((ld)1);
int dp[200][MX];
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,wt;
	cin>>n>>wt;
	pi w[n+1];
	for(int i=1;i<=n;i++){
		cin>>w[i].first>>w[i].second;
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=wt;j++){
			if(i==0 or j==0)
				dp[i][j]=0;
			else if(w[i].first<=j)
				dp[i][j]=max(dp[i-1][j],w[i].second+dp[i-1][j-w[i].first]);
			else
				dp[i][j]=dp[i-1][j];
		}
	cout<<dp[n][wt]<<endl;
}

Measured memory_bytes: 234496
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int num;
    int i,j,a;
    int tn,f,rn,pn;
    int room[4][3][10]={0};
    scanf("%d",&num);
    for(i=0;i<num;i++){
        scanf("%d %d %d %d",&tn,&f,&rn,&pn);
        if(room[tn-1][f-1][rn-1]+pn<0){
            pn=0;
        }
        room[tn-1][f-1][rn-1]+=pn;
    }for(i=0;i<4;i++){
        if(i!=0){
            printf("\n");
            printf("####################\n");
        }
        for(j=0;j<3;j++){
            if(j!=0){
                printf("\n");
            }
            for(a=0;a<10;a++){
                printf("%2d",room[i][j][a]);
            }
        }
        
    }printf("\n");
    return 0;
}

Measured memory_bytes: 620
#include <iostream>
#include <algorithm>
#define MAX 100005
using namespace std;
int n,a[MAX],L[MAX];

int lis() {
    L[0] = a[0];
    int length = 1;
    for(int i=1;i<n;i++) {
        if(L[length-1] < a[i])  L[length++] = a[i];
        else                    *lower_bound(L,L+length,a[i]) = a[i];
    }
    return length;
}

int main() {
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    cout << lis() << endl;
    return 0;
}



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

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

    if(N == 1){
        cout << 1 << endl;
        return 0;
    }
    ll L[90];
    L[0] = 2;
    L[1] = 1;
    for(int i=2;i<=N;i++){
        L[i] = L[i-1] + L[i-2];
    }
 
    cout << L[N] << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
Boolean isNull = str.equals("");
while(!isNull){
String[] datas = new String[8];
datas = str.split(" ",8);
double x1 = Double.parseDouble(datas[0]);
double y1 = Double.parseDouble(datas[1]);
double x2 = Double.parseDouble(datas[2]);
double y2 = Double.parseDouble(datas[3]);
double x3 = Double.parseDouble(datas[4]);
double y3 = Double.parseDouble(datas[5]);
double xp = Double.parseDouble(datas[6]);
double yp = Double.parseDouble(datas[7]);
double x = xp-x1;
double y = yp-y1;
double p = x2-x1;
double q = y2-y1;
double r = x3-x1;
double u = y3-y1;
double[] coefficient = new double[2];
coefficient = Simultaneous(p,r,x,q,u,y);
double s = coefficient[0];
double t = coefficient[1];
if(s<0||t<0){
System.out.println("NO");
}else if(s+t>0 && s+t<1){
System.out.println("YES");
}else{
System.out.println("NO");
}
str = br.readLine();
str = str == null?"":str;
isNull = str.equals("");

}
}
public static double[] Simultaneous(double a,double b,double c,double d,double e,double f){
double x = (double) (e*c-b*f)/(a*e-b*d);
double y = (double) (a*f-c*d)/(a*e-b*d);
double[] answer = new double[2];
answer[0]=x;
answer[1]=y;
return answer;
}
}

Measured memory_bytes: 24916
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let (n,t) = {
        let t = read_vec::<usize>();
        (t[0],t[1])
    };
    let tn = read_vec::<usize>();
    let mut ans = 0;
    for j in 0..n-1{
        if tn[j+1]-tn[j] < t {
            ans += tn[j+1]-tn[j]
        } else {
            ans += t;
        }
    }
    ans += t;
    println!("{}",ans);
}

Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n); i >= 0; i--)
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define REVSORT(c) SORT(c);REVERSE(c)
#define ALL(x) (x).begin(),(x).end()
#define INF 1e9
const long long MOD = 1000000007;
typedef long long ll;

int main(){
	int N, Y;
	cin >> N >> Y;
	
	Y /= 1000;
	int A = -1;
	int B = -1;
	int C = -1;
	
	for(int i = 0; i <= N; i++){//10,000JPY
		for(int j = 0; j <= N; j++){//5,000JPY
			int k = N - i - j;//1,000JPY
			if(k < 0)continue;
			if(i * 10 + j * 5 + k == Y){
				A = i;
				B = j;
				C = k;
				break;
			}
		}
	}
	
	cout << A << " " << B << " " << C << endl;
}

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

typedef long long LL;
const int INF = int(1e9);
const int MAX = 1000020;
LL N;
LL a[MAX],b[MAX],c[MAX];
 
void Cin(LL a[]){
    for(int i = 1;i<=N;i++)
        scanf("%lld",&a[i]);
}
 
int main(){
    cin>>N;
    Cin(a),Cin(b),Cin(c);
    sort(a+1,a+1+N),sort(b+1,b+1+N),sort(c+1,c+1+N);
    LL sum = 0;
    LL ai = 0,ci = 0;
    for(int i = 1;i<=N;i++){
        while(a[ai+1]<b[i]&&ai+1<=N)
            ai++;
        while(c[ci+1]<=b[i]&&ci+1<=N)
            ci++;
        sum += ai*(N-ci);
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 9216
#include <iostream>

int main()
{
    int buf[4][3][10] = {};
    int n;
    std::cin >> n;
    int b, f, r, v;
    for (int i = 0; i < n; i++) {
        std::cin >> b >> f >> r >> v;
        buf[b-1][f-1][r-1] += v;
    }

    for (b = 0; b < 4; b++) {
        for (f = 0; f < 3; f++) {
            for (r = 0; r < 10; r++) {
                std::cout << ' ' << buf[b][f][r];
            }
            std::cout << std::endl;
        }
        if (b != 3) {
            std::cout << "####################" << std::endl;
        }
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<double> point;
#define F first
#define S second

#define int ll

void br(ll n)
{
	ll r = 0;
	for (ll m = 1; m <= 2*n; ++m)
		if ((n/m) == n % m)
			r += m;
	cout << r << endl;
}

vector<pair<ll, int>> d[1000005];

signed main()
{
	#ifdef DGC
		//freopen("a.txt", "r", stdin);
		//freopen("b.txt", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	const int N = 1e6 + 4;
	vector<bool> p(N + 5);
	for (ll i = 3; i <= N; i += 2)
	    if (!p[i])
	        for (ll j = i * i; j <= N; j += 2 * i)
	            p[j] = true;

	for (int i = 4; i <= N; i += 2)
		p[i] = true;

	ll n, ans = 0;
	cin >> n;

	for (int i = 2; i <= N; ++i)
		if (!p[i])
			for (ll x = max((n-1000002 + i-1) / i, 1LL); x*i <= n; ++x)
				d[n - x*i].push_back({ i, 0 });

	ll b, e;
	int sz, R;
	function<void(int, ll)> gen = [&](int p, ll x)
	{
		if (x > e) return;
		if (p == sz)
		{
			if (x >= b)
				ans += x;
			return;
		}
		for (int i = 0; i <= d[R][p].S; ++i)
		{
			gen(p+1, x);
			x *= d[R][p].F;
		}
	};

	for (ll r = 1; r*r <= n; ++r)
	{
		e = (n)/r;
		b = (n)/(r+1) + 1;
		b = max(b, r+1);

		ll t = n-r;
		for (auto &i : d[r])
			while (t % i.F == 0) t /= i.F, ++i.S;
		if (t > 1)
			d[r].push_back({ t, 1 });

		sz = d[r].size();
		R = r;
		gen(0, 1);

		/*for (; b <= e; ++b)
			if ((n-r) % b == 0)
				ans += b;*/
	}

	cout << ans << "\n";

	return 0;
}


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

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

    int a[N];
    for (int i=0; i<N; i++) cin >> a[i];

    sort(a,a+N,greater<int>());
    int Alice=0;
    int Bob=0;

    for (int i=0; i<N; i++){
        if (i%2==0) Alice+=a[i];
        else Bob+=a[i];
    }

    int ans=Alice-Bob;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n=int(input())
p=list(map(int,input().split()))
p2=[i for i in p]
stack=[0]*(n+1)
ans=0
if p[0]<=0:
  ans+=1-p[0]
  p[0]=1
  stack[1]=1
else:
  stack[1]=p[0]
for i in range(1,n):
  if i%2==1:
    if p[i]+p[i-1]+stack[i-1]>=0:
      ans+=(p[i]+p[i-1]+stack[i-1])+1
      p[i]-=(p[i]+p[i-1]+stack[i-1])+1
  else:
    if p[i]+p[i-1]+stack[i-1]<=0:
      ans+=-(p[i]+p[i-1]+stack[i-1])+1
      p[i]+=-(p[i]+p[i-1]+stack[i-1])+1
  stack[i+1]=p[i]+p[i-1]+stack[i-1]
stack=[0]*(n+1)
ans2=0
if p2[0]>=0:
  ans2+=p2[0]+1
  p2[0]=-1
  stack[1]=-1
else:
  stack[1]=p2[0]
for i in range(1,n):
  if i%2==0:
    if p2[i]+p2[i-1]+stack[i-1]>=0:
      ans2+=(p2[i]+p2[i-1]+stack[i-1])+1
      p2[i]-=(p2[i]+p2[i-1]+stack[i-1])+1
  else:
    if p2[i]+p2[i-1]+stack[i-1]<=0:
      ans2+=-(p2[i]+p2[i-1]+stack[i-1])+1
      p2[i]+=-(p2[i]+p2[i-1]+stack[i-1])+1
  stack[i+1]=p2[i]+p2[i-1]+stack[i-1]
print(min(ans,ans2))      

Measured memory_bytes: 14340
using System;
using System.Linq;

namespace Project1
{
    class B046_3
    {
        static void Main()
        {
            var n = int.Parse(Console.ReadLine());

            decimal x = 1;
            decimal y = 1;

            foreach (var i in Enumerable.Range(0, n))
            {
                var l = Console.ReadLine().Split();
                var t = decimal.Parse(l[0]);
                var a = decimal.Parse(l[1]);

                decimal m = Math.Ceiling((Math.Max(Math.Max(x / t, y / a), 1)));
                x = m * t;
                y = m * a;
            }


            Console.WriteLine("{0}", x + y);
        }
    }
}


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

signed main() {
  	int N;
  	cin >> N;
  	vector<int> vec(N);
  	for(int i = 0;i < N;i++) {
      	cin >> vec.at(i);
    }
  	int ret = 0;
  	sort(vec.begin(),vec.end());
  	for(int i = 0;i < N - 2;i++) {
      	for(int j = i + 1;j < N - 1;j++) {
          	for(int k = j + 1;k < N;k++) {
              	if(vec.at(i) + vec.at(j) > vec.at(k)) {
                  	ret++;
                }
            }
        }
    }
  	cout << ret << endl;
}

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


template<Int MOD = 1000000007>
struct Mod{
  Int prev=0;
  vector<Int> fact,inv,finv;
  Mod(){}
  Mod(Int n){init(n);}
  
  Int pow(Int x,Int n){
    Int res=1;
    while(n){
      if(n&1) (res*=x)%=MOD;
      (x*=x)%=MOD;
      n>>=1;
    }
    return res;
  }
  
  Int inverse(Int a){
    return pow(a,MOD-2);
  }
  
  void init(Int n){
    if(prev>=n) return;
    prev=n;
    fact=inv=finv=vector<Int>(n);
    
    fact[0]=1;
    for(Int i=1;i<n;i++)
      fact[i]=(fact[i-1]*i)%MOD;
    
    inv[1]=1;
    for(Int i=2;i<n;i++)
      inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    
    finv[0]=1;
    for(Int i=1;i<n;i++)
      finv[i]=finv[i-1]*inv[i]%MOD;
  }
  
  Int comb(Int n,Int k){
    Int res=1;
    for(Int i=0;i<k;i++){
      res*=(n-i)%MOD;
      res%=MOD;
      res*=inverse(i+1);
      res%=MOD;
    }
    return res;
  }
  
  //only for prime MOD
  Int C(Int n,Int k){
    if(k<0||k>n) return 0;
    return fact[n]*finv[k]%MOD*finv[n-k]%MOD;
  }
  
  Int P(int n,int k){
    if(k<0||k>n) return 0;
    return fact[n]*finv[n-k]%MOD;    
  }

  Int H(Int n,Int k){
    return C(n+k-1,n);
  }

  Int S(Int n,Int k){
    Int res=0;
    for(Int i=1;i<=k;i++){
      Int tmp=C(k,i)*pow(i,n)%MOD;
      if((k-i)&1) res+=MOD-tmp;
      else res+=tmp;
      res%=MOD;
    }
    res=res*finv[k]%MOD;
    return res;
  }
  
  Int B(Int n,Int k){
    Int res=0;
    for(Int j=1;j<=k;j++){
      res+=S(n,j);
      res%=MOD;
    }
    return res;
  }
  
  Int montmort(Int n){
    Int res=0,rinv=1;
    for(Int k=2;k<=n;k++){
      rinv=rinv*inverse(k)%MOD;
      if(k%2) res+MOD-rinv;
      else res+=rinv;
      res%=MOD;
    }
    for(Int i=1;i<=n;i++) res=res*i%MOD;
    return res;
  }
  
  // calculate P(t) from given points in [0,N]
  Int LagrangePolynomial(vector<Int> &y,Int t){
    Int n=y.size()-1;
    init(n+1);
    Int num=1;
    for(Int i=0;i<=n;i++)
      num=num*((t-i)%MOD)%MOD;
    Int res=0;
    for(Int i=0;i<=n;i++){
      Int tmp=(y[i]*num%MOD)*inverse((t-i)%MOD)%MOD;
      tmp=tmp*finv[i]%MOD;
      tmp=tmp*finv[n-i]%MOD;
      if((n-i)&1) tmp=MOD-tmp;
      res=(res+tmp)%MOD;
    }
    return res;
  }
};


//INSERT ABOVE HERE
signed main(){
  const Int MOD = 1e9+7;
  Mod<MOD> mod(2e5);
  Int n,k;
  cin>>n>>k;
  cout<<mod.P(k,n)<<endl;
  return 0;
}



Measured memory_bytes: 7480
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = (1e9)+7;
void fastIO(){
  ios_base::sync_with_stdio(0); cin.tie(0);
}


int main(){
  fastIO();
  int n;
  cin>>n;
  vector<int>score(n);
  for(int i=0;i<n;i++){
  	cin>>score[i];
  }
  int cnt=0,ans=0;
  bool gray=false,brown=false,green=false,
  	   cyan=false,blue=false,yellow=false,
  	   orange=false,red=false;
  for(int i=0;i<n;i++){
  	if(score[i]<=399&&!gray){
  		gray=true;
  		ans++;
  	}else if(score[i]>399&&score[i]<=799&&!brown){
  		brown=true;
  		ans++;
  	}else if(score[i]>799&&score[i]<=1199&&!green){
  		green=true;
  		ans++;
  	}else if(score[i]>1199&&score[i]<=1599&&!cyan){
  		cyan=true;
  		ans++;
  	}else if(score[i]>1599&&score[i]<=1999&&!blue){
  		blue=true;
  		ans++;
  	}else if(score[i]>1999&&score[i]<=2399&&!yellow){
  		yellow=true;
  		ans++;
  	}else if(score[i]>2399&&score[i]<=2799&&!orange){
  		orange=true;
  		ans++;
  	}else if(score[i]>2799&&score[i]<3200&&!red){
  		red=true;
  		ans++;
    }else if(score[i]>=3200){
  		cnt++;
  	}
  }
  cout<<max(1,ans)<<" "<<max(cnt+ans,1)<<endl; 
}  


Measured memory_bytes: 256
# include <stdio.h>

int main(){

	char um[5];
	char dos[5];
	char tre[5];

	scanf("%s", um);
	scanf("%s", dos);
	scanf("%s", tre);

	printf("%c", um[0]);
	printf("%c", dos[1]);
	printf("%c", tre[2]);

	printf("\n");





	return 0;
}


Measured memory_bytes: 128
n = str(input())
iL = len(n)
count = 0
for i in range(1,iL+1):
  
  if i != iL and i % 2 != 0:
    count += (100**(i//2))*9
  elif i == iL and i% 2 != 0:
    count += int(n) - 100**(i//2)+1
print(count)


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

typedef long long ll;
typedef complex<double> Vec;

ll N, K;
vector<ll> A;
ll Sum;
set<ll> Divs;
ll R;

int main() {
  cin >> N >> K;
  A.resize(N);
  for (ll i = 0; i < N; ++i) {
    cin >> A[i];
    Sum += A[i];
  }
  for (ll i = 1; i * i <= Sum; ++i) {
    if (Sum % i == 0) {
      Divs.insert(i);
      Divs.insert(Sum / i);
    }
  }
  for (ll div : Divs) {
    vector<ll> rems;
    ll diff = 0, k = 0;
    for (ll a : A) {
      ll rem = a % div;
      rems.push_back(rem);
      diff -= rem;
      k += rem;
    }
    assert(diff % div == 0);
    sort(rems.begin(), rems.end(), greater<ll>());
    for (ll rem : rems) {
      if (diff == 0) break;
      diff += div;
      k -= rem;
    }
    if (k <= K) R = max(R, div);
  }
  cout << R << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      //入力した数値を格納
        int L, R, d;
      //倍数の数を格納
        int countflag = 0;
        Scanner scanner = new Scanner(System.in);

        L = scanner.nextInt();
        R = scanner.nextInt();
        d = scanner.nextInt();

		//L以上R以下の整数でdの倍数の個数をカウント
        for(int i = L; i <= R; i++) {
            if(i % d == 0) {
                countflag++;
            }
        }
	//結果を出力
        System.out.println(countflag);
	//スキャナーの解放
        scanner.close();
    }
}

Measured memory_bytes: 35664
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>h(n);
    for(int i=0;i<n;i++)
    {
        cin>>h[i];
    }
    vector<int>dp(n,INT_MAX);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {

        for(int j=1;j<=2;j++)
        {
            if(i>=j){
                dp[i]=min(dp[i],abs(h[i]-h[i-j])+dp[i-j]);
            }
        }
    }
    cout<<dp[n-1];
}

Measured memory_bytes: 3988
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)

    n,m = LI()
    s = S()
    t = S()
    g = gcd(n,m)
    l = n*m//g
    n_ = n//g
    m_ = m//g
    for i in range(g):
        if s[n_*i] != t[m_*i]:
            print(-1)
            return
    print(l)
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    A()


Measured memory_bytes: 53232
//PRZEMYSL ASSERTY

//SPRAWDZ CORNER CASE'Y, MINIMALNE I MAKSYMALNE WEJŚCIE I WYJŚCIE

//MODULO = 1

//while (clock()<=69*CLOCKS_PER_SEC)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

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

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

#define imie(x) "[" << #x ": " << (x) << "] "

#define shandom_ruffle random_shuffle

const int nax=1000*1007;

int n, m;

vector <int> graf[nax];

deque <int> kol;

int bylo[nax];

int s;

int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		int p1, p2;
		scanf("%d%d", &p1, &p2);
		graf[p1].push_back(p2);
		graf[p2].push_back(p1);
		s=p1;
	}
	bylo[s]=1;
	kol.push_front(s);
	while(1)
	{
		int ok=-1;
		s=kol.front();
		for (int i=0; i<graf[s].size(); i++)
			if (!bylo[graf[s][i]])
				ok=graf[s][i];
		if (ok>0)
		{
			bylo[ok]=1;
			kol.push_front(ok);
			continue;
		}
		
		s=kol.back();
		for (int i=0; i<graf[s].size(); i++)
			if (!bylo[graf[s][i]])
				ok=graf[s][i];
		if (ok>0)
		{
			bylo[ok]=1;
			kol.push_back(ok);
			continue;
		}
		break;
	}
	printf("%d\n", (int)kol.size());
	for (int i=0; i<(int)kol.size(); i++)
		printf("%d ", kol[i]);
	printf("\n");
	return 0;
}


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

string solve(map<int, int>& count, int n) {
	if (count.size() == 1 && (count.begin()->first == n - 1 || 2 * count.begin()->first <= n)) {
		return "Yes";
	} else if (count.size() == 2 && count.rbegin()->first - count.begin()->first == 1) {
		int x = count.begin()->second, y = count.rbegin()->second;
		if (x + 1 <= count.rbegin()->first && count.rbegin()->first <= x + y / 2) {
			return "Yes";
		}
	}
	return "No";
}

int main() {
	int n;
	cin >> n;
	map<int, int> count;
	for (int a; cin >> a; count[a]++) {
	}
	cout << solve(count, n);
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,a[102][102]={0};
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>a[i][j];
      a[i][m]+=a[i][j];
      a[n][j]+=a[i][j];
      a[n][m]+=a[i][j];
    }
  }
  for(int i=0;i<=n;i++){
    for(int j=0;j<=m;j++){
      cout<<a[i][j];
      if(j!=m)cout<<" ";
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3136