akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
int main(){
  int n;
  std::cin >> n;
  std::vector<int> cnt(n + 1), sum(n + 1), ans(n);
  for(int i = 0; i != n; ++i){
    int a;
    std::cin >> a;
    ++sum[cnt[a]++];
  }
  int it = 0, acc = 0;
  for(int t = n; t != 0; --t){
    while(acc >= it * t)
      acc += sum[it++];
    ans[t - 1] = it - 1;
  }
  for(const int e : ans)
    std::cout << e << std::endl;
}

Measured memory_bytes: 4352
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
#include <string>
#include <bitset>
#include <stack>
#include <queue>
#include <tuple>
#include <regex>
#include <cmath>
#include <map>
#include <set>
#include <functional>
#include <cstring>

using namespace std;

template<typename T> bool chmax( T &a, const T b ) { if ( a <= b ) { a = b; return ( true ); } else { return ( false ); } }
template<typename T> bool chmin( T &a, const T b ) { if ( a >= b ) { a = b; return ( true ); } else { return ( false ); } }

using ll = long long;
using Pint = pair<int, int>;
using Pll  = pair<ll, ll>;

#define eb emplace_back
#define pb push_back
#define mp make_pair

#define F first
#define S second

#define popcnt __builtin_popcountll

#define rep( i, n ) for ( ll i = 0; i < (ll)( n ); ++i )
#define reps( i, n ) for ( ll i = 1; i <= (ll)( n ); ++i )
#define rrep( i, n ) for ( ll i = (ll)( ( n ) - 1 ); i >= 0; --i )
#define rreps( i, n ) for ( ll i = (ll)( ( n ) ); i > 0; --i )
#define arep( i, v ) for ( auto &&i : ( v ) )

#define ALL( c ) ( c ).begin(), ( c ).end()
#define RALL( c ) ( c ).rbegin(), ( c ).rend()
#define UNIQUE( c ) ( c ).erase( unique( ( c ).begin(), ( c ).end() ), ( c ).end() )

template<typename T = ll> constexpr T MAX = numeric_limits<T>::max();
template<typename T> T gcd( const T a, const T b ) { return ( b ? gcd( b, a % b ) : a ); }
template<typename T> T lcm( const T a, const T b ) { return ( a / gcd( a, b ) * b ); }


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

	ll ans = 0;
	reps( i, 1000000 )
	{
		reps( j, 1000000 )
		{
			if ( i * j > n ) break;
			if ( n - i * j > 0 )
			{
//				cout << i << ", " << j << ", " << n - i * j << endl;
				++ans;
			}
		}
	}

	cout << ans << endl;

	return ( 0 );
}


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


const int MaxH = 1e4+10;
const int MaxN = 1e3+10;
const int Inf = 0x3fffffff;
int f[MaxH];
int h, n;
int a[MaxN], b[MaxN];


void solve()
{
    for (int i = 1; i <= h; i++) f[i] = Inf;
    for (int i = 1; i <= n; i++) {
        for (int v = a[i]; v < h; v++)
            f[v] = min(f[v], f[v - a[i]] + b[i]);
        for (int k = max(0, h - a[i]); k < h; k++)
            f[h] = min(f[h], f[k] + b[i]);
    }
    cout << f[h] << endl;
}


int main()
{
    cin >> h >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    solve();
    return 0;
}


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

int main(){
  long n, m;  cin >> n >> m;
  vector<pair<long, long>> cb;
  for(int i=0; i<n; i++){
    long a;  cin >> a;
    cb.push_back({a, 1});
  }
  for(int i=0; i<m; i++){
    int b, c;  cin >> b >> c;
    cb.push_back({c, b});
  }
  sort(cb.rbegin(), cb.rend());

  long num = 0, idx = 0, ans = 0;
  while(num < n){
    ans += cb[idx].first * min(cb[idx].second, n-num);
    num += cb[idx].second;
    idx++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 7440
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    r = int(input())
    print(3 * r**2)

if __name__ == '__main__':
    main()

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

int main(){
  int ans=0,n;
  cin >> n;
  int a[n];
  for ( int i = 0 ;  i < n ; i++ ){
    cin >> a[i];
  }
  while (1){
    bool f=false;
    for ( int i = 0 ;  i < n ; i++ ){
      if (a[i]%2!=0){
        f=true;
        break;
      }
    }
    if (f) break;
    else {
      for ( int i = 0 ;  i < n ; i++ ) a[i]=a[i]/2;
      ans++;
    }
  }

  cout << ans;
  return 0;
}

Measured memory_bytes: 3672
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = I()
if n == 1:
    print(0)
    quit()
f = factorization(n)
ans = 0
for i, j in f:
    tmp = 1
    while j >= tmp:
        ans += 1
        j -= tmp
        tmp += 1
print(ans)

Measured memory_bytes: 66812
#include <bits/stdc++.h>
using namespace std;
 
int N;
vector<int> Li; 
 
int main() {
  cin >> N;
  Li = vector<int>(N);
  for (int i=0;i<N;i++){
    cin >> Li.at(i);
  }

  int sum=0;
  sort(Li.begin(), Li.end());
  for (int i=0;i<N-1;i++){
    sum += Li.at(i);
  }

  cout << ((sum > Li.at(N-1)) ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int, input().split()))

count = 0

for i in range(n):    
    while h[i] >= 1:
        wid = 0
        for l in range(i,n):
            if h[l] >= 1:
                    wid = wid + 1
            else:
                break
        
        #widの分だけ水をやる
        for k in range(wid):
            h[i + k] = h[i+k] - 1
        
        count = count + 1

print(count)

Measured memory_bytes: 3060
input_list = []

while True:
    N = int(input())
    if N == 0:
        break
    input_list.append(N)

n = 123456*2
isPrime = [True for i in range(n)]

for i in range(int(n)):
    if i % 2 != 0:
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                isPrime[i] = False
                break
    else:
        isPrime[i] = False

isPrime[2] = True


while input_list:
    tmp = input_list.pop(0)
    tmp_isPrime = isPrime[tmp+1: tmp*2+1]
    print(tmp_isPrime.count(True))

Measured memory_bytes: 11948
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define $ if(0)

using namespace std;

int n;
char z[120000];
void work () {
	int i , sum;
	scanf ( "%s" , z + 1 );
	n = strlen ( z + 1 );
	sum = 0;
	for ( i = 1 ; i <= n ; i++ ) if ( z[i] == 'p' ) sum++;
	printf ( "%d\n" , n / 2 - sum );
}
int main () {
	work ();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	for(int i=0;i<s.size();++i) {
		if(s[i]==',') cout << ' ';
		else cout << s[i];
	}
	cout << '\n';
}

Measured memory_bytes: 256
n = gets.to_i
a = Array.new(n).map{Array.new(2, 0)}
0.upto(n - 1) do |i|
  a[i][0], a[i][1] = gets.split.map(&:to_i)
end
a.sort!{|a, b| a[1]<=>b[1] || b[0]<=>a[0]}
ans = 0
0.upto(n - 1) do |i|
  ans += a[i][0]
  if ans > a[i][1]
    puts "No"
    exit
  end
end
puts "Yes"

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

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

    int takh,taks;
    int aokh,aoks;
    cin>>takh>>taks;
    cin>>aokh>>aoks;
    while(takh>0 || aokh>0){
        aokh-=taks;
        if(aokh<=0)
            break;
        takh-=aoks;
    }
    if(takh>0)
        cout<<"Yes";
    else
        cout<<"No";
}


Measured memory_bytes: 3584
import sys
input=sys.stdin.readline
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  """
  始点sから各頂点への最短距離を返す

  Parameters
  ----------
  s : int
      視点とする頂点（0-indexed）
  n : int
      グラフの要素数
  eage:list
      グラグ

  Returns
  -------
  dist ：list
  始点sから各頂点への最短距離
  """
  dist=[float("inf")]*n
  dist[s]=0
  used=[-1]*n
  hq=[[dist[s],s]]
  while hq:
    d,cur=heappop(hq)
    if dist[cur]<d:continue # 距離が最小でない場合は飛ばす
    for nx,nxd in edge[cur]:
      if dist[cur]+nxd<dist[nx]:
        dist[nx]=dist[cur]+nxd
        used[nx]=cur
        heappush(hq,[dist[cur]+nxd,nx])
  return dist

n,m,s,t=map(int,input().split())
Gs=[[] for i in range(n)]
Gt=[[] for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  Gs[u-1].append([v-1,a])
  Gs[v-1].append([u-1,a])
  Gt[u-1].append([v-1,b])
  Gt[v-1].append([u-1,b])
s-=1
t-=1
yen=dijkstra(s,n,Gs)
snk=dijkstra(t,n,Gt)
cost=[10**15-(yen[i]+snk[i]) for i in range(n)]
for i in range(n-2,-1,-1):
  cost[i]=max(cost[i],cost[i+1])
for c in cost:
  print(c)



Measured memory_bytes: 124576
#include <cstdio>
#include <algorithm>
const int dx[4] = { 0, 0, 1, -1 }, dy[4] = { -1, 1, 0, 0 };
int N, M, K, a[802][802], X, Y, qx[640001], qy[640001], dis[802][802], O = 1000000000;
int main()
{
	scanf("%d%d%d", &N, &M, &K);
	for (int i = 1; i <= N; i++)
	{
		static char I[802];
		scanf("%s", I + 1);
		for (int j = 1; j <= M; j++)
			if (I[j] != '#')
			{
				a[i][j] = 1;
				if (I[j] == 'S')
				{
					X = i;
					Y = j;
				}
			}
	}
	int H = 0, T = 1;
	qx[1] = X;
	qy[1] = Y;
	dis[X][Y] = 1;
	while (H < T)
	{
		H++;
		int ux = qx[H], uy = qy[H];
		for (int i = 0; i < 4; i++)
		{
			int vx = ux + dx[i], vy = uy + dy[i];
			if (a[vx][vy] && !dis[vx][vy])
			{
				T++;
				qx[T] = vx;
				qy[T] = vy;
				dis[vx][vy] = dis[ux][uy] + 1;
			}
		}
	}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (1 <= dis[i][j] && dis[i][j] <= K + 1)
				O = std::min(O, (std::min(std::min(i - 1, N - i), std::min(j - 1, M - j)) + K - 1) / K + 1);
	printf("%d\n", O);
}


Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
long long INF = 1e18;
int n;
long long a[20];
struct State {
    int l, xl, r, xr;
    State(){};
    State(int l, int xl, int r, int xr): l(l), xl(xl), r(r), xr(xr) {};
    bool operator < (const State& oo) const {
        if (this->l != oo.l) return this-> l < oo.l;
        if (this->xl != oo.xl) return this->xl < oo.xl;
        if (this->r != oo.r) return this->r < oo.r;
        return this->xr < oo.xr;
    }
};
map<State, long long> dp;
long long cal(int l, int xl, int r, int xr) {
    if (dp.count({l, xl, r, xr})) return dp[{l, xl, r, xr}];
    long long &ans = dp[{l, xl, r, xr}];
    //cerr << l << ' ' << r << '\n';
    ans = INF;
    if (l + 1 == r) return ans = 0;
    for(int m = l+1; m < r; ++m) ans = min(ans, a[m] * (xl + xr) + cal(l, xl, m, xl+xr) + cal(m, xl+xr, r, xr));
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; ++i) cin >> a[i];
    cout << a[1] + a[n] + cal(1, 1, n, 1);
    return 0;
}

Measured memory_bytes: 32896
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e3 + 5;
int n,p[N],not_inv[N];
LL A,B,f[N][N];
//#define R
int main()
{
	cin>>n>>A>>B;
	for (int i = 1;i <= n; ++i)
		cin>>p[i]; 
	for (int i = 1;i <= n; ++i)
	{
		not_inv[i] = 0;
		for (int j = 1;j < i; ++j)
			if (p[j] < p[i])
				not_inv[i]++;
	}
	for (int i = 1;i <= n; ++i)
		for (int j = 1;j <= i; ++j)
			if (not_inv[i] + 1 > j)
				f[i][j] = f[i - 1][j];
			else
				f[i][j] = min(f[i - 1][j - 1] + B,f[i - 1][not_inv[i]] + A * ((LL)j - 1 - not_inv[i])); 
				//f[i - 1][not_inv[i]] + min(A,B * ((LL)j - 1 - not_inv[i]));
	#ifdef R
	for (int i = 1;i <= n; ++i)
	{
		for (int j = 1;j <= n; ++j)
			cout<<f[i][j]<<" ";
		puts("");
	}
	#endif
	cout<<f[n][n];
 } 

Measured memory_bytes: 194048
#include <iostream>

using namespace std;

int main()
{
    int n,m,x=-2,y=-1;
    cin>>n>>m;
    char arr[n][m],brr[n*2][m];
    for (int i=0;i<n;i++){
        x+=2,y+=2;
        for (int j=0;j<m;j++){
            cin>>arr[i][j];
            brr[x][j]=arr[i][j];
            brr[y][j]=arr[i][j];
        }
    }
    for (int i=0;i<n*2;i++){
        for (int j=0;j<m;j++){
            cout<<brr[i][j];
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

typedef long long ll;
typedef pair< int, int > pii;

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

int pow(int x, int y){
  int result = 1;
  for(int i = 0; i < y; i++){
    result *= x;
  }
  return result;
}

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

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

  int s = 1;
  for(int i = 0; i < n; i++){
    if(a[i] % 2 == 0){
      s *= 2;
    }
  }

  int ans = pow(3, n) - s;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 632
/**
*    created: 21.06.2020 00:14:16
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define mod 1000000007
#define pi acos(-1.0)
using namespace std;

signed main() {

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

    int k, s;
    cin >> k >> s;
    int cnt = 0;
    rep(x,k+1) {
        rep(y,k+1) {
            int z = s - x - y;
            if (0 <= z && z <= k) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3576
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        int x = i;
        if(x % 3 == 0)
        {
            cout << " " << i;
            continue;
        }
        do
        {
            if(x % 10 == 3)
            {
                cout << " " << i;
                break;
            }
            x /= 10;
        }while(x);
    }
    cout << "\n";

    return 0;
}


Measured memory_bytes: 3116
from math import sqrt, ceil

N = 1000000
temp = [True]*(N+1)
temp[0] = temp[1] = False
for i in range(2, ceil(sqrt(N+1))):
    if temp[i]:
        temp[i+i::i] = [False]*(len(temp[i+i::i]))

while True:
    try:print(len([1 for _ in temp[:int(input())+1] if _]))
    except:break


Measured memory_bytes: 26448
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(18);
}
#define MOD 1000000007

signed main(){
  init_io();
  ll n,k,ma=0,mi=0,ans=0;
  cin >> n >> k;
  for(int i=0;i<k;i++){
    mi += i;
    ma += (n-i);
    mi %= MOD;
    ma %= MOD;
  }
  for(ll i=k;i<=n+1;i++){
    ans += (ma-mi+1+MOD)%MOD;
    ans %= MOD;
    mi += i;
    mi %= MOD;
    ma += n-i;
    ma %= MOD;
  }
  cout << ans << endl;
}


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

int main(){
    int n, fx, j=1;
    cin >> n;
    for (int i=0; i<9; i++){
        fx += (n/j)%10;
        j *= 10;
    }
    if (n%fx==0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,m,n) for(ll i=m;i<(ll)(n);i++)
typedef pair<int,long long> pint;
typedef long long ll;
const ll mod= 1e9+7;
const ll  longinf = 1LL<<60;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};



int main(){
  int n;cin>>n;
  int a[n];
  rep(i,n)cin>>a[i];
  int ans=0;
  rep(i,n-1)
    if(a[i]==i+1){
      ans++;
      swap(a[i],a[i+1]);
      }
  if(a[n-1]==n)ans++;
  cout<<ans<<endl;

  return 0;   

  }

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 2e5+10;
struct node{
    int to,nxt;
}e[maxn<<1];
int head[maxn<<1],tot;
int n,m,res[maxn],vis[maxn];
void add(int u,int v){ e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++;}

queue<int>que;
void bfs(int st){
    que.push(st);
    vis[st]=1;

    while( !que.empty()){
        int u=que.front();que.pop();
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].to;
            if( !vis[v] ){
                res[v]=u,vis[v]=1;
                que.push(v);
            }
            else continue;
        }
    }
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    bfs(1);
    int flag=0;
    for(int i=1;i<=n;i++){
        if( !vis[i] ){
            flag=1;
            break;
        }
    }
    if( flag ) printf("No\n");
    else printf("Yes\n");

    for(int i=2;i<=n;i++){
        printf("%d\n",res[i]);
    }
    return 0;
}


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

using namespace std;

#define IOS ios::sync_with_stdio(0);cin.tie(0);

int main(){
	IOS;
	int n;
	while(cin>>n){
		if(n>=1000){
			cout<<"ABD"<<endl;
		}
		else{
			cout<<"ABC"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
a =[int(n) for n in input().split()]

product = 1
if 0 in a:
    print(0)
else:
    for i in range(N):
        product *= a[i]
        if product > 10 ** 18:
            print('-1')
            break
    if product <= 10 ** 18:
        print(product)

Measured memory_bytes: 21784
z['   '],i;main(j){for(;++i<2e3;)for(j=z[i>>5]&1<<i?1e7:-2*i*~i;j<5e6;j+=i-~i)z[j>>5]|=1<<j;for(;~scanf("%d",&i);)for(j=~i/-2;i;)z[--j>>5]&1<<j|z[j-1>>5]&1<<j-1|z[j-3>>5]&1<<j-3|z[j-4>>5]&1<<j-4||printf("%d\n",j*2+1,i=0);}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(){
    int n,m;
    cin >> n >> m;
    if(abs(n-m)>1){
        cout << 0 << endl;
        return 0;
    }
    mint per[max(n,m)];
    per[0] = 1;
    for(int i = 1; i<max(n,m)+1; i++){
        per[i] = per[i-1]*mint(i);
    }
    if(abs(n-m) == 0){
        cout << mint(2) * per[m] * per[n] << endl;
    }else{
        cout << per[m] * per[n] << endl;
    }
    return 0;
}

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

#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define reset(a, v) memset((a), v, sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 100005;

int n;
ii dat[N];

bool comp(ii A, ii B) {
	return A.se < B.se;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x, l; scanf("%d %d", &x, &l);
		dat[i].fi = x-l;
		dat[i].se = x+l;
	}
	sort(dat, dat+n, comp);
	int ans = 1;
	int last = 0;
	for (int i = 1; i < n; i++) {
		if (dat[i].fi >= dat[last].se) {
			ans++;
			last = i;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
int n;
int t[100000];
int x[100000];
int y[100000];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=0;i<n;i++) cin>>t[i]>>x[i]>>y[i];
    int xn=0;
    int yn=0;
    int timen=0;
    for(int i=0;i<n;i++){
        if((((abs(x[i]-xn)+abs(y[i]-yn))%2)!=(t[i]-timen)%2)||abs(x[i]-xn)+abs(y[i]-yn)>t[i]-timen){
                no;
                return 0;
        }
        timen=t[i];
        xn=x[i];
        yn=y[i];
    }
    yes;
    return 0;
}

Measured memory_bytes: 1408
import java.io.*;
import java.util.*;
 
public class Main {
 
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    
    private static StringTokenizer st;
 
    public static void main ( String [] args ) throws IOException
    {
    new Main().cal();
    }
 
  
    private void cal() throws IOException 
    {
    int N = Integer.parseInt(br.readLine());
    int [] nums = new int[N];
     
    for(int i = 0; i < N; i++)
        nums[i] = Integer.parseInt(br.readLine());
 
    int count = 0;
    for(int n : nums)
        if ( isPrime(n) ) count++;
 
    System.out.println(count);
 
    }
 
    private boolean isPrime(int n) {
    if ( n == 2 ) return true;
    else if ( n % 2 == 0 ) return false;
    else if ( n < 9 ) return true;
    else if ( n % 3 == 0 ) return false;
    else {
        for(int i = 5; i * i <= n; i+=6) {
        if ( n % i == 0 ) return false;
        else if ( n % (i+2) == 0 ) return false;
        }
        return true;
    }
 
 
    }
 
}

Measured memory_bytes: 30108
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;
using ll = long long;
constexpr double INF{ 1e9 };
constexpr int MAGIC_PRIME{ 1000000000 + 7 };
constexpr array<int, 4> dy{ -1, 1, 0, 0 };
constexpr array<int, 4> dx{ 0, 0, -1, 1 };
constexpr int div_ru(int a, int b)
{
    return (a - b + 1) / b;
}
ll pow_mod(ll b, ll e, ll m)
{ // https://atcoder.jp/contests/atc002/tasks/atc002_b
    ll r = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            r = (r * b) % m;
        b = (b * b) % m;
    }
    return r;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int& x : a)
        cin >> x;
    a.push_back(-1);

    // dp[i] i段目にたどり着くまでの移動方法の通り
    vector<int> dp(n + 1);

    for (int i = 0, ia = 0; i < n + 1; i++)
    {
        if (i == 0)
            dp[i] = 1;
        else if (i == 1)
            if (a[ia] == i)
                ia++;
            else
                dp[i] = dp[i - 1]%MAGIC_PRIME;
        else
            if (a[ia] == i) 
                ia++;
            else
                dp[i] = (dp[i - 1]%MAGIC_PRIME + dp[i - 2]%MAGIC_PRIME)%MAGIC_PRIME;
    }

    cout << dp.back() << endl;

}
// vector<vector<int>> mm(h, vector<int>(w, -1));


Measured memory_bytes: 1152
N,M=map(int,input().split())
from collections import defaultdict

d1=defaultdict(int)
d2=defaultdict(int)

for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        d1[b]=1
        if d2[b]==1:
            print('POSSIBLE')
            exit()
    if b==N:
        d2[a]=1
        if d1[a]==1:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')


Measured memory_bytes: 90584
import math
a, b, h, m = map(int,input().split())
h_angle = (h+m/60)/12
m_angle = m/60
diff_angle = abs(h_angle-m_angle)*360
ans = math.sqrt(a**2+b**2-2*a*b*math.cos(math.radians(diff_angle)))
print(ans)

Measured memory_bytes: 9508
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
/*-------------------------------------------*/

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

    int n;
    cin >> n;
    ll cnt[20][20]{};
    rep(i, n) {
        string s;
        cin >> s;
        int idx = 0;
        ll a = 0;
        while(idx < s.size() && s[idx] != '.') {
            a *= 10;
            a += s[idx] - '0';
            idx++;
        }
        idx++;
        rep(j, 9) {
            a *= 10;
            if(idx < s.size()) a += s[idx] - '0';
            idx++;
        }
        int cnt2 = 0;
        while(cnt2 + 1 <= 18 && a % 2 == 0) {
            a /= 2;
            cnt2++;
        }
        int cnt5 = 0;
        while(cnt5 + 1 <= 18 && a % 5 == 0) {
            a /= 5;
            cnt5++;
        }
        cnt[cnt2][cnt5]++;
    }

    ll ans = 0;
    rep(i, 19) rep(j, 19) {
        ll num = 0;
        FOR(x, 18 - i, 19) FOR(y, 18 - j, 19) num += cnt[x][y];
        if(i >= 9 && j >= 9) ans -= cnt[i][j];
        ans += num * cnt[i][j];
    }

    cout << ans / 2 << endl;

    return 0;
}

Measured memory_bytes: 3612
N = int(input())
T,A = map(int, input().split())
H = list(map(int, input().split()))
ans = 0
mindT = float("inf")
for i in range(N):
  if abs(T-0.006*H[i]-A) < mindT:
    ans = i+1
    mindT = abs(T-0.006*H[i]-A)

print(ans)

Measured memory_bytes: 3064
n, k = map(int, input().split())
MOD = 10**9+7
count  = 0
for i in range(k, n+2):
    count = (count + int(((1/2*i*(i-1)+i*(n-i+1)) -(1/2*i*(i+1)-i)+1)%MOD))%MOD

print(count)

Measured memory_bytes: 9192
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
  if(a>b)
    return gcd(b,a);
  if(a==0)
    return b;
  return gcd(b%a,a);
}
int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)
    cin>>a.at(i);
  int gp=a.at(0);
  int g0=0;
  int p=0;
  for(int i=1;i<n;i++){
    if(gcd(gp,a.at(p))>gcd(gp,a.at(i))){
      gp=gcd(gp,a.at(p));
      p=i;
    }else
      gp=gcd(gp,a.at(i));
    g0=gcd(g0,a.at(i));
  }
  cout<<max(g0,gp)<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<int,int> P;
#define all(v) (v).begin(),v.end()
#define fi first
#define se second
const ll inf=(1e18);
const ll mod=1000000007;
bool dp[100000];
int main(){
while(1){
int w,h;
cin>>w>>h;
if(w==0||h==0)return 0;
vector<vector<int>> s(h,vector<int>(w)),a(h,vector<int>(w,-1));
for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
        cin>>s[i][j];
        if(s[i][j]==1)a[i][j]=0;
    }
}
queue<P> que;
int ans=0;
for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
        if(a[i][j]==0){
            a[i][j]=1;
            que.push(P(i,j));
            while(!que.empty()){
                P p=que.front();
                  que.pop();
                  for(int dy=-1;dy<=1;dy++){
                      for(int dx=-1;dx<=1;dx++){
                          int ny=dy+p.fi,nx=dx+p.se;
                          if(ny<0||ny>=h||nx<0||nx>=w||a[ny][nx]!=0)continue;
                          a[ny][nx]=1;
                          que.push(P(ny,nx));
                      }
                  }
            }
            ans++;
        }
    }
}
cout<<ans<<endl;
}
}






Measured memory_bytes: 3180
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define ALL(a) (a).begin(), (a).end()
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/

int main(void){
  int a, b;
  cin >> a >> b;
  if (b/100 == 1) a = a*1e+3;
  else if (b/10>=1) a = a*1e+2;
  else a = a*10;
  int ans = a+b;
  rep(i, 400){
    if (pow(i, 2) == ans) {
      cout<< "Yes" << endl;
      return 0;
    }
  }
  cout <<"No" << endl;
  return 0;
}


Measured memory_bytes: 256
<?php

fscanf(STDIN, '%d', $n);
$A = array();
for ($i = 0; $i < $n; $i++) {
    fscanf(STDIN, '%d', $m);
    $A[] = $m;
}
shellSort($A, $n);

function insertionSort(&$A, $n, $g)
{
    global $cnt;
    for ($i = $g; $i < $n; $i++) {
        $v = $A[$i];
        $j = $i - $g;
        while ($j >= 0 && $A[$j] > $v) {
            $A[$j + $g] = $A[$j];
            $j -= $g;
            $cnt++;
        }
        $A[$j + $g] = $v;
    }
}

function shellSort($A, $n)
{
    global $cnt;
    $cnt = 0;
    $G = explode(',', '1,4,13,40,121,364,1093,3280,9841,29524,88573,265720,797161');
    $m = count($G);
    while ($G[$m - 1] > $n) {
        $m--;
    }

    echo $m, PHP_EOL;
    for ($i = $m - 1, $arr = array(); $i >= 0; $i--) {
        $arr[] = $G[$i];
    }
    echo implode(' ', $arr), PHP_EOL;
    for ($i = $m - 1; $i >= 0; $i--) {
        insertionSort($A, $n, $G[$i]);
    }
    echo $cnt, PHP_EOL, implode(PHP_EOL, $A);
}

Measured memory_bytes: 251852
#include <iostream>

using namespace std;

int main(void) {
    string c[110];
    int i, H, W;
    cin >> H >> W;
    for (i=0;i<H;i++) cin >> c[i];
    for (i=0;i<2*H;i++) cout << c[i/2] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int n, m;
bool used[5001];
int cmp[5001];
vector<int> g[5001], gr[5001];
vector<int> vs;
void add(int x, int y){
  g[x].push_back(y);
  gr[y].push_back(x);
}
void dfs(int x){
	used[x]=1;
	for(auto y:g[x]){
		if(!used[y]) dfs(y);
	}
	vs.push_back(x);
}
 
void rdfs(int v, int k){
	used[v]=1;
	cmp[v]=k;
	for(auto y:gr[v]){
		if(!used[y]) rdfs(y, k);
	}
}
 
int scc(){
	fill(used, used+n, 0);
	vs.clear();
	for(int i=0; i<n; i++){
		if(!used[i]) dfs(i);
	}
	fill(used, used+n, 0);
	int k=0;
	for(int i=vs.size()-1; i>=0; i--){
		if(!used[vs[i]]) rdfs(vs[i], k++);
	}
	return k;
}
int main()
{
	cin>>n; cin>>m;
  for(int i=0; i<m; i++){
    int a, b;
    cin>>a>>b;
    a--; b--;
    add(a, b);
  }
  scc();
  int ans[5001];
  for(int i=0; i<n; i++){
    ans[cmp[i]]=i;
  }
  for(int i=0; i<n; i++){
    cout<<ans[i]+1<<endl;
  }
  for(int i=0; i<n-1; i++){
    bool ok=0;
    for(auto y:g[ans[i]]){
      if(y==ans[i+1]){
        ok=1;
        break;
      }
    }
    if(!ok){
      cout<<1<<endl;
      return 0;
    }
  }
  cout<<0<<endl;
	return 0;
}


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

public class Main implements Runnable {

	public static void main(String[] args) {

		new Thread(null, new Main(), "", 16 * 1024 * 1024).start();

	}

	@Override
	public void run() {
		exec();
	}

	private void exec() {

		FastScanner sc = new FastScanner(System.in);
		int n = sc.nextInt();
		int yen = sc.nextInt();
		if(yen % 1000 != 0) {
			System.out.println("-1 -1 -1");
			System.exit(0);
		}
		int x = 0;
		int y = 0;
		int z = 0;
		x = yen / 1000;
		if(x == n) {
			System.out.println("0 0 " + x);
			System.exit(0);
		}
		int sa = x - n;
		if(sa < 0) {
			System.out.println("-1 -1 -1");
			System.exit(0);
		}
		for(int i = 0 ; i * 4 <= sa ; i++) {
			for(int j = 0 ; i * 4 + j * 9 <= sa ; j++) {
				if(i * 4 + j * 9 == sa) {
					y = i;
					z = j;
					x -= (y * 5 + z * 10);
					if(x < 0) {
						System.out.println("-1 -1 -1");
					} else {
						System.out.println(z + " " + y + " " + x);
					}
					System.exit(0);
				}
			}
		}
		System.out.println("-1 -1 -1");
	}

}

class FastScanner {

	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	public FastScanner(InputStream in) {
		this.in = in;
	}

	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: 22868
using System;
class Pg
{
    static void Main()
    {
        int n;
        while ((n = int.Parse(Console.ReadLine())) != 0)
        {
            Console.WriteLine(GetDig(n));
        }
    }
    static int GetDig(int n)
    {
        var ans = 0;
        for (int i = 5; i <= n; ++i)
        {
            int t = i;
            while (t % 5 == 0)
            {
                ++ans;
                t /= 5;
            }
        }
        return ans;
    }
}


Measured memory_bytes: 15944
import java.util.Scanner;

public final class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        String[] s = new String[h];
        char[][] grid = new char[h][w];
        for(int i=0; i<h; i++){
            s[i] = sc.next();
        }
        int i=0;
        for(String str : s){
            for(int j=0; j<w; j++){
                // System.out.println(i+" "+j);
                grid[i][j] = str.charAt(j);
            }
            i++;
        }
        long[][] dp = new long[h+1][w+1];
        dp[1][1] = 1;
        for(i=1; i<h+1; i++){
            for(int j=1; j<w+1; j++){   
                if(grid[i-1][j-1] == '#'){
                    dp[i][j] = 0;
                    continue;                    
                }
                dp[i][j] = Math.max(dp[i][j],dp[i-1][j]+dp[i][j-1])%1000000007;
            }
        }
        // for(i=1; i<h+1; i++){
        //     for(int j=1; j<w+1; j++){   
        //         System.out.print(dp[i][j]+" ");
        //     }System.out.println();
        // }
        System.out.println(dp[h][w]);
        sc.close();
    }
}

Measured memory_bytes: 40220
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,k,q;
int a[N],c[N];
pair<int,int> sor[N];
void movit(int l,int r){
	memset(c,0,sizeof(c));
	for(int i=l;i<=r;i++)
		c[sor[i].second]=1;
	for(int i=r+1;i<=n;i++)
		c[sor[i].second]=2;
}
bool  judge(){
	int ans=0,len=0,h=0;
	for(int i=1;i<=n+1;i++)
		if(c[i]) len++,h+=2-c[i];
		else{
			ans+= len>=k ? min(len-k+1,h):0;
			len=0,h=0;
		}
	return ans>=q;
}
int main()
{	
	scanf("%d%d%d",&n,&k,&q);
	for(int temp,i=1;i<=n;i++){
		scanf("%d",&a[i]);sor[i]=make_pair(a[i],i);
	}
	sort(sor+1,sor+n+1);
	int ans=1e9+10;
	for(int i=1;i<=n;i++){
		int l=i,r=n+1;
		while(l<r){
			int mid=(l+r)>>1;
			movit(i,mid);
			if(judge()) r=mid;
			else l=mid+1;
		}
		if(l>n) continue;
		ans=min(ans,sor[l].first-sor[i].first);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 384
def solve():
    n, m = list(map(int, input().split()))

    p = [[] for _ in range(m + 1)]
    y = [[] for _ in range(m + 1)]

    pref = [[] for _ in range(n + 1)]
    
    for i in range(m):
        _p, _y = list(map(int, input().split()))
        p[i] = _p
        y[i] = _y

        pref[_p].append(_y)

    for i in range(len(pref)):
        pref[i] = list((sorted(pref[i])))

    _pref = [[] for _ in range(len(pref))]
    for i in range(len(_pref)):
        _pref[i] = dict(zip(pref[i], range(1, len(pref[i]) + 1)))


    for i in range(m):
        print("{:06}{:06}".format(p[i], _pref[p[i]][y[i]]))

if __name__ == "__main__":
    solve()

Measured memory_bytes: 62852
#include <bits/stdc++.h>
using namespace std;
# define MOD 1000000007
typedef long long ll;
void multiply(vector<vector<ll>>& a, vector<vector<ll>>& b, int n){
    vector<vector<ll>> mul(n, vector<ll>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            mul[i][j] = 0;
            for(int k=0;k<n;k++){
                ll curr = a[i][k]*b[k][j];
                mul[i][j] = (mul[i][j] + curr)%MOD; 
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j] = mul[i][j];
        }
    }
}
void power(vector<vector<ll>>& res, vector<vector<ll>>& arr, int n, ll k){
    if(k == 1){
        return;
    }
    power(res, arr, n, k/2);
    multiply(res, res, n);
    if(k%2 != 0){
        multiply(res, arr, n);
    }
}
int main(){
	int n;
	ll k;
	cin>>n>>k;
    vector<vector<ll>> arr(n, vector<ll> (n));
    vector<vector<ll>> res(n, vector<ll> (n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
            res[i][j] = arr[i][j];
        }
    }
    power(res, arr, n, k);
    int ans = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ans = (ans + res[i][j])%MOD;
        }
    }
    cout<<ans;
	return 0;
}

Measured memory_bytes: 256
S = input()
cnt_C = 0
length = len(S)
for i, s in enumerate(S):
    if i == 0 and s != "A":
        print("WA")
        exit()
    elif 2 <= i < length - 1:
        if s == "C":
            cnt_C += 1

    if not (s == "A" or s == "C" or "a" <= s <= "z"):
        print("WA")
        exit()

if cnt_C != 1:
    print("WA")
    exit()

print("AC")


Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>




int main(void){
int h,w;

for(;;){
    scanf("%d %d",&h,&w);
    if(h==w&&h==0){break;}

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(i%2==0){
                if(j%2==0){printf("#");}
                else{printf(".");}
            }
            if(i%2!=0){
                if(j%2==0){printf(".");}
                else{printf("#");}
            }
        }
        printf("\n");
    }
    printf("\n");
}



return 0;
}



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

using namespace std;

int main() {
	string A, B, C;
	cin >> A >> B >> C;


	if (A.back() == B.front() && B.back() == C.front())
	{
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	
}



Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000
#define GUARD 1000000000
 
struct Card{
  char match;
  int value;
};

struct Card R[MAX / 2 + 2], L[MAX / 2 + 2];

void merge(struct Card A[], int n,int l, int m, int r)
{
  int i;
  int j;
  int k;
  int n1 = m - l;
  int n2 = r - m;

  for( i = 0 ; i < n1 ; i++ )L[i] = A[l+i];
  for( i = 0 ; i < n2 ; i++ )R[i] = A[m+i];
  L[n1].value = R[n2].value = GUARD;
  i = j = 0;
  for( k = l ; k < r ; k++ ){
    if( L[i].value <= R[j].value ){
      A[k] = L[i++];
    }
    else{
      A[k] = R[j++];
    }
  }
}

void mergesort(struct Card A[],int n,int l,int r)
{
  int m;

  if( l + 1 < r ){
    m = (l+r)/2;
    mergesort(A,n,l,m);
    mergesort(A,n,m,r);
    merge(A,n,l,m,r);
  }
}

int partition(struct Card A[], int n,int p, int r)
{
  int i;
  int j;
  struct Card change,b;
  b = A[r];
  i = p - 1;
  for( j = p; j < r; j++ ){
    if( A[j].value <= b.value ){
      i++;
      change = A[i];
      A[i] = A[j];
      A[j] = change;
    }
  }
  change = A[i+1];
  A[i+1] = A[r];
  A[r] = change;
  return i+1;
}

void quick(struct Card A[], int n, int p, int r)
{
  int q;

  if( p < r ){
    q = partition(A,n,p,r);
    quick(A,n,p,q-1);
    quick(A,n,q+1,r);
  }
}



int main()
{
  int n;
  int i;
  int w;
  struct Card A[MAX],B[MAX];
  char F[10];
  int stable = 1;

  scanf("%d",&n);
  for( i = 0 ; i < n; i++ ){
    scanf("%s%d",F,&w);
    A[i].match = B[i].match = F[0];
    A[i].value = B[i].value = w;
  }

  mergesort(A,n,0,n);
  quick(B,n,0,n-1);

  for( i = 0 ; i < n ; i++ ){
    if( A[i].match != B[i].match ) stable = 0;
  }

  if( stable == 1 )printf("Stable\n");
  else printf("Not stable\n");
  for( i = 0 ; i < n ; i++ ){
    printf("%c %d\n",B[i].match,B[i].value);
  }
  return 0;
}

  



Measured memory_bytes: 4148
import bisect
N=int(input().strip())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
a.sort()
#b.sort(reverse=True)
c.sort()
ans=0
#for i in range(len(b)):
#    la=bisect.bisect_left(a, b[i])
#    ra=bisect.bisect_right(c, b[i])
#    ans+=la*(len(c)-ra)
#    print(la,(len(c)-ra))


for i in range(len(b)):
    la=bisect.bisect_left(a, b[i])
    ra=bisect.bisect_right(c, b[i])
    #print(la*(len(c)-ra))
    ans+=la*(len(c)-ra)
#print(ans)
#la=bisect.bisect_left(a, 8)
#ra=bisect.bisect_right(a, 8)
#print(la,len(a)-ra)

print(ans)

Measured memory_bytes: 23360
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std ;

typedef long long ll ;
#define rep (i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

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

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

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

	int sum = 0;
	for (int i = 1; i < b - a; i++)
	{
		sum += i;
	}

	cout << sum - a << endl;
	
	return 0;
}

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

int main(){
    ll N;
    string S;
    cin >> S;
    N = S.size();
    ll cntp=0, cntg=0, score=0;
    rep(i,N){
        if(S[i] == 'g'){
            if(cntg > cntp){
                cntp++;
                score++;
            }else{
                cntg++;
            }
        }else{
            if(cntg > cntp){
                cntp++;
            }else{
                cntg++;
                score--;
            }
        }
    }
    cout << score << endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int phi(int n){
    int sum=1;
    for(int i=2;i*i<=n;i++){
        int k=0;
        while(n%i==0) {
            n /= i;
            k++;
        }  
        if(k) sum *= ((int)pow(i*1.0,k-1))*(i-1);
    }
    if(n>1) sum *= (n-1);
    return sum;
}
int main(){
    int n;
    while(cin>>n){
        int sum = phi(n);
        cout<<sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 3080
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ok = []
S = 0
ans = 0
for a, b in zip(A, B):
    if a >= b:
        ok.append(a - b)
    else:
        ans += 1
        S += (b - a)
ok.sort()
while S > 0 and ok:
    ans += 1
    S -= ok.pop()

ans = -1 if S > 0 else ans
print(ans)

Measured memory_bytes: 18396
import java.util.Scanner;
import java.util.Arrays;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int a[] = new int[3];
	
		for(int i = 0;i < 3; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		System.out.println(a[0] + a[1]);
	}
 
}

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

int main()
{
 
	int n;
	cin >> n;
	if (n % 1000 == 0)
		cout << 0 << '\n';
	else
	{	long c = 0;
		while ((n % 1000) != 0)
		{
			c++;
			n++;
		}
		cout << c;
	}
}

Measured memory_bytes: 3560
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<unordered_map>
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define rt register int
#define l putchar('\n')
#define ll long long
#define r read()
using namespace std;
inline ll read(){
    ll x=0;char zf=1;char ch=getchar();
    while(ch!='-'&&!isdigit(ch))ch=getchar();
    if(ch=='-')zf=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt;ll ans;
int a[200010];
unordered_map<int,int>s;
int main(){
	n=r;
	for(rt i=1;i<=n;i++)a[i]=r,s[a[i]]++;
	sort(a+1,a+n+1,greater<int>());
	int lim=1<<30;
	for(rt i=1;i<=n;i++)if(s[a[i]]){
		while(a[i]+a[i]<lim)lim>>=1;
		if(a[i]+a[i]==lim){
			if(s[a[i]]>=2)ans++,s[a[i]]-=2;
		}
		else {
			if(s[lim-a[i]])ans++,s[lim-a[i]]--;
			s[a[i]]--;			
		}

	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 17524
#include <bits/stdc++.h>
#define VanLoi "bai2"
#define f first
#define s second
#define fi(a,b,c) for( int a= b; a<= c;++a)
#define fid(a,b,c) for( int a= b; a>= c;--a)
#define pii pair< int, int>
#define ll long long
#define pb push_back
#define getbit(x,i) (x>>i&1)
#define maxn 100005
#define oo 1e18
#define mod 1000000007

using namespace std;

int n, a[maxn];
ll sn, res = 0, k;

int main()
{
    ios_base:: sync_with_stdio(0);
    //freopen(VanLoi".inp","r",stdin);
    //freopen(VanLoi".out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    fi(i, 1, n) cin >> a[i];
    sn = (k * (k + 1) / 2) % mod;
    fi(i, 1, n - 1){
        ll dem = 0;
        fi(j, i + 1, n) if (a[i] > a[j]) dem++;
        res += (dem * sn) % mod;
        res %= mod;
    }
    sn = (k * (k - 1) / 2) % mod;
    fi(i, 1, n){
        ll dem = 0;
        fi(j, 1, i - 1) if (a[i] > a[j]) dem++;
        res += (dem * sn) % mod;
        res %= mod;
    }
    cout << res;
}


Measured memory_bytes: 256